<pre>   a - 0    b - 100    c - 101    d - 110    e - 111</pre><p>對例子中信息的編碼為：</p><pre>cabcedeacacdeddaaabaababaaabbacdebaceada</pre><pre>101 0 100 101 111 110 111 0 101 0 101 ......</pre><p>碼長共 88 位。這比使用 Shannon-Fano編碼要更短一點。</p><p>讓我們回顧一下熵的知識，使用我們在第二章學到的計算方法，上面的例子中，每個字符的熵為：</p><pre>Ea = - log<font size="3"><sub>2</sub></font>(16 / 40) = 1.322Eb = - log<font size="3"><sub>2</sub></font>( 7 / 40) = 2.515Ec = - log<font size="3"><sub>2</sub></font>( 6 / 40) = 2.737Ed = - log<font size="3"><sub>2</sub></font>( 6 / 40) = 2.737Ee = - log<font size="3"><sub>2</sub></font>( 5 / 40) = 3.000</pre><p align="left">信息的熵為：</p><div align="left"><pre>E = Ea * 16 + Eb * 7 + Ec * 6 + Ed * 6 + Ee * 5 = 86.601</pre></div><p align="left">也就是說，表示該條信息最少需要86.601 位。我們看到，Shannon-Fano 編碼和 Huffman編碼都已經比較接近該信息的熵值了。同時，我們也看出，無論是Shannon-Fano 還是 Huffman，都只能用近似的整數位來表示單個符號，而不是理想的小數位。我們可以將它們做一個對比：</p><div align="left"><pre>   符號      理想位數     S-F 編碼    Huffman 編碼             ( 熵 )       需要位數    需要位數 ----------------------------------------------------    a         1.322         2           1    b         2.515         2           3    c         2.737         2           3    d         2.737         3           3    e         3.000         3           3 ----------------------------------------------------  總 計      86。601        91          88</pre></div><p align="left">這就是象 Huffman這樣的整數位編碼方式無法達到最理想的壓縮效果的原因。</p><p align="left"><strong>為 Huffman編碼選擇模型（附范式 Huffman 編碼）</strong></p><p align="left">最簡單，最容易被 Huffman編碼利用的模型是“靜態統計模型”，也就是說在編碼前統計要編碼的信息中所有字符的出現頻率，讓后根據統計出的信息建立編碼樹，進行編碼。這種模型的缺點是顯而易見的：首先，對數據量較大的信息，靜態統計要消耗大量的時間；其次，必須保存統計出的結果以便解碼時構造相同的編碼樹，或者直接保存編碼樹本身，而且，對于每次靜態統計，都有不同的結果，必須分別予以保存，這要消耗大量的空間（這意味著壓縮效率的下降）；再次，事實上，即使不將編碼樹計算在內，對通常含有0 - 255 字符集的計算機文件來說，靜態統計模型統計出的頻率是字符在整個文件中的出現頻率，往往反映不出字符在文件中不同局部出現頻率的變化情況，使用這一頻率進行壓縮，大多數情況下得不到太好壓縮效果，文件有時甚至在壓縮后反而增大了。所以，“靜態統計模型”一般僅作為復雜算法的某一部分出現，在信息的某一局部完成壓縮功能。我們很難將其用于獨立的壓縮系統。</p><p align="left">有一種有效的“靜態統計模型”的替代方案，如果我們要壓縮的所有信息具有某些共同的特性，也即在分布上存在著共同的特征，比如我們要壓縮的是普通的英文文本，那么，字母a 或者字母 e 的出現頻率應當是大致穩定的。使用語言學家事先已經建立好的字母頻率表來進行壓縮和解壓縮，不但不用保存多份統計信息，而且一般說來對該類文件有著較好的壓縮效果。這種方案除了適應性不太強以外，偶爾還會有一些尷尬的時候。讀一遍下面這段話：</p><p align="left">If Youth，throughout all history， had had achampion to stand up for it； to show a doubting world that achild can think；and， possibly， do it practically； youwouldn't constantly run across folks today who claim that &quot;achild don't know anything.&quot; - <em>Gadsby</em> by <em>E.V.Wright,1939.</em></p><p align="left">發現什么問題了嗎？哦，整段話中竟沒有出現一次英文中出現頻率最高的字母e ！真讓人驚訝，但沒有辦法，事先擬定的頻率分布總有意外的時候。</p><p align="left">對英文或中文文本，有一種比較實用的靜態模型：不是把字符而是把英文單詞或中文詞語作為統計頻率和編碼的單位進行壓縮。也就是說，每次編碼的不再是a b c 這樣的單個符號，而是 the look flower這樣的單詞。這種壓縮方式可以達到相當不錯的壓縮效果，并被廣泛地用于全文檢索系統。</p><p align="left">對基于詞的編碼方式，需要解決幾個技術難點。首先是分詞的問題，英文單詞可以由詞間空格分隔，但中文怎么辦呢？其實，有很多中文分詞算法可以解決這個問題，本書就不再詳細介紹了。王笨笨就曾開發過一個不錯的分詞模塊，但希望通過收取一定報酬的方式提供該模塊，如有需要，請和王笨笨E-Mail 聯系。一旦我們將詞語分離出來，我們就可以對每個詞進行頻率統計，然后建立Huffman 編碼樹，輸出編碼時，一個編碼將代替一個詞語。但要注意，英文和漢語的單詞數量都在幾萬到十幾萬左右，也就是說，我們的Huffman編碼樹將擁有十幾萬個葉子節點，這對于一棵樹來說太大太大了，系統將無力承擔所需要的資源，這怎么辦呢？我們可以暫時拋開樹結構，采用另一種構造Huffman 編碼的方式——范式 Huffman 編碼。</p><p align="left">范式 Huffman 編碼(Canonical Huffman Code)的基本思路是：并非只有使用二叉樹建立的前綴編碼才是Huffman 編碼，只要符合(1)是前綴編碼(2)某一字符編碼長度和使用二叉樹建立的該字符的編碼長度相同這兩個條件的編碼都可以叫做Huffman 編碼。考慮對下面六個單詞的編碼：</p><div align="left"><pre>  符號   出現次數   傳統 Huffman 編碼    范式 Huffman 編碼------------------------------------------------------------  單詞1     10           000                 000  單詞2     11           001                 001  單詞3     12           100                 010  單詞4     13           101                 011  單詞5     22           01                  10  單詞6     23           11                  11</pre></div><p align="left">注意到范式 Huffman編碼的獨特之處了嗎？你無法使用二叉樹來建立這組編碼，但這組編碼確實能起到和Huffman 編碼相同的作用。而且，范式 Huffman編碼具有一個明顯的特點：當我們把要編碼的符號按照其頻率從小到大排列時，如果把范式Huffman編碼本身作為單詞的話，也呈現出從小到大的字典順序。</p><p align="left">構造范式 Huffman 編碼的方法大致是：</p><p align="left">1) 統計每個要編碼符號的頻率。</p><p align="left">2)根據這些頻率信息求出該符號在傳統 Huffman編碼樹中的深度（也就是表示該符號所需要的位數-編碼長度）。因為我們關心的僅僅是該符號在樹中的深度，我們完全沒有必要構造二叉樹，僅用一個數組就可以模擬二叉樹的創建過程并得到符號的深度，具體方法這里就不詳述了。</p><p align="left">3) 分別統計從最大編碼長度 maxlength到 1 的每個長度對應了多少個符號。根據這一信息從maxlength 個 0開始以遞增順序為每個符號分配編碼。例如，編碼長度為5 的符號有 4 個，長度為 3 的有 1 個，長度為 2的有 3 個，則分配的編碼依次為： 00000 00001 0001000011 001 01 10 11</p><p align="left">4)編碼輸出壓縮信息，并保存按照頻率順序排列的符號表，然后保存每組同樣長度編碼中的最前一個編碼以及該組中的編碼個數。</p><p align="left">現在完全可以不依賴任何樹結構進行高速解壓縮了。而且在整個壓縮、解壓縮過程中需要的空間比傳統Huffman 編碼少得多。</p><p align="left">最后要提到的是，Huffman編碼可以采用自適應模型，根據已經編碼的符號頻率決定下一個符號的編碼。這時，我們無需為解壓縮預先保存任何信息，整個編碼是在壓縮和解壓縮過程中動態創建的，而且自適應編碼由于其符號頻率是根據信息內容的變化動態得到的，更符合符號的局部分布規律，因此在壓縮效果上比靜態模型好許多。但是，采用自適應模型必須考慮編碼表的動態特性，即編碼表必須可以隨時更新以適應符號頻率的變化。對于Huffman編碼來說，我們很難建立能夠隨時更新的二叉樹，使用范式Huffman編碼是個不錯的選擇，但依然存在不少技術上的難題。幸好，如果愿意的話，我們可以暫時不考慮自適應模型的Huffman 編碼，因為對于自適應模型我們還有許多更好的選擇，下面幾章將要談到的算術編碼、字典編碼等更為適合采用自適應模型，我們將在其中深入探討自適應模型的各種實現方法。</p><div align="center"><center><address>    <a href="Chapter2.htm">第二章</a> <a href="Chapter4.htm">第四章</a></address></center></div><p align="center">　</p><div align="right"><address>    <a href="mailto:wangyg@contextfree.net">有問題嗎？有建議嗎？快給王笨笨寫信</a></address></div><div align="right"><address>    <strong>章節書簽：</strong><a href="default.htm">前言</a>    <a href="content.htm">目錄</a> <a href="Chapter1.htm">1</a>    <a href="Chapter2.htm">2</a> <a href="Chapter3.htm">3</a> <a    href="Chapter4.htm">4</a> <a href="Chapter5.htm">5</a> <a    href="Chapter6.htm">6</a> <a href="Chapter7.htm">7</a> <a    href="Chapter8.htm">8</a> <a href="Chapter9.htm">9</a> <a    href="Chapter10.htm">10</a> <a href="Chapter11.htm">11</a> <a    href="Chapter12.htm">12</a> </address></div></body></html>