有趣！史記：數(shù)據(jù)壓縮算法列傳

電腦里的數(shù)據(jù)壓縮其實(shí)類似于美眉們的瘦身運(yùn)動(dòng)，不外有兩大功用。

第一，可以節(jié)省空間。拿瘦身美眉來(lái)說(shuō)，要是八個(gè)美眉可以擠進(jìn)一輛出租車?yán)铮窃撚卸嗍″X?。?/p>

第二，可以減少對(duì)帶寬的占用。例如，我們都想在不到 100Kbps 的 GPRS 網(wǎng)上觀看 DVD 大片，這就好比瘦身美眉們總希望用一尺布裁出七件吊帶衫，前者有待于數(shù)據(jù)壓縮技術(shù)的突破性進(jìn)展，后者則取決于美眉們的恒心和毅力。

簡(jiǎn)單地說(shuō)，如果沒(méi)有數(shù)據(jù)壓縮技術(shù)，我們就沒(méi)法用 WinRAR 為 Email 中的附件瘦身；如果沒(méi)有數(shù)據(jù)壓縮技術(shù)，市場(chǎng)上的數(shù)碼錄音筆就只能記錄不到20 分鐘的語(yǔ)音；如果沒(méi)有數(shù)據(jù)壓縮技術(shù)，從 Internet上下載一部電影也許要花半年的時(shí)間……可是這一切究竟是如何實(shí)現(xiàn)的呢？數(shù)據(jù)壓縮技術(shù)又是怎樣從無(wú)到有發(fā)展起來(lái)的呢？

概率奇緣

一千多年前的中國(guó)學(xué)者就知道用“班馬”這樣的縮略語(yǔ)來(lái)指代班固和司馬遷，這種崇尚簡(jiǎn)約的風(fēng)俗一直延續(xù)到了今天的 Internet 時(shí)代：當(dāng)我們?cè)?BBS上用“ 7456 ”代表“氣死我了”，或是用“ B4 ”代表“ Before ”的時(shí)候，我們至少應(yīng)該知道，這其實(shí)就是一種最簡(jiǎn)單的數(shù)據(jù)壓縮呀。

嚴(yán)格意義上的數(shù)據(jù)壓縮起源于人們對(duì)概率的認(rèn)識(shí)。當(dāng)我們對(duì)文字信息進(jìn)行編碼時(shí)，如果為出現(xiàn)概率較高的字母賦予較短的編碼，為出現(xiàn)概率較低的字母賦予較長(zhǎng)的編碼，總的編碼長(zhǎng)度就能縮短不少。遠(yuǎn)在計(jì)算機(jī)出現(xiàn)之前，著名的 Morse電碼就已經(jīng)成功地實(shí)踐了這一準(zhǔn)則。在 Morse碼表中，每個(gè)字母都對(duì)應(yīng)于一個(gè)唯一的點(diǎn)劃組合，出現(xiàn)概率最高的字母 e 被編碼為一個(gè)點(diǎn)“ 。 ”，而出現(xiàn)概率較低的字母 z 則被編碼為“ --”。顯然，這可以有效縮短最終的電碼長(zhǎng)度。

信息論之父 C. E.Shannon第一次用數(shù)學(xué)語(yǔ)言闡明了概率與信息冗余度的關(guān)系。在 1948 年發(fā)表的論文“通信的數(shù)學(xué)理論（ A Mathematical Theory of Communication ）”中， Shannon 指出，任何信息都存在冗余，冗余大小與信息中每個(gè)符號(hào)（數(shù)字、字母或單詞）的出現(xiàn)概率或者說(shuō)不確定性有關(guān)。Shannon 借鑒了熱力學(xué)的概念，把信息中排除了冗余后的平均信息量稱為“信息熵”，并給出了計(jì)算信息熵的數(shù)學(xué)表達(dá)式。這篇偉大的論文后來(lái)被譽(yù)為信息論的開山之作，信息熵也奠定了所有數(shù)據(jù)壓縮算法的理論基礎(chǔ)。從本質(zhì)上講，數(shù)據(jù)壓縮的目的就是要消除信息中的冗余，而信息熵及相關(guān)的定理恰恰用數(shù)學(xué)手段精確地描述了信息冗余的程度。利用信息熵公式，人們可以計(jì)算出信息編碼的極限，即在一定的概率模型下，無(wú)損壓縮的編碼長(zhǎng)度不可能小于信息熵公式給出的結(jié)果。

