霍夫曼編碼（Huffman Coding） | 2021全台活動資訊網

霍夫曼編碼(Huffman Coding)是一種編碼方法，霍夫曼編碼是可變字長編碼(VLC)的一種。

霍夫曼編碼使用變長編碼表對源符號（如檔案中的一個字母）進行編碼，其中變長編碼表是通過一種評估來源符號出現機率的方法得到的，出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之後的字串的平均長度、期望值降低，從而達到無失真壓縮資料的目的。

霍夫曼編碼的具體步驟如下：

1）將信源符號的概率按減小的順序排隊。

2）把兩個最小的概率相加，並繼續這一步驟，始終將較高的概率分支放在右邊，直到最後變成概率１。

3）畫出由概率１處到每個信源符號的路徑，順序記下沿路徑的０和１，所得就是該符號的霍夫曼碼字。

4）將每對組合的左邊一個指定為0，右邊一個指定為1（或相反）。

例：現有一個由5個不同符號組成的30個符號的字串：

BABACAC ADADABB CBABEBE DDABEEEBB

1首先計算出每個字元出現的次數（概率）：

2把出現次數（概率）最小的兩個相加，並作為左右子樹，重複此過程，直到概率值為1

第一次：將概率最低值3和4相加，組合成7：

第二次：將最低值5和7相加，組合成12：

第三次：將8和10相加，組合成18：

第四次：將最低值12和18相加，結束組合：

3 將每個二叉樹的左邊指定為0，右邊指定為1

我們可以看到出現次數（概率）越多的會越在上層，編碼也越短，出現頻率越少的就越在下層，編碼也越長。當我們編碼的時候，我們是按“bit”來編碼的，解碼也是通過bit來完成，如果我們有這樣的bitset “10111101100″ 那麼其解碼後就是 “ABBDE”。所以，我們需要通過這個二叉樹建立我們Huffman編碼和解碼的字典表。

這裡需要注意的是，Huffman編碼使得每一個字元的編碼都與另一個字元編碼的前一部分不同，不會出現像’A’：00，  ’B’：001，這樣的情況，解碼也不會出...