動機
前綴碼消除了串接二進制描述時的歧義,但它本身並不能選擇經濟的長度。讓常見符號獲得較短的描述聽起來合理;然而要證明某棵特定的貪心樹是最優的,單靠這種直覺是不夠的。我們會找出某個最優解必定包含的一對兄弟節點,把它們收縮,然後求解規模更小的問題。
由此得到的算法就是 Huffman 編碼。對於給定的有限概率分佈,其輸出在所有二元前綴碼中使平均長度最小。這一陳述並不使最大長度最小,不保證樹是唯一的,也沒有計入學習並傳輸該分佈的代價。我們還要區分無損信源壓縮與通道錯誤的糾正。
單符號描述的長度是整數,因此其平均長度可能明顯高於熵。對已知大小的分塊編碼會改變被編碼的分佈,並減小每個原始符號的超出量。該論證會證明碼率結論,並揭示分塊字母表的指數規模,而不是把一個龐大的存在性碼本當作高效的通用壓縮器。
定義
定義 3.2.1
(前綴碼、字典樹與平均長度)
設符號 的概率 且和為一。二元前綴碼給每個符號指派有限位元串 ,使其中任何一個都不是另一個的前綴。記 ,。其字典樹(trie)是以邊承載位元、符號串為葉子的有根樹。若 ,容許空串,其長度為零;此時解析需要符號個數或其他成幀資訊。
定義 3.2.2
(滿二叉樹與節點權重)
對 ,滿二叉樹的每個內部節點恰有兩個子節點,葉子承載符號。葉子的深度等於碼長。節點的權重是其下所有葉子概率之和。交換符號會改變加權代價,但不改變前綴性質。
熵為 。前一章關於前綴碼的內容證明了 Kraft 不等式及其逆命題:整數長度存在二元前綴實現,當且僅當 。我們使用的是這一已證明的構造,而不是假定的編碼定理。下文所有算法中的權重比較都是精確的;按位元複雜度實現時,採用以二進制表示的正有理概率。
定理/命題
定理 3.2.3
(Huffman 合併規則是最優的)
反覆將兩個當前權重最小的節點合併為一個父節點,其權重為二者之和。從符號概率出發,最終得到單一的根。兄弟邊可按任意次序標記為零和一。所得編碼在給定正概率的所有二元前綴碼中使 最小。出現並列時可任意處理。
定理 3.2.4
(熵界與精確的等號條件)
設最優平均長度為 ,則
等號 成立,當且僅當每個 都是 的形式,其中 為非負整數。對於單符號信源,最優值與熵均為零。
定理 3.2.5
(獨立分塊逼近熵)
對於具有該分佈的獨立同分佈信源,對全部 個長度為 的分塊做 Huffman 編碼,其期望分塊長度 滿足
在分塊邊界已知的情況下,可由分塊碼字精確還原信源。該定理並不斷言構造在分塊長度上是高效的,也不處理使用相同乘積概率的任意相依信源。
證明思路或證明
把優化問題化歸為有限滿樹
證明
(化為有限多棵滿樹)
從任意一棵容納有限個符號的前綴字典樹出發。刪去不含任何符號的分支。若某個內部節點只有一個子節點,則收縮這條邊。其所有後代碼字縮短一位,且仍保持前綴無關;由於它們的總概率為正,平均長度嚴格減小。重複這一過程,得到恰有 個葉子的滿樹。
有 個葉子的滿樹有 個內部節點:把邊數一方面記為內部節點數的兩倍,另一方面記為節點總數減一,即可得出。因此其最深葉子的深度至多為 。這樣的樹形與符號指派只有有限多種。最優解在其中存在,並且任何非滿的字典樹都不能優於它。這一有限化歸避免了不加證明地假定實數加權長度的下確界可以取到。
把兩個概率最小的符號放在最深的兄弟對上
證明
(貪婪選擇與最優子結構)
取一個最深的葉子。它的兄弟必定也是葉子:若兄弟是內部節點,則它會有更深的後代。設 是兩個概率最小的符號。存在某棵最優滿樹,可以把它們放在這對兄弟位置上。
事實上,若 當前的深度為 ,而符號 佔據了所選的深度 位置,則交換二者使代價改變 。由於原樹是最優的,交換後仍然最優。接著把 換到另一個最深兄弟位置;同一不等式依然適用,且不會移動 。出現並列時改變量為零,不造成任何困難。
把這兩個兄弟葉子收縮為一個概率為 的單一符號。代價恰好減少 ,因為這兩個符號各少一位,而其他所有長度保持不變。收縮後的樹必須對合併後的分佈是最優的。否則,用更便宜的合併樹替換它,再把兩個子節點展開,就會改進原來的最優解。
反過來,取任一最優的合併樹,把其合併葉子展開為原來的兩個子節點。其代價等於合併後的最優值加上 ,這與剛才確定的原問題最優值相同。因此貪心的第一次合併是安全的。對符號個數用歸納法即可證明完整的算法,以單符號的空樹為基礎情形。
證明透視
交換與收縮各自證明了甚麼
證明有兩個步驟,分別回答不同的問題。交換步驟只用到 與 ;它說明的是某個最優樹(而不是每個最優樹)把兩個概率最小的符號放在最深的兄弟位置上,而相等的情形使代價變化為零而非負數。最深兄弟對的存在用到滿樹性質,這由先前的化簡提供:在非滿的字典樹中,最深的葉可能是獨生子節點。
收縮步驟是最優子結構進入的地方。合併兄弟葉使代價恰好減少 ,這個量與樹的其餘部分無關;正是這個常數平移,使最優性能夠在原問題與合併後的問題之間雙向傳遞。對 歸納即完成論證;之後的合併作用於子樹權重而非原來的概率,所以交換步驟必須對每個較小的問題重新應用。
交換與收縮這一對論證,正是貪婪規則安全的原因;缺少它的看似合理的貪婪規則可能失敗。
反例模式
自上而下的均衡分割並非最優
斷言:把排好序的符號分成總概率盡量相等的兩組,再遞歸進行,可得最優前綴碼。對概率 ,最均衡的第一次分割是 對 ,總和分別為 與 。把第二組分為 對 ,得長度 ,以及
Huffman 依次合併 、、 與 ,合併權重之和為 ;其長度為 。因此均衡分割不是最優的。修正後的命題就是定理:自下而上合併兩個權重最小的節點是最優的。
用合併權重為平均長度作證書
證明
(合併權重與實現代價)
所有內部節點的權重之和等於 。每個葉子的概率對其每個內部祖先各計一次,而這些祖先的個數就是它的深度。在 Huffman 構造中,內部節點的權重恰好就是各次合併所產生的權重。因此把合併權重相加,就得到一個無需列出每個碼字的獨立代價證書。
最小優先隊列可在每次合併的對數時間內選出兩個最小權重並插入它們的和,總計 次權重比較與 個樹節點。這裏統計的是精確的運算次數,而不是把任意精度比較的代價當作零。對於有理概率,取各輸入分母的乘積作為公分母 。其二進制長度至多為各輸入長度之和。所有節點的分子都是不超過 的非負整數,因此算術與比較的位元代價關於輸入規模是多項式的。
寫出全部顯式位元串本身就可能需要二次的總輸出長度:共有 個葉子,每個深度至多為 。用樹來表示可避免把這一輸出代價算入堆比較的次數。此處沒有包含概率估計或碼本傳輸的代價。
用 Kraft 不等式與散度確定最優值的位置
證明
(Kraft 不等式與散度)
對任意前綴碼,令 ,並令 。這些 構成一個正分佈。由先前已證明的散度非負性,得到
因此 。要使全程取等號,需要 且 。反之,如果各概率具有這種冪的形式,則 Kraft 逆命題給出相應的前綴長度,其平均恰為熵。於是 Huffman 最優性迫使其平均長度也是同一個值。
對於上界,使用 Shannon 長度 。它們的 Kraft 和至多為 ,且每個長度都嚴格小於 。因此具有這些長度的前綴碼,其平均長度嚴格小於 。Huffman 最優解不會更差。這一界比較的是平均長度;它並不表示 Huffman 使用的正是這些取整後的長度。
把符號字母表換成已知大小的分塊
證明
(獨立塊的熵)
對於獨立分塊 ,其概率為 。展開對數並對所有分塊求和,得到 :每個座標的貢獻是一份 ,因為其餘各座標的概率之和為一。把剛證明的單字母表界應用到這個分塊分佈上,再除以 。
這一構造在分塊層面是精確且前綴無關的。解碼器沿分塊碼樹行走直至葉子,輸出該葉子的 個符號,然後回到根。不完整的最後一塊需要填充並記錄原始長度,或採用另行規定的約定。對有限檔案而言,這些成幀代價並非悄悄地為零。此外,可能的分塊列表有 個,因此直接做 Huffman 構造通常關於 是指數級的,儘管其超出碼率趨於零。
例題詳解
例題 3.2.6
(由三次合併讀出最優值)
對於概率 ,先將 與 合併為 ,再將兩個 節點合併為 ,最後把 與 合併為一。合併權重之和為 。一種編碼是按概率由大到小依次為 ,其加權長度同樣給出 。熵約為 ,故間隙為正且小於一。貪心證明確立了最優性;僅僅觀察到常見符號有較短碼字並不能做到這一點。
例題 3.2.7
(二進制冪分佈的等號及其整數約束)
對於概率 ,編碼 的平均長度為 ,恰好等於熵。相比之下,三個等概率符號的最優長度為一、二、二,平均為 ,而熵是 。沒有任何三個整數碼長能使這些概率取到等號,因為 不是 的倒數冪。並列的符號中,任何一個都可以得到較短的碼字。
例題 3.2.8
(兩符號分塊改進了碼率)
對於概率為 的二元信源,逐符號的前綴編碼每個符號花費一位元。兩符號分塊的概率為 。其 Huffman 合併權重為 ,所以分塊代價是 ,即每個原始符號 。這更接近熵(約 ),但仍高於它。這一收益利用了四葉分塊字母表與獨立性;它並非來自改變已經最優的兩葉單符號樹。
常見錯誤
即使在最優碼之中,樹本身也不是唯一確定的。
反例模式
最優平均長度未必決定樹形
對於概率 ,並列情形下的 Huffman 合併可以得到四個深度為二的葉子,也可以得到深度為一、二、三、三的樹,其中概率為 的符號位於深度一。兩者的平均長度都是二。因此,最優平均長度並不固定最大長度,也不決定唯一的樹。限制碼長的編碼問題增加了另一種約束,需要另行分析。
常見錯誤
(零概率符號會改變問題)
正概率是一條明確的假設。如果仍然要求零概率符號擁有不同的前綴描述,它就可能影響分配給正概率符號的長度。例如,概率為一和零時,若兩個標籤都必須可被解碼,則仍需要兩個非空碼字;刪去不可能出現的符號則容許空字,平均長度為零。在去掉零項之前,應先說明被編碼的是哪個字母表。
常見錯誤
(前綴碼不能糾錯)
前綴無關也不是糾錯。翻轉一個傳輸位元可能選中另一條分支,並擾亂後續的符號邊界。信源模型下的熵最優性不提供任何距離保證、認證,也不能防止此類更改。
練習
快速檢查
(對於概率 ,求 Huffman 合併權重與最優平均長度。)
把相等的權重兩兩合併。
解答
把四個八分之一兩兩合併,得到兩個四分之一,再將它們合併為二分之一,最後把兩個二分之一合併。內部權重為 ,和為二。概率為二分之一的符號長度為一,每個八分之一的符號長度為三,平均長度同樣為二。這些長度就是各概率的以二為底對數的相反數,所以熵的等號確認了這個值。
快速檢查
(為甚麼把最不可能的符號放在最深處,只能證明第一次合併是合理的,而不能自動證明後面每一步貪心?)
想一想第一次合併後較小的問題必須滿足甚麼。
解答
交換步驟確立了存在一棵含有所選兄弟對的最優原樹。只有收縮論證才證明,它剩餘的樹對合併後的分佈是最優的,並且任何最優的合併解都可以展開回去。隨後用歸納法使之後所有的合併合理化,這些合併的權重是子樹之和,而不是原始概率。
快速檢查
(說明滿樹的最大深度如何能達到 ,以及這對寫出全部碼字意味著甚麼。)
數一數由根到葉的路徑上的內部節點。
解答
滿樹有 個內部節點,從根到葉的路徑不可能使用比全部內部節點更多的節點。梳狀的滿樹可以達到深度 。因此,即使樹只有線性多個節點,把 個顯式字串的長度加起來也可能是二次的;優先隊列的比較次數界並不包含整個輸出。
快速檢查
(對於分塊長度 , 至少為多大才能使已證明的超出碼率小於每符號 位元?還剩下甚麼計算上的限制?)
使用超額界 。
解答
嚴格的界是超出量小於 ,所以 就已經使超出量嚴格小於 。分塊字母表有 個可能的條目,這會使直接構造與儲存不切實際。超出量很小的定理並不是實際的複雜度保證。
快速檢查
(某個相依二元信源在一個初始的公平位元之後,在零與一之間確定性地交替。為甚麼乘積分佈的分塊證明不適用?)
比較塊的聯合分佈與其邊緣分佈的乘積。
解答
每個座標的邊緣分佈都是公平的,但長度為 的分塊只有兩個可能的交替字,每個的概率為二分之一。其聯合熵為一位元,而不是 位元。把聯合概率換成乘積、把熵換成求和的獨立性步驟在此不成立。對實際的分塊分佈編碼是另一個定義明確的問題。