有了完備的理論，接下來(lái)的事就是要想辦法實(shí)現(xiàn)具體的算法，并盡量使算法的輸出接近信息熵的極限了。當(dāng)然，大多數(shù)工程技術(shù)人員都知道，要將一種理論從數(shù)學(xué)公式發(fā)展成實(shí)用技術(shù)，就像僅憑一個(gè) E=mc 2 的公式就要去制造核武器一樣，并不是一件很容易的事。

數(shù)學(xué)游戲

設(shè)計(jì)具體的壓縮算法的過(guò)程通常更像是一場(chǎng)數(shù)學(xué)游戲。開發(fā)者首先要尋找一種能盡量精確地統(tǒng)計(jì)或估計(jì)信息中符號(hào)出現(xiàn)概率的方法，然后還要設(shè)計(jì)一套用最短的代碼描述每個(gè)符號(hào)的編碼規(guī)則。統(tǒng)計(jì)學(xué)知識(shí)對(duì)于前一項(xiàng)工作相當(dāng)有效，迄今為止，人們已經(jīng)陸續(xù)實(shí)現(xiàn)了靜態(tài)模型、半靜態(tài)模型、自適應(yīng)模型、 Markov模型、部分匹配預(yù)測(cè)模型等概率統(tǒng)計(jì)模型。相對(duì)而言，編碼方法的發(fā)展歷程更為曲折一些。

1948年，Shannon在提出信息熵理論的同時(shí)，也給出了一種簡(jiǎn)單的編碼方法―― Shannon 編碼。1952 年， R. M. Fano 又進(jìn)一步提出了 Fano編碼。這些早期的編碼方法揭示了變長(zhǎng)編碼的基本規(guī)律，也確實(shí)可以取得一定的壓縮效果，但離真正實(shí)用的壓縮算法還相去甚遠(yuǎn)。

第一個(gè)實(shí)用的編碼方法是由D. A. Huffman 在 1952 年的論文“最小冗余度代碼的構(gòu)造方法（ A Method for the Construction of Minimum Redundancy Codes ）”中提出的。直到今天，許多《數(shù)據(jù)結(jié)構(gòu)》教材在討論二叉樹時(shí)仍要提及這種被后人稱為 Huffman 編碼的方法。Huffman 編碼在計(jì)算機(jī)界是如此著名，以至于連編碼的發(fā)明過(guò)程本身也成了人們津津樂(lè)道的話題。據(jù)說(shuō)， 1952 年時(shí)，年輕的 Huffman 還是麻省理工學(xué)院的一名學(xué)生，他為了向老師證明自己可以不參加某門功課的期末考試，才設(shè)計(jì)了這個(gè)看似簡(jiǎn)單，但卻影響深遠(yuǎn)的編碼方法。

Huffman編碼效率高，運(yùn)算速度快，實(shí)現(xiàn)方式靈活，從 20 世紀(jì) 60 年代至今，在數(shù)據(jù)壓縮領(lǐng)域得到了廣泛的應(yīng)用。例如，早期 UNIX 系統(tǒng)上一個(gè)不太為現(xiàn)代人熟知的壓縮程序 COMPACT 實(shí)際就是 Huffman 0 階自適應(yīng)編碼的具體實(shí)現(xiàn)。20 世紀(jì) 80 年代初，Huffman 編碼又出現(xiàn)在 CP/M 和 DOS 系統(tǒng)中，其代表程序叫 SQ 。今天，在許多知名的壓縮工具和壓縮算法（如 WinRAR、 gzip 和 JPEG ）里，都有 Huffman編碼的身影。不過(guò)， Huffman 編碼所得的編碼長(zhǎng)度只是對(duì)信息熵計(jì)算結(jié)果的一種近似，還無(wú)法真正逼近信息熵的極限。正因?yàn)槿绱?，現(xiàn)代壓縮技術(shù)通常只將 Huffman 視作最終的編碼手段，而非數(shù)據(jù)壓縮算法的全部。

