從存在界到具體構造
上一個熵單元構造了期望長度比熵多不足一位元的前綴碼。這是有用保證,但未必是給定信源的最短期望長度。Huffman 構造反覆合併概率最小的兩個符號或群組,解決這個有限優化問題。我們會證明為何局部選擇能出現在全局最優解中,而不只把一個短例子當成證明。
設信源有 個必須編碼的不同符號,概率 且 。這些概率描述單個符號;最小化下面的單符號目標不需要連續符號互相獨立。只有當規格不要求為零概率符號提供碼字時,才可省略它。
定義 6.1.1
(二元前綴碼、碼樹與期望長度)
符號 的二元前綴碼為每個 指定長度為 的有限二元字 ,並且任何碼字都不是另一個不同碼字的前綴。其期望長度為
若同一組符號沒有任何二元前綴碼的期望長度更小,則稱該碼對 最優。碼樹是有根二叉樹,通往左子節點的邊標 ,通往右子節點的邊標 ;前綴碼對應以碼字為葉的樹,而 就是 所在葉的深度。若每個內部節點都恰有兩個子節點,則稱該樹為滿樹。
期望長度還可以用另一種方式從樹上讀出,而這種讀法恰好描述 Huffman 算法。
概念視角組合
期望長度是內部節點權重之和
給碼樹的每個內部節點 指定權重 ,即 以下各葉的概率總和。則
的葉在深度 ,恰有 個真祖先,而且全是內部節點,所以 在右邊恰被計算 次。Huffman 算法每次合併產生一個內部節點,其權重就是合併所得的權重,因此 Huffman 樹的期望長度等於 次合併權重之和。把權重 的一對同胞葉縮成父節點,恰好移除一個權重為 的內部節點,其餘內部節點的權重不變。
樹與貪心規則
以碼樹表示有限前綴碼。若 且概率全為正,最優樹不會有只有一個子節點的內部節點:刪除它並把其子樹上移一條邊,會嚴格減少加權長度。單符號時,空字長度為零;接收方必須另知符號數量,因為空位元流本身沒有提供數量。
Huffman 算法從各符號的概率葉開始。只要剩下多於一棵樹,就選目前權重最小的兩棵,作為新父節點的子樹,父節點權重為兩者之和。最後為每對子邊標上 和 ;由根到葉的字便構成前綴碼。權重相等時可任意破同分;不同選擇可以得到不同的最優碼。
為何貪心合併安全?
最優性的證明分兩個引理。第一個引理把兩個最小概率的符號放到第一次合併所放的位置;第二個引理說明合併它們後,問題化為符號較少的問題,而不損失最優性。
引理 6.1.2
(兩個最小概率符號可作最深同胞)
設 且 。存在一個最優前綴碼,其碼樹為滿樹,並且兩個概率最小的符號標在深度最大的一對同胞葉上。
證明
(先證存在,再作交換)
存在性。若內部節點 只有一個子節點,刪除 ,並把其子樹接到 原來的位置。 以下每片葉都上升一層,所以 嚴格減少,而各葉仍構成前綴碼。因此每個前綴碼都被某棵滿樹超越或追平。有 片葉的滿二叉樹有 個內部節點,所以帶 片標籤葉的滿樹只有有限多棵;其中有一棵 在這些樹中使 最小,因而在所有前綴碼中最優。
最深同胞。設 為 的最大葉深度, 為深度 的葉。由於 , 不是根;由於 是滿樹, 有同胞 。若 是內部節點, 以下的葉深度會大於 。故 是深度 的葉。
交換。設 為 上標籤的概率,並假設 以外某片葉上的符號 滿足 ;不妨設最大值在 取得。交換 所在葉與 的標籤。由於 ,期望長度的改變為
所以樹仍是最優的滿樹。每次交換都令 嚴格減少,而標籤方式只有有限多種,所以經有限次交換後不再有這樣的 。此時 上兩個標籤的概率都不大於其餘任何概率:它們是兩個最小概率 ,同分亦包括在內。
第二個引理比較原問題與把兩個最小符號當作一個符號所得的問題。
引理 6.1.3
(縮合最小概率的一對符號)
設 , 是兩個概率最小的符號,概率 ;令 為把 換成一個概率為 的新符號 所得、有 個符號的問題。以 記最優期望長度。則
並且若 對 最優,則給葉 加上標籤為 的兩個子節點所得的樹對 最優。
證明
(展開得一個不等式,縮合得另一個)
展開。設 是 的任一棵樹, 在深度 。給 加上子節點 ,得到 的一棵樹,其期望長度為 。因此 。
縮合。由上一引理,存在 的最優樹 ,其中 是深度 的同胞葉。把它們換成其父節點,即深度 、標籤為 的葉,得到 的一棵樹,期望長度為 。因此 。
兩個不等式合起來給出 。若 對 最優,其展開的期望長度為 ,所以它對 最優。
有了兩個引理,定理便可對符號數歸納得出。
定理 6.1.4
(合併最小兩項的最優性)
對概率全為正的有限信源,此規則產生的樹在所有二元前綴碼中使期望長度最小。 時,樹只有根,碼字為空字。
證明
(對符號數歸納)
時,任何字的長度都至少為零,所以空字最優,而 Huffman 算法只返回根。
設 ,並假設定理對 個符號成立。第一次合併把概率最小的兩片葉 (概率 )合在一起。此後算法把合併所得的樹當作權重 的單一項目,所以其餘 次合併恰好是 Huffman 算法在 上的一次運行,同分選擇亦相同。該運行給出 的樹 ,而 的最終樹就是把 的葉 展開成 。 有 個正概率且總和為一,故由歸納假設 最優,再由縮合引理,其展開對 最優。兩個引理對兩個最小概率的任何選擇都成立,所以證明不依賴特定的破同分規則。∎
證明透視
各個條件在歸納中的位置
有限性只用了一次:保證使 最小的滿樹存在;沒有它,交換步驟便沒有可以修改的最優解。正概率令刪除單子節點成為嚴格改善,所以每棵最優樹都是滿樹;後面的步驟其實只需要「某棵最優樹是滿樹」,而這在權重可為零時仍然成立,因為刪除單子節點從不增加 。
不明顯的一步是交換。它並沒有說每棵最優樹都以 為最深同胞,而是修改某一棵最優樹直到如此。正是這一棵樹提供縮合不等式 ,而任意樹的展開提供相反的不等式。單憑其中一個方向,都不能證明 Huffman 樹最優。
歸納之所以能收結,是因為縮合後的問題仍是概率全為正且總和為一的信源,只是少了一個符號;而且 Huffman 在 上第一次合併之後的運行,正是 Huffman 在 上的運行。若某規則不能化為同一規則在較小問題上的運行,例如下面反例中的自頂向下分割,這個論證就幫不上忙。
證明談的是樹本身;構造樹的成本則取決於存放當前各樹的數據結構。
命題 6.1.5
(以二元堆實現的運行時間)
假設權重的比較與加法為單位成本。若以按權重排序的二元堆優先佇列存放當前各樹,Huffman 算法對 個符號在建堆後進行 次合併及 次堆操作,總時間為 。
證明
(點算堆操作)
以由下而上的堆化建立 片葉的堆需時 。每次合併令樹的數目減一,所以恰有 次合併。每次合併用兩次取最小值及一次插入,由於堆內項目從不多於 個,每次操作需時 ,而建立父節點需時 。總計為 。最後遍歷 個節點,可在 時間求出所有深度;若要逐一寫出每個碼字,則需 次位元操作,對極度偏斜的信源可達 的量級。
精確有理數權重及其編碼可能需要另作位元複雜度分析。每次重新排序或掃描當前各樹的直接實現可有不同操作次數。
四個符號的例子
例題 6.1.6
(概率各不相同的四個符號)
令 的概率為 。先合併 得 ;此時最小的兩項是這個群組與 ,都重 ,合併得 ;最後與 合併。一組標記是
長度為 ,因此每符號期望長度 位元。合併權重給出同一數值:。熵約為 位元。相反,將各 分別向上取整,得到長度 ,期望長度 。兩種方法都產生前綴碼;熵構造的近最優界並沒有說它的具體長度必定最小。
解碼器沿邊走到葉便輸出符號並回到根。例如 可解析為 ,即 。這假設碼樹已知、位元流完整而有效;傳送碼樹、訊息分框和處理位元損壞是額外成本或問題。
第二個例子說明同分能改變甚麼、不能改變甚麼。
例題 6.1.7
(改變長度分佈的同分)
令 的概率為 。第一次合併是確定的: 合成 。此時有三棵樹都重 ,即 、 和 。
若把 與 合併,權重變為 ;再把 與 合併得 ,最後根把它與 連接。長度為 ,。
若改為把 與 合併,權重變為 ;再把 與 合併得 ,最後根把它與 連接。長度為 ,。
兩次運行都合規,由定理兩者都最優,期望長度亦相同,但長度的多重集不同:一者最長碼字有四位元,另一者只有三位元。單是交換左右邊的標籤,已能改變碼字而不改變任何長度。最優性指期望長度,不代表位元分配唯一,也不代表長度分佈唯一。
最後一個例子涵蓋與熵比較時的兩個極端。
例題 6.1.8
(二進分佈信源與偏斜的雙符號信源)
對 ,各次合併權重為 、 和 ,所以 位元,長度為 。此時每個 ,所以 恰好等於熵 位元。
對 及 ,唯一的合併給出長度 ,所以 位元,而
Huffman 碼仍然最優:兩個必須編碼的符號,任何前綴碼的兩個長度都至少為一。將近一位元的差距,是逐個符號以整數位元長度編碼的代價,並非貪心規則失效。
常見錯誤
一個看似合理的替代做法,是由根向下而非由葉向上建樹。
反例模式
平衡的自頂向下分割並非最優
聲稱:把符號按概率排序,將列表分成兩段相連、總概率盡量相等的部分,兩部分的首位元分別為 和 ,再遞歸處理;所得的碼最優。取 的概率為 。頂層分割是 ,總和為 與 ;其他分割的差分別為 和 。接著 分成 ,差為 ,另一種分割的差為 。長度為 ,。Huffman 依次合併 、、,最後 ,得到長度 及 。自頂向下規則背後沒有交換與縮合的論證;有最優性保證的是由下而上合併兩個最小權重。
另外兩個錯誤,關乎合併規則如何應用,以及它的最優性承諾了甚麼。
常見錯誤
(把每個新群組都與下一個符號連接)
四符號例子中,合併所得的群組恰好每次都與下一個符號合併,但這不是規則。合併後的權重要放回候選之中。對四個概率均為 的符號,鏈狀連接給出長度 及 ;Huffman 則分別合併兩對,給出長度 及 。
常見錯誤
(平均最優不等於每個訊息最短)
Huffman 碼最小化的是每符號的期望長度。個別訊息可以比用另一個碼時更長:用四符號碼, 需要 位元,而固定兩位元碼只需 位元。平均而言 Huffman 碼仍然較短,每符號 位元對 位元。
練習
快速檢查
(對概率 執行合併,求期望長度。)
解答 · 答案
先合併兩個 ,再與 合併。長度為 , 位元;由於信源是二進分佈,這正好等於熵。
快速檢查
(為何單符號信源在空字慣例下期望長度為零?解碼另需甚麼資訊?)
解答 · 答案
唯一的葉是根,故碼字長度為零。接收方需要另行指定符號數;單靠空位元流無法得知數量。
快速檢查
(用上面的四符號碼解碼 。)
解答 · 答案
解析為 ,得到 。
快速檢查
(若概率 的兩個符號被放在深度 ,交換標籤後期望長度改變多少?)
解答 · 答案
新長度減舊長度是 。把較小權重移得更深不會增加目標值。
延伸閱讀
MIT OpenCourseWare:Huffman Codes 與 CMU:Introduction to Data Compression 討論最優前綴編碼。