講解霍夫曼編碼提出的思路歷程

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

目錄

故事背景

思路歷程

通信系統(tǒng)示意

衡量信息量

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

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

霍夫曼的改進(jìn)

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

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

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

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

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

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

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

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

圖 4 如何衡量信息量

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

圖 5 信息量例子

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

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

信息量永遠(yuǎn)大于等于 0，因?yàn)槭录陌l(fā)生不會(huì)導(dǎo)致信息損失

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

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

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

圖 6 自信息定義

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

圖 7 香農(nóng)定理

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

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

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

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

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

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

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

圖 11 霍夫曼的改進(jìn)1

圖 12 霍夫曼的改進(jìn)2

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

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