科學(xué)家們一直沒(méi)有放棄向信息熵極限挑戰(zhàn)的理想。1968 年前后， P. Elias發(fā)展了 Shannon 和 Fano 的編碼方法，構(gòu)造出從數(shù)學(xué)角度看來(lái)更為完美的 Shannon-Fano-Elias編碼。沿著這一編碼方法的思路， 1976 年， J. Rissanen 提出了一種可以成功地逼近信息熵極限的編碼方法――算術(shù)編碼。1982年， Rissanen 和 G. G. Langdon 一起改進(jìn)了算術(shù)編碼。之后，人們又將算術(shù)編碼與 J. G. Cleary 和 I. H.Witten 于1984 年提出的部分匹配預(yù)測(cè)模型（ PPM ）相結(jié)合，開發(fā)出了壓縮效果近乎完美的算法。今天，那些名為 PPMC 、 PPMD 或PPMZ 并號(hào)稱壓縮效果天下第一的通用壓縮算法，實(shí)際上全都是這一思路的具體實(shí)現(xiàn)。

對(duì)于無(wú)損壓縮而言， PPM模型與算術(shù)編碼相結(jié)合，已經(jīng)可以最大程度地逼近信息熵的極限?？雌饋?lái)，壓縮技術(shù)的發(fā)展可以到此為止了。不幸的是，事情往往不像想象中的那樣簡(jiǎn)單：算術(shù)編碼雖然可以獲得最短的編碼長(zhǎng)度，但其本身的復(fù)雜性也使得算術(shù)編碼的任何具體實(shí)現(xiàn)在運(yùn)行時(shí)都慢如蝸牛。即使在摩爾定律大行其道， CPU速度日新月異的今天，算術(shù)編碼程序的運(yùn)行速度也很難滿足日常應(yīng)用的需求。沒(méi)辦法，如果不是后文將要提到的那兩個(gè)猶太人，我們還不知要到什么時(shí)候才能用上 WinZIP 這樣方便實(shí)用的壓縮工具呢。

異族傳說(shuō)

逆向思維永遠(yuǎn)是科學(xué)和技術(shù)領(lǐng)域里出奇制勝的法寶。就在大多數(shù)人絞盡腦汁想改進(jìn) Huffman 或算術(shù)編碼，以獲得一種兼顧了運(yùn)行速度和壓縮效果的“完美”編碼的時(shí)候，兩個(gè)聰明的猶太人 J. Ziv 和 A. Lempel 獨(dú)辟蹊徑，完全脫離Huffman 及算術(shù)編碼的設(shè)計(jì)思路，創(chuàng)造出了一系列比 Huffman編碼更有效，比算術(shù)編碼更快捷的壓縮算法。我們通常用這兩個(gè)猶太人姓氏的縮寫，將這些算法統(tǒng)稱為 LZ 系列算法。

按照時(shí)間順序，LZ 系列算法的發(fā)展歷程大致是：Ziv 和 Lempel 于 1977 年發(fā)表題為“順序數(shù)據(jù)壓縮的一個(gè)通用算法（ A Universal Algorithm for Sequential Data Compression ）”的論文，論文中描述的算法被后人稱為 LZ77 算法。

1978 年，二人又發(fā)表了該論文的續(xù)篇“通過(guò)可變比率編碼的獨(dú)立序列的壓縮（ Compression of Individual Sequences via Variable Rate Coding ）”，描述了后來(lái)被命名為 LZ78 的壓縮算法。1984 年， T. A. Welch 發(fā)表了名為“高性能數(shù)據(jù)壓縮技術(shù)（ A Technique for High Performance Data Compression ）”的論文，描述了他在 Sperry 研究中心（該研究中心后來(lái)并入了 Unisys 公司）的研究成果，這是 LZ78 算法的一個(gè)變種，也就是后來(lái)非常有名的 LZW 算法。1990 年后， T. C. Bell 等人又陸續(xù)提出了許多 LZ 系列算法的變體或改進(jìn)版本。

