?? chapter4.htm
字號:
<html>
<head>
<meta http-equiv="Content-Type"
content="text/html; charset=gb_2312-80">
<meta name="GENERATOR" content="Microsoft FrontPage Express 2.0">
<title>笨笨數(shù)據(jù)壓縮教程</title>
</head>
<body bgcolor="#FFFFFF">
<p align="right"><a href="http://www.contextfree.net/">返回斷章取義堂</a> <a href="http://www.contextfree.net/wangyg/">返回詠剛的家</a></p>
<p style="background-color:#AAEEFF;font-size:14px;color:#0000AA">《笨笨數(shù)據(jù)壓縮教程》是我在1998年因工作需要研究壓縮算法時寫的文章（算是一種工作筆記吧，其中難免有許多疏漏），1999年初隨著項目變遷，就把壓縮技術(shù)的研究暫時擱置了。從那以后，一是工作太忙，二是自己懶惰，總之是沒能把半部壓縮教程補全。非常對不住大家。——王詠剛，2003年3月</p>
<p><img src="benben.jpg"
alt="笨笨數(shù)據(jù)壓縮教程(Benben's Data Compression Guide)"
width="370" height="129"></p>
<h2>第四章 向極限挑戰(zhàn)：算術(shù)編碼</h2>
<div align="right">
<address>
<a href="chapter3.htm">第三章</a> <a href="chapter5.htm">第五章</a>
</address>
</div>
<p>我們在上一章中已經(jīng)明白，Huffman
編碼使用整數(shù)個二進制位對符號進行編碼，這種方法在許多情況下無法得到最優(yōu)的壓縮效果。假設(shè)某個字符的出現(xiàn)概率為
80%，該字符事實上只需要 -log<sub>2</sub>(0.8) = 0.322
位編碼，但 Huffman 編碼一定會為其分配一位 0
或一位 1 的編碼。可以想象，整個信息的 80%
在壓縮后都幾乎相當(dāng)于理想長度的 3
倍左右，壓縮效果可想而知。</p>
<p>難道真的能只輸出 0.322 個 0 或 0.322 個 1
嗎？是用剪刀把計算機存儲器中的二進制位剪開嗎？計算機真有這樣的特異功能嗎？慢著慢著，我們不要被表面現(xiàn)象所迷惑，其實，在這一問題上，我們只要換一換腦筋，從另一個角度……哎呀，還是想不通，怎么能是半個呢？好了，不用費心了，數(shù)學(xué)家們也不過是在十幾年前才想到了算術(shù)編碼這種神奇的方法，還是讓我們虛心地研究一下他們究竟是從哪個角度找到突破口的吧。</p>
<p><strong>輸出：一個小數(shù)</strong></p>
<p>更神奇的事情發(fā)生了，算術(shù)編碼對整條信息（無論信息有多么長），其輸出僅僅是一個數(shù)，而且是一個介于
0 和 1
之間的二進制小數(shù)。例如算術(shù)編碼對某條信息的輸出為
1010001111，那么它表示小數(shù) 0.1010001111，也即十進制數(shù)
0.64。</p>
<p>咦？怎么一會兒是表示半個二進制位，一會兒又是輸出一個小數(shù)，算術(shù)編碼怎么這么古怪呀？不要著急，我們借助下面一個簡單的例子來闡釋算術(shù)編碼的基本原理。為了表示上的清晰，我們暫時使用十進制表示算法中出現(xiàn)的小數(shù)，這絲毫不會影響算法的可行性。</p>
<p>考慮某條信息中可能出現(xiàn)的字符僅有 a b c
三種，我們要壓縮保存的信息為 bccb。</p>
<p>在沒有開始壓縮進程之前，假設(shè)我們對 a b c
三者在信息中的出現(xiàn)概率一無所知（我們采用的是自適應(yīng)模型），沒辦法，我們暫時認為三者的出現(xiàn)概率相等，也就是都為
1/3，我們將 0 - 1
區(qū)間按照概率的比例分配給三個字符，即 a 從
0.0000 到 0.3333，b 從 0.3333 到 0.6667，c 從 0.6667 到
1.0000。用圖形表示就是：</p>
<pre> +-- 1.0000
|
Pc = 1/3 |
|
+-- 0.6667
|
Pb = 1/3 |
|
+-- 0.3333
|
Pa = 1/3 |
|
+-- 0.0000</pre>
<p>現(xiàn)在我們拿到第一個字符 b，讓我們把目光投向
b 對應(yīng)的區(qū)間 0.3333 - 0.6667。這時由于多了字符 b，三個字符的概率分布變成：Pa
= 1/4，Pb = 2/4，Pc = 1/4。好，讓我們按照新的概率分布比例劃分
0.3333 - 0.6667 這一區(qū)間，劃分的結(jié)果可以用圖形表示為：</p>
<pre> +-- 0.6667
Pc = 1/4 |
+-- 0.5834
|
|
Pb = 2/4 |
|
|
+-- 0.4167
Pa = 1/4 |
+-- 0.3333</pre>
<p>接著我們拿到字符 c，我們現(xiàn)在要關(guān)注上一步中得到的
c 的區(qū)間 0.5834 - 0.6667。新添了 c
以后，三個字符的概率分布變成 Pa = 1/5，Pb = 2/5，Pc
= 2/5。我們用這個概率分布劃分區(qū)間 0.5834 - 0.6667：</p>
<pre> +-- 0.6667
|
Pc = 2/5 |
|
+-- 0.6334
|
Pb = 2/5 |
|
+-- 0.6001
Pa = 1/5 |
+-- 0.5834</pre>
<p>現(xiàn)在輸入下一個字符 c，三個字符的概率分布為：Pa
= 1/6，Pb = 2/6，Pc = 3/6。我們來劃分 c 的區(qū)間 0.6334
- 0.6667：</p>
<pre> +-- 0.6667
|
|
Pc = 3/6 |
|
|
+-- 0.6501
|
Pb = 2/6 |
|
+-- 0.6390
Pa = 1/6 |
+-- 0.6334</pre>
<p>輸入最后一個字符 b，因為是最后一個字符，不用再做進一步的劃分了，上一步中得到的
b 的區(qū)間為 0.6390 - 0.6501，好，讓我們在這個區(qū)間內(nèi)隨便選擇一個容易變成二進制的數(shù)，例如
0.64，將它變成二進制 0.1010001111，去掉前面沒有太多意義的
0 和小數(shù)點，我們可以輸出 1010001111，這就是信息被壓縮后的結(jié)果，我們完成了一次最簡單的算術(shù)壓縮過程。</p>
<p>怎么樣，不算很難吧？可如何解壓縮呢？那就更簡單了。解壓縮之前我們?nèi)匀患俣ㄈ齻€字符的概率相等，并得出上面的第一幅分布圖。解壓縮時我們面對的是二進制流
1010001111，我們先在前面加上 0
和小數(shù)點把它變成小數(shù) 0.1010001111，也就是十進制
0.64。這時我們發(fā)現(xiàn) 0.64 在分布圖中落入字符 b
的區(qū)間內(nèi)，我們立即輸出字符 b，并得出三個字符新的概率分布。類似壓縮時采用的方法，我們按照新的概率分布劃分字符
b 的區(qū)間。在新的劃分中，我們發(fā)現(xiàn) 0.64
落入了字符 c 的區(qū)間，我們可以輸出字符 c。同理，我們可以繼續(xù)輸出所有的字符，完成全部解壓縮過程（注意，為了敘述方便，我們暫時回避了如何判斷解壓縮結(jié)束的問題，實際應(yīng)用中，這個問題并不難解決）。</p>
<p><font color="#FF8000">現(xiàn)在把教程拋開，仔細回想一下，直到你理解了算術(shù)壓縮的基本原理，并產(chǎn)生了許多新的問題為止。</font></p>
<p><strong>真的能接近極限嗎？</strong></p>
<p>現(xiàn)在你一定明白了一些東西，也一定有了不少新問題，沒有關(guān)系，讓我們一個一個解決。</p>
<p>首先，我們曾反復(fù)強調(diào)，算術(shù)壓縮可以表示小數(shù)個二進制位，并由此可以接近無損壓縮的熵極限，怎么從上面的描述中沒有看出來呢？</p>
<p>算術(shù)編碼實際上采用了化零為整的思想來表示小數(shù)個二進制位，我們確實無法精確表示單個小數(shù)位字符，但我們可以將許多字符集中起來表示，僅僅允許在最后一位有些許的誤差。</p>
<p>結(jié)合上面的簡單例子考慮，我們每輸入一個符號，都對概率的分布表做一下調(diào)整，并將要輸出的小數(shù)限定在某個越來越小的區(qū)間范圍內(nèi)。對輸出區(qū)間的限定是問題的關(guān)鍵所在，例如，我們輸入第一個字符
b 時，輸出區(qū)間被限定在 0.3333 - 0.6667 之間，我們無法決定輸出值得第一位是
3、4、5 還是 6，也就是說，b 的編碼長度小于一個十進制位（注意我們用十進制講解，和二進制不完全相同），那么我們暫時不決定輸出信息的任何位，繼續(xù)輸入下面的字符。直到輸入了第三個字符
c 以后，我們的輸出區(qū)間被限定在 0.6334 - 0.6667
之間，我們終于知道輸出小數(shù)的第一位（十進制）是
6，但仍然無法知道第二位是多少，也即前三個字符的編碼長度在
1 和 2 之間。等到我們輸入了所有字符之后，我們的輸出區(qū)間為
0.6390 - 0.6501，我們始終沒有得到關(guān)于第二位的確切信息，現(xiàn)在我們明白，輸出所有的
4 個字符，我們只需要 1
點幾個十進制位，我們唯一的選擇是輸出 2
個十進制位 0.64。這樣，我們在誤差不超過 1
個十進制位的情況下相當(dāng)精確地輸出了所有信息，很好地接近了熵值（需要注明的是，為了更好地和下面的課程接軌，上面的例子采用的是
0 階自適應(yīng)模型，其結(jié)果和真正的熵值還有一定的差距）。</p>
<p><strong>小數(shù)有多長？</strong></p>
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -