<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
編碼要更短一點(diǎn)。</p>

<p>讓我們回顧一下熵的知識，使用我們在第二章學(xué)到的計(jì)算方法，上面的例子中，每個字符的熵為：</p>

<pre>Ea = - log<font size="3"><sub>2</sub></font>(16 / 40) = 1.322
Eb = - log<font size="3"><sub>2</sub></font>( 7 / 40) = 2.515
Ec = - log<font size="3"><sub>2</sub></font>( 6 / 40) = 2.737
Ed = - log<font size="3"><sub>2</sub></font>( 6 / 40) = 2.737
Ee = - 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
編碼都已經(jīng)比較接近該信息的熵值了。同時，我們也看出，無論是
Shannon-Fano 還是 Huffman，都只能用近似的整數(shù)位來表示單個符號，而不是理想的小數(shù)位。我們可以將它們做一個對比：</p>
<div align="left">

<pre>   符號      理想位數(shù)     S-F 編碼    Huffman 編碼
             ( 熵 )       需要位數(shù)    需要位數(shù)
 ----------------------------------------------------
    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
 ----------------------------------------------------
  總 計(jì)      86。601        91          88</pre>
</div>

<p align="left">這就是象 Huffman
這樣的整數(shù)位編碼方式無法達(dá)到最理想的壓縮效果的原因。</p>

<p align="left"><strong>為 Huffman
編碼選擇模型（附范式 Huffman 編碼）</strong></p>

<p align="left">最簡單，最容易被 Huffman
編碼利用的模型是“靜態(tài)統(tǒng)計(jì)模型”，也就是說在編碼前統(tǒng)計(jì)要編碼的信息中所有字符的出現(xiàn)頻率，讓后根據(jù)統(tǒng)計(jì)出的信息建立編碼樹，進(jìn)行編碼。這種模型的缺點(diǎn)是顯而易見的：首先，對數(shù)據(jù)量較大的信息，靜態(tài)統(tǒng)計(jì)要消耗大量的時間；其次，必須保存統(tǒng)計(jì)出的結(jié)果以便解碼時構(gòu)造相同的編碼樹，或者直接保存編碼樹本身，而且，對于每次靜態(tài)統(tǒng)計(jì)，都有不同的結(jié)果，必須分別予以保存，這要消耗大量的空間（這意味著壓縮效率的下降）；再次，事實(shí)上，即使不將編碼樹計(jì)算在內(nèi)，對通常含有
0 - 255 字符集的計(jì)算機(jī)文件來說，靜態(tài)統(tǒng)計(jì)模型統(tǒng)計(jì)出的頻率是字符在整個文件中的出現(xiàn)頻率，往往反映不出字符在文件中不同局部出現(xiàn)頻率的變化情況，使用這一頻率進(jìn)行壓縮，大多數(shù)情況下得不到太好壓縮效果，文件有時甚至在壓縮后反而增大了。所以，“靜態(tài)統(tǒng)計(jì)模型”一般僅作為復(fù)雜算法的某一部分出現(xiàn)，在信息的某一局部完成壓縮功能。我們很難將其用于獨(dú)立的壓縮系統(tǒng)。</p>

<p align="left">有一種有效的“靜態(tài)統(tǒng)計(jì)模型”的替代方案，如果我們要壓縮的所有信息具有某些共同的特性，也即在分布上存在著共同的特征，比如我們要壓縮的是普通的英文文本，那么，字母
a 或者字母 e 的出現(xiàn)頻率應(yīng)當(dāng)是大致穩(wěn)定的。使用語言學(xué)家事先已經(jīng)建立好的字母頻率表來進(jìn)行壓縮和解壓縮，不但不用保存多份統(tǒng)計(jì)信息，而且一般說來對該類文件有著較好的壓縮效果。這種方案除了適應(yīng)性不太強(qiáng)以外，偶爾還會有一些尷尬的時候。讀一遍下面這段話：</p>

<p align="left">If Youth，throughout all history， had had a
champion to stand up for it； to show a doubting world that a
child can think；and， possibly， do it practically； you
wouldn't constantly run across folks today who claim that &quot;a
child don't know anything.&quot; - <em>Gadsby</em> by <em>E.V.Wright,
1939.</em></p>

<p align="left">發(fā)現(xiàn)什么問題了嗎？哦，整段話中竟沒有出現(xiàn)一次英文中出現(xiàn)頻率最高的字母
e ！真讓人驚訝，但沒有辦法，事先擬定的頻率分布總有意外的時候。</p>

<p align="left">對英文或中文文本，有一種比較實(shí)用的靜態(tài)模型：不是把字符而是把英文單詞或中文詞語作為統(tǒng)計(jì)頻率和編碼的單位進(jìn)行壓縮。也就是說，每次編碼的不再是
a b c 這樣的單個符號，而是 the look flower
這樣的單詞。這種壓縮方式可以達(dá)到相當(dāng)不錯的壓縮效果，并被廣泛地用于全文檢索系統(tǒng)。</p>