說(shuō)實(shí)話， LZ 系列算法的思路并不新鮮，其中既沒(méi)有高深的理論背景，也沒(méi)有復(fù)雜的數(shù)學(xué)公式，它們只是簡(jiǎn)單地延續(xù)了千百年來(lái)人們對(duì)字典的追崇和喜好，并用一種極為巧妙的方式將字典技術(shù)應(yīng)用于通用數(shù)據(jù)壓縮領(lǐng)域。通俗地說(shuō)，當(dāng)你用字典中的頁(yè)碼和行號(hào)代替文章中每個(gè)單詞的時(shí)候，你實(shí)際上已經(jīng)掌握了 LZ系列算法的真諦。這種基于字典模型的思路在表面上雖然和 Shannon 、 Huffman 等人開創(chuàng)的統(tǒng)計(jì)學(xué)方法大相徑庭，但在效果上一樣可以逼近信息熵的極限。而且，可以從理論上證明， LZ系列算法在本質(zhì)上仍然符合信息熵的基本規(guī)律。

LZ系列算法的優(yōu)越性很快就在數(shù)據(jù)壓縮領(lǐng)域里體現(xiàn)了出來(lái)，使用 LZ 系列算法的工具軟件數(shù)量呈爆炸式增長(zhǎng)。UNIX 系統(tǒng)上最先出現(xiàn)了使用 LZW算法的 compress程序，該程序很快成為了 UNIX 世界的壓縮標(biāo)準(zhǔn)。緊隨其后的是 MS-DOS 環(huán)境下的 ARC 程序，以及PKWare 、 PKARC 等仿制品。20 世紀(jì) 80 年代，著名的壓縮工具 LHarc 和 ARJ 則是 LZ77 算法的杰出代表。

今天， LZ77 、 LZ78 、 LZW 算法以及它們的各種變體幾乎壟斷了整個(gè)通用數(shù)據(jù)壓縮領(lǐng)域，我們熟悉的 PKZIP 、WinZIP 、 WinRAR 、 gzip 等壓縮工具以及 ZIP 、 GIF 、 PNG等文件格式都是 LZ 系列算法的受益者，甚至連 PGP 這樣的加密文件格式也選擇了 LZ 系列算法作為其數(shù)據(jù)壓縮的標(biāo)準(zhǔn)。

沒(méi)有誰(shuí)能否認(rèn)兩位猶太人對(duì)數(shù)據(jù)壓縮技術(shù)的貢獻(xiàn)。我想強(qiáng)調(diào)的只是，在工程技術(shù)領(lǐng)域，片面追求理論上的完美往往只會(huì)事倍功半，如果大家能像 Ziv 和 Lempel 那樣，經(jīng)常換個(gè)角度來(lái)思考問(wèn)題，沒(méi)準(zhǔn)兒你我就能發(fā)明一種新的算法，就能在技術(shù)方展史上揚(yáng)名立萬(wàn)呢。

音畫時(shí)尚

LZ系列算法基本解決了通用數(shù)據(jù)壓縮中兼顧速度與壓縮效果的難題。但是，數(shù)據(jù)壓縮領(lǐng)域里還有另一片更為廣闊的天地等待著我們?nèi)ヌ剿鳌hannon的信息論告訴我們，對(duì)信息的先驗(yàn)知識(shí)越多，我們就可以把信息壓縮得越小。換句話說(shuō)，如果壓縮算法的設(shè)計(jì)目標(biāo)不是任意的數(shù)據(jù)源，而是基本屬性已知的特種數(shù)據(jù)，壓縮的效果就會(huì)進(jìn)一步提高。這提醒我們，在發(fā)展通用壓縮算法之余，還必須認(rèn)真研究針對(duì)各種特殊數(shù)據(jù)的專用壓縮算法。比方說(shuō)，在今天的數(shù)碼生活中，遍布于數(shù)碼相機(jī)、數(shù)碼錄音筆、數(shù)碼隨身聽、數(shù)碼攝像機(jī)等各種數(shù)字設(shè)備中的圖像、音頻、視頻信息，就必須經(jīng)過(guò)有效的壓縮才能在硬盤上存儲(chǔ)或是通過(guò) USB電纜傳輸。實(shí)際上，多媒體信息的壓縮一直是數(shù)據(jù)壓縮領(lǐng)域里的重要課題，其中的每一個(gè)分支都有可能主導(dǎo)未來(lái)的某個(gè)技術(shù)潮流，并為數(shù)碼產(chǎn)品、通信設(shè)備和應(yīng)用軟件開發(fā)商帶來(lái)無(wú)限的商機(jī)。

