壓縮算法入門

第一章數(shù)據(jù)壓縮技術(shù)簡史電腦里的數(shù)據(jù)壓縮其實類似于美眉們的瘦身運動，不外有兩大功用。第一，可以節(jié)省空間。拿瘦身美眉來說，要是八個美眉可以擠進一輛出租車里，那該有多省錢??！第二，可以減少對帶寬的占用。例如，我們都想在不到100Kbps的GPRS網(wǎng)上觀看DVD大片，這就好比瘦身美眉們總希望用一尺布裁出七件吊帶衫，前者有待于數(shù)據(jù)壓縮技術(shù)的突破性進展，后者則取決于美眉們的恒心和毅力。簡單地說，如果沒有數(shù)據(jù)壓縮技術(shù)，我們就沒法用WinRAR為Email中的附件瘦身；如果沒有數(shù)據(jù)壓縮技術(shù)，市場上的數(shù)碼錄音筆就只能記錄不到20分鐘的語音；如果沒有數(shù)據(jù)壓縮技術(shù)，從Internet上下載一部電影也許要花半年的時間......可是這一切究竟是如何實現(xiàn)的呢？數(shù)據(jù)壓縮技術(shù)又是怎樣從無到有發(fā)展起來的呢？數(shù)學(xué)游戲設(shè)計具體的壓縮算法的過程通常更像是一場數(shù)學(xué)游戲。開發(fā)者首先要尋找一種能盡量精確地統(tǒng)計或估計信息中符號出現(xiàn)概率的方法，然后還要設(shè)計一套用最短的代碼描述每個符號的編碼規(guī)則。統(tǒng)計學(xué)知識對于前一項工作相當有效，迄今為止，人們已經(jīng)陸續(xù)實現(xiàn)了靜態(tài)模型、半靜態(tài)模型、自適應(yīng)模型、Markov模型、部分匹配預(yù)測模型等概率統(tǒng)計模型。相對而言，編碼方法的發(fā)展歷程更為曲折一些。1948年，Shannon在提出信息熵理論的同時，也給出了一種簡單的編碼方法——Shannon編碼。1952年，R.M.Fano又進一步提出了Fano編碼。這些早期的編碼方法揭示了變長編碼的基本規(guī)律，也確實可以取得一定的壓縮效果，但離真正實用的壓縮算法還相去甚遠。第一個實用的編碼方法是由D.A.Huffman在1952年的論文“最小冗余度代碼的構(gòu)造方法(AMethodfortheConstructionofMinimumRedundancyCodes)"中提出的。直到今天，許多《數(shù)據(jù)結(jié)構(gòu)》教材在討論二叉樹時仍要提及這種被后人稱為Huffman編碼的方法。Huffman編碼在計算機界是如此著名，以至于連編碼的發(fā)明過程本身也成了人們津津樂道的話題。據(jù)說，1952年時，年輕的Huffman還是麻省理工學(xué)院的一名學(xué)生，他為了向老師證明自己可以不參加某門功課的期末考試，才設(shè)計了這個看似簡單，但卻影響深遠的編碼方法。Huffman編碼效率高，運算速度快，實現(xiàn)方式靈活，從20世紀60年代至今，在數(shù)據(jù)壓縮領(lǐng)域得到了廣泛的應(yīng)用。例如，早期UNIX系統(tǒng)上一個不太為現(xiàn)代人熟知的壓縮程序COMPACT實際就是Huffman0階自適應(yīng)編碼的具體實現(xiàn)。20世紀80年代初，Huffman編碼又出現(xiàn)在CP/M和DOS系統(tǒng)中，其代表程序叫SQ。今天，在許多知名的壓縮工具和壓縮算法(如WinRAR、gzip和JPEG)里，都有Huffman編碼的身影。不過，Huffman編碼所得的編碼長度只是對信息熵計算結(jié)果的一種近似，還無法真正逼近信息熵的極限。正因為如此，現(xiàn)代壓縮技術(shù)通常只將Huffman視作最終的編碼手段，而非數(shù)據(jù)壓縮算法的全部。科學(xué)家們一直沒有放棄向信息熵極限挑戰(zhàn)的理想。 1968年前后，P.Elias發(fā)展了Shannon和Fano的編碼方法，構(gòu)造出從數(shù)學(xué)角度看來更為完美的Shannon-Fano-Elias編碼。沿著這一編碼方法的思路，1976年，J.Rissanen提出了一種可以成功地逼近信息熵極限的編碼方法 算術(shù)編碼。1982年，Rissanen和G.G.Langdon一起改進了算術(shù)編碼。之后，人們又將算術(shù)編碼與J.G.Cleary和I.H.Witten于1984年提出的部分匹配預(yù)測模型(PPM)相結(jié)合，開發(fā)出了壓縮效果近乎完美的算法。今天，那些名為PPMC、PPMD或PPMZ并號稱壓縮效果天下第一的通用壓縮算法，實際上全都是這一思路的具體實現(xiàn)。對于無損壓縮而言，PPM模型與算術(shù)編碼相結(jié)合，已經(jīng)可以最大程度地逼近信息熵的極限?？雌饋?，壓縮技術(shù)的發(fā)展可以到此為止了。不幸的是，事情往往不像想象中的那樣簡單：算術(shù)編碼雖然可以獲得最短的編碼長度，但其本身的復(fù)雜性也使得算術(shù)編碼的任何具體實現(xiàn)在運行時都慢如蝸牛。即使在摩爾定律大行其道，CPU速度日新月異的今天，算術(shù)編碼程序的運行速度也很難滿足日常應(yīng)用的需求。沒辦法，如果不是后文將要提到的那兩個猶太人，我們還不知要到什么時候才能用上WinZIP這樣方便實用的壓縮工具呢。異族傳說逆向思維永遠是科學(xué)和技術(shù)領(lǐng)域里出奇制勝的法寶。就在大多數(shù)人絞盡腦汁想改進Huffman或算術(shù)編碼，以獲得一種兼顧了運行速度和壓縮效果的“完美”編碼的時候，兩個聰明的猶太人J.Ziv和A.Lempel獨辟蹊徑，完全脫離Huffman及算術(shù)編碼的設(shè)計思路，創(chuàng)造出了一系列比Huffman編碼更有效，比算術(shù)編碼更快捷的壓縮算法。我們通常用這兩個猶太人姓氏的縮寫，將這些算法統(tǒng)稱為LZ系列算法。按照時間順序，LZ系列算法的發(fā)展歷程大致是：Ziv和Lempel于1977年發(fā)表題為“順序數(shù)據(jù)壓縮的一個通用算法(AUniversalAlgorithmforSequentialDataCompression)”的論文，論文中描述的算法被后人稱為LZ77算法。1978年，二人又發(fā)表了該論文的續(xù)篇“通過可變比率編碼的獨立序列的壓縮(CompressionofIndividualSequencesviaVariableRateCoding)”，描述了后來被命名為LZ78的壓縮算法。1984年，T.A.Welch發(fā)表了名為“高性能數(shù)據(jù)壓縮技術(shù)(ATechniqueforHighPerformanceDataCompression)”的論文，描述了他在Sperry研究中心(該研究中心后來并入了Unisys公司)的研究成果，這是LZ78算法的一個變種，也就是后來非常有名的LZW算法。1990年后，T.C.Bell等人又陸續(xù)提出了許多LZ系列算法的變體或改進版本。說實話，LZ系列算法的思路并不新鮮，其中既沒有高深的理論背景，也沒有復(fù)雜的數(shù)學(xué)公式，它們只是簡單地延續(xù)了千百年來人們對字典的追崇和喜好，并用一種極為巧妙的方式將字典技術(shù)應(yīng)用于通用數(shù)據(jù)壓縮領(lǐng)域。通俗地說，當你用字典中的頁碼和行號代替文章中每個單詞的時候，你實際上已經(jīng)掌握了LZ系列算法的真諦。這種基于字典模型的思路在表面上雖然和Shannon、Huffman等人開創(chuàng)的統(tǒng)計學(xué)方法大相徑庭，但在效果上一樣可以逼近信息熵的極限。而且，可以從理論上證明，LZ系列算法在本質(zhì)上仍然符合信息熵的基本規(guī)律。LZ系列算法的優(yōu)越性很快就在數(shù)據(jù)壓縮領(lǐng)域里體現(xiàn)了出來，使用LZ系列算法的工具軟件數(shù)量呈爆炸式增長。UNIX系統(tǒng)上最先出現(xiàn)了使用LZW算法的compress程序，該程序很快成為了UNIX世界的壓縮標準。緊隨其后的是MS-DOS環(huán)境下的ARC程序，以及PKWare、PKARC等仿制品。20世紀80年代，著名的壓縮工具LHarc和ARJ則是LZ77算法的杰出代表。今天，LZ77、LZ78、LZW算法以及它們的各種變體幾乎壟斷了整個通用數(shù)據(jù)壓縮領(lǐng)域，我們熟悉的PKZIP、WinZIP、WinRAR、gzip等壓縮工具以及ZIP、GIF、PNG等文件格式都是LZ系列算法的受益者，甚至連PGP這樣的加密文件格式也選擇了LZ系列算法作為其數(shù)據(jù)壓縮的標準。沒有誰能否認兩位猶太人對數(shù)據(jù)壓縮技術(shù)的貢獻。我想強調(diào)的只是，在工程技術(shù)領(lǐng)域，片面追求理論上的完美往往只會事倍功半，如果大家能像Ziv和Lempel那樣，經(jīng)常換個角度來思考問題，沒準兒你我就能發(fā)明一種新的算法，就能在技術(shù)方展史上揚名立萬呢。音畫時尚LZ系列算法基本解決了通用數(shù)據(jù)壓縮中兼顧速度與壓縮效果的難題。但是，數(shù)據(jù)壓縮領(lǐng)域里還有另一片更為廣闊的天地等待著我們?nèi)ヌ剿?。Shannon的信息論告訴我們，對信息的先驗知識越多，我們就可以把信息壓縮得越小。換句話說，如果壓縮算法的設(shè)計目標不是任意的數(shù)據(jù)源，而是基本屬性已知的特種數(shù)據(jù)，壓縮的效果就會進一步提高。這提醒我們，在發(fā)展通用壓縮算法之余，還必須認真研究針對各種特殊數(shù)據(jù)的專用壓縮算法。比方說，在今天的數(shù)碼生活中，遍布于數(shù)碼相機、數(shù)碼錄音筆、數(shù)碼隨身聽、數(shù)碼攝像機等各種數(shù)字設(shè)備中的圖像、音頻、視頻信息，就必須經(jīng)過有效的壓縮才能在硬盤上存儲或是通過USB電纜傳輸。實際上，多媒體信息的壓縮一直是數(shù)據(jù)壓縮領(lǐng)域里的重要課題，其中的每一個分支都有可能主導(dǎo)未來的某個技術(shù)潮流，并為數(shù)碼產(chǎn)品、通信設(shè)備和應(yīng)用軟件開發(fā)商帶來無限的商機。讓我們先從圖像數(shù)據(jù)的壓縮講起。通常所說的圖像可以被分為二值圖像、灰度圖像、彩色圖像等不同的類型。每一類圖像的壓縮方法也不盡相同。傳真技術(shù)的發(fā)明和廣泛使用促進了二值圖像壓縮算法的飛速發(fā)展。CCITT（國際電報電話咨詢委員會，是國際電信聯(lián)盟ITU下屬的一個機構(gòu)）針對傳真類應(yīng)用建立了一系列圖像壓縮標準，專用于壓縮和傳遞二值圖像。實際上，對于二值圖像和非連續(xù)的灰度、彩色圖像而言，包括LZ系列算法在內(nèi)的許多通用壓縮算法都能獲得很好的壓縮效果。例如，誕生于1987年的GIF圖像文件格式使用的是LZW壓縮算法，1995年出現(xiàn)的PNG格式比GIF格式更加完善，它選擇了LZ77算法的變體zlib來壓縮圖像數(shù)據(jù)。此外，利用前面提到過的Huffman編碼、算術(shù)編碼以及PPM模型，人們事實上已經(jīng)構(gòu)造出了許多行之有效的圖像壓縮算法。但是，對于生活中更加常見的，像素值在空間上連續(xù)變化的灰度或彩色圖像（比如數(shù)碼照片），通用壓縮算法的優(yōu)勢就不那么明顯了。幸運的是，科學(xué)家們發(fā)現(xiàn)，如果在壓縮這一類圖像數(shù)據(jù)時允許改變一些不太重要的像素值，或者說允許損失一些精度（在壓縮通用數(shù)據(jù)時，我們絕不會容忍任何精度上的損失，但在壓縮和顯示一幅數(shù)碼照片時，如果一片樹林里某些樹葉的顏色稍微變深了一些，看照片的人通常是察覺不到的），我們就有可能在壓縮效果上獲得突破性的進展。這一思想在數(shù)據(jù)壓縮領(lǐng)域具有革命性的地位：通過在用戶的忍耐范圍內(nèi)損失一些精度，我們可以把圖像（也包括音頻和視頻）壓縮到原大小的十分之一、百分之一甚至千分之一，這遠遠超出了通用壓縮算法的能力極限。也許，這和生活中常說的“退一步海闊天空”的道理有異曲同工之妙吧。這種允許精度損失的壓縮也被稱為有損壓縮。在圖像壓縮領(lǐng)域，著名的JPEG標準是有損壓縮算法中的經(jīng)典。JPEG標準由靜態(tài)圖像聯(lián)合專家組（JointPhotographicExpertsGroup，JPEG）于1986年開始制定，1994年后成為國際標準。JPEG以離散余弦變換（DCT）為核心算法，通過調(diào)整質(zhì)量系數(shù)控制圖像的精度和大小。對于照片等連續(xù)變化的灰度或彩色圖像，JPEG在保證圖像質(zhì)量的前提下，一般可以將圖像壓縮到原大小的十分之一到二十分之一。如果不考慮圖像質(zhì)量，JPEG甚至可以將圖像壓縮到“無限小”。JPEG標準的最新進展是1996年開始制定，2001年正式成為國際標準的JPEG2000。與JPEG相比，JPEG2000作了大幅改進，其中最重要的是用離散小波變換（DWT）替代了JPEG標準中的離散余弦變換。在文件大小相同的情況下，JPEG2000壓縮的圖像比JPEG質(zhì)量更高，精度損失更小。作為一個新標準，JPEG2000暫時還沒有得到廣泛的應(yīng)用，不過包括數(shù)碼相機制造商在內(nèi)的許多企業(yè)都對其應(yīng)用前景表示樂觀，JPEG2000在圖像壓縮領(lǐng)域里大顯身手的那一天應(yīng)該不會特別遙遠。JPEG標準中通過損失精度來換取壓縮效果的設(shè)計思想直接影響了視頻數(shù)據(jù)的壓縮技術(shù)。CCITT于1988年制定了電視電話和會議電視的H.261建議草案。H.261的基本思路是使用類似JPEG標準的算法壓縮視頻流中的每一幀圖像，同時采用運動補償?shù)膸g預(yù)測來消除視頻流在時間維度上的冗余信息。在此基礎(chǔ)上，1993年，ISO通過了動態(tài)圖像專家組（MovingPictureExpertsGroup，MPEG）提出的MPEG-1標準。MPEG-1可以對普通質(zhì)量的視頻數(shù)據(jù)進行有效編碼。我們現(xiàn)在看到的大多數(shù)VCD影碟，就是使用MPEG-1標準來壓縮視頻數(shù)據(jù)的。為了支持更清晰的視頻圖像，特別是支持數(shù)字電視等高端應(yīng)用，ISO于1994年提出了新的MPEG-2標準（相當于CCITT的H,262標準）。MPEG-2對圖像質(zhì)量作了分級處理，可以適應(yīng)普通電視節(jié)目、會議電視、高清晰數(shù)字電視等不同質(zhì)量的視頻應(yīng)用。在我們的生活中，可以提供高清晰畫面的DVD影碟所采用的正是MPEG-2標準。Internet的發(fā)展對視頻壓縮提出了更高的要求。在內(nèi)容交互、對象編輯、隨機存取等新需求的刺激下，ISO于1999年通過了MPEG-4標準（相當于CCITT的H,263和H.263+標準）。MPEG-4標準擁有更高的壓縮比率，支持并發(fā)數(shù)據(jù)流的編碼、基于內(nèi)容的交互操作、增強的時間域隨機存取、容錯、基于內(nèi)容的尺度可變性等先進特性。Internet上新興的DivX和XviD文件格式就是采用MPEG-4標準來壓縮視頻數(shù)據(jù)的，它們可以用更小的存儲空間或通信帶寬提供與DVD不相上下的高清晰視頻，這使我們在Internet上發(fā)布或下載數(shù)字電影的夢想成為了現(xiàn)實。就像視頻壓縮和電視產(chǎn)業(yè)的發(fā)展密不可分一樣，音頻數(shù)據(jù)的壓縮技術(shù)最早也是由無線電廣播、語音通信等領(lǐng)域里的技術(shù)人員發(fā)展起來的。這其中又以語音編碼和壓縮技術(shù)的研究最為活躍。自從1939年H.Dudley發(fā)明聲碼器以來，人們陸續(xù)發(fā)明了脈沖編碼調(diào)制（PCM）、線性預(yù)測（LPC）、矢量量化（VQ）、自適應(yīng)變換編碼（ATC）、子帶編碼（SBC）等語音分析與處理技術(shù)。這些語音技術(shù)在采集語音特征，獲取數(shù)字信號的同時，通常也可以起到降低信息冗余度的作用。像圖像壓縮領(lǐng)域里的JPEG一樣，為獲得更高的編碼效率，大多數(shù)語音編碼技術(shù)都允許一定程度的精度損失。而且，為了更好地用二進制數(shù)據(jù)存儲或傳送語音信號，這些語音編碼技術(shù)在將語音信號轉(zhuǎn)換為數(shù)字信息之后又總會用Huffman編碼、算術(shù)編碼等通用壓縮算法進一步減少數(shù)據(jù)流中的冗余信息。對于電腦和數(shù)字電器(如數(shù)碼錄音筆、數(shù)碼隨身聽)中存儲的普通音頻信息，我們最常使用的壓縮方法主要是MPEG系列中的音頻壓縮標準。例如，MPEG-1標準提供了LayerI、LayerII和LayerIII共三種可選的音頻壓縮標準，MPEG-2又進一步引入了AAC(AdvancedAudioCoding)音頻壓縮標準，MPEG-4標準中的音頻部分則同時支持合成聲音編碼和自然聲音編碼等不同類型的應(yīng)用。在這許多音頻壓縮標準中，聲名最為顯赫的恐怕要數(shù)MPEG-1LayerIII，也就是我們常說的MP3音頻壓縮標準了。從MP3播放器到MP3手機，從硬盤上堆積如山的MP3文件到Internet上版權(quán)糾紛不斷的MP3下載，MP3早已超出了數(shù)據(jù)壓縮技術(shù)的范疇，而成了一種時尚文化的象征了。很顯然，在多媒體信息日益成為主流信息形態(tài)的數(shù)字化時代里，數(shù)據(jù)壓縮技術(shù)特別是專用于圖像、音頻、視頻的數(shù)據(jù)壓縮技術(shù)還有相當大的發(fā)展空間一一畢竟，人們對信息數(shù)量和信息質(zhì)量的追求是永無止境的?；氐轿磥韽男畔㈧氐剿阈g(shù)編碼，從猶太人到WinRAR，從JPEG到MP3，數(shù)據(jù)壓縮技術(shù)的發(fā)展史就像是一個寫滿了“創(chuàng)新”、“挑戰(zhàn)”、“突破”和“變革”的羊皮卷軸。也許，我們在這里不厭其煩地羅列年代、人物、標準和文獻，其目的只是要告訴大家，前人的成果只不過是后人有望超越的目標而已，誰知道在未來的幾年里，還會出現(xiàn)幾個Shannon，幾個Huffman呢？談到未來，我們還可以補充一些與數(shù)據(jù)壓縮技術(shù)的發(fā)展趨勢有關(guān)的話題。1994年，M.Burrows和D.J.Wheeler共同提出了一種全新的通用數(shù)據(jù)壓縮算法。這種算法的核心思想是對字符串輪轉(zhuǎn)后得到的字符矩陣進行排序和變換，類似的變換算法被稱為Burrows-Wheeler變換，簡稱BWT。與Ziv和Lempel另辟蹊徑的做法如出一轍，Burrows和Wheeler設(shè)計的BWT算法與以往所有通用壓縮算法的設(shè)計思路都迥然不同。如今，BWT算法在開放源碼的壓縮工具bzip中獲得了巨大的成功，bzip對于文本文件的壓縮效果要遠好于使用LZ系列算法的工具軟件。這至少可以表明，即便在日趨成熟的通用數(shù)據(jù)壓縮領(lǐng)域，只要能在思路和技術(shù)上不斷創(chuàng)新，我們?nèi)匀豢梢哉业叫碌耐黄瓶?。分形壓縮技術(shù)是圖像壓縮領(lǐng)域近幾年來的一個熱點。這一技術(shù)起源于B.Mandelbrot于1977年創(chuàng)建的分形幾何學(xué)。M.Barnsley在20世紀80年代后期為分形壓縮奠定了理論基礎(chǔ)。從20世紀90年代開始，A.Jacquin等人陸續(xù)提出了許多實驗性的分形壓縮算法。今天，很多人相信，分形壓縮是圖像壓縮領(lǐng)域里最有潛力的一種技術(shù)體系，但也有很多人對此不屑一顧。無論其前景如何，分形壓縮技術(shù)的研究與發(fā)展都提示我們，在經(jīng)過了幾十年的高速發(fā)展之后，也許，我們需要一種新的理論，或是幾種更有效的數(shù)學(xué)模型，以支撐和推動數(shù)據(jù)壓縮技術(shù)繼續(xù)向前躍進。人工智能是另一個可能對數(shù)據(jù)壓縮的未來產(chǎn)生重大影響的關(guān)鍵詞。既然Shannon認為，信息能否被壓縮以及能在多大程度上被壓縮與信息的不確定性有直接關(guān)系，假設(shè)人工智能技術(shù)在某一天成熟起來，假設(shè)計算機可以像人一樣根據(jù)已知的少量上下文猜測后續(xù)的信息，那么，將信息壓縮到原大小的萬分之一乃至十萬分之一，恐怕就不再是天方夜譚了?；仡櫄v史之后，人們總喜歡暢想一下未來。但未來終究是未來，如果僅憑你我?guī)拙湓捑涂梢岳砬逦磥淼募夹g(shù)發(fā)展趨勢，那技術(shù)創(chuàng)新的工作豈不就索然無味了嗎？依我說，未來并不重要，重要的是，趕快到Internet上下載幾部大片，然后躺在沙發(fā)里，好好享受一下數(shù)據(jù)壓縮為我們帶來的無限快樂吧。第二章技術(shù)準備:概率、模型和編碼第二章技術(shù)準備:概率、模型和編碼什么是熵數(shù)據(jù)壓縮不僅起源于40年代由ClaudeShannon首創(chuàng)的信息論，而且其基本原理即信息究竟能被壓縮到多小，至今依然遵循信息論中的一條定理，這條定理借用了熱力學(xué)中的名詞“熵”(Entropy)來表示一條信息中真正需要編碼的信息量：考慮用0和1組成的二進制數(shù)碼為含有n個符號的某條信息編碼，假設(shè)符號Fn在整條信息中重復(fù)出現(xiàn)的概率為Pn，則該符號的熵也即表示該符號所需的位數(shù)位為：En=-log2(Pn)整條信息的熵也即表示整條信息所需的位數(shù)為：E=^En舉個例子，對下面這條只出現(xiàn)了abc三個字符的字符串：aabbaccbaa字符串長度為10，字符abc分別出現(xiàn)了532次，則abc在信息中出現(xiàn)的概率分別為0.50.30.2，他們的熵分別為：Ea=-log2(0.5)=1Eb=-log2(0.3)=1.737Ec=-log2(0.2)=2.322整條信息的熵也即表達整個字符串需要的位數(shù)為：E=Ea*5+Eb*3+Ec*2=14.855位回想一下如果用計算機中常用的ASCII編碼，表示上面的字符串我們需要整整80位呢！現(xiàn)在知道信息為什么能被壓縮而不丟失原有的信息內(nèi)容了吧。簡單地講，用較少的位數(shù)表示較頻繁出現(xiàn)的符號，這就是數(shù)據(jù)壓縮的基本準則。細心的讀者馬上會想到，我們該怎樣用01這樣的二進制數(shù)碼表示零點幾個二進制位呢？確實很困難，但不是沒有辦法。一旦我們找到了準確表示零點幾個二進制位的方法，我們就有權(quán)利向無損壓縮的極限挑戰(zhàn)了。不要著急，看到第四章就明白了。模型從上面的描述，我們明白，要壓縮一條信息，首先要分析清楚信息中每個符號出現(xiàn)的概率。不同的壓縮程序通過不同的方法確定符號的出現(xiàn)概率，對符號的概率計算得越準確，也就越容易得到好的壓縮效果。在壓縮程序中，用來處理輸入信息，計算符號的概率并決定輸出哪個或哪些代碼的模塊叫做模型。難道對信息中字符的出現(xiàn)概率這么難以估計以至于有各種不同的壓縮模型嗎？對上面的字符串我們不是很容易就知道每個字符的概率了嗎？是的是的，不過上面的字符串僅有10個字符長呀，那只是例子而已。考慮我們現(xiàn)實中要壓縮的文件，大多數(shù)可是有幾十K甚至幾百K長，幾M字節(jié)的文件不是也屢見不鮮嗎？是的，我們可以預(yù)先掃描文件中的所有字符，統(tǒng)計出每個字符出現(xiàn)的概率，這種方法在壓縮術(shù)語里叫做“靜態(tài)統(tǒng)計模型”。但是，不同的文件中，字符有不同的分布概率，我們要么先花上大量的時間統(tǒng)計我們要壓縮的所有文件中的字符概率，要么為每一個單獨的文件保存一份概率表以備解壓縮時需要。糟糕的是，不但掃描文件要消耗大量時間，而且保存一份概率表也使壓縮后的文件增大了不少。所以，在實際應(yīng)用中，“靜態(tài)統(tǒng)計模型”應(yīng)用的很少。真正的壓縮程序中使用的大多是一種叫“自適應(yīng)模型”的東西。自適應(yīng)模型可以說是一臺具有學(xué)習功能的自動機。他在信息被輸入之前對信息內(nèi)容一無所知并假定每個字符的出現(xiàn)概率均等，隨著字符不斷被輸入和編碼，他統(tǒng)計并紀錄已經(jīng)出現(xiàn)過的字符的概率并將這些概率應(yīng)用于對后續(xù)字符的編碼。也就是說，自適應(yīng)模型在壓縮開始時壓縮效果并不理想，但隨著壓縮的進行，他會越來越接近字符概率的準確值，并達到理想的壓縮效果。自適應(yīng)模型還可以適應(yīng)輸入信息中字符分布的突然變化，可以適應(yīng)不同的文件中的字符分布而不需要保存概率表。上面提到的模型可以統(tǒng)稱為“統(tǒng)計模型”，因為他們都是基于對每個字符出現(xiàn)次數(shù)的統(tǒng)計得到字符概率的。另一大類模型叫做'字典模型”。實際上，當我們在生活中提到'工行”這個詞的時候，我們都知道其意思是指“中國工商銀行”，類似的例子還有不少，但共同的前提是我們心中都有一本約定俗成的縮寫字典。字典模型也是如此，他并不直接計算字符出現(xiàn)的概率，而是使用一本字典，隨著輸入信息的讀入，模型找出輸入信息在字典中匹配的最長的字符串，然后輸出該字符串在字典中的索引信息。匹配越長，壓縮效果越好。事實上，字典模型本質(zhì)上仍然是基于對字符概率的計算的，只不過，字典模型使用整個字符串的匹配代替了對某一字符重復(fù)次數(shù)的統(tǒng)計。可以證明，字典模型得到的壓縮效果仍然無法突破熵的極限。當然，對通用的壓縮程序來說，保存一本大字典所需的空間仍然是無法讓人忍受的，況且，任何一本預(yù)先定義的字典都無法適應(yīng)不同文件中數(shù)據(jù)的變化情況。對了，字典模型也有相應(yīng)的“自適應(yīng)”方案。我們可以隨著信息的不斷輸入，從已經(jīng)輸入的信息中建立合適的字典，并不斷更新這本字典，以適應(yīng)數(shù)據(jù)的不斷變化。讓我們從另一個角度理解一下自適應(yīng)模型。CluadeShannon曾試圖通過一個“聚會游戲"(partygame)來測定英語的真實信息容量。他每次向聽眾公布一條被他隱藏起一個字符的消息，讓聽眾來猜下一個字符是什么，一次猜一個，直到猜對為止。然后，Shannon使用猜測次數(shù)來確定整個信息的熵。在這個實驗中，一種根據(jù)前面出現(xiàn)過的字符估計下一個字符概率的模型就存在于聽眾的頭腦中，比計算機中使用的自適應(yīng)模型更為高級的是，聽眾除了根據(jù)字符出現(xiàn)過的次數(shù)外，還可以根據(jù)他們對語言的經(jīng)驗進行猜測。編碼通過模型，我們已經(jīng)確定了對某一個符號該用多少位二進制數(shù)進行編碼?，F(xiàn)在的問題是，如何設(shè)計一種編碼方案，使其盡量精確地用模型計算出來的位數(shù)表示某個符號。最先被考慮的問題是，如果對a用3個二進制位就可以表示，而對b用4個二進制位就可以表示，那么，在解碼時，面對一連串的二進制流，我怎么知道哪三個位是a，哪四個位是b呢？所以，必須設(shè)計出一種編碼方式，使得解碼程序可以方便地分離每個字符的編碼部分。于是有了一種叫“前綴編碼”的技術(shù)。該技術(shù)的主導(dǎo)思想是，任何一個字符的編碼，都不是另一個字符編碼的前綴。反過來說就是，任何一個字符的編碼，都不是由另一個字符的編碼加上若干位0或1組成?？匆幌虑熬Y編碼的一個最簡單的例子：符號編碼TOC\o"1-5"\h\zA 0B 10C 110D 1110E 11110有了上面的碼表，你一定可以輕松地從下面這串二進制流中分辨出真正的信息內(nèi)容了：1110010101110110111100010-DABBDCEAAB下一個問題是：象上面這樣的前綴編碼只能表示整數(shù)位的符號，對幾點幾位的符號只能用近似的整數(shù)位輸出，那么怎樣輸出小數(shù)位數(shù)呢？科學(xué)家們用算術(shù)編碼解決了這個問題，我們將在第四章對算術(shù)編碼作詳細的討論?？偨Y(jié)一下不同的模型使用不同的方法計算字符的出現(xiàn)概率，由此概率可以得出字符的熵；然后使用不同的編碼方法，盡量接近我們期望得到的熵值。所以，壓縮效果的好壞一方面取決于模型能否準確地得到字符概率，另一方面也取決于編碼方法能否準確地用期望的位數(shù)輸出字符代碼。換句話說，壓縮=模型+編碼。如下圖所示： 符號 概率 代碼 I輸入I >1模型I >1編碼I >1輸出I第三章奇妙的二叉樹：Huffman的貢獻提起Huffman這個名字，程序員們至少會聯(lián)想到二叉樹和二進制編碼。的確，我們總以Huffman編碼來概括D.A.Huffman個人對計算機領(lǐng)域特別是數(shù)據(jù)壓縮領(lǐng)域的杰出貢獻。我們知道，壓縮=模型+編碼，作為一種壓縮方法，我們必須全面考慮其模型和編碼兩個模塊的功效；但同時，模型和編碼兩個模塊又相互具有獨立性。舉例來說，一個使用Huffman編碼方法的程序，完全可以采用不同的模型來統(tǒng)計字符在信息中出現(xiàn)的概率。因此，我們這一章將首先圍繞Huffman先生最為重要的貢獻 Huffman編碼展開討論，隨后，我們再具體介紹可以和Huffman聯(lián)合使用的概率模型。為什么是二叉樹為什么壓縮領(lǐng)域中的編碼方法總和二叉樹聯(lián)系在一起呢？原因非常簡單，回憶一下我們介紹過的“前綴編碼”：為了使用不固定的碼長表示單個字符，編碼必須符合“前綴編碼”的要求，即較短的編碼決不能是較長編碼的前綴。要構(gòu)造符合這一要求的二進制編碼體系，二叉樹是最理想的選擇?？疾煜旅孢@棵二叉樹：根(root)TOC\o"1-5"\h\z0 | 1+ + +\o"CurrentDocument"0 | 1 0| 1\o"CurrentDocument"+ 1 + + 1 +\o"CurrentDocument"I I I I\o"CurrentDocument"a | d e0 | 1+ 1 +| |b c要編碼的字符總是出現(xiàn)在樹葉上，假定從根向樹葉行走的過程中，左轉(zhuǎn)為0，右轉(zhuǎn)為1，則一個字符的編碼就是從根走到該字符所在樹葉的路徑。正因為字符只能出現(xiàn)在樹葉上，任何一個字符的路徑都不會是另一字符路徑的前綴路徑，符合要求的前綴編碼也就構(gòu)造成功了：a-00b-010c-011d-10e-11Shannon-Fano編碼進入Huffman先生構(gòu)造的神奇二叉樹之前，我們先來看一下它的前身，由 ClaudeShannon和R.M.Fano兩人提出的Shannon-Fano編碼。討論之前，我們假定要編碼字符的出現(xiàn)概率已經(jīng)由某一模型統(tǒng)計出來，例如，對下面這

