浙江大學-數據結構-選講Huffman Codes-7.4.1

02-25

Huffman Codes

huffman codes最大的問題就在於huffman編碼是不唯一的，我們來看一個非常簡單的例子，比如說我們有4個字元，它的頻率分別是1，1，2，2，按照huffman演算法，我們把兩個頻率最小的先合併，然後再跟頻率次小的去合併，最後再合併最後一個字元，那麼我們就得到了這樣一棵哈夫曼編碼樹，那麼根據這棵樹呢，

這兩個頻率為1的字元，它們的編碼長度分別是3(就是數從根結點6到葉子結點1的長度),最後根據哈夫曼的結論這樣得到的編碼總長度一定是最優的，但是像這樣的一棵樹，它對應的編碼並不是唯一的，一個最簡單的不唯一的例子，就是將整棵樹鏡像的反一下，換言之，我們把向左的分叉都定義為0，向右的分叉都定義為1的話，那這就相當於我把編碼里的0和1對調了一下，得到的編碼仍然是另一套哈夫曼編碼，那麼除此之外呢，比如說這兩個字元(最下面的1和1),雖然它們的頻率相等，都是1和1，但是字元的位置是可以交換的，比如說左邊字元是A,右邊字元是B,那麼交換後左邊放B,右邊放A,我又得到一套不一樣的編碼，但是它們都是最優編碼，那麼除了這個編碼裡面，0和1會互換，還有一種這個樹可能也完全長的不一樣，比如說我在合併了1和1之後，得到一個新的結點，它的權重是2，那麼這時我有3個2，如果不是由剛才新生成的2與另外兩個2來組合的話，而是由原本的兩個2進行組合的話，就可以得到一個等長編碼的結果，這個等長編碼仍然是一套哈夫曼編碼，它仍然是最優編碼，那這些都說明哈夫曼編碼是不唯一的，那另外還有一個額外的問題是說，哈夫曼同學在他的博士論文里證明了，用他的演算法得到的編碼一定是最優的，但是呢，這個命題反過來是不成立的，最優編碼不是只能通過Huffman演算法才能得到，最優編碼還可以通過其它的方式來得到。

你能想一個反例出來嗎？其實這個反例很現成，我們還是來看這四個字元，既然說等長編碼也是最優編碼的話，那麼我把這4個字元怎麼放都是沒關係的，我可以先合併1和2，再合併另一個1和2，然後得到這個等長編碼，跟上圖的等長編碼最後的效果是一樣的。所以最優編碼還可以通過各種其它的途徑得到

說到這呢，如果我們把這道題的意思理解為僅僅為要判斷它是不是哈夫曼編碼，可能不太準確，事實上，我們要的是，只要它滿足最優編碼的條件，就都是正確的，那接下來我們就來看一下，在寫程序的時候，我們讀進來一段編碼，要判斷它的哪些特點，首先這個學生提交的編碼它一定要是最優編碼，就意味著它的編碼的總長度WPL一定是最小的，那麼你要想一個最簡單的情況是，我把每一個字元都給它，或者是0，或者是1，就一個編碼，行不行呢？這樣的話，我整個加起來的總長度肯定是最小的嗎？但是那個不行的，因為你還要考慮到解碼，所以我們這個編碼一定得是無歧義的解碼。

前面已經講過，這樣的碼就是前綴碼，那前綴碼對應到一棵二叉樹裡面，就意味著，每一個字元都一定要放在這一棵樹的葉子結點上，如果有任何一個字元放在了中間的內部結點上，那就意味一定存在另外一個字元它的編碼會經過這個字元的編碼，也就是說這個字元就會成為另外一個字元的前綴編碼，這個解碼的就會有歧義，當然了，哈夫曼樹是沒有度為1的結點，但其實呢，這一條在程序裡面，是不需要判斷的，因為如果一套編碼，它滿足第一和第二的話，它一定沒有度為1的結點，為什麼是這樣呢？想一下看，如果不是的話，那我們用反證法，如果在這棵樹裡面，存在一個度為1的結點，那麼這個結點假設它有這樣的一棵子樹的話，它肯定不是葉子結點，對不對？於是在這個結點上，一定不會放真正的字元，那麼它的一棵子樹下面，一定是有葉子結點的，那些葉子結點是對應的真正的字元的，那麼如果我們把這個結點給它去掉的話，會有什麼影響呢？如果我們把這個結點去掉，並不影響其它的編碼仍然保持成前綴碼這個特點，因為所有的字元還都在葉子結點上，那麼它的原來這棵子樹上面所有的葉子結點，它們所有的編碼都會縮短一個單位，於是我們就得到了一套更短的編碼，但是呢，如果我們還說它的條件一是滿足的，它本身已經是一個最優編碼了，那麼這是不可能的，我們應該不可能得到更短的編碼，所以這就是一個矛盾，於是我們用反證法證明了這一點，所以當我們寫這個程序去實現的時候，只要我們能判斷兩個條件，第一，它的編碼長度是最優的，第二，它的所有的真正的字元，都是落在這棵樹的葉子結點上，能判斷清楚這兩點，我們就能保證說OK,這個編碼是對的，當然我們注意到，如果要這樣寫程序的話，首先我要知道最優編碼長度到底是多少，就是我先得有一個標準答案，我再把學生的答案往標準答案上去套，那麼要求這個標準答案呢，我就必須要去建一棵哈夫曼樹，那麼有些有小聰明的同學，要想個辦法把這些事情繞過去，他不想建那棵哈夫曼樹，那怎麼辦呢？他就想通過判斷2和3來決定這個編碼是不是對的，但是你要知道同時滿足2和3的樹可不一定我們要的有最優編碼的那棵樹，

你能舉一個反例出來嗎？

我們看一個非常簡答的反例，比如說我們有3個字元，它的頻率分別是1，2，2(就是3個葉子結點到根結點的長度),我們構造了兩棵二叉樹，看上去呢，好像都是滿足2和3的，首先它們的字元都是在葉子結點上，沒錯吧？所有的結點要麼是葉子結點，要麼度都是為2的，這個3也沒錯吧，但是你看一下這兩棵樹都是最優編碼樹嗎?

但是左邊的樹不是最優編碼樹，雖然滿足條件2，條件3