讓我們先從圖像數(shù)據(jù)的壓縮講起。通常所說(shuō)的圖像可以被分為二值圖像、灰度圖像、彩色圖像等不同的類型。每一類圖像的壓縮方法也不盡相同。

傳真技術(shù)的發(fā)明和廣泛使用促進(jìn)了二值圖像壓縮算法的飛速發(fā)展。CCITT （國(guó)際電報(bào)電話咨詢委員會(huì)，是國(guó)際電信聯(lián)盟 ITU下屬的一個(gè)機(jī)構(gòu)）針對(duì)傳真類應(yīng)用建立了一系列圖像壓縮標(biāo)準(zhǔn)，專用于壓縮和傳遞二值圖像。這些標(biāo)準(zhǔn)大致包括 20 世紀(jì) 70 年代后期的 CCITT Group 1 和 Group 2 ， 1980 年的 CCITT Group 3 ，以及 1984 年的 CCITT Group 4 。

為 了適應(yīng)不同類型的傳真圖像，這些標(biāo)準(zhǔn)所用的編碼方法包括了一維的 MH 編碼和二維的 MR 編碼，其中使用了行程編碼（ RLE ）和 Huffman 編碼等技術(shù)。今天，我們?cè)谵k公室或家里收發(fā)傳真時(shí)，使用的大多是 CCITT Group 3 壓縮標(biāo)準(zhǔn)，一些基于數(shù)字網(wǎng)絡(luò)的傳真設(shè)備和存放二值圖像的 TIFF 文件則使用了 CCITT Group 4 壓縮標(biāo)準(zhǔn)。1993 年， CCITT 和 ISO（國(guó)際標(biāo)準(zhǔn)化組織）共同成立的二值圖像聯(lián)合專家組（ Joint Bi-level Image Experts Group ， JBIG ）又將二值圖像的壓縮進(jìn)一步發(fā)展為更加通用的 JBIG 標(biāo)準(zhǔn)。

實(shí)際上，對(duì)于二值圖像和非連續(xù)的灰度、彩色圖像而言，包括 LZ 系列算法在內(nèi)的許多通用壓縮算法都能獲得很好的壓縮效果。例如，誕生于 1987 年的GIF 圖像文件格式使用的是 LZW 壓縮算法， 1995 年出現(xiàn)的 PNG 格式比 GIF 格式更加完善，它選擇了 LZ77 算法的變體zlib 來(lái)壓縮圖像數(shù)據(jù)。此外，利用前面提到過(guò)的 Huffman 編碼、算術(shù)編碼以及 PPM模型，人們事實(shí)上已經(jīng)構(gòu)造出了許多行之有效的圖像壓縮算法。

但是，對(duì)于生活中更加常見(jiàn)的，像素值在空間上連續(xù)變化的灰度或彩色圖像（比如數(shù)碼照片），通用壓縮算法的優(yōu)勢(shì)就不那么明顯了。幸運(yùn)的是，科學(xué)家們發(fā)現(xiàn)，如果在壓縮這一類圖像數(shù)據(jù)時(shí)允許改變一些不太重要的像素值，或者說(shuō)允許損失一些精度（在壓縮通用數(shù)據(jù)時(shí)，我們絕不會(huì)容忍任何精度上的損失，但在壓縮和顯示一幅數(shù)碼照片時(shí)，如果一片樹林里某些樹葉的顏色稍微變深了一些，看照片的人通常是察覺(jué)不到的），我們就有可能在壓縮效果上獲得突破性的進(jìn)展。這一思想在數(shù)據(jù)壓縮領(lǐng)域具有革命性的地位：通過(guò)在用戶的忍耐范圍內(nèi)損失一些精度，我們可以把圖像（也包括音頻和視頻）壓縮到原大小的十分之一、百分之一甚至千分之一，這遠(yuǎn)遠(yuǎn)超出了通用壓縮算法的能力極限。也許，這和生活中常說(shuō)的“退一步海闊天空”的道理有異曲同工之妙吧。

