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

核心演算法

對每位學生的提交，檢查它們的編碼是否正確，檢查的事項如下

• 長度是否正確（編碼的總長度是不是正確)
• 建樹的過程中檢查是否滿足前綴碼要求(在長度正確的前提下)

檢查長度是否正確，這件事情是比較簡單的，我只要把每一個字元對應的編碼讀到一個code字元串裡面，然後我求字元串的長度，我用字元串的長度乘以它的頻率，然後求和就得到了它的總長度，然後把這個總長度跟我上一步算出來的標準答案去比對一下，這裡頭有一個細節問題，你要注意到學生有可能是給錯誤的提交，那麼code這個字元串要定義到多長，是合理的呢？換句話說，如果這個編碼是正確的話，那麼哪一個字元它對應的最大編碼長度應該是多少呢？

最變態的情況，這棵哈夫曼樹長什麼樣呢？

就會長成上圖的樣子，所以在這種情況下，如果我們有N個結點的話，就會有N-1個中間結點，也就對應了這個編碼的最長編碼的長度，就是N-1，我們在這其實可以卡一刀，在這裡你要申明一個長度為N-1的字元串，然後讀的時候，如果發現它的長度居然超過了N-1,那麼其實後面也就不用做了，你就可以直接說這個學生肯定是提交錯了。當然了，這個學生的提交還是要完全讀完，才能給出最後的結論，否則的話，會影響你讀下一個學生的提交，OK,如果長度檢查這一關，是正確的，那我們就開始逐個檢查它的每一段Code是不是滿足前綴碼的要求，怎麼做呢？一個最直接了當的方法就是真的去建一棵樹，首先我們先建一個根結點，然後我們來逐行檢查這個Code,比如說我們下一個讀進來的Code是1011，那我們從它的第一個字元開始，第一個字元是1，

那就意味著從當前結點，我們應該向右拓展一層，當前這個結點我們檢查一下它有右子樹嗎？沒有，它的右邊是空的，那麼這一步是OK的，我們就直接給它建立一個右孩子，

然後接著去讀它的下一個是0，當前結點在這裡，它有左孩子嗎？沒有的話，OK,我們給它建立一個左孩子，繼續往下，下一個是1，

當前結點在這裡，因為它的右孩子為空，所以給它建立一個新的右孩子，

再繼續又是一個1，那我們繼續建立一個右孩子，到這個時候呢，我讀到了字元串的結尾，

那也就意味著，在現在這個結點上，我應該把真正的字元以及它的權重放進去了，其實字元沒有必要放進去，我今天把它這個權重，也就是它的頻率放進去了，在放進去之前，我需要很慎重的檢查一下，這個結點是葉子結點嗎？也就是它的左右子樹都是空的嗎？就這個問題上來說，它是空的，所以OK,我就把這個頻率寫到葉子結點裡面去了，

那接下去我們看又來了一行Code,它是100，

我們又回到了根結點，從根結點出發，它的第一個字元是1，那就意味著我們要往右邊走一個單元，那我發現右邊這個結點已經存在了，這個時候我們要檢查一下，它是一個有權重的結點嗎？不是的，它是一個空結點，如果是一個空結點，這件事情就對了，OK,那我們繼續往下走，下一個是0，那我們走到這(第三個球)

然後再下一個又是0，那我們看當前結點的左孩子是空的，我們建立一個新的左孩子，這時我讀到了字元串的結尾，檢查一下這的確是一個葉子結點，OK,沒問題，那我就把這個權重寫進了這個葉子結點裡面，結束這個Code

接下來呢，我們在看，什麼情況下，有可能出錯，如果我讀進來的這個Code是1001，

會發生什麼事情呢，我們從根結點出發，我們發現1是OK的，0是OK的，再讀到第三個字元的時候，它又是一個0，那就意味著我們要往左邊再往下拓展一層，這個時候我發現這是一個帶權重的結點，之前我已經寫了一個在這裡了，就意味著這個字元的編碼一定是這個編碼的前綴，事實也是這樣，100是1001的前綴，所以我們讀到這裡，就知道這是錯了

我們再來看另外一種錯誤，比如說我讀進來的Code是101，

很明顯，我們看到101是1011的前綴，那麼在這棵樹裡頭，我們是怎麼發現的呢？我們仍然從根結點出發，我們看第一個字元是1，OK,沒問題，第二個字元是0，它是一個空結點，沒問題，第三個字元是1，是一個空結點，也沒發現問題，什麼時候發現問題了呢？就是我發現現在已經到了字元串的結尾，而這個結尾停了這個結點，它不是一個葉子結點，那這就意味著101這個代碼一定是某一個代碼，在我們這個例子裡頭，也就是1011的前綴碼，所以當我們走到這裡的時候，就知道它不是一個葉子結點，所以這裡就出錯了。