霍夫曼編碼（Huffman Coding）是一種編碼方式，是一種用於無損數據壓縮的熵編碼（權編碼）算法。
霍夫曼編碼（英語：Huffman Coding），又譯為哈夫曼編碼、赫夫曼編碼，是一種用於無損數據壓縮的熵編碼（權編碼）算法。由大衛·霍夫曼在1952年發明。
在計算機數據處理中，霍夫曼編碼使用變長編碼表對源符號（如檔案中的一個字母）進行編碼，其中變長編碼表是通過一種評估來源符號出現機率的方法得到的，出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之後的字元串的平均長度、期望值降低，從而達到無損壓縮數據的目的。
例如，在英文中，e的出現機率最高，而z的出現機率則最低。當利用霍夫曼編碼對一篇英文進行壓縮時，e極有可能用一個比特來表示，而z則可能花去25個比特（不是26）。用普通的表示方法時，每個英文字母均占用一個位元組，即8個比特。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實現對於英文中各個字母出現機率的較準確的估算，就可以大幅度提高無損壓縮的比例。
霍夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度之和。
基本介紹
- 中文名：霍夫曼編碼
- 外文名：Huffman Encoding
歷史,問題定義與解法,廣義[編輯],狹義[編輯],示例[編輯],實現方法,數據壓縮[編輯],數據解壓縮[編輯],
霍夫曼編碼（Huffman Encoding）
歷史
1951年，霍夫曼和他在MIT資訊理論的同學得選擇是完成學期報告還是期末考試。導師羅伯特·法諾出的學期報告題目是，查找最有效的二進制編碼。由於無法證明哪個已有編碼是最有效的，霍夫曼放棄對已有編碼的研究，轉向新的探索，最終發現了基於有序頻率二叉樹編碼的想法，並很快證明了這個方法是最有效的。霍夫曼使用自底向上的方法構建二叉樹，避免了次優算法香農-范諾編碼的最大弊端──自頂向下構建樹。
1952年，於論文《一種構建極小多餘編碼的方法》（A Method for the Construction of Minimum-Redundancy Codes）中發表了這個編碼方法。
Huffman在1952年根據香農（Shannon）在1948年和范若（Fano）在1949年闡述的這種編碼思想提出了一種不定長編碼的方法，也稱霍夫曼（Huffman）編碼。霍夫曼編碼的基本方法是先對圖像數據掃描一遍，計算出各種像素出現的機率，按機率的大小指定不同長度的唯一碼字，由此得到一張該圖像的霍夫曼碼錶。編碼後的圖像數據記錄的是每個像素的碼字，而碼字與實際像素值的對應關係記錄在碼錶中。
霍夫曼編碼是可變字長編碼(VLC)的一種。 Huffman於1952年提出一種編碼方法，該方法完全依據字元出現機率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就稱Huffman編碼。下面引證一個定理，該定理保證了按字元出現機率分配碼長，可使平均碼長最短。
? 定理：在變字長編碼中，如果碼字長度嚴格按照對應符號出現的機率大小逆序排列，則其平 均碼字長度為最小。
? 現在通過一個實例來說明上述定理的實現過程。設將信源符號按出現的機率大小順序排列為 ： ?
U： ( a1 a2 a3 a4 a5 a6 a7 )
0.20 0.19 0.18 0.17 0.15 0.10 0.01
? 給機率最小的兩個符號a6與a7分別指定為“1”與“0”，然後將它們的機率相加再與原來的 a1~a5組合併重新排序成新的原為：
U′： ( a1 a2 a3 a4 a5 a6′ )
0.20 0.19 0.18 0.17 0.15 0.11
? 對a5與a′6分別指定“1”與“0”後，再作機率相加並重新按機率排序得
U″：（0.26 0.20 0.19 0.18 0.17）…
? 直到最後得 U″″：（0.61 0.39）
? 霍夫曼編碼的具體方法：先按出現的機率大小排隊，把兩個最小的機率相加，作為新的機率 和剩餘的機率重新排隊，再把最小的兩個機率相加，再重新排隊，直到最後變成1。每次相 加時都將“0”和“1”賦與相加的兩個機率，讀出時由該符號開始一直走到最後的“1”， 將路線上所遇到的“0”和“1”按最低位到最高位的順序排好，就是該符號的霍夫曼編碼。
例如a7從左至右，由U至U″″，其碼字為0000；
? a6按踐線將所遇到的“0”和“1”按最低位到最高位的順序排好，其碼字為0001…
? 上例為：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit
? 可以算出本例的信源熵為2.61bit，二者已經是很接近了。
Huffman方法構造出來的碼並不是唯一的。但對於同一信源而言，其平均碼字長是相同的，編碼效率是一樣的。
Huffman編碼對不同信源的編碼的編碼效率是不同的。只有當信源機率分布不均勻時，Huffman才會收到顯著效果。
問題定義與解法
廣義[編輯]
- 給定
- 一組符號（Symbol）和其對應的權重值（weight），其權重通常表示成機率（%）。
- 欲知
- 一組二元的前置碼，其二元碼的長度為最短。
狹義[編輯]
- 輸入
- 符號集合{\displaystyle S=\left\{s_{1},s_{2},\cdots ,s_{n}\right\}}，其S集合的大小為{\displaystyle n}。
- 權重集合{\displaystyle W=\left\{w_{1},w_{2},\cdots ,w_{n}\right\}}，其W集合不為負數且{\displaystyle w_{i}=\mathrm {weight} \left(s_{i}\right),1\leq i\leq n}。
- 輸出
- 一組編碼{\displaystyle C\left(S,W\right)=\left\{c_{1},c_{2},\cdots ,c_{n}\right\}}，其C集合是一組二進制編碼且{\displaystyle c_{i}}為{\displaystyle s_{i}}相對應的編碼，{\displaystyle 1\leq i\leq n}。
- 目標
- 設{\displaystyle L\left(C\right)=\sum _{i=1}^{n}{w_{i}\times \mathrm {length} \left(c_{i}\right)}}為{\displaystyle C}的加權的路徑長，對所有編碼{\displaystyle T\left(S,W\right)}，則{\displaystyle L\left(C\right)\leq L\left(T\right)}
示例[編輯]
霍夫曼樹常處理符號編寫工作。根據整組數據中符號出現的頻率高低，決定如何給符號編碼。如果符號出現的頻率越高，則給符號的碼越短，相反符號的號碼越長。假設我們要給一個英文單字"F O R G E T"進行霍夫曼編碼，而每個英文字母出現的頻率分別列在Fig.1。
演算過程[編輯]
（一）進行霍夫曼編碼前，我們先創建一個霍夫曼樹。
- ⒈將每個英文字母依照出現頻率由小排到大，最小在左，如Fig.1。
- ⒉每個字母都代表一個終端節點（葉節點），比較F.O.R.G.E.T六個字母中每個字母的出現頻率，將最小的兩個字母頻率相加合成一個新的節點。如Fig.2所示，發現F與O的頻率最小，故相加2+3=5。
- ⒊比較5.R.G.E.T，發現R與G的頻率最小，故相加4+4=8。
- ⒋比較5.8.E.T，發現5與E的頻率最小，故相加5+5=10。
- ⒌比較8.10.T，發現8與T的頻率最小，故相加8+7=15。
- ⒍最後剩10.15，沒有可以比較的對象，相加10+15=25。
最後產生的樹狀圖就是霍夫曼樹，參考Fig.2。
（二）進行編碼
（二）進行編碼
- 1.給霍夫曼樹的所有左連結'0'與右連結'1'。
- 2.從樹根至樹葉依序記錄所有字母的編碼，如Fig.3。
實現方法
數據壓縮[編輯]
一開始，所有的節點都是終端節點，節點內有三個欄位：
1.符號（Symbol）
2.權重（Weight、Probabilities、Frequency）
3.指向父節點的連結（Link to its parent node）
而非終端節點內有四個欄位：
1.權重（Weight、Probabilities、Frequency）
2.指向兩個子節點的連結（Links to two child node）
3.指向父節點的連結（Link to its parent node）
基本上，我們用'0'與'1'分別代表指向左子節點與右子節點，最後為完成的二叉樹共有n個終端節點與n-1個非終端節點，去除了不必要的符號並產生最佳的編碼長度。
過程中，每個終端節點都包含著一個權重（Weight、Probabilities、Frequency），兩兩終端節點結合會產生一個新節點，新節點的權重是由兩個權重最小的終端節點權重之總和，並持續進行此過程直到只剩下一個節點為止。
實現霍夫曼樹的方式有很多種，可以使用優先佇列（Priority Queue）簡單達成這個過程，給與權重較低的符號較高的優先權（Priority），算法如下：
⒈把n個終端節點加入優先佇列，則n個節點都有一個優先權Pi，1 ≤ i ≤ n
⒉如果佇列內的節點數>1，則：
- ⑴從佇列中移除兩個最小的Pi節點，即連續做兩次remove（min（Pi）, Priority_Queue)
- ⑵產生一個新節點，此節點為（1）之移除節點之父節點，而此節點的權重值為（1）兩節點之權重和
- ⑶把（2）產生之節點加入優先佇列中
⒊最後在優先佇列里的點為樹的根節點（root）
而此算法的時間複雜度（Time Complexity）為O（nlogn）；因為有n個終端節點，所以樹總共有2n-1個節點，使用優先佇列每個循環須O（logn）。
此外，有一個更快的方式使時間複雜度降至線性時間（Linear Time）O（n），就是使用兩個佇列（Queue）創件霍夫曼樹。第一個佇列用來存儲n個符號（即n個終端節點）的權重，第二個佇列用來存儲兩兩權重的合（即非終端節點）。此法可保證第二個佇列的前端（Front）權重永遠都是最小值，且方法如下：
⒈把n個終端節點加入第一個佇列（依照權重大小排列，最小在前端）
⒉如果佇列內的節點數>1，則：
- ⑴從佇列前端移除兩個最低權重的節點
- ⑵將（1）中移除的兩個節點權重相加合成一個新節點
- ⑶加入第二個佇列
⒊最後在第一個佇列的節點為根節點
雖然使用此方法比使用優先佇列的時間複雜度還低，但是注意此法的第1項，節點必須依照權重大小加入佇列中，如果節點加入順序不按大小，則需要經過排序，則至少花了O（nlogn）的時間複雜度計算。
但是在不同的狀況考量下，時間複雜度並非是最重要的，如果我們今天考慮英文字母的出現頻率，變數n就是英文字母的26個字母，則使用哪一種算法時間複雜度都不會影響很大，因為n不是一筆龐大的數字。
數據解壓縮[編輯]
簡單來說，霍夫曼碼樹的解壓縮就是將得到的前置碼（Prefix Huffman code）轉換回符號，通常藉由樹的追蹤（Traversal），將接收到的比特串（Bits stream）一步一步還原。但是要追蹤樹之前，必須要先重建霍夫曼樹 ；某些情況下，如果每個符號的權重可以被事先預測，那么霍夫曼樹就可以預先重建，並且存儲並重複使用，否則，傳送端必須預先傳送霍夫曼樹的相關信息給接收端。
最簡單的方式，就是預先統計各符號的權重並加入至壓縮之比特串，但是此法的運算量花費相當大，並不適合實際的套用。若是使用Canonical encoding，則可精準得知樹重建的數據量只占B2^B比特（其中B為每個符號的比特數（bits））。如果簡單將接收到的比特串一個比特一個比特的重建，例如：'0'表示父節點，'1'表示終端節點，若每次讀取到1時，下8個比特則會被解讀是終端節點（假設數據為8-bit字母），則霍夫曼樹則可被重建，以此方法，數據量的大小可能為2~320位元組不等。雖然還有很多方法可以重建霍夫曼樹，但因為壓縮的數據串包含"traling bits"，所以還原時一定要考慮何時停止，不要還原到錯誤的值，如在數據壓縮時時加上每筆數據的長度等。