這種允許精度損失的壓縮也被稱為有損壓縮。在圖像壓縮領(lǐng)域，著名的JPEG標(biāo)準(zhǔn)是有損壓縮算法中的經(jīng)典。JPEG 標(biāo)準(zhǔn)由靜態(tài)圖像聯(lián)合專家組（ Joint Photographic Experts Group ，JPEG ）于 1986 年開始制定， 1994 年后成為國(guó)際標(biāo)準(zhǔn)。JPEG以離散余弦變換（ DCT ）為核心算法，通過(guò)調(diào)整質(zhì)量系數(shù)控制圖像的精度和大小。對(duì)于照片等連續(xù)變化的灰度或彩色圖像， JPEG在保證圖像質(zhì)量的前提下，一般可以將圖像壓縮到原大小的十分之一到二十分之一。如果不考慮圖像質(zhì)量， JPEG甚至可以將圖像壓縮到“無(wú)限小”。

JPEG標(biāo)準(zhǔn)的最新進(jìn)展是 1996 年開始制定， 2001 年正式成為國(guó)際標(biāo)準(zhǔn)的 JPEG 2000。與 JPEG 相比， JPEG 2000 作了大幅改進(jìn)，其中最重要的是用離散小波變換（ DWT ）替代了 JPEG 標(biāo)準(zhǔn)中的離散余弦變換。在文件大小相同的情況下， JPEG 2000壓縮的圖像比 JPEG 質(zhì)量更高，精度損失更小。作為一個(gè)新標(biāo)準(zhǔn)， JPEG 2000暫時(shí)還沒(méi)有得到廣泛的應(yīng)用，不過(guò)包括數(shù)碼相機(jī)制造商在內(nèi)的許多企業(yè)都對(duì)其應(yīng)用前景表示樂(lè)觀， JPEG 2000在圖像壓縮領(lǐng)域里大顯身手的那一天應(yīng)該不會(huì)特別遙遠(yuǎn)。

JPEG標(biāo)準(zhǔn)中通過(guò)損失精度來(lái)?yè)Q取壓縮效果的設(shè)計(jì)思想直接影響了視頻數(shù)據(jù)的壓縮技術(shù)。CCITT 于 1988 年制定了電視電話和會(huì)議電視的 H.261 建議草案。H.261的基本思路是使用類似 JPEG 標(biāo)準(zhǔn)的算法壓縮視頻流中的每一幀圖像，同時(shí)采用運(yùn)動(dòng)補(bǔ)償?shù)膸g預(yù)測(cè)來(lái)消除視頻流在時(shí)間維度上的冗余信息。在此基礎(chǔ)上， 1993 年， ISO通過(guò)了動(dòng)態(tài)圖像專家組（ Moving Picture Experts Group ， MPEG ）提出的 MPEG-1標(biāo)準(zhǔn)。MPEG-1 可以對(duì)普通質(zhì)量的視頻數(shù)據(jù)進(jìn)行有效編碼。我們現(xiàn)在看到的大多數(shù) VCD 影碟，就是使用 MPEG-1 標(biāo)準(zhǔn)來(lái)壓縮視頻數(shù)據(jù)的。

為了支持更清晰的視頻圖像，特別是支持?jǐn)?shù)字電視等高端應(yīng)用，ISO 于 1994 年提出了新的 MPEG-2 標(biāo)準(zhǔn)（相當(dāng)于 CCITT 的 H.262 標(biāo)準(zhǔn)）。MPEG-2 對(duì)圖像質(zhì)量作了分級(jí)處理，可以適應(yīng)普通電視節(jié)目、會(huì)議電視、高清晰數(shù)字電視等不同質(zhì)量的視頻應(yīng)用。在我們的生活中，可以提供高清晰畫面的 DVD影碟所采用的正是 MPEG-2 標(biāo)準(zhǔn)。

