動機
二元前綴碼為每個符號指派一個位元串,使得沒有任何碼字是另一個碼字的前綴。常用符號應獲得較短的碼字,但前綴條件限制了哪些長度可以同時出現。霍夫曼(Huffman)算法反覆合併兩個最小權重,再從所得的二叉樹中讀出碼字。
貪心選擇並不能僅憑「小權重似乎適合放在較深的葉子上」就得到證明。證明必須說明:存在某棵全局最優樹,使兩個最小權重成為最深層的兄弟葉子;並且收縮這對兄弟之後,剩下的較小問題仍然是最優的。
定義
定義 2.7.1
(前綴碼與霍夫曼算法)
設有 個符號,其非負權重為 。二元前綴碼為各符號指派互不相同的有限二進制串,使得沒有任何碼字是另一個碼字的前綴。其代價為 ,其中 是符號 的碼字長度。一個碼對應於一棵二叉樹的帶標號葉子:左、右邊分別標為零和一,葉子的由根到葉的邊標號即為其碼字。
當 時,霍夫曼算法反覆取出兩個最小權重的節點,建立其父節點(權重等於二者之和),並將其重新放回。當只剩一個節點時,將每個內部節點的兩條子邊分別標為零和一。當 時,本單元容許空碼字,代價為零。若通訊格式要求碼字非空,或並不另行知道符號個數,則屬於另一種約定。
定理
定理 2.7.2
(貪心兄弟性質)
當 時,存在某棵代價最小的二元前綴碼樹,使兩個最小權重是位於最大深度的兄弟葉子。
定理 2.7.3
(霍夫曼最優性)
對於非負權重,在所述約定下,霍夫曼構造給出代價最小的二元前綴碼。對 ,使用帶索引的最小堆可在 時間和 空間內構造碼樹;若要顯式寫出全部碼字,則額外需要與碼字總長度成正比的時間。
證明思路或證明
證明
(交換與收縮)
碼樹可以在不增加代價的前提下化為滿樹,即每個內部節點都有兩個子節點:收縮一個只有一個子節點的內部節點,並縮短其下方的碼字。由於權重非負,縮短碼字不會增加加權代價。在具有 個帶標號葉子的滿樹中存在最小者,因為這樣的樹形與標號方式只有有限多種。
在滿樹中,最大深度的葉子的兄弟也是葉子;否則該兄弟會有更深的後代。若較輕的權重佔據的葉子比較重的權重所佔的更淺,則交換兩者不會增加代價。事實上,對權重 與深度 ,把 放到深度 、把 放到深度 後,代價的變化為 。反覆交換可使兩個最小權重在某棵最優樹中位於最深的兄弟對。
設這兩個權重為 。把它們的兄弟葉子收縮成一個權重為 的葉子。其他所有深度不變,而原來的兩個葉子都比收縮後的葉子低一層。因此原來的代價等於收縮後樹的代價加上 。若收縮後的樹對於較小的權重多重集並非最優,則將其換成代價更低的樹,再把合併出的葉子展開為兩個子節點,就會與原樹的最優性矛盾。反之,展開一棵較小的最優樹,代價恰好增加 。對 作歸納即證明:霍夫曼的最小權重合併序列是最優的,包括出現並列與零權重的情形。
二元最小堆存放當前的權重。 次合併中,每次進行兩次取最小值操作和一次插入,每個操作耗時 ;插入初始權重至多耗時 。該樹有 個葉子和 個內部節點,故儲存量為 。邊的標號可在之後再指派。
證明透視
交換與收縮扮演不同的角色
交換說明貪心選出的那一對可以同時出現在某棵最優樹中。收縮說明該最優樹的其餘部分解決的是一個較小的實例。歸納需要這兩步缺一不可。
非負性只在第一步使用:縮短只有一個子節點的內部節點時,代價不可上升。交換不等式 只用到權重的大小次序,而收縮恆等式對任何權重都精確成立。任何一對兄弟葉子都滿足收縮恆等式;交換論證保證的是,位於最深兄弟位置的兩個最小權重會同時出現在某棵最優樹中。
例題詳解
例題 2.7.4
(四個權重)
對權重 ,先合併 ,再合併 ,最後合併 。所得碼長可以是 ,代價為 。各次合併的權重之和同樣是 。
例題 2.7.5
(並列可以改變編碼)
當四個正權重全部相等時,最先被選中的兩個符號可以是任意一對。不同的並列選擇和左右標號會產生不同的碼字,但每個霍夫曼結果都具有相同的最優加權代價。
例題 2.7.6
(零權重)
對權重 ,先合併 與其中一個單位權重,再把所得結果與另一個單位權重合併。兩個正權重的深度分別為二和一,所以代價為三。零權重的符號仍然被分配到一個互不相同的前綴碼葉子。
常見錯誤
反例模式
負權重使最小值消失
斷言:霍夫曼構造對任意實數權重都最優。取兩個符號,權重為 與 。霍夫曼算法使兩個碼字長度都是一,代價為 。但若權重 的符號取碼字 0,權重 的符號取由 個一組成的碼字,這是合法的前綴碼,代價為 。當 增大時代價沒有下界,所以不存在最小代價的碼。可見非負性是必要的:它使收縮只有一個子節點的內部節點是安全的,並使代價有下界。
常見錯誤
(獨立地選取短碼字)
字串 0 與 01 不能同時作為前綴碼的碼字,因為 0 是 01 的前綴。若逐個挑選看似最短的可用字串,而不檢查整棵樹,就可能得到無效的碼。應從同一棵二叉樹的葉子讀出碼字,這樣任何碼字都不會是另一個的前綴。
常見錯誤
(以為每棵最優樹都使用被合併的那一對)
證明所找到的是包含合適貪心兄弟對的一棵最優樹;它並沒有說當權重並列時,每棵最優樹都必須使用完全相同的那一對。
單個符號時採用空碼字的約定必須明確說明,因為某些實際格式要求碼字非空。
前綴碼與樹
二元碼字描述從根出發的一條路徑。若一個碼字是另一個碼字的前綴,則其路徑會終止於另一個碼字所在葉子的祖先。因此前綴碼樹的所有碼字都位於葉子。反過來,在任何二叉樹中,通向不同葉子的路徑不可能互為前綴,所以給兩條子邊標上不同的位元即得到前綴碼。
含有只有一個子節點的內部節點的樹可以縮短:移除該節點,把其子節點直接接到其父節點上;若該節點是根,則把子節點移為根。該子樹中所有葉子的路徑各少一個位元,前綴自由性仍然成立。在權重非負時,這不會增加代價。若該節點下方所有權重都為零,代價可能保持不變;證明只需要存在一棵滿的最優樹,而不要求每棵最優樹都是滿的。
具有 個葉子的滿二叉樹有 個內部節點。一種證明是數邊:每個內部節點有兩個子節點,共 條邊;而含 個節點的有限樹有 條邊。故 。這種有限性使得我們可以合理地選取一棵最優的滿帶標號樹,即使定義中並未限定碼字長度的上界。
例題 2.7.7
(更長的合併序列)
對權重 ,霍夫曼先合併 ,再合併 ,最後合併 。加權代價為 。一棵樹的深度為 ,代價為 。兩種計算相符。
含並列情形的交換論證
固定一棵最優滿樹和一對最深的兄弟。若兩個最小權重之一尚未在該對中,就把它與佔據這些最深葉子之一的權重交換。較小的權重移到不小於原來的深度,較大的權重則移到原來的深度。證明中的代數計算顯示這不會增加代價。對另一個最小權重重複同樣的操作,同時要保證第一個權重仍然留在最深的兄弟葉子上。
所得的樹的代價不超過一棵最優樹的代價,因此它也是最優的。若某些權重或深度相等,交換可能使代價保持不變。這已經足夠:定理斷言的是存在包含所選這一對的最優樹,而不是所有最優樹都含有這一對。正是這種存在性的表述,使得貪心算法在出現並列時可以任意選取兩個最小權重。
收縮之後,合併得到的權重代表該葉子之下的總權重。位於它之上的每一個額外層級,對原來的兩個葉子各計算一次,因而貢獻它們的和。展開該葉子會使兩個原符號各加深一層,並使代價恰好增加 。這個恆等式與收縮後的葉子在較小的樹中處於何處無關。
為甚麼合併權重之和等於代價
概念視角結構
代價等於內部節點權重之和
每次合併產生一個內部節點,其權重是其子樹中所有原葉子權重之和。把整棵霍夫曼樹的這些內部節點權重相加。權重為 的葉子對其每個祖先所對應的內部節點權重恰好貢獻一次,而祖先的個數等於其深度 。因此合併權重之和等於 。
這一恆等式提供了計算已構造的樹的代價的獨立方法。它本身並不能證明最優性:不同的合併序列同樣有各自的內部權重之和。交換與收縮的證明才說明了,為甚麼每一步都選取兩個最小權重,能在所有有效的碼樹中使該和最小。
左右邊具體被指派的位元不會改變碼字長度或代價。但它們會影響實際的碼本,所以編碼器與解碼器必須使用同一棵帶標號的樹,或約定好的規範表示。這裏的數學優化問題只涉及加權長度;傳輸碼本、訊息分幀以及處理被破壞的數據流是另外的問題。
輸出與複雜度
堆的分析在 的堆操作時間內構造出具有 個節點的樹。若要求的輸出是每個葉子的顯式位元串,則寫出這些字串所需時間與 成正比。滿二叉樹的深度可以高度不均,因此輸出長度可能超過 。若把僅僅堆的時間界當作列印所有碼字的時間,就忽略了輸出的規模。
證明假設所給權重可以被精確比較和相加。若權重是有二進制編碼的有理數,實作必須正確表示並比較和;對於任意表示方式,單純統計堆操作次數本身並不是完整的位元複雜度分析。負權重被排除在外:縮短負權重的碼字可能增加目標值,所以滿樹化約不能用同樣的論證得出。
當 時,在這一數學約定下,空字是唯一的葉子路徑,代價為零。對於單符號字母表它是前綴自由的,但一串空碼字在沒有外部分幀的情況下無法表明發送了多少個符號。若某種格式要求每個符號一個位元,則其受約束的最優解不同。這是建模上的選擇,而不是隱藏在貪心證明中的例外。
檢驗給定的碼
檢驗一個給定的碼時,首先確認所列出的碼字中沒有任何一個是另一個的前綴。然後根據給定的權重和碼字長度計算加權長度。對於由霍夫曼算法產生的樹,合併權重之和是一個有用的算術交叉檢驗。代價低的有效前綴碼不一定是最優的;最優性來自貪心兄弟與收縮定理,或者來自單獨的下界證書。
若權重表示概率,它們的和可以為一,但歸一化對優化並非必要:將每個權重乘以同一個正常數,會使每個碼的代價同比例縮放,不會改變哪個碼是最優的。零權重是容許的,算法仍會為列出的每個符號構造碼字。證明把權重當作非負的代價,不假設任何隨機模型。
對概率而言,最優平均長度與熵相差不到一個位元。
自然延伸的下一個問題
前綴碼最接近熵有多近?
對概率而言,最優平均長度與熵相差不到一個位元。
若權重是概率 ,最優二進制前綴碼的平均長度 滿足 ,其中 。上文的權重 對應概率 ,於是 ,下界剛好取到。對概率 ,則 而 ,可見差距可以接近一個位元。
總結
存在滿的最優樹,可把兩個最小權重放在最深的兄弟葉子上。收縮這一對會縮小問題,並使代價改變它們的和。重複這種安全的合併,即得到最優的前綴碼樹。
練習
快速檢查
(兩個符號的權重為 和 ,其霍夫曼代價是多少?)
解答 · 答案
兩個碼字的長度均為一,所以代價為 。
快速檢查
(為甚麼在有限滿樹中,最深葉子的兄弟不可能是內部節點?)
解答 · 答案
若兄弟是內部節點,它就會有比所選最大深度葉子更深的後代葉子。
快速檢查
(合併權重 與 所產生的父節點被指派甚麼權重?)
解答 · 答案
父節點的權重為 。
快速檢查
(為甚麼證明容許出現並列?)
解答 · 答案
交換與收縮論證使用的是非嚴格不等式,所以在相等的最小權重之間任意選擇,都可以在某棵最優樹中使用。