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