背景

Huffman编码 在通信和数据压缩领域具有重要的应用。

在介绍 Huffman 编码具体实现之前，先介绍几个相关的概念。

概念1：树中结点的带权路径长度 -- 根结点到该结点的路径长度与该结点权值的乘积。

概念2：树的带权路径长度 -- 树中所有叶子结点的带权路径长度之和。

概念3：huffman树 -- n个带权叶子结点构成的所有二叉树中，带权路径长度最小的二叉树。

概念4：前缀码规则 -- 对字符集编码时，字符集中任一字符的编码都不是其它字符编码的前缀。

概念5：哈夫曼编码 -- 将哈夫曼树中，每个分支结点的左分支标0，右分支标1，把从根结点到每个叶子结点的路径上的标号连接起来作为该叶子结点所代表符号的编码，这样得到的编码称为Huffman编码。

huffman编码 是满足前缀码规则的编码方案，对利用 huffman编码 的字符集，进行解码时不存在二义性。

技术分析

要对一个字符集合，例如“state，seat，act，tea，cat，set，a，eat”进行编码。

首先，要对每个字符出现的频数进行统计，根据统计的结果构造 Huffman 树。

构造 Huffman 树的算法如下：

第1步：根据给定的 n 个权值 w1,w2,……,wn，构成 n 棵二叉树的森林 F={T1,T2,……，Tn} ，其中每棵二叉树 Ti 中都只有一个权值为 wi 的根结点，其左右子树均为空（对应代码实现的Step3）。

第2步：在森林 F 中选出两棵根结点权值最小的树作为一棵新树的左右子树，且置新树的根结点的权值为其左右子树上根结点的权值之和。

第3步：从 F 中删除构成新树的哪两棵树，同时把新树加入 F 中。

第4步：重复第2和3步，直到 F 中只含有一棵树为止，此树便是Huffman树（对应代码实现的Step4）。

该算法为典型的贪心算法，以上字符集经过处理后得到的 Huffman树，如下所示：

c算法经典教材（技术图文如何利用C）(1)

huffman树

其次，利用 Huffman 树对字符集中的每个字符进行编码，得到字符与编码对应的字典（对应代码实现的Step5）。

最后，利用字典对数据进行编码和解码（对应代码实现的Step6、Step7）。

对数据 state，seat，act，tea，cat，set，a，eat 进行编码，得到的结果如下：

1111100010110011111110001001001110100110110000111100010011111110100100011100010

当然，由于 Huffman 编码满足前缀码规则，解码之后仍然为：state，seat，act，tea，cat，set，a，eat，具有唯一性。

代码实现

Step1：构造 Huffman 树结点的结构 HuffmanTreenode。

封装二叉树结点的结构