Internet的發(fā)展對(duì)視頻壓縮提出了更高的要求。在內(nèi)容交互、對(duì)象編輯、隨機(jī)存取等新需求的刺激下， ISO 于 1999 年通過(guò)了 MPEG-4 標(biāo)準(zhǔn)（相當(dāng)于CCITT 的 H.263 和 H.263+標(biāo)準(zhǔn)）。MPEG-4 標(biāo)準(zhǔn)擁有更高的壓縮比率，支持并發(fā)數(shù)據(jù)流的編碼、基于內(nèi)容的交互操作、增強(qiáng)的時(shí)間域隨機(jī)存取、容錯(cuò)、基于內(nèi)容的尺度可變性等先進(jìn)特性。Internet上新興的 DivX 和 XviD 文件格式就是采用 MPEG-4 標(biāo)準(zhǔn)來(lái)壓縮視頻數(shù)據(jù)的，它們可以用更小的存儲(chǔ)空間或通信帶寬提供與 DVD不相上下的高清晰視頻，這使我們?cè)?Internet 上發(fā)布或下載數(shù)字電影的夢(mèng)想成為了現(xiàn)實(shí)。

就像視頻壓縮和電視產(chǎn)業(yè)的發(fā)展密不可分一樣，音頻數(shù)據(jù)的壓縮技術(shù)最早也是由無(wú)線電廣播、語(yǔ)音通信等領(lǐng)域里的技術(shù)人員發(fā)展起來(lái)的。這其中又以語(yǔ)音編碼和壓縮技術(shù)的研究最為活躍。自從 1939 年H. Dudley 發(fā)明聲碼器以來(lái)，人們陸續(xù)發(fā)明了脈沖編碼調(diào)制（ PCM ）、線性預(yù)測(cè)（ LPC ）、矢量量化（ VQ ）、自適應(yīng)變換編碼（ATC ）、子帶編碼（ SBC）等語(yǔ)音分析與處理技術(shù)。這些語(yǔ)音技術(shù)在采集語(yǔ)音特征，獲取數(shù)字信號(hào)的同時(shí)，通常也可以起到降低信息冗余度的作用。像圖像壓縮領(lǐng)域里的 JPEG一樣，為獲得更高的編碼效率，大多數(shù)語(yǔ)音編碼技術(shù)都允許一定程度的精度損失。而且，為了更好地用二進(jìn)制數(shù)據(jù)存儲(chǔ)或傳送語(yǔ)音信號(hào)，這些語(yǔ)音編碼技術(shù)在將語(yǔ)音信號(hào)轉(zhuǎn)換為數(shù)字信息之后又總會(huì)用 Huffman 編碼、算術(shù)編碼等通用壓縮算法進(jìn)一步減少數(shù)據(jù)流中的冗余信息。

對(duì)于電腦和數(shù)字電器（如數(shù)碼錄音筆、數(shù)碼隨身聽）中存儲(chǔ)的普通音頻信息，我們最常使用的壓縮方法主要是MPEG 系列中的音頻壓縮標(biāo)準(zhǔn)。例如， MPEG-1 標(biāo)準(zhǔn)提供了Layer I 、 Layer II 和 Layer III 共三種可選的音頻壓縮標(biāo)準(zhǔn)， MPEG-2 又進(jìn)一步引入了 AAC （ Advanced Audio Coding ）音頻壓縮標(biāo)準(zhǔn)， MPEG-4標(biāo)準(zhǔn)中的音頻部分則同時(shí)支持合成聲音編碼和自然聲音編碼等不同類型的應(yīng)用。在這許多音頻壓縮標(biāo)準(zhǔn)中，聲名最為顯赫的恐怕要數(shù) MPEG-1 Layer III ，也就是我們常說(shuō)的 MP3 音頻壓縮標(biāo)準(zhǔn)了。從 MP3 播放器到 MP3 手機(jī)，從硬盤上堆積如山的 MP3 文件到 Internet上版權(quán)糾紛不斷的 MP3 下載， MP3 早已超出了數(shù)據(jù)壓縮技術(shù)的范疇，而成了一種時(shí)尚文化的象征了。

很顯然，在多媒體信息日益成為主流信息形態(tài)的數(shù)字化時(shí)代里，數(shù)據(jù)壓縮技術(shù)特別是專用于圖像、音頻、視頻的數(shù)據(jù)壓縮技術(shù)還有相當(dāng)大的發(fā)展空間――畢竟，人們對(duì)信息數(shù)量和信息質(zhì)量的追求是永無(wú)止境的。

回到未來(lái)

