專利精神時光屋

霍夫曼編碼(Huffman Coding)是一種編碼方式，是一種用於無損數據壓縮的熵編碼（權編碼）演算法。1952年，David A. Huffman在麻省理工攻讀博士時所發明的，並發表於《一種構建極小多餘編碼的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。

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

例如，在英文中，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是最小的。