問題：給常見符號短編碼
假設你要用位元把一段長文字存起來。偷懶的做法是讓每個字元用一樣多的位元——比方像 ASCII 那樣每個 8 位元。但這很浪費空間：在英文裡 'e' 不斷出現、'q' 卻很罕見，可是兩者都付一樣的 8 位元。自然的點子是用可變長度編碼——常見符號用短位元串、罕見符號用長位元串——好讓「總」位元數（依每個符號出現的頻率加權後）盡可能地小。這是一個最佳化問題：在所有合法的編碼裡，找出讓期望編碼長度最小的那一個。
這裡有個陷阱，讓它比表面上更難。如果 'a' 編成 0、'b' 編成 01，那麼位元串 001 就有歧義——它可能是 'a','a','b'……等等，不對，0-0-1 根本沒法解碼，因為沒有東西以剩下的 1 開頭，而 0-01 讀成 'a','b'、00-1 卻讀成一團亂碼。解藥是無前綴性質：任何符號的編碼都不可以是另一個符號編碼的「前綴」。只要沒有任何碼字是另一個碼字的前綴，那麼當你由左往右讀位元時，一旦你看過的位元恰好對上某個碼字，這個對應就是唯一且不會誤認的——你解出它，然後重新開始。
霍夫曼的貪婪一步
貪婪的點子來了，而且簡單得令人愉快。看看頻率「最小」的那兩個符號。不管最佳的樹最後長什麼樣，這兩個最罕見的符號都可以放心地讓它們在最底層當兄弟——給它們一個父節點，把這個父節點當成一個全新的符號（其頻率是那兩者之和），然後忘掉原本的兩個。接著對縮小後的集合重複。每次合併移除兩個符號、加入一個，所以合併夠多次之後只剩單一個符號：那就是完工的樹的根。這就是霍夫曼演算法，它是由葉子往上、而不是由根往下地建出樹來。
while more than one symbol remains:
x = extract symbol of smallest frequency
y = extract symbol of next-smallest frequency
z = new node with freq(z) = freq(x) + freq(y)
make x and y the two children of z
insert z back into the pool
the last remaining node is the root拿頻率 a:5、b:2、c:1、d:1 來追蹤。最小的兩個是 c:1 和 d:1；把它們合併成一個節點 (cd):2。現在的池子是 a:5、b:2、(cd):2。最小的兩個是 b:2 和 (cd):2；合併成 (bcd):4。池子變成 a:5、(bcd):4。把這兩個合併成根:9。讀這棵樹，a 拿到短碼（深度 1），而 c 和 d 拿到長碼（深度 3）——正是我們想要的形狀：常見的 'a' 便宜、罕見的 'c'、'd' 付得多。總成本是 5·1 + 2·2 + 1·3 + 1·3 = 15 位元，你可以驗算它勝過這裡任何固定長度的方案。
跑這個要花多少？每一輪都需要最小的兩個頻率，而這恰好是最小優先佇列（一個二元堆積）能廉價提供的。有 n 個符號時你做大約 n 次合併，每次做兩次 extract-min 和一次 insert、每個 O(log n)，所以整件事是 O(n log n)。（若頻率已經排好序，用兩個佇列就能在 O(n) 內完成。）這個演算法又短又快，而且——不像許多貪婪法——是可被證明為最佳的，這正是我們接下來要談的部分。
為什麼合併最罕見的兩個是安全的：貪婪選擇性質
整個證明立足於一個主張，也就是這個問題的貪婪選擇性質：「某一棵」最佳樹會把頻率最小的兩個符號（叫它們 x 和 y）放在最深一層當兄弟葉子。只要我們能證明這點，貪婪的第一步就永遠不會把最佳解封死——總是存在一棵最佳樹，與貪婪剛剛做的事一致。如同你在本階段前面幾篇指南看過的，這是每個貪婪證明反覆出現的引擎：證明貪婪選擇與最佳性「相容」，然後遞迴下去。
我們用一個交換論證來證明它，就是你兩篇之前認識的那個工具。隨便取一棵最佳樹 T。令 a 和 b 是 T 裡坐得最深、且互為兄弟的兩個符號（一棵滿二元樹底層總有這樣一對兄弟葉子）。現在 x 和 y 是全域最不常出現的兩個符號，所以 freq(x) ≤ freq(a) 且 freq(y) ≤ freq(b)。把 x 和 a 對調、把 y 和 b 對調。每一次對調都把一個低頻符號移得「更深」、把一個較高頻的符號移得「更淺」——而既然成本是頻率乘以深度，這個交換只會讓總成本下降、絕不會上升。
- 令 T 是任一棵最佳樹，並令 a、b 是 T 裡最深的一對兄弟葉子。依演算法的選擇，x 和 y 是全域頻率最小的兩個符號。
- 把 x 和 a 對調。成本的變化是 (freq(x) - freq(a)) × (depth(a) - depth(x))。兩個因子的正負號都對——x 不比 a 常出現，而 a 坐得不比 x 淺——所以乘積 ≤ 0：成本不會上升。
- 基於同樣理由把 y 和 b 對調；成本同樣不上升。結果是一棵樹 T'，它仍是最佳的（成本 ≤ T，而 T 本就最佳，故兩者相等），而現在 x 和 y 是最深的兄弟——正是貪婪所決定的那個配置。
把迴圈收尾：最佳子結構與歸納
貪婪選擇性質只處理了第一次合併。要證明「整個」演算法最佳，我們還需要最佳子結構：當我們把 x 和 y 融成單一個超級符號 z（freq(z) = freq(x) + freq(y)）之後，較小問題（以 z 取代 x 和 y）的一棵最佳樹，只要把 z 拆回它的兩個孩子，就能延展成原問題的一棵最佳樹。成本的帳算得剛剛好：把 z 那片葉子換成一個帶有 x、y 兩片葉子的內部節點，會替總和加上 freq(x) + freq(y)，這正好就是 freq(z)，所以把縮減後的問題最佳化，就把原問題最佳化了。
兩塊都到手後，正確性證明就是一個乾淨的對符號數目的歸納。基底情況是一個符號——一棵單節點的樹，顯然最佳。歸納步驟裡，假設霍夫曼在每個 n-1 個符號的實例上都最佳。給定 n 個符號時，依貪婪選擇性質，貪婪的第一次合併是安全的；其餘是一個 n-1 個符號的實例，由歸納假設最佳地解出；而最佳子結構把這兩者縫在一起。於是霍夫曼在 n 個符號上最佳，歸納完成。
值得停下來體會這兩個性質擔負了多少。貪婪選擇性質讓我們能不必前瞻就確定一步；最佳子結構則讓這已確定的一步把問題縮成它自己的一個較小副本。每個乾淨的貪婪證明——你先前看過的區間排程那個、你將會遇見的 Prim 與 Kruskal 生成樹那些——都恰好是這一對：一個安全的第一選擇，加上一個自我相似的餘下部分。當兩者都成立時，貪婪就不是一個「通常有效」的啟發法；它是恰好正確的。
誠實的邊界：霍夫曼承諾什麼、不承諾什麼
把主張說精確。霍夫曼給出的是「對固定頻率、逐符號的無前綴碼」中的最佳——在那個範圍裡這是真正的最佳、沒有附註。但這個範圍是有牆的。它並不承諾一般情況下最小的壓縮檔，因為真實的壓縮器會利用霍夫曼忽略的結構：相鄰符號之間的相關性、重複出現的子字串，以及「有時你能為每個符號花上『分數』個位元」這件事。舉例來說，算術編碼之所以能勝過霍夫曼，正是因為霍夫曼卡在只能給每個符號整數個位元。
關於輸入還有一句安靜的老實話。霍夫曼最小化的成本——各符號的「頻率 × 深度」之總和——是對你餵給它的那個符號分布取的「平均」。如果你餵的是某段文字的頻率，卻拿去編另一段符號組成截然不同的文字，這個編碼對第二段文字可能離最佳很遠，就像平均情況執行時間只描述你假設的那個分布一樣。最佳性是相對於給定的頻率，而不是對「之後出現的任何資料」的普世保證。
最後，把霍夫曼當成一個讓人安心的例外，而不是一張通行證。貪婪失敗的次數遠多於成功；緊接著的下一篇指南會建出 0/1 背包，在那裡，讓「分數背包」獲勝的那個「拿走局部最佳物品」的直覺，徹底失靈，然後它會說明：那些貪婪可被證明有效的結構（像霍夫曼的建樹、以及生成樹演算法）被一個叫做擬陣的抽象所捕捉。霍夫曼是那個幸運的情況：一個仔細的交換論證，把一個簡單、快速、局部貪婪的迴圈變成了一條定理。