日常生活中經(jīng)常會使用到文件壓縮，但是基本很少有人會問到壓縮是如何實現(xiàn)的。所謂的帜矾，就是把文本重新進行編碼，減少不必要的空間屑柔。目前最新技術在編碼上已經(jīng)很強大屡萤，但是筆者不打算說那些很高深的壓縮技術（其實那些高深的壓縮技術，其實筆者也不懂）掸宛。雖然有很多高深的壓縮技術死陆，但是目前經(jīng)常使用到的壓縮和解壓縮技術都是基于赫夫曼的研究基礎上發(fā)展而來。所以今天就簡單介紹一個最基本的壓縮編碼方法-----赫夫曼編碼唧瘾。
一措译、實例開篇
if a < 60 {
b = "不及格"
}else if a < 70{
b = "及格"
}else if a < 80 {
b = "中等"
}else if a < 90{
b = "良好"
}else {
b = "優(yōu)秀"
}
如上代碼是百分制考試的評分標準。粗略看上面的代碼饰序，貌似沒有什么問題瞳遍。但是通常情況來說一個班級的學生成績分布在及格、中等菌羽、良好的相對較多掠械，分布在優(yōu)秀和不及格的相對較少。但是上面的代碼注祖，最開始的邏輯是先判斷是否及格猾蒂，再逐漸向上得到結果。當輸入量很大的時候是晨，算法在效率方面是存在一定問題的肚菠。
假設實際中學生在5個等級上成績分布的概率如下表所示。如果按照上述的代碼邏輯執(zhí)行罩缴，70分以上的成績占總概率的80%蚊逢，但是想判斷出一個70分以上的成績至少需要執(zhí)行3次以上的判斷才能得到結果，顯然是十分不合理的箫章。
如果能依照成績概率分布的規(guī)律,如下圖烙荷，更改成績等級判斷邏輯，那么程序判斷的次數(shù)將大大較少檬寂。
二终抽、赫夫曼定義
按照上面的兩種邏輯，可以把上述的邏輯分別簡化成下圖的二叉樹結構。其中A表示不及格昼伴、B及格匾旭、C中等、D良好圃郊、E優(yōu)秀价涝。分支線上的數(shù)字表示成績所占比例數(shù)。
在說赫夫曼之前先說明另個概念：
-
路徑長度: 從樹中的一個結點到另一個結點之間的分支構成兩個結點之間的路徑,路徑上的分支數(shù)目稱作路徑長度持舆。
-
樹的路徑長度 : 樹的路徑長度就是從樹根到每一個結點的路徑長度之和飒泻。
說完了上述的兩個概念，看一下赫夫曼樹的定義吏廉。
若將樹中結點賦給一個有著某種含義的數(shù)值泞遗，則這個數(shù)值稱為該結點的權。結點的帶權路徑WPL長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積席覆。給定n個權值作為n的葉子結點史辙，構造一棵二叉樹，若帶權路徑WPL長度達到最小佩伤，稱這樣的二叉樹為最優(yōu)二叉樹聊倔，也稱為哈夫曼樹(Huffman Tree)。
關于赫夫曼樹的定義出現(xiàn)了權生巡。如果考慮到帶權的節(jié)點耙蔑，節(jié)點的帶權路徑長度為從該節(jié)點到樹根之間的路徑長度與節(jié)點上權的乘積。
按照上述所講孤荣，則上圖中二叉樹a的WPL = 5 * 1 + 15 * 2 + 40 * 3 + 30 * 4 + 10 * 4 = 315甸陌。二叉樹b的WPL = 5 * 3 + 15 * 3 + 40 * 2 + 30 * 2 + 10 * 2 = 220。315和220這兩個結果分別意味著盐股，如果用二叉樹 a 的判斷方法钱豁，10000個學生的成績需要做31500次比較，而二叉樹 b 的判斷方法只要做22000次比較疯汁。很顯然牲尺，二叉樹b的效率比a高了很多。
三幌蚊、赫夫曼構造原理
看了上述兩個二叉樹的對比谤碳，但是想二叉樹 b 這樣的高效的二叉樹又是如何得到的？
總共分為四個步驟溢豆。
-
1蜒简、構成初始集合
對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點沫换，它的左右子樹均為空臭蚁。（為方便在計算機上實現(xiàn)算法，一般還要求以Ti的權值Wi的升序排列讯赏。）
-
2垮兑、選取左右子樹
在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和漱挎。
-
3系枪、刪除左右子樹
從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中磕谅。
-
4私爷、重復二和三兩步，
重復二和三兩步膊夹，直到集合F中只有一棵二叉樹為止衬浑。
結合上述的步驟，看看如何將二叉樹 a 轉為二叉樹 b放刨。
第一步,先把有權值得葉子結點按照從小到大的順序排列成一個有序序列,即為A5,D10,B15,C70工秩。
第二步,取頭兩個最小權值的結點作為一個新結點N1的兩個子結點,注意相對較小的的孩子是左孩子,這里A就是N1的左孩子,D為N1的右孩子, 新結點的權值為兩個葉子結點的權值之和 5 + 10 = 15;
第三步,將N1替換A與E,插入有序序列中,保持從小到大的排序,即 N1 15,B15,C70;
第四步,重復步驟2,將N1與B作為一個新結點N2的兩個子結點, N2的權值 = 15 + 15 = 30;
第五步,將N2替換N1與B,插入有序序列中,保持從小到大的排序,即 N2 ，D30,C40;
第六步,重復步驟2,將N2和D作為一個新結點N3的兩個子結點进统。N3的權值為30+30 = 60
- 第七步助币，將N3替換N2和D，排序得到C40螟碎，N3為40眉菱。
-
第八步，重復步驟二掉分，將C于N3作為一個新節(jié)點T的兩個子節(jié)點俭缓。即完成赫夫曼樹的構造。
赫夫曼樹構造完成
四酥郭、赫夫曼編碼
赫夫曼樹最大的成績是在當前遠距離通訊過程中尔崔，解決了數(shù)據(jù)傳輸最優(yōu)化問題。比如有ABCDEF六個字母褥民，通過0和1編碼用二進制字符發(fā)送季春。編碼后的數(shù)據(jù)為000001010011100101，解碼的時候可以按照3位一份來解碼消返。是上上载弄，不管是任何文字語言，字母或漢字在某一話題或其他方面出現(xiàn)的頻率是不一樣的撵颊。如漢字中的“的”宇攻、“了”、“你”等等倡勇，都是頻率極高的漢字逞刷。所以因為頻頻的不同，可以按照赫夫曼樹的規(guī)律來規(guī)劃。
假設ABCDEF出現(xiàn)的概率分別為27%夸浅、8%仑最、15%、15%帆喇、30%警医、5%。則形成的赫夫曼樹如下圖坯钦。此外我們可以將左右分支分別改為0和1预皇，然后用0和1來編碼字母。則編碼結果為A=01婉刀、B=1001吟温、C=101、D=00突颊、E=11溯街、F=1000。
原本的編碼結果為：000001010011100101
現(xiàn)在的編碼結果為:0110011010011100
現(xiàn)在的編碼結果明顯要比之前的少了一些洋丐，短短是幾個字母編碼后呈昔，少的量不是很大，如果是通篇的文章或更多友绝，那么編碼量將會節(jié)省很多堤尾，這就是文件壓縮的原理。并且隨著字符的增多迁客，按照權重優(yōu)先級編碼郭宝，這種壓縮會進一步提升很多。
既然有編碼掷漱，就必然有解碼粘室。簡單說說解碼，按照赫夫曼樹這種編碼方法卜范，非0即1衔统，且每個字符編碼長短不等很容易混淆。所以若要設計出長短不等的編碼海雪，則必須是任意字符的編碼都不是另一個字符編碼的前綴（這種編碼通常稱為前綴編碼）锦爵。自己觀察A=01、B=1001奥裸、C=101险掀、D=00、E=11湾宙、F=1000根本就不存在容易和 1001 樟氢、1000混淆的10和100編碼冈绊，這一點從上面的0和1的左右分支圖也能輕易的總結出，因為ABCDEF這幾個字符都在輸?shù)淖钅┒瞬嚎校圆粫霈F(xiàn)這種容易混淆的問題死宣。另外一點，當然是編碼和解碼都要規(guī)定好同樣的赫夫曼編碼規(guī)則霸妹。