串出現(xiàn)了五種字符的信息（40個字符長）:cabcedeacacdeddaaabaababaaabbacdebaceada五種字符的出現(xiàn)次數(shù)分別：a-16,b-7,c-6,d-6,e-5。Shannon-Fano編碼的核心仍然是構(gòu)造二叉樹，構(gòu)造的方式非常簡單：1） 將給定符號按照其頻率從大到小排序。對上面的例子，應(yīng)該得到：a-16b-7c-6d-6e-52） 將序列分成上下兩部分，使得上部頻率總和盡可能接近下部頻率總和。我們有:a-16b-73）我們把第二步中劃分出的上部作為二叉樹的左子樹，記0，下部作為二叉樹的右子樹，記1。4）分別對左右子樹重復(fù)23兩步，直到所有的符號都成為二叉樹的樹葉為止?，F(xiàn)在我們有如下的二叉樹：0+ 0I10+ 0I1+ + +\o"CurrentDocument"I Ia bI1TOC\o"1-5"\h\z+ +0I1+---+ +Ic0\o"CurrentDocument"+ + +\o"CurrentDocument"I Id e于是我們得到了此信息的編碼表:a-00b-01c-10d-110e-111可以將例子中的信息編碼為：cabcedeacacdeddaaabaababaaabbacdebaceada1000011011111011100100010 碼長共91位?？紤]用ASCII碼表示上述信息需要8*40=240位，我們確實實現(xiàn)了數(shù)據(jù)壓縮。Huffman編碼Huffman編碼構(gòu)造二叉樹的方法和Shannon-Fano正好相反，不是自上而下，而是從樹葉到樹根生成二叉樹?，F(xiàn)在，我們?nèi)匀皇褂蒙厦娴睦觼韺W(xué)習Huffman編碼方法。將各個符號及其出現(xiàn)頻率分別作為不同的小二叉樹(目前每棵樹只有根節(jié)點)。a(16) b(7) c(6) d(6) e(5)在1中得到的樹林里找出頻率值最小的兩棵樹，將他們分別作為左、右子樹連成一棵大一些的二叉樹，該二叉樹的頻率值為兩棵子樹頻率值之和。對上面的例子，我們得到一個新的樹林：|(11)a(16) b(7) c(6) +---+---+IIde對上面得到的樹林重復(fù)2的做法，直到所有符號都連入樹中為止。這一步完成后，我們有這樣的二叉樹：根(root)0 | 1+++|||a0+ 10+---I---+---1---+1I-+-0+ 1---+I---+---1 +1IbIcIdIe由此，我們可以建立和Shannon-Fano編碼略微不同的編碼表：a-0b-100c-101d-110e-111對例子中信息的編碼為：cabcedeacacdeddaaabaababaaabbacdebaceada101010010111111011101010101 碼長共88位。這比使用Shannon-Fano編碼要更短一點。讓我們回顧一下熵的知識，使用我們在第二章學(xué)到的計算方法，上面的例子中，每個字符的熵為：Ea=-log(16/40)=1.322TOC\o"1-5"\h\z\o"CurrentDocument"Eb= - log：( 7 / 40) = 2.515\o"CurrentDocument"Ec= - log：( 6 / 40) = 2.737\o"CurrentDocument"Ed= - log：( 6 / 40) = 2.737\o"CurrentDocument"Ee= - log：( 5 / 40) = 3.000信息的熵為：E=Ea*16+Eb*7+Ec*6+Ed*6+Ee*5=86.601也就是說，表示該條信息最少需要86.601位。我們看到，Shannon-Fano編碼和Huffman編碼都已經(jīng)比較接近該信息的熵值了。同時，我們也看出，無論是Shannon-Fano還是Huffman，都只能用近似的整數(shù)位來表示單個符號，而不是理想的小數(shù)位。我們可以將它們做一個對比：符號理想位數(shù)(熵)S-F編碼需要位數(shù)Huffman編碼需要位數(shù) a1.3222 1b2.51523c2.73723d2.73733e3.00033 總計86.60191 88這就是象Huffman這樣的整數(shù)位編碼方式無法達到最理想的壓縮效果的原因。為Huffman編碼選擇模型(附范式Huffman編碼)最簡單，最容易被Huffman編碼利用的模型是“靜態(tài)統(tǒng)計模型”，也就是說在編碼前統(tǒng)計要編碼的信息中所有字符的出現(xiàn)頻率，讓后根據(jù)統(tǒng)計出的信息建立編碼樹，進行編碼。這種模型的缺點是顯而易見的：首先，對數(shù)據(jù)量較大的信息，靜態(tài)統(tǒng)計要消耗大量的時間；其次，必須保存統(tǒng)計出的結(jié)果以便解碼時構(gòu)造相同的編碼樹，或者直接保存編碼樹本身，而且，對于每次靜態(tài)統(tǒng)計，都有不同的結(jié)果，必須分別予以保存，這要消耗大量的空間(這意味著壓縮效率的下降)；再次，事實上，即使不將編碼樹計算在內(nèi)，對通常含有0-255字符集的計算機文件來說，靜態(tài)統(tǒng)計模型統(tǒng)計出的頻率是字符在整個文件中的出現(xiàn)頻率，往往反映不出字符在文件中不同局部出現(xiàn)頻率的變化情況，使用這一頻率進行壓縮，大多數(shù)情況下得不到太好壓縮效果，文件有時甚至在壓縮后反而增大了。所以，“靜態(tài)統(tǒng)計模型”一般僅作為復(fù)雜算法的某一部分出現(xiàn)，在信息的某一局部完成壓縮功能。我們很難將其用于獨立的壓縮系統(tǒng)。有一種有效的“靜態(tài)統(tǒng)計模型”的替代方案，如果我們要壓縮的所有信息具有某些共同的特性，也即在分布上存在著共同的特征，比如我們要壓縮的是普通的英文文本，那么，字母a或者字母e的出現(xiàn)頻率應(yīng)當是大致穩(wěn)定的。使用語言學(xué)家事先已經(jīng)建立好的字母頻率表來進行壓縮和解壓縮，不但不用保存多份統(tǒng)計信息，而且一般說來對該類文件有著較好的壓縮效果。這種方案除了適應(yīng)性不太強以外，偶爾還會有一些尷尬的時候。讀一遍下面這段話：IfYouth,throughoutallhistory，hadhadachampiontostandupforit；toshowadoubtingworldthatachildcanthink；and，possibly，doitpractically；youwouldn'tconstantlyrunacrossfolkstodaywhoclaimthat"achilddon'tknowanything."-GadsbybyE.V.Wright,1939.發(fā)現(xiàn)什么問題了嗎？哦，整段話中竟沒有出現(xiàn)一次英文中出現(xiàn)頻率最高的字母e！真讓人驚訝，但沒有辦法，事先擬定的頻率分布總有意外的時候。對英文或中文文本，有一種比較實用的靜態(tài)模型：不是把字符而是把英文單詞或中文詞語作為統(tǒng)計頻率和編碼的單位進行壓縮。也就是說，每次編碼的不再是abc這樣的單個符號，而是thelookflower這樣的單詞。這種壓縮方式可以達到相當不錯的壓縮效果，并被廣泛地用于全文檢索系統(tǒng)。對基于詞的編碼方式，需要解決幾個技術(shù)難點。首先是分詞的問題，英文單詞可以由詞間空格分隔，但中文怎么辦呢？其實，有很多中文分詞算法可以解決這個問題，本文就不再詳細介紹了。一旦我們將詞語分離出來，我們就可以對每個詞進行頻率統(tǒng)計，然后建立Huffman編碼樹，輸出編碼時，一個編碼將代替一個詞語。但要注意，英文和漢語的單詞數(shù)量都在幾萬到十幾萬左右，也就是說，我們的Huffman編碼樹將擁有十幾萬個葉子節(jié)點，這對于一棵樹來說太大太大了，系統(tǒng)將無力承擔所需要的資源，這怎么辦呢？我們可以暫時拋開樹結(jié)構(gòu)，采用另一種構(gòu)造Huffman編碼的方式 范式Huffman編碼。范式Huffman編碼(CanonicalHuffmanCode)的基本思路是：并非只有使用二叉樹建立的前綴編碼才是Huffman編碼，只要符合(1)是前綴編碼(2)某一字符編碼長度和使用二叉樹建立的該字符的編碼長度相同這兩個條件的編碼都可以叫做Huffman編碼?？紤]對下面六個單詞的編碼：符號出現(xiàn)次數(shù)傳統(tǒng)Huffman編碼范式Huffman編碼單詞110000000單詞211001001單詞312100010單詞413101011單詞5220110單詞6231111注意到范式Huffman編碼的獨特之處了嗎？你無法使用二叉樹來建立這組編碼，但這組編碼確實能起到和Huffman編碼相同的作用。而且，范式Huffman編碼具有一個明顯的特點：當我們把要編碼的符號按照其頻率從小到大排列時，如果把范式Huffman編碼本身作為單詞的話，也呈現(xiàn)出從小到大的字典順序。構(gòu)造范式Huffman編碼的方法大致是：1） 統(tǒng)計每個要編碼符號的頻率。2） 根據(jù)這些頻率信息求出該符號在傳統(tǒng)Huffman編碼樹中的深度（也就是表示該符號所需要的位數(shù)-編碼長度）。因為我們關(guān)心的僅僅是該符號在樹中的深度，我們完全沒有必要構(gòu)造二叉樹，僅用一個數(shù)組就可以模擬二叉樹的創(chuàng)建過程并得到符號的深度，具體方法這里就不詳述了。3） 分別統(tǒng)計從最大編碼長度maxlength到1的每個長度對應(yīng)了多少個符號。根據(jù)這一信息從maxlength個0開始以遞增順序為每個符號分配編碼。例如，編碼長度為5的符號有4個，長度為3的有1個，長度為2的有3個，則分配的編碼依次為：000000000100010000110010110114） 編碼輸出壓縮信息，并保存按照頻率順序排列的符號表，然后保存每組同樣長度編碼中的最前一個編碼以及該組中的編碼個數(shù)?，F(xiàn)在完全可以不依賴任何樹結(jié)構(gòu)進行高速解壓縮了。而且在整個壓縮、解壓縮過程中需要的空間比傳統(tǒng)Huffman編碼少得多。最后要提到的是，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īng)模型我們還有許多更好的選擇，下面幾章將要談到的算術(shù)編碼、字典編碼等更為適合采用自適應(yīng)模型，我們將在其中深入探討自適應(yīng)模型的各種實現(xiàn)方法。