<p align="left">對基于詞的編碼方式，需要解決幾個技術(shù)難點(diǎn)。首先是分詞的問題，英文單詞可以由詞間空格分隔，但中文怎么辦呢？其實(shí)，有很多中文分詞算法可以解決這個問題，本文就不再詳細(xì)介紹了。一旦我們將詞語分離出來，我們就可以對每個詞進(jìn)行頻率統(tǒng)計(jì)，然后建立
Huffman 編碼樹，輸出編碼時，一個編碼將代替一個詞語。但要注意，英文和漢語的單詞數(shù)量都在幾萬到十幾萬左右，也就是說，我們的
Huffman
編碼樹將擁有十幾萬個葉子節(jié)點(diǎn)，這對于一棵樹來說太大太大了，系統(tǒng)將無力承擔(dān)所需要的資源，這怎么辦呢？我們可以暫時拋開樹結(jié)構(gòu)，采用另一種構(gòu)造
Huffman 編碼的方式——范式 Huffman 編碼。</p>

<p align="left">范式 Huffman 編碼(Canonical Huffman Code)的基本思路是：并非只有使用二叉樹建立的前綴編碼才是
Huffman 編碼，只要符合(1)是前綴編碼(2)某一字符編碼長度和使用二叉樹建立的該字符的編碼長度相同這兩個條件的編碼都可以叫做
Huffman 編碼。考慮對下面六個單詞的編碼：</p>
<div align="left">

<pre>  符號   出現(xiàn)次數(shù)   傳統(tǒng) 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
編碼的獨(dú)特之處了嗎？你無法使用二叉樹來建立這組編碼，但這組編碼確實(shí)能起到和
Huffman 編碼相同的作用。而且，范式 Huffman
編碼具有一個明顯的特點(diǎn)：當(dāng)我們把要編碼的符號按照其頻率從小到大排列時，如果把范式
Huffman
編碼本身作為單詞的話，也呈現(xiàn)出從小到大的字典順序。</p>

<p align="left">構(gòu)造范式 Huffman 編碼的方法大致是：</p>

<p align="left">1) 統(tǒng)計(jì)每個要編碼符號的頻率。</p>

<p align="left">2)
根據(jù)這些頻率信息求出該符號在傳統(tǒng) Huffman
編碼樹中的深度（也就是表示該符號所需要的位數(shù)
-
編碼長度）。因?yàn)槲覀冴P(guān)心的僅僅是該符號在樹中的深度，我們完全沒有必要構(gòu)造二叉樹，僅用一個數(shù)組就可以模擬二叉樹的創(chuàng)建過程并得到符號的深度，具體方法這里就不詳述了。</p>

<p align="left">3) 分別統(tǒng)計(jì)從最大編碼長度 maxlength
到 1 的每個長度對應(yīng)了多少個符號。根據(jù)這一信息從
maxlength 個 0
開始以遞增順序?yàn)槊總€符號分配編碼。例如，編碼長度為
5 的符號有 4 個，長度為 3 的有 1 個，長度為 2
的有 3 個，則分配的編碼依次為： 00000 00001 00010
00011 001 01 10 11</p>

<p align="left">4)
編碼輸出壓縮信息，并保存按照頻率順序排列的符號表，然后保存每組同樣長度編碼中的最前一個編碼以及該組中的編碼個數(shù)。</p>

<p align="left">現(xiàn)在完全可以不依賴任何樹結(jié)構(gòu)進(jìn)行高速解壓縮了。而且在整個壓縮、解壓縮過程中需要的空間比傳統(tǒng)
Huffman 編碼少得多。</p>

<p align="left">最后要提到的是，Huffman
編碼可以采用自適應(yīng)模型，根據(jù)已經(jīng)編碼的符號頻率決定下一個符號的編碼。這時，我們無需為解壓縮預(yù)先保存任何信息，整個編碼是在壓縮和解壓縮過程中動態(tài)創(chuàng)建的，而且自適應(yīng)編碼由于其符號頻率是根據(jù)信息內(nèi)容的變化動態(tài)得到的，更符合符號的局部分布規(guī)律，因此在壓縮效果上比靜態(tài)模型好許多。但是，采用自適應(yīng)模型必須考慮編碼表的動態(tài)特性，即編碼表必須可以隨時更新以適應(yīng)符號頻率的變化。對于
Huffman
編碼來說，我們很難建立能夠隨時更新的二叉樹，使用范式
Huffman
編碼是個不錯的選擇，但依然存在不少技術(shù)上的難題。幸好，如果愿意的話，我們可以暫時不考慮自適應(yīng)模型的
Huffman 編碼，因?yàn)閷τ谧赃m應(yīng)模型我們還有許多更好的選擇，下面幾章將要談到的算術(shù)編碼、字典編碼等更為適合采用自適應(yīng)模型，我們將在其中深入探討自適應(yīng)模型的各種實(shí)現(xiàn)方法。</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>
    有問題嗎？有建議嗎？快給王笨笨寫信：wangyg@contextfree.net
</address>
</div><div align="right">

<address>
    <strong>章節(jié)書簽：</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>