從信息熵到算術(shù)編碼，從猶太人到 WinRAR ，從 JPEG 到 MP3，數(shù)據(jù)壓縮技術(shù)的發(fā)展史就像是一個(gè)寫滿了“創(chuàng)新”、“挑戰(zhàn)”、“突破”和“變革”的羊皮卷軸。也許，我們?cè)谶@里不厭其煩地羅列年代、人物、標(biāo)準(zhǔn)和文獻(xiàn)，其目的只是要告訴大家，前人的成果只不過(guò)是后人有望超越的目標(biāo)而已，誰(shuí)知道在未來(lái)的幾年里，還會(huì)出現(xiàn)幾個(gè) Shannon ，幾個(gè)Huffman 呢？

談到未來(lái)，我們還可以補(bǔ)充一些與數(shù)據(jù)壓縮技術(shù)的發(fā)展趨勢(shì)有關(guān)的話題。

1994年，M. Burrows和D. J. Wheeler共同提出了一種全新的通用數(shù)據(jù)壓縮算法。這種算法的核心思想是對(duì)字符串輪轉(zhuǎn)后得到的字符矩陣進(jìn)行排序和變換，類似的變換算法被稱為 Burrows-Wheeler 變換，簡(jiǎn)稱 BWT 。與 Ziv 和 Lempel 另辟蹊徑的做法如出一轍， Burrows 和 Wheeler 設(shè)計(jì)的 BWT 算法與以往所有通用壓縮算法的設(shè)計(jì)思路都迥然不同。如今， BWT 算法在開放源碼的壓縮工具bzip 中獲得了巨大的成功， bzip 對(duì)于文本文件的壓縮效果要遠(yuǎn)好于使用 LZ系列算法的工具軟件。這至少可以表明，即便在日趨成熟的通用數(shù)據(jù)壓縮領(lǐng)域，只要能在思路和技術(shù)上不斷創(chuàng)新，我們?nèi)匀豢梢哉业叫碌耐黄瓶凇?/p>

分形壓縮技術(shù)是圖像壓縮領(lǐng)域近幾年來(lái)的一個(gè)熱點(diǎn)。這一技術(shù)起源于B. Mandelbrot 于 1977 年創(chuàng)建的分形幾何學(xué)。M. Barnsley 在 20 世紀(jì) 80 年代后期為分形壓縮奠定了理論基礎(chǔ)。從 20 世紀(jì) 90 年代開始， A. Jacquin等人陸續(xù)提出了許多實(shí)驗(yàn)性的分形壓縮算法。今天，很多人相信，分形壓縮是圖像壓縮領(lǐng)域里最有潛力的一種技術(shù)體系，但也有很多人對(duì)此不屑一顧。無(wú)論其前景如何，分形壓縮技術(shù)的研究與發(fā)展都提示我們，在經(jīng)過(guò)了幾十年的高速發(fā)展之后，也許，我們需要一種新的理論，或是幾種更有效的數(shù)學(xué)模型，以支撐和推動(dòng)數(shù)據(jù)壓縮技術(shù)繼續(xù)向前躍進(jìn)。

人工智能是另一個(gè)可能對(duì)數(shù)據(jù)壓縮的未來(lái)產(chǎn)生重大影響的關(guān)鍵詞。既然 Shannon認(rèn)為，信息能否被壓縮以及能在多大程度上被壓縮與信息的不確定性有直接關(guān)系，假設(shè)人工智能技術(shù)在某一天成熟起來(lái)，假設(shè)計(jì)算機(jī)可以像人一樣根據(jù)已知的少量上下文猜測(cè)后續(xù)的信息，那么，將信息壓縮到原大小的萬(wàn)分之一乃至十萬(wàn)分之一，恐怕就不再是天方夜譚了。

回顧歷史之后，人們總喜歡暢想一下未來(lái)。但未來(lái)終究是未來(lái)，如果僅憑你我?guī)拙湓捑涂梢岳砬逦磥?lái)的技術(shù)發(fā)展趨勢(shì)，那技術(shù)創(chuàng)新的工作豈不就索然無(wú)味了嗎？依我說(shuō)，未來(lái)并不重要，重要的是，趕快到 Internet 上下載幾部大片，然后躺在沙發(fā)里，好好享受一下數(shù)據(jù)壓縮為我們帶來(lái)的無(wú)限快樂(lè)吧。

審核編輯 ：李倩