霍夫曼編碼介紹
霍夫曼編碼（Huffman Coding）是一種無(wú)損的編碼算法，在數(shù)據(jù)壓縮和信息傳輸領(lǐng)域有廣泛的應(yīng)用。它是由戴維·霍夫曼(David Albert Huffman帝洪，1925.08.09-1999.10.17)于1952年所發(fā)明（發(fā)表于論文《A Method for the Construction of Minimum-Redundancy Codes》）
1951年款青，正在麻省理工攻讀博士學(xué)位的霍夫曼收到了他的老師Robert M. Fano教授（給全班學(xué)生）布置的一個(gè)選擇題：或者努力復(fù)習(xí)準(zhǔn)備期末考試做修，或者交出一份學(xué)期論文——找到使用二進(jìn)制代碼表示數(shù)字、字母或者其他符號(hào)的最佳編碼方法——實(shí)際上這正是Fano教授自己正在研究的課題抡草。
霍夫曼不想?yún)⒓涌荚囀渭埃谑沁x擇了挑戰(zhàn)論文。挑戰(zhàn)的過(guò)程無(wú)疑是痛苦的康震，不過(guò)幸好時(shí)間沒(méi)有那么長(zhǎng)——眼看成功無(wú)望燎含，霍夫曼決定“懸崖勒馬”，好好復(fù)習(xí)準(zhǔn)備期末考試——奇跡在最后一刻發(fā)生了腿短。準(zhǔn)備將論文草稿扔進(jìn)垃圾桶的那一剎那屏箍，霍夫曼突然間靈光一現(xiàn)，找到了答案橘忱∠吵“突然恍然大悟，猶如閃電一般 ”鹦付，霍夫曼回憶那個(gè)時(shí)刻尚粘，如是說(shuō)到。
于是敲长，霍夫曼提出了以他名字命名的“霍夫曼編碼”郎嫁。那么，霍夫曼編碼究竟是解決什么樣的問(wèn)題呢祈噪？簡(jiǎn)單地說(shuō)泽铛，就是任意多段文字（或者數(shù)字、或者其他符號(hào)）辑鲤，該用什么編碼表示盔腔，使得其平均編碼長(zhǎng)度最短≡氯欤霍夫曼是怎么做的呢弛随？我們以一個(gè)簡(jiǎn)單的例子，來(lái)描述霍夫曼編碼的算法宁赤。
比如舀透，對(duì)于字符串“AABCBADAEACCBDB”（記為S1），最常見(jiàn)决左、最簡(jiǎn)單的是編碼方式ASCII（American Standard Code for Information Interchange愕够，美國(guó)信息交換標(biāo)準(zhǔn)代碼）走贪。每個(gè)字母占用8個(gè)比特（A = 0x41 = 01000001，B = 0x42 = 01000010惑芭，...）坠狡，那么S1將占用120個(gè)比特（120 = 15 * 8）。不過(guò)遂跟，這種編碼方式擦秽，似乎有點(diǎn)浪費(fèi)。
換個(gè)思路漩勤，既然S1中其實(shí)只包含5個(gè)不同的字母（ABCDE），那么實(shí)際上可以用3個(gè)比特來(lái)編碼每個(gè)字母：A = 000缩搅、B = 001越败、C = 010、D = 011硼瓣、E = 100究飞。我們將這種編碼方式取名A3碼（只是隨便取一個(gè)名字）。那么堂鲤，按照A3編碼亿傅，S1將占用45個(gè)比特（45 = 15 * 3）。雖然比ASCII碼要好很多瘟栖，不過(guò)這似乎這并不是最短的葵擎，而且也沒(méi)有任何通用性可言。比如半哟，對(duì)于S2 = “ABCDEFGHI”酬滤，此編碼方式就失效了（因?yàn)榘凑者@種方式，3個(gè)比特?zé)o法表達(dá)9個(gè)不同的字母）寓涨。
ASCII碼和A3碼盯串，都是定長(zhǎng)碼——每個(gè)字母所占用的比特?cái)?shù)是相同的（ASCII = 8，A3 = 3）戒良，如果換個(gè)思路体捏，改成變長(zhǎng)碼呢？比如這樣編碼（取名V碼）：A = 0（1個(gè)比特）糯崎、B = 1（1個(gè)比特）几缭、C = 01（2個(gè)比特）、D = 10（2個(gè)比特）沃呢、E = 11（2個(gè)比特）奏司。按照V碼，S1將占用21個(gè)比特（21 = 5 * 1 + 4 * 1 + 3 * 2 + 2 * 2 + 1 * 2）樟插。從編碼長(zhǎng)度來(lái)說(shuō)韵洋，這看起來(lái)非常不錯(cuò)竿刁，但是V碼卻有個(gè)致命問(wèn)題，那就是歧義性搪缨，如圖4-2所示食拜。
通過(guò)圖4-2可以看到，由于歧義性副编，V碼顯然不是一種合適的編碼方式负甸。不過(guò)，饒是如此痹届，它的“變長(zhǎng)”編碼方式呻待，卻有著霍夫曼編碼的影子《痈霍夫曼編碼的精髓蚕捉，正是“變長(zhǎng)”+“無(wú)歧義”（當(dāng)然，還包括“無(wú)損”）柴淘。而且為了使（平均）編碼長(zhǎng)度最短迫淹，霍夫曼編碼使得出現(xiàn)頻率最高的字母使用最短編碼、出現(xiàn)頻率最低的字母使用最長(zhǎng)編碼为严。
第1步敛熬，霍夫曼編碼統(tǒng)計(jì)各個(gè)字母的出現(xiàn)頻率（出現(xiàn)次數(shù)），然后按照頻率大小第股，從小到大排列应民。對(duì)于S1，霍夫曼編碼的統(tǒng)計(jì)排序結(jié)果夕吻，如表4-1所示瑞妇。
第2步，霍夫曼編碼開始構(gòu)建二叉樹梭冠。選取最小頻率的兩個(gè)節(jié)點(diǎn)（1:E）辕狰、(2:D)，并將其頻率相加控漠，作為父節(jié)點(diǎn)蔓倍，如圖4-3所示。
第3步盐捷，將新生成的父節(jié)點(diǎn)與原來(lái)的節(jié)點(diǎn)合并偶翅，組成新的霍夫曼編碼統(tǒng)計(jì)排序表，如表4-2所示碉渡。
表4-2中聚谁，新生的節(jié)點(diǎn)命名為“3”，同時(shí)它的“頻率”也設(shè)置為3滞诺。另外形导，由于E环疼、D已經(jīng)構(gòu)建為霍夫曼二叉樹的葉子節(jié)點(diǎn)，所以朵耕，從霍夫曼表中刪除炫隶。
接下來(lái)，重復(fù)第2步阎曹，得到的霍夫曼二叉樹伪阶，如圖4-4所示。
重復(fù)第3步处嫌，得到的霍夫曼表栅贴，如表4-3所示。
注意熏迹，表4-3中新生成的節(jié)點(diǎn)“6”（“3”節(jié)點(diǎn)和C節(jié)點(diǎn)的父節(jié)點(diǎn)）檐薯，按照頻率順序，排在了最后一列癣缅。
接下來(lái)，繼續(xù)重復(fù)第2步哄酝、第3步友存，所生成的霍夫曼樹和霍夫曼表，分別如圖4-5和表4-4所示陶衅。
仍然是繼續(xù)重復(fù)第2步屡立、第3步，所生成的霍夫曼樹和霍夫曼表搀军，分別如圖4-6和表4-5所示膨俐。
通過(guò)表4-5可以看到，只剩下一個(gè)節(jié)點(diǎn)罩句，那么迭代結(jié)束焚刺。
迭代結(jié)束以后，將圖4-6的邊门烂，打上標(biāo)記乳愉，左為“0”，右為“1”屯远，如圖4-7所示蔓姚。
按照?qǐng)D4-7，則字母ABCDE就可以得到霍夫曼編碼：從根節(jié)點(diǎn)開始慨丐，到達(dá)對(duì)應(yīng)葉子節(jié)點(diǎn)的所有路徑上“標(biāo)記”組合坡脐，如圖4-8和表4-6所示。
通過(guò)圖4-8或表4-6可以看到房揭，任何一個(gè)字母的編碼备闲，都不會(huì)是另一個(gè)字母編碼的前綴晌端。這種編碼也稱為前綴編碼（Prefix Encoding）。但是這種稱呼浅役，非常令人迷惑：明明不是人家的前綴斩松，偏偏要叫前綴編碼。為了消除迷惑呢觉既，這種編碼有時(shí)候也被稱為無(wú)前綴編碼（Prefix-free Encoding）惧盹。迷惑是消除了，但是更加混亂了——前綴編碼和非前綴編碼瞪讼，說(shuō)的竟然是同一回事钧椰。
好吧，不糾結(jié)其他稱呼了符欠，只須記住“霍夫曼編碼”這個(gè)名字就好嫡霞，其算法如偽碼4-1所示。
- 偽碼4-１ 霍夫曼編碼算法
# 偽碼4-１ 霍夫曼編碼算法
S = 待編碼對(duì)象 # 比如字符集希柿，等等
HuffmanTable = 統(tǒng)計(jì)并且按照出現(xiàn)頻率排序(S) # 比如[E:1,D:2,C:3,B:4,A:5]
HuffmanTree = [] #霍夫曼二叉樹诊沪，初始化為空
# 構(gòu)建霍夫曼樹
while(True)
{
if (HuffmanTable.size() <= 1)
{
break;
}
# 構(gòu)建霍夫曼樹
node1, node2 = 從HuffmanTable中選取頻率最小的前兩個(gè)元素
p.value = node1.value + node2.value # 父節(jié)點(diǎn)
p.left_son = node1
p.right_son = node2
p.left_edge = 0
p.right_edge = 1
HuffmanTree.add(p)
HuffmanTree.root = p
# 更新霍夫曼表
HuffmanTabel.remove(node1, node2)
HuffmanTable.add&sort(p)
}
# 構(gòu)建霍夫曼編碼
遍歷霍夫曼樹(HuffmanTree)
針對(duì)每個(gè)葉子節(jié)點(diǎn)，得到霍夫曼編碼
