霍夫曼編碼

Created: November-22, 2018

霍夫曼程式碼是一種特殊型別的最佳字首程式碼，通常用於無損資料壓縮。它可以非常有效地壓縮資料，從 20％到 90％的記憶體，具體取決於被壓縮資料的特性。我們認為資料是一系列字元。Huffman 的貪婪演算法使用一個表來說明每個字元出現的頻率（即其頻率），以建立將每個字元表示為二進位制字串的最佳方式。霍夫曼程式碼由 David A. Huffman於 1951 年提出。

假設我們有一個 100,000 字元的資料檔案，我們希望緊湊地儲存。我們假設該檔案中只有 6 個不同的字元。字元的頻率由下式給出：

+------------------------+-----+-----+-----+-----+-----+-----+
|        Character       |  a  |  b  |  c  |  d  |  e  |  f  |
+------------------------+-----+-----+-----+-----+-----+-----+
|Frequency (in thousands)|  45 |  13 |  12 |  16 |  9  |  5  |
+------------------------+-----+-----+-----+-----+-----+-----+

我們有很多選擇來表示這樣的資訊檔案。在這裡，我們考慮設計二進位制字元程式碼的問題，其中每個字元由唯一的二進位制字串表示，我們稱之為程式碼字。

https://i.stack.imgur.com/VP5UP.jpg

構建的樹將為我們提供：

+------------------------+-----+-----+-----+-----+-----+-----+
|        Character       |  a  |  b  |  c  |  d  |  e  |  f  |
+------------------------+-----+-----+-----+-----+-----+-----+
| Fixed-length Codeword  | 000 | 001 | 010 | 011 | 100 | 101 |
+------------------------+-----+-----+-----+-----+-----+-----+
|Variable-length Codeword|  0  | 101 | 100 | 111 | 1101| 1100|
+------------------------+-----+-----+-----+-----+-----+-----+

如果我們使用固定長度的程式碼，我們需要三位代表 6 個字元。此方法需要 300,000 位來編碼整個檔案。現在的問題是，我們能做得更好嗎？

一個可變長度程式碼可以做得比固定長度的程式碼相當好，通過給頻繁字元短的碼字和偶發字元長碼字。此程式碼需要：（45 X 1 + 13 X 3 + 12 X 3 + 16 X 3 + 9 X 4 + 5 X 4）X 1000 = 224000 位表示檔案，可節省大約 25％的記憶體。

需要記住的一點是，我們在此僅考慮其中沒有程式碼字也是某些其他程式碼字的字首的程式碼。這些被稱為*字首程式碼。*對於可變長度編碼，我們將 3 字元檔案 abc 編碼為 0.101.100 = 0101100，其中“。” 表示連線。

字首程式碼是理想的，因為它們簡化了解碼。由於沒有程式碼字是任何其他程式碼字的字首，因此開始編碼檔案的程式碼字是明確的。我們可以簡單地識別初始碼字，將其轉換回原始字元，並對編碼檔案的其餘部分重複解碼過程。例如，001011101 唯一地解析為 0.0.101.1101，其解碼為 aabe 。簡而言之，二進位制表示的所有組合都是唯一的。例如，如果一個字母用 110 表示，則 1101 或 1100 不會表示其他字母。這是因為你可能會在選擇 110 或繼續連線下一位並選擇該位時遇到困惑。

壓縮技術：

該技術通過建立節點的二叉樹來工作。這些可以儲存在常規陣列中，其大小取決於符號數 n 。節點可以是葉節點或內部節點。最初所有節點都是葉節點，它包含符號本身，其頻率以及可選的連結到其子節點。作為慣例，位'0’表示左子，位'1’表示右子。優先順序佇列用於儲存節點，在彈出時為節點提供最低頻率。該過程描述如下：

為每個符號建立一個葉節點，並將其新增到優先順序佇列。
雖然佇列中有多個節點：
1. 從佇列中刪除具有最高優先順序的兩個節點。
2. 建立一個新的內部節點，將這兩個節點作為子節點，頻率等於兩個節點頻率的總和。
3. 將新節點新增到佇列中。
其餘節點是根節點，霍夫曼樹已完成。

對於我們的例子： https://i.stack.imgur.com/mOobp.jpg

虛擬碼看起來像：

Procedure Huffman(C):     // C is the set of n characters and related information
n = C.size
Q = priority_queue()
for i = 1 to n
    n = node(C[i])
    Q.push(n)
end for
while Q.size() is not equal to 1
    Z = new node()
    Z.left = x = Q.pop
    Z.right = y = Q.pop
    Z.frequency = x.frequency + y.frequency
    Q.push(Z)
end while
Return Q

雖然線性時間給定排序輸入，但在一般情況下任意輸入，使用此演算法需要預先排序。因此，由於在一般情況下排序需要 O(nlogn) 時間，因此兩種方法具有相同的複雜性。

由於這裡的 n 是字母表中的符號數，通常是非常小的數字（與要編碼的訊息的長度相比），因此在選擇該演算法時時間複雜度不是很重要。

減壓技術：

解壓縮的過程簡單地是將字首碼流轉換為單個位元組值的問題，通常通過在從輸入流中讀取每個位元時逐節點地遍歷霍夫曼樹。到達葉節點必然終止對該特定位元組值的搜尋。葉值表示所需的字元。通常，霍夫曼樹是使用每個壓縮週期的統計調整資料構建的，因此重建非常簡單。否則，重建樹的資訊必須單獨傳送。虛擬碼：

Procedure HuffmanDecompression(root, S):   // root represents the root of Huffman Tree
n := S.length                              // S refers to bit-stream to be decompressed
for i := 1 to n
    current = root
    while current.left != NULL and current.right != NULL
        if S[i] is equal to '0'
            current := current.left
        else
            current := current.right
        endif
        i := i+1
    endwhile
    print current.symbol
endfor

貪婪說明：
霍夫曼編碼檢視每個字元的出現並以最佳方式將其儲存為二進位制字串。其思想是為輸入字元分配可變長度程式碼，分配程式碼的長度基於相應字元的頻率。我們建立一個二叉樹並以自下而上的方式對其進行操作，以便至少兩個頻繁字元儘可能地從根目錄開始。通過這種方式，最常見的字元獲得最小的程式碼，而最不頻繁的字元獲得最大的程式碼。

參考文獻：

演算法簡介 - Charles E. Leiserson，Clifford Stein，Ronald Rivest 和 Thomas H. Cormen
霍夫曼編碼 - 維基百科
離散數學及其應用 - Kenneth H. Rosen