第四章向極限挑戰(zhàn):算術(shù)編碼第四章向極限挑戰(zhàn):算術(shù)編碼我們在上一章中已經(jīng)明白，Huffman編碼使用整數(shù)個二進制位對符號進行編碼，這種方法在許多情況下無法得到最優(yōu)的壓縮效果。假設(shè)某個字符的出現(xiàn)概率為80%，該字符事實上只需要-log2（0.8）=0.322位編碼，但Huffman編碼一定會為其分配一位0或一位1的編碼?？梢韵胂?，整個信息的80%在壓縮后都幾乎相當于理想長度的3倍左右，壓縮效果可想而知。難道真的能只輸出0.322個0或0.322個1嗎？是用剪刀把計算機存儲器中的二進制位剪開嗎？計算機真有這樣的特異功能嗎？慢著慢著，我們不要被表面現(xiàn)象所迷惑，其實，在這一問題上，我們只要換一換腦筋，從另一個角度??…哎呀，還是想不通，怎么能是半個呢？好了，不用費心了，數(shù)學(xué)家們也不過是在十幾年前才想到了算術(shù)編碼這種神奇的方法，還是讓我們虛心地研究一下他們究竟是從哪個角度找到突破口的吧。輸出：一個小數(shù)更神奇的事情發(fā)生了，算術(shù)編碼對整條信息（無論信息有多么長），其輸出僅僅是一個數(shù)，而且是一個介于0和1之間的二進制小數(shù)。例如算術(shù)編碼對某條信息的輸出為1010001111，那么它表示小數(shù)0.1010001111，也即十進制數(shù)0.64。咦？怎么一會兒是表示半個二進制位，一會兒又是輸出一個小數(shù)，算術(shù)編碼怎么這么古怪呀？不要著急，我們借助下面一個簡單的例子來闡釋算術(shù)編碼的基本原理。為了表示上的清晰，我們暫時使用十進制表示算法中出現(xiàn)的小數(shù)，這絲毫不會影響算法的可行性?？紤]某條信息中可能出現(xiàn)的字符僅有abc三種，我們要壓縮保存的信息為bccb。在沒有開始壓縮進程之前，假設(shè)我們對abc三者在信息中的出現(xiàn)概率一無所知（我們采用的是自適應(yīng)模型），沒辦法，我們暫時認為三者的出現(xiàn)概率相等，也就是都為1/3,我們將0-1區(qū)間按照概率的比例分配給三個字符，即a從0.0000到0.3333,b從0.3333到0.6667，c從0.6667至U1.0000。用圖形表示就是：+--1.0000IPc=1/3 |I+--0.6667IPb=1/3 |I+--0.3333IPa=1/3II+--0.0000現(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é)果可以用圖形表示為：+--0.6667TOC\o"1-5"\h\z\o"CurrentDocument"Pc=1/4 |+--0.5834IIPb=2/4 |II+--0.4167\o"CurrentDocument"Pa=1/4 |+--0.3333接著我們拿到字符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：+--0.6667IPc=2/5II+--0.6334IPb=2/5II+--0.6001Pa=1/5I+--0.5834現(xiàn)在輸入下一個字符c，三個字符的概率分布為：Pa=1/6,Pb=2/6,Pc=3/6。我們來劃分c的區(qū)間0.6334-0.6667：+--0.6667IIPc=3/6III+--0.6501IPb=2/6II+--0.6390Pa=1/6 |Pa=+--0.6334輸入最后一個字符b,因為是最后一個字符，不用再做進一步的劃分了，上一步中得到的b的區(qū)間為0.6390-0.6501，好，讓我們在這個區(qū)間內(nèi)隨便選擇一個容易變成二進制的數(shù)，例如0.64，將它變成二進制0.1010001111，去掉前面沒有太多意義的0和小數(shù)點，我們可以輸出1010001111，這就是信息被壓縮后的結(jié)果，我們完成了一次最簡單的算術(shù)壓縮過程。怎么樣，不算很難吧？可如何解壓縮呢？那就更簡單了。解壓縮之前我們?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)用中，這個問題并不難解決）?，F(xiàn)在把教程拋開，仔細回想一下，直到你理解了算術(shù)壓縮的基本原理，并產(chǎn)生了許多新的問題為止。真的能接近極限嗎？現(xiàn)在你一定明白了一些東西，也一定有了不少新問題，沒有關(guān)系，讓我們一個一個解決。首先，我們曾反復(fù)強調(diào)，算術(shù)壓縮可以表示小數(shù)個二進制位，并由此可以接近無損壓縮的熵極限，怎么從上面的描述中沒有看出來呢？算術(shù)編碼實際上采用了化零為整的思想來表示小數(shù)個二進制位，我們確實無法精確表示單個小數(shù)位字符，但我們可以將許多字符集中起來表示，僅僅允許在最后一位有些許的誤差。結(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個十進制位的情況下相當精確地輸出了所有信息，很好地接近了熵值（需要注明的是，為了更好地和下面的課程接軌，上面的例子采用的是0階自適應(yīng)模型，其結(jié)果和真正的熵值還有一定的差距）。小數(shù)有多長？你一定已經(jīng)想到，如果信息內(nèi)容特別豐富，我們要輸出的小數(shù)將會很長很長，我們該如何在內(nèi)存中表示如此長的小數(shù)呢？其實，沒有任何必要在內(nèi)存中存儲要輸出的整個小數(shù)。我們從上面的例子可以知道，在編碼的進行中，我們會不斷地得到有關(guān)要輸出小數(shù)的各種信息。具體地講，當我們將區(qū)間限定在0.6390-0.6501之間時，我們已經(jīng)知道要輸出的小數(shù)第一位（十進制）一定是6,那么我們完全可以將6從內(nèi)存中拿掉，接著在區(qū)間0.390-0.501之間繼續(xù)我們的壓縮進程。內(nèi)存中始終不會有非常長的小數(shù)存在。使用二進制時也是一樣的，我們會隨著壓縮的進行不斷決定下一個要輸出的二進制位是0還是1，然后輸出該位并減小內(nèi)存中小數(shù)的長度。靜態(tài)模型如何實現(xiàn)？我們知道上面的簡單例子采用的是自適應(yīng)模型，那么如何實現(xiàn)靜態(tài)模型呢？其實很簡單。對信息bccb我們統(tǒng)計出其中只有兩個字符，概率分布為Pb=0.5,Pc=0.5。我們在壓縮過程中不必再更新此概率分布，每次對區(qū)間的劃分都依照此分布即可，對上例也就是每次都平分區(qū)間。這樣，我們的壓縮過程可以簡單表示為：輸出區(qū)間的下限 輸出區(qū)間的上限壓縮前0.01.0輸入b0.00.5輸入c0.250.5輸入c0.3750.5輸入b0.3750.4375我們看出，最后的輸出區(qū)間在0.375-0.4375之間，甚至連一個十進制位都沒有確定，也就是說，整個信息根本用不了一個十進制位。如果我們改用二進制來表示上述過程的話，我們會發(fā)現(xiàn)我們可以非常接近該信息的熵值（有的讀者可能已經(jīng)算出來了，該信息的熵值為4個二進制位）。為什么用自適應(yīng)模型？既然我們使用靜態(tài)模型可以很好地接近熵值，為什么還要采用自適應(yīng)模型呢？要知道，靜態(tài)模型無法適應(yīng)信息的多樣性，例如，我們上面得出的概率分布沒法在所有待壓縮信息上使用，為了能正確解壓縮，我們必須再消耗一定的空間保存靜態(tài)模型統(tǒng)計出的概率分布，保存模型所用的空間將使我們重新遠離熵值。其次，靜態(tài)模型需要在壓縮前對信息內(nèi)字符的分布進行統(tǒng)計，這一統(tǒng)計過程將消耗大量的時間，使得本來就比較慢的算術(shù)編碼壓縮更加緩慢。另外還有最重要的一點，對較長的信息，靜態(tài)模型統(tǒng)計出的符號概率是該符號