public class BinTreeNode<T> : where T : IComparable<T> { private T _data; /// <summary> /// 获取或设置该结点的左孩子 /// </summary> public BinTreeNode<T> LeftChild { get; set; } /// <summary> /// 获取或设置该结点的右孩子 /// </summary> public BinTreeNode<T> RightChild { get; set; } /// <summary> /// 获取或设置该结点的数据元素 /// </summary> public T Data { get { return _data; } set { if (value == null) throw new ArgumentNullException(); _data = value; } } /// <summary> /// 初始化BinTreeNode类的新实例 /// </summary> /// <param name="data">该结点的数据元素 </param> /// <param name="lChild">该结点的左孩子</param> /// <param name="rChild">该结点的右孩子</param> public BinTreeNode(T data, BinTreeNode<T> lChild = null, BinTreeNode<T> rChild = null) { if (data == null) throw new ArgumentNullException(); LeftChild = lChild; _data = data; RightChild = rChild; } }

封装 Huffman 树结点的结构，该结点为二叉树节点的子类。

public class HuffmanTreeNode : BinTreeNode<char> { /// <summary> /// 结点的权值 /// </summary> public int Weight { get; set; } /// <summary> /// 叶子结点 -- 字符 /// </summary> /// <param name="data"></param> /// <param name="weight"></param> public HuffmanTreeNode(char data, int weight) : base(data) { Weight = weight; } /// <summary> /// 其它结点 /// </summary> /// <param name="weight"></param> public HuffmanTreeNode(int weight):base('\0') { Weight = weight; } }

Step2：封装编码字典的结构HuffmanDicItem。

public class HuffmanDicItem { /// <summary> /// 字符 /// </summary> public char Character { get; set; } /// <summary> /// 编码 /// </summary> public string code { get; set; } /// <summary> /// 构造函数 /// </summary> /// <param name="charactor"></param> /// <param name="code"></param> public HuffmanDicItem(char charactor, string code) { Character = charactor; Code = code; } }

Step3：对字符集中的字符进行统计的函数，即构造最初始的森林F。

private List<HuffmanTreeNode> CreateInitForest(string str) { if (string.IsNullOrEmpty(str)) throw new ArgumentNullException(); List<HuffmanTreeNode> result = new List<HuffmanTreeNode>(); char[] charArray = str.ToCharArray(); List<IGrouping<char, char>> lst = charArray.GroupBy(a => a).ToList(); foreach (IGrouping<char, char> g in lst) { char data = g.Key; int weight = g.ToList().Count; HuffmanTreeNode node = new HuffmanTreeNode(data, weight); result.Add(node); } return result; }

Step4：构造Huffman树的函数。

private HuffmanTreeNode CreateHuffmanTree(List<HuffmanTreeNode> sources) { if (sources == null) throw new ArgumentNullException(); if (sources.Count < 2) throw new ArgumentException("构造Huffman树，最少为2个结点。"); HuffmanTreeNode root = default(HuffmanTreeNode); bool isNext = true; while (isNext) { List<HuffmanTreeNode> lst = sources.OrderBy(a => a.Weight).ToList(); HuffmanTreeNode n1 = lst[0]; HuffmanTreeNode n2 = lst[1]; int weight = n1.Weight n2.Weight; HuffmanTreeNode node = new HuffmanTreeNode(weight); node.LeftChild = n1; node.RightChild = n2; if (lst.Count == 2) { root = node; isNext = false; } else { sources = lst.GetRange(2, lst.Count - 2); sources.Add(node); } } return root; }

Step5：构造Huffman编码字典的函数。

private List<HuffmanDicItem> CreateHuffmanDict(string code, HuffmanTreeNode current) { if (current == null) throw new ArgumentNullException(); List<HuffmanDicItem> result = new List<HuffmanDicItem>(); if (current.LeftChild == null && current.RightChild == null) { result.Add(new HuffmanDicItem(current.Data, code)); } else { List<HuffmanDicItem> dictL = CreateHuffmanDict(code "0", (HuffmanTreeNode) current.LeftChild); List<HuffmanDicItem> dictR = CreateHuffmanDict(code "1", (HuffmanTreeNode) current.RightChild); result.AddRange(dictL); result.AddRange(dictR); } return result; } private List<HuffmanDicItem> CreateHuffmanDict(HuffmanTreeNode root) { if (root == null) throw new ArgumentNullException(); return CreateHuffmanDict(string.Empty, root); }

Step6：对字符串进行编码的函数。

private string ToHuffmanCode(string source, List<HuffmanDicItem> lst) { if (string.IsNullOrEmpty(source)) throw new ArgumentNullException(); if (lst == null) throw new ArgumentNullException(); string result = string.Empty; for (int i = 0; i < source.Length; i ) { result = lst.Single(a => a.Character == source[i]).Code; } return result; } // 被外界调用的函数，对字符串进行huffman编码。 public string StringToHuffmanCode(out List<HuffmanDicItem> dict, string str) { List<HuffmanTreeNode> forest = CreateInitForest(str); HuffmanTreeNode root = CreateHuffmanTree(forest); dict = CreateHuffmanDict(root); string result = ToHuffmanCode(str, dict); return result; }

Step7：对编码后的字符串进行解码的函数。

public string HuffmanCodeToString(List<HuffmanDicItem> dict, string code) { string result = string.Empty; for (int i = 0; i < code.Length;) { foreach (HuffmanDicItem item in dict) { if (code[i] == item.Code[0] && item.Code.Length i <= code.Length) { string temp = code.Substring(i, item.Code.Length); if (temp == item.Code) { result = item.Character; i = item.Code.Length; break; } } } } return result; }

总结

我们把 Step3至Step7 的代码封装在HuffmanTree的结构中。通过调用该结构提供的两个 public 方法StringToHuffmanCode和HuffmanCodeToString就可以实现对给定字符集的 huffman 编码与解码的操作。

static void Main(string[] args) { string str = "state,seat,act,tea,cat,set,a,eat"; Console.WriteLine(str); HuffmanTree huffmanTree = new HuffmanTree(); List<HuffmanDicItem> dic; string code = huffmanTree.StringToHuffmanCode(out dic, str); for (int i = 0; i < dic.Count; i ) { Console.WriteLine(dic[i].Character ":" dic[i].Code); } Console.WriteLine(code); string decode = huffmanTree.HuffmanCodeToString(dic, code); Console.WriteLine(decode); Console.ReadLine(); }

运行的结果如下所示：

c算法经典教材（技术图文如何利用C）(2)

huffman编码实验

好了，有关 Huffman编码就给大家介绍完了，该编码是二叉树的重要应用之一，希望对学习数据结构与算法的同学有所帮助。See You！

相关图文：

,