背景

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樹

其次，利用 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<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(); }

運行的結果如下所示：

huffman編碼實驗

好了，有關 Huffman編碼就給大家介紹完了，該編碼是二叉樹的重要應用之一，希望對學習數據結構與算法的同學有所幫助。See You！

相關圖文：

• 如何利用 C# 實現 K 最鄰近算法？
• 如何利用 C# 實現 K-D Tree 結構？
• 如何利用 C# KDTree 實現 K 最鄰近算法？
• 如何利用 C# 對神經網絡模型進行抽象？
• 如何利用 C# 實現神經網絡的感知器模型？
• 如何利用 C# 實現 Delta 學習規則？
• 如何利用 C# 開發「桌面版百度翻譯」軟件！
• 如何利用 C# 開發「股票數據分析軟件」（上）
• 如何利用 C# 開發「股票數據分析軟件」（中）
• 如何利用 C# 開發「股票數據分析軟件」（下）
• 如何利用 C# 爬取「财報說」中的股票數據？
• 如何利用 C# 爬取 One 持有者返利數據！
• 如何利用 C# 爬取Gate.io交易所的公告！
• 如何利用 C# 爬取BigOne交易所的公告！
• 如何利用 C# 爬取 ONE 的交易數據？
• 如何利用 C# 爬取「京東 - 計算機與互聯網圖書銷量榜」！
• 如何利用 C# 爬取「當當 - 計算機與互聯網圖書銷量榜」！
• 如何利用 C# 爬取「互動出版網 - 計算機圖書銷量榜」！
• 如何利用 C# 爬取「中國圖書網 - 計算機與互聯網圖書銷量榜」！
• 如何利用 C# 爬取「貓眼電影：熱映口碑榜」及對應影片信息！
• 如何利用 C# 爬取「貓眼電影專業版：票房」數據！
• 如何利用 C# 爬取「貓眼電影：最受期待榜」及對應影片信息！
• 如何利用 C# 爬取「貓眼電影：國内票房榜」及對應影片信息！
• 如何利用 C# Python 破解貓眼電影的反爬蟲機制？
• 如何利用 C# 爬取帶 Token 驗證的網站數據？
• 如何利用 C# 向 Access 數據庫插入大量數據？

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!