簡介
Huffman 編碼是一種編碼方式，是一種用於無損數據壓縮的熵編碼（權編碼）算法。1952年，David A. Huffman在麻省理工攻讀博士時所發明的，並發表於《一種構建極小多餘編碼的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。
數據壓縮技術的理論基礎是資訊理論。根據資訊理論的原理，可以找到最佳數據壓縮編碼方法，數據壓縮的理論極限是信息熵。如果要求在編碼過程中不丟失信息量，即要求保存信息熵，這種信息保持編碼又叫做熵保存編碼，或者叫熵編碼。 熵編碼是無失真數據壓縮，用這種編碼結果經解碼後可無失真地恢復出原圖像。當考慮到人眼對失真不易覺察的生理特徵時，有些圖像編碼不嚴格要求熵保存，信息可允許部分損失以換取高的數據壓縮比，這種編碼是有失真數據壓縮，通常運動圖像的數據壓縮是有失真編碼。 JPEG壓縮算法使用了兩種熵編碼方法：哈夫曼編碼和算術編碼。哈夫曼編碼Huffman方法於1952年問世，迄今為止仍經久不衰，廣泛套用於各種數據壓縮技術中，且仍不失為熵編碼中的最佳編碼方法。
哈夫曼編碼的理論依據是變字長編碼理論。在變字長編碼中，編碼器的編碼輸出碼字是字長不等的碼字，按編碼輸入信息符號出現的統計機率，給輸出碼字分配以不同的字長。對於編碼輸入中，出現大機率的信息符號，賦以短字長的輸出碼字； 對於編碼輸入中，出現小機率的信息符號，賦以長字長的輸出碼字。可以證明，按照機率出現大小的順序，對輸出碼字分配不同碼字長度的變字長編碼方法，其輸出碼字的平均碼長最短，與信源熵值最接近，編碼方法最佳。
來源
在電腦資料處理中，霍夫曼編碼使用變長編碼表對源符號（如檔案中的一個字母）進行編碼，其中變長編碼表是通過一種評估來源符號出現機率的方法得到的，出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之後的字元串的平均長度、期望值降低，從而達到無損壓縮數據的目的。
例如，在英文中，e的出現機率最高，而z的出現機率則最低。當利用霍夫曼編碼對一篇英文進行壓縮時，e極有可能用一個位元來表示，而z則可能花去25個位元（不是26）。用普通的表示方法時，每個英文字母均占用一個位元組（byte），即8個位元。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實現對於英文中各個字母出現機率的較準確的估算，就可以大幅度提高無損壓縮的比例。
霍夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度之和，記為wpl=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1,2,...n)。可以證明霍夫曼樹的WPL是最小的。
實例
Huffman樹是二叉樹的一種特殊轉化形式。以下是構建Huffman樹的例子：
比如有以下數據， ABFACGCAHGBBAACECDFGFAAEABBB 先進行統計A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1) 括弧裡面的是統計次數生成Huffman樹：每次取最小的那兩個節點(node)合併成一個節點(node)，並且將累計數值相加作為新的接點的累計數值，最頂層的是根節點(root) 註：列表中最小節點的是指包括合併了的節點在內的所有節點，已經合併的節點不在列表中編碼和解碼
戴維·霍夫曼解碼：利用檔案中保存的Huffman編碼，一一對應，解讀編碼，把可變長編碼轉換為定長編碼。
huffman 編碼 為了提高儲存效率. 里並不直接保存數值, 而是將數值按位數分成 16 組: 數值 組 實際保存值 0 0 - -1,1 1 0,1 -3,-2,2,3 2 00,01,10,11 -7,-6,-5,-4,4,5,6,7 3 000,001,010,011,100,101,110,111 -15,..,-8,8,..,15 4 0000,..,0111,1000,..,1111 -31,..,-16,16,..,31 5 00000,..,01111,10000,..,11111 -63,..,-32,32,..,63 6 . -127,..,-64,64,..,127 7 . -255,..,-128,128,..,255 8 . -511,..,-256,256,..,511 9 . -1023,..,-512,512,..,1023 10 . -2047,..,-1024,1024,..,2047 11 . -4095,..,-2048,2048,..,4095 12 . -8191,..,-4096,4096,..,8191 13 . -16383,..,-8192,8192,..,16383 14 .-32767,..,-16384,16384,..,32767 15 .還是來看前面的例子: (0,57) ; (0,45) ; (4,23) ; (1,-30) ; (0,-8) ; (2,1) ; (0,0)只處理每對數右邊的那個: 57 是第 6 組的, 實際保存值為 111001 , 所以被編碼為 (6,111001) 45 , 同樣的操作, 編碼為 (6,101101) 23 -> (5,10111) -30 -> (5,00001) -8 -> (4,0111) 1 -> (1,1)前面的那串數字就變成了: (0,6), 111001 ; (0,6), 101101 ; (4,5), 10111; (1,5), 00001; (0,4) , 0111 ; (2,1), 1 ; (0,0)括弧里的數值正好合成一個位元組. 後面被編碼的數字表示範圍是 -32767..32767.合成的位元組里, 高 4 位是前續 0 的個數, 低 4 位描述了後面數字的位數.繼續剛才的例子, 如果 06 的 huffman 編碼為 111000 69 = (4,5) --- 1111111110011001 ( 注: 69=4*16+5 ) 21 = (1,5) --- 11111110110 4 = (0,4) --- 1011 33 = (2,1) --- 11011 0 = EOB = (0,0) --- 1010那dfgdsrfgrtyuytj dtyre6yn 怒同意體育與一句話要回家雷射焊接金凱利喔了基礎 由於Huffman編碼需要掃描兩次，第一次是統計數字，第二次是編碼寫檔案，大大影響了速度，因此有人發明了enhanced Huffman aglorithm。這種算法只掃描一遍檔案，動態產生Huffman樹，即每讀n個位元組就重新編碼一次Huffman樹，以達到提高速度的目的。在解碼的過程中使用動態還原技術。
哈夫曼編碼的具體步驟
歸納如下：
①;機率統計（如對一幅圖像，或m幅同種類型圖像作灰度信號統計），得到n個不同機率的信息符號。
②;將n個信源信息符號的n個機率，按機率大小排序。
③將n個機率中，最後兩個小機率相加，這時機率個數減為n-1個。
④將n-1個機率，按大小重新排序。
⑤;重複③，將新排序後的最後兩個小機率再相加，相加和與其餘機率再排序。
⑥如此反覆重複n-2次，得到只剩兩個機率序列。
⑦以二進制碼元（0.1）賦值，構成哈夫曼碼字。編碼結束。
哈夫曼碼字長度和信息符號出現機率大小次序正好相反，即大概信息符號分配碼字長度短，小機率信息符號分配碼字長度長。
注意：
採用霍夫曼編碼時有兩個問題值得注意：①霍夫曼碼沒有錯誤保護功能，在解碼時，如果碼串中沒有錯誤，那么就能一個接一個地正確譯出代碼。但如果碼串中有錯誤，哪僅是1位出現錯誤，不但這個碼本身譯錯，更糟糕的是一錯一大串，全亂了套，這種現象稱為錯誤傳播(error propagation)。計算機對這種錯誤也無能為力，說不出錯在哪裡，更談不上去糾正它。②霍夫曼碼是可變長度碼，因此很難隨意查找或調用壓縮檔案中間的內容，然後再解碼，這就需要在存儲代碼之前加以考慮。儘管如此，霍夫曼碼還是得到廣泛套用。
