該視頻詳細講解了霍夫曼編碼提出的思路歷程。

目錄

故事背景

思路歷程

通信系統(tǒng)示意

衡量信息量

編碼和熵的關(guān)系

香農(nóng)-馮諾編碼

霍夫曼的改進

故事背景1951 年，麻省理工學(xué)院的一名研究生 David Huffman 在 Robert Fano 的信息論課程上名列前茅。Fano 教授讓學(xué)生們在期末考試和學(xué)期論文間做出選擇，年輕的 Huffman 在一開始就選擇了學(xué)期論文。論文的題目如圖 1 所示，給定一組數(shù)字或符號，找到最有效的方法來使用二進制碼表示它們。

圖 1 Huffman 的學(xué)期論文題目

在基礎(chǔ)層面上，這是一個數(shù)據(jù)壓縮問題。事實上你在計算機上看到的文本和圖像本質(zhì)上都是一組字母、數(shù)字或符號，如果將其歸結(jié)為最簡單的表示形式，那么它們其實都是一組 0 和 1 的組合，每個標(biāo)準的數(shù)據(jù)類型都有一個標(biāo)準的位表示。這個問題的本質(zhì)是將它們壓縮成盡可能少的位數(shù)。這是一個自計算出現(xiàn)以來就存在的問題，但 Fano 沒有告訴學(xué)生的是，這在當(dāng)時是信息論和數(shù)據(jù)壓縮領(lǐng)域的一個未解決的問題。Huffman 在研究生時解決了這個問題，他的解決方案就是大名鼎鼎的霍夫曼編碼算法。

圖 2 數(shù)據(jù)壓縮問題

思路歷程通信系統(tǒng)示意在一個通信系統(tǒng)中，我們通常有一個信息發(fā)送方和信息接受方。發(fā)送方想要通過網(wǎng)絡(luò)向接受方發(fā)送一些原始信息，但在網(wǎng)絡(luò)中唯一有意義的信息是二進制比特。因此，發(fā)送方必須根據(jù)符號和二進制代碼間的某種映射對原始信息進行編碼。而接收方需要對二進制代碼進行解碼以恢復(fù)原始信息。

圖 3 通信系統(tǒng)示意圖

編碼方法一般針對從原始信息到二進制碼的映射進行優(yōu)化，從原始信息到二進制碼的映射有一些內(nèi)在要求。一是每個符號必須被映射到唯一的二進制碼，二是接收方必須能夠準確解碼出原始信息。霍夫曼編碼算法完全符合這些要求。

衡量信息量對數(shù)據(jù)進行壓縮時，我們需要考慮一種平衡。如果使用太多的比特表示符號，那么會導(dǎo)致冗余;如果使用太少的比特表示，則會導(dǎo)致信息丟失，因此最優(yōu)的無損壓縮算法應(yīng)該在兩者之間找到平衡。那么我們首先需要知道在不丟失原始信息的情況下，最大的壓縮率是多少。對于這個問題，我們可以理解為，需要找到在原始信息中包含的真正的信息量是多少。那我們?nèi)绾魏饬啃畔⒘康亩嗌倌?

圖 4 如何衡量信息量

一句話中包含的信息量與文字的長度并沒有直接的關(guān)聯(lián)。如圖 5 所示，對于這兩句話來說，顯然在沙哈拉沙漠下雪所包含的信息量更大，因為在沙漠下雪的概率極小。因此可以想到，事件相關(guān)的信息量與事件發(fā)生的概率有很大的關(guān)系。

圖 5 信息量例子

香農(nóng)根據(jù)信息的性質(zhì)總結(jié)了四個定律：

信息量的大小跟事件發(fā)生的概率反相關(guān)

信息量永遠大于等于 0，因為事件的發(fā)生不會導(dǎo)致信息損失

如果一件事發(fā)生的概率是 100%，那么它不包含任何信息量

如果兩個不相關(guān)事件被分別觀察到，那么它包含的信息量應(yīng)該是這兩個事件單獨信息量的和

香農(nóng)根據(jù)這四個定律給出了自信息的定義。當(dāng)信息以 bit 為單位時，log 函數(shù)的底數(shù)取 2。

圖 6 自信息定義

但香農(nóng)更偉大的貢獻在于將自信息推廣到了更廣的分布上，給出了信息熵的概念，也就是著名的香農(nóng)定理。香農(nóng)定理作為信息論的基礎(chǔ)，給出了衡量信息量的標(biāo)準公式。

圖 7 香農(nóng)定理

編碼和熵的關(guān)系當(dāng)衡量不同編碼方式的性能時，我們需要計算不同編碼方式的平均字符長度。在信息論中，我們通常將符號編碼的長度根據(jù)符號出現(xiàn)的概率進行加權(quán)求和得到平均的符號長度。香農(nóng)發(fā)現(xiàn)，無論對符號進行哪種方式的無損壓縮編碼，它的長度總是大于等于信息熵，這就是香農(nóng)的源編碼定理。

圖 8 香農(nóng)源編碼定理

香農(nóng)-馮諾編碼香農(nóng)-馮諾編碼首先對符號按照概率進行升序排列。然后找到最好的分割方法將符號分為兩組，使得兩組的符號概率和盡可能接近。之后對每個組進行遞歸劃分，直到每個符號都被單獨分為一組。

圖 9 香農(nóng)-馮諾編碼分組

分完組之后，編碼就變得很簡單了。從頭部向下，如果向左，那么對符號編碼添加 0，向右走則添加 1，最終可以得到所有符號的二進制編碼。而且對于這個樹形圖的表示，在解碼端是不會存在歧義的。

圖 10 香農(nóng)-馮諾編碼樹形圖

霍夫曼的改進但是香農(nóng)-馮諾編碼并不總是最優(yōu)的，在思考最小化平均符號長度時，可以想到，兩個最不可能出現(xiàn)的符號應(yīng)該出現(xiàn)在二叉樹的最底部，也就是編碼長度最長的地方。這符合我們的直覺，那就是最不常出現(xiàn)的符號應(yīng)該具有更長的編碼長度。因此我們可以想到，先將兩個最不可能出現(xiàn)的符號放在最底部去構(gòu)建一個二叉樹，然后將這個二叉樹的根節(jié)點視作一個新的符號節(jié)點，該符號節(jié)點的概率是兩個子節(jié)點的和。然后對剩余的符號節(jié)點做相同的操作，直到構(gòu)建出一個完整的二叉樹，這就是霍夫曼編碼。

圖 11 霍夫曼的改進1

圖 12 霍夫曼的改進2

原文標(biāo)題：[基礎(chǔ)知識] 霍夫曼編碼

文章出處：【微信公眾號：LiveVideoStack】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。