哈夫曼樹

哈夫曼編碼（Huffman Coding）

哈夫曼編碼，又稱為霍夫曼編碼，它是現(xiàn)代壓縮算法的基礎(chǔ)

假設(shè)要把字符串 [ABBBCCCCCCCCDDDDDDEE] 轉(zhuǎn)成二進制編碼進行傳輸。

可以轉(zhuǎn)成 ASCII 編碼 (65_69，10000011000101) ，但是有點冗長，如果希望編碼更短呢？

可以先約定好字符串中的 5 個字母對應(yīng)的二進制，如下所示

如果使用哈夫曼編碼，可以壓縮至 41 個二進制位，約為原來長度的 68.3%

哈夫曼樹

構(gòu)建哈夫曼樹

構(gòu)建哈夫曼編碼

如何求得 5 個字母對應(yīng)的哈夫曼編碼？

• 從根節(jié)點開始，以 left 為 0，right 為 1 開始往下一個節(jié)點一個節(jié)點的數(shù)，即可得出。

ght 為 1 開始往下一個節(jié)點一個節(jié)點的數(shù)，即可得出。