技术图文：如何利用C#实现Huffman编码？ |
您所在的位置：网站首页 › 哈夫曼编码的应用领域 › 技术图文：如何利用C#实现Huffman编码？ |
技术图文：如何利用C#实现Huffman编码？
|
背景
Huffman编码 在通信和数据压缩领域具有重要的应用。 在介绍 Huffman 编码具体实现之前，先介绍几个相关的概念。 概念1：树中结点的带权路径长度 – 根结点到该结点的路径长度与该结点权值的乘积。 概念2：树的带权路径长度 – 树中所有叶子结点的带权路径长度之和。 概念3：huffman树 – n个带权叶子结点构成的所有二叉树中，带权路径长度最小的二叉树。 概念4：前缀码规则 – 对字符集编码时，字符集中任一字符的编码都不是其它字符编码的前缀。 概念5：哈夫曼编码 – 将哈夫曼树中，每个分支结点的左分支标0，右分支标1，把从根结点到每个叶子结点的路径上的标号连接起来作为该叶子结点所代表符号的编码，这样得到的编码称为Huffman编码。 huffman编码 是满足前缀码规则的编码方案，对利用 huffman编码 的字符集，进行解码时不存在二义性。 技术分析要对一个字符集合，例如“state，seat，act，tea，cat，set，a，eat”进行编码。 首先，要对每个字符出现的频数进行统计，根据统计的结果构造 Huffman 树。 字符c，出现的频数为2。字符s，出现的频数为3。字符e，出现的频数为5。字符a，出现的频数为7。字符,，出现的频数为7。字符t，出现的频数为8。构造 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树，如下所示：
其次，利用 Huffman 树对字符集中的每个字符进行编码，得到字符与编码对应的字典（对应代码实现的Step5）。 字符c，对应的编码1110。字符s，对应的编码1111。字符e，对应的编码110。字符a，对应的编码00。字符,，对应的编码01。字符t，对应的编码10。最后，利用字典对数据进行编码和解码（对应代码实现的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 : where T : IComparable { private T _data; /// /// 获取或设置该结点的左孩子 /// public BinTreeNode LeftChild { get; set; } /// /// 获取或设置该结点的右孩子 /// public BinTreeNode RightChild { get; set; } /// /// 获取或设置该结点的数据元素 /// public T Data { get { return _data; } set { if (value == null) throw new ArgumentNullException(); _data = value; } } /// /// 初始化BinTreeNode类的新实例 /// /// 该结点的数据元素 /// 该结点的左孩子 /// 该结点的右孩子 public BinTreeNode(T data, BinTreeNode lChild = null, BinTreeNode rChild = null) { if (data == null) throw new ArgumentNullException(); LeftChild = lChild; _data = data; RightChild = rChild; } }封装 Huffman 树结点的结构，该结点为二叉树节点的子类。 public class HuffmanTreeNode : BinTreeNode { /// /// 结点的权值 /// public int Weight { get; set; } /// /// 叶子结点 -- 字符 /// /// /// public HuffmanTreeNode(char data, int weight) : base(data) { Weight = weight; } /// /// 其它结点 /// /// public HuffmanTreeNode(int weight):base('\0') { Weight = weight; } }Step2：封装编码字典的结构HuffmanDicItem。 public class HuffmanDicItem { /// /// 字符 /// public char Character { get; set; } /// /// 编码 /// public string Code { get; set; } /// /// 构造函数 /// /// /// public HuffmanDicItem(char charactor, string code) { Character = charactor; Code = code; } }Step3：对字符集中的字符进行统计的函数，即构造最初始的森林F。 private List CreateInitForest(string str) { if (string.IsNullOrEmpty(str)) throw new ArgumentNullException(); List result = new List(); char[] charArray = str.ToCharArray(); List lst = charArray.GroupBy(a => a).ToList(); foreach (IGrouping 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 sources) { if (sources == null) throw new ArgumentNullException(); if (sources.Count root = node; isNext = false; } else { sources = lst.GetRange(2, lst.Count - 2); sources.Add(node); } } return root; }Step5：构造Huffman编码字典的函数。 private List CreateHuffmanDict(string code, HuffmanTreeNode current) { if (current == null) throw new ArgumentNullException(); List result = new List(); if (current.LeftChild == null && current.RightChild == null) { result.Add(new HuffmanDicItem(current.Data, code)); } else { List dictL = CreateHuffmanDict(code + "0", (HuffmanTreeNode) current.LeftChild); List dictR = CreateHuffmanDict(code + "1", (HuffmanTreeNode) current.RightChild); result.AddRange(dictL); result.AddRange(dictR); } return result; } private List CreateHuffmanDict(HuffmanTreeNode root) { if (root == null) throw new ArgumentNullException(); return CreateHuffmanDict(string.Empty, root); }Step6：对字符串进行编码的函数。 private string ToHuffmanCode(string source, List lst) { if (string.IsNullOrEmpty(source)) throw new ArgumentNullException(); if (lst == null) throw new ArgumentNullException(); string result = string.Empty; for (int i = 0; i List forest = CreateInitForest(str); HuffmanTreeNode root = CreateHuffmanTree(forest); dict = CreateHuffmanDict(root); string result = ToHuffmanCode(str, dict); return result; }Step7：对编码后的字符串进行解码的函数。 public string HuffmanCodeToString(List dict, string code) { string result = string.Empty; for (int i = 0; i if (code[i] == item.Code[0] && item.Code.Length + i 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 dic; string code = huffmanTree.StringToHuffmanCode(out dic, str); for (int i = 0; i |
【本文地址】
今日新闻 |
推荐新闻 |