霍夫曼編碼（Huffman coding）
/ HUFF-mun /
為了精簡地儲存文字，你可以給每個字元一個二進位碼，而高頻字元值得較短的碼——就像摩斯電碼給「E」一個單點。但這些碼必須不靠分隔符就能解碼，這意味著任一個碼都不可是另一個碼的前綴（前綴碼）。霍夫曼編碼依各字元出現的頻率，建造使編碼後訊息總長最短的前綴碼。
它是一個貪婪的由下而上合併。把每個字元放入一個池中，各以其頻率為權重。反覆取出池中頻率「最小的兩個」項目，合併成一個新節點（其頻率為兩者之和），再放回池中。如此直到只剩一個節點——一棵二元樹。從根讀樹，左分支標 0、右分支標 1；每片葉子的路徑拼出它的碼。罕見字元落在深處（長碼），高頻者落在淺處（短碼）。貪婪選擇——永遠合併頻率最小的兩個——由交換論證證成：在某個最佳樹中，頻率最小的兩個符號是最深層的兄弟節點，因為若某個更深的葉子放著更高頻的符號，你可以把它往上換而縮短總長。最佳子結構接著說，把那兩個合併成一個符號留下一個結構相同的較小實例，故歸納法完成證明。配合最小堆積，整個建構為 O(n log n)。
霍夫曼碼在所有「逐符號」前綴碼中可證為最佳，並嵌在 DEFLATE（ZIP、PNG、gzip）與 JPEG 等真實格式裡。兩個誠實的限制：最佳性只相對於「獨立地對每個符號編碼」——建模上下文或對整塊編碼的方法（算術編碼、現代壓縮器）能勝過它——而霍夫曼需要知道頻率，故它要嘛對資料掃兩遍，要嘛把碼表隨壓縮輸出一併送出。
頻率 a:5, b:2, c:1, d:1。合併 c+d（2），再與 b 合併（4），再與 a 合併（9）。碼：a=0, b=10, c=110, d=111。總位元數 = 5*1 + 2*2 + 1*3 + 1*3 = 15，相對於固定 2 位元碼的 18。頻率最小的符號 c 與 d 落在最深處。
反覆合併頻率最小的兩個節點，建出最佳前綴碼；罕見符號得到最長的碼字。
霍夫曼只在「逐符號獨立編碼」的前綴碼中最佳。它需要已知頻率，而建模上下文或整塊的方法（算術編碼）能壓得更小。