把編碼看成帶權樹
設 個不同符號的權重 均非負。我們希望為符號指定位元字串,使常用符號得到較短的字串,同時令每段編碼訊息都能由左至右唯一解碼。
定義 5.1.1
(前綴碼與加權長度)
二元前綴碼為每個符號指定有限位元字串,任何碼字都不是另一碼字的前綴。它的二元 trie 以葉節點表示各符號,符號 的葉深 就是其碼字長度。該編碼(或其樹 )的加權長度為
我們要在二元前綴碼中最小化此和。若權重是概率,它是每符號的期望位元數;若是出現次數,它是總加權長度。問題假設符號權重已給定,並未計入傳送碼本的成本。此處排除單一符號的約定:應用須另外指定是否容許空碼字。
為何最小的兩個權重可以是兄弟
定義 5.1.2
(滿二叉樹)
若二叉樹的每個內部節點都恰有兩個子節點,便稱為滿二叉樹。
任何前綴碼樹都可化為滿二叉樹。若某內部節點只有一個子節點,繞過該節點;其後代深度都減一,因權重非負,成本不會增加。重複後得到相同葉節點的滿二叉樹。對固定 ,滿二叉樹形狀及符號配置只有有限種,因此存在最優滿二叉樹。有 個葉的滿二叉樹有 個內部節點。
引理 5.1.3
(兩個最小權重可作最深的兄弟)
設 為兩個符號,且對其餘每個符號 都有 。則存在某棵最優滿二叉樹,使 成為位於最大深度的兄弟葉。
證明
(交換標籤)
取一棵最優滿二叉樹。若較輕的葉比較重的葉淺,交換兩者標籤使成本改變 ,因此不會增加成本。
最深的葉有一個同為葉的兄弟:因為樹是滿的,兄弟存在;若它是內部節點,便會有更深的後代。設 為最大深度 的一對兄弟葉。交換 與 處符號的標籤。由於 權重最小而 已最深,成本不增加。接著交換 與 處符號;此時 在 以外的符號中權重最小,成本同樣不增加。兩次交換後 是深度 的兄弟,而成本仍是最小,所以此樹最優。
引理 5.1.4
(收縮一對兄弟葉)
設 為滿二叉樹,其中葉 為兄弟;刪去它們,並把它們的父節點視為權重 的新葉 ,得到 。則 。反過來,縮減權重下任何以 為葉的樹 都可展開成這樣的 。
證明
(只差一層深度)
設父節點深度為 。在 中 的深度為 ,貢獻 ;在 中 貢獻 。其他葉在兩棵樹中的深度相同。相減即得等式。把任何樹 的葉 展開為標記 的兩個子節點,就是逆運算。
定理 5.1.5
(霍夫曼合併法則最優)
反覆合併當前兩個最小權重的項目,以權重為其和的一項取代,直至只剩一項。如此建成的樹在所有二元前綴碼中使 最小,不論以何種固定規則打破平手。
證明
(對符號數作歸納)
時,唯一的滿二叉樹有兩個深度為 的葉,合併步驟恰好建出它。
設 ,並設 是第一次合併所合併的兩項;因為合併取的是兩個最小權重,它們滿足第一個引理的假設。令 為此程序對縮減權重(以 取代 )所建的樹;由歸納假設, 對縮減問題最優,成本為 。此程序對原權重所建的樹 就是展開 後的 ,故由第二個引理 。
由第一個引理,某棵最優樹 以 為兄弟。收縮後得到縮減權重的樹 ,故 ,且
由於 最優, 也是最優。
證明透視
為何安全的第一步已經足夠
證明的兩半用到不同的假設。交換部分只用到一次權重非負,就是繞過單子節點而不增加成本,從而化為滿二叉樹;滿性保證最深葉必有同為葉的兄弟。交換本身只用到權重的次序: 與 使乘積 不為正。收縮部分對權重不作任何假設,它只是關於深度的等式。
關鍵一步是把「選擇」與「求解」分開。交換引理說明貪心選擇,即把兩個最小權重放在最底部,是安全的:某棵最優樹包含這個選擇。收縮等式再說明其餘部分是少一個符號的同一問題,成本只相差固定的 ,所以最優化其餘部分就是最優化縮減問題。
論證由兩葉的基底情況出發,對 歸納收結。平手不費分毫,因為第一個引理對任何一對最小權重成立,而非只對某一對。論證會失效之處是第一個引理:合併不是最小的兩項,會破壞 ,下面的合併次序例子正要付出代價。
從各符號的單葉樹開始,反覆合併最小兩個權重便構造這樣的樹。最後一次合併得到一個根;其左右邊可以任意次序標為 和 。每個符號在其葉節點解碼,故沒有碼字是另一碼字的前綴。
概念視角組合
成本是內部節點的權重之和
深度為 的葉恰有 個真祖先,全是內部節點。把每片葉的權重對它的每個祖先各計一次,得到 ,對所有內部節點 求和,其中 是 之下所有葉的權重總和。每次合併產生一個內部節點,其權重就是合併後的權重,所以成本等於所有合併權重之和。收縮一對兄弟葉恰好移除一個權重為 的內部節點,這就是收縮恆等式。
例題
例題 5.1.6
(合併過程的跟蹤)
令 的權重為 。貪心法先把 合併成 ;此時最小的兩項是 ,合併成 ;然後 合併成 。一組所得碼為
其加權長度為 。等價地,每次合併對總和增加其合併權重,得到 。注意 是根的權重,不是成本。
反例模式
並非每個合併次序都最優
先合併 和 得 ,再把原來的 與這個 合併得 ,最後把權重為 的原符號 與 合併。合併權重之和為 ,所得前綴碼合法,但成本是 而非 。直接計算: 深度為 , 深度為 , 深度為 ,成本為 。合法前綴樹本身不足以證明最優性:每次合併都必須取兩個最小權重。
例題 5.1.7
(平手會給出不同的最優樹)
設權重為 。第一次合併把兩個 合併成權重 ,餘下三個權重為 的項。若合併兩個原來權重為 的符號得 ,再把 與 合併,合併權重為 ,每個符號深度均為 :。若改為把新項與一個權重為 的符號合併得 ,再與另一個符號合併,合併權重同樣是 ,但深度變為 :。兩棵樹都最優,碼字長度卻不同。
例題 5.1.8
(最小的例子,含零權重)
設 ,權重為 和 。只有一次合併,權重為 ,碼字為 和 ,加權長度為 。零權重的符號仍然有碼字,成本與其深度無關。這就是歸納的基底情況。
算法成本與範圍
命題 5.1.9
(時間與空間)
使用最小優先隊列,為 個符號建樹需 次插入,以及 輪(每輪取出兩項並插入一項)。在權重比較及加法為常數時間下,需 時間及 個儲存節點與隊列項。
證明
(計算隊列操作次數)
初始有 次插入,而 次合併各作兩次取出及一次插入,所以隊列操作合共 次。在堆上每次花 ,總計 。樹有 個葉及 個內部節點,儲存量為 。
輸出全部碼字還需與輸出總長度成比例的時間,該長度可以超過 。有限精度溢出、碼本元數據及無限數據流編碼是另行處理的實作問題。
常見錯誤
常見錯誤
(把根的權重當作成本)
根的權重是全部符號的權重總和,在上面的跟蹤中是 。成本是所有內部節點權重之和,這裏是 ,等價於各葉的權重乘深度之和。
常見錯誤
(總是把下一個最小符號接上去)
合併出來的節點與符號同在隊列中競爭。反覆把最小的未用符號接到不斷增長的子樹上,形成梳狀樹,並不是霍夫曼(Huffman) 法則。對四個權重均為 的符號,梳狀樹的深度為 ,成本是 ;先把符號兩兩合併,深度為 ,成本是 。
權重非負用於化為滿二叉樹,下面的例子說明這項假設不能隨便放棄。
反例模式
負權會破壞合併法則
取權重 ,它們不符合非負的假設。合併法則把 與 合併成 ,再把 與 合併成 ,成本為 。直接計算:未合併的 在深度 ,其餘在深度 ,得 。但前綴碼 以 、、 合法,成本為 ,更小。權重為負時,深的葉可以有利,繞過單子節點也不再安全。修正後的陳述就是上面所證的:權重必須非負。
習題與解答
快速檢查
(0 和 01 能同時是前綴碼的碼字嗎?)
逐個字元比較這兩個字串。
解答 · 答案
不能;0 是 01 的前綴。
快速檢查
(合併權重 及 的葉時,以甚麼權重取代?該次合併對加權長度貢獻多少?)
使用收縮等式。
解答 · 答案
父節點權重為 ,該次合併對加權長度貢獻 。
快速檢查
(若兩個權重相等,最優碼的位元字串必定唯一嗎?)
想想交換某節點的兩個子節點。
解答 · 答案
不必。平手及交換左右子節點可得到不同的最優碼,而加權成本仍最優。
快速檢查
(有些權重為零時,為何仍可繞過單子節點?)
比較縮短前後的成本。
解答 · 答案
權重全部非負,縮短後代的碼字不會增加總和;有零權重時成本可以不變。