|
數(shù)據(jù)壓縮技術(shù)簡史 簡單地說，如果沒有數(shù)據(jù)壓縮技術(shù)，我們就沒法用 WinRAR 為 Email 中的附件瘦身；如果沒有數(shù)據(jù)壓縮技術(shù)，市場上的數(shù)碼錄音筆就只能記錄不到 20 分鐘的語音；如果沒有數(shù)據(jù)壓縮技術(shù)，從 Internet 上下載一部電影也許要花半年的時間……可是這一切究竟是如何實現(xiàn)的呢？數(shù)據(jù)壓縮技術(shù)又是怎樣從無到有發(fā)展起來的呢？ 概率奇緣 嚴格意義上的數(shù)據(jù)壓縮起源于人們對概率的認識。當我們對文字信息進行編碼時，如果為出現(xiàn)概率較高的字母賦予較短的編碼，為出現(xiàn)概率較低的字母賦予較長的編碼，總的編碼長度就能縮短不少。遠在計算機出現(xiàn)之前，著名的 Morse 電碼就已經(jīng)成功地實踐了這一準則。在 Morse 碼表中，每個字母都對應于一個唯一的點劃組合，出現(xiàn)概率最高的字母 e 被編碼為一個點“ . ”，而出現(xiàn)概率較低的字母 z 則被編碼為“ --.. ”。顯然，這可以有效縮短最終的電碼長度。 信息論之父 C. E. Shannon 第一次用數(shù)學語言闡明了概率與信息冗余度的關(guān)系。在 1948 年發(fā)表的論文“通信的數(shù)學理論（ A Mathematical Theory of Communication ）”中， Shannon 指出，任何信息都存在冗余，冗余大小與信息中每個符號（數(shù)字、字母或單詞）的出現(xiàn)概率或者說不確定性有關(guān)。 Shannon 借鑒了熱力學的概念，把信息中排除了冗余后的平均信息量稱為“信息熵”，并給出了計算信息熵的數(shù)學表達式。這篇偉大的論文后來被譽為信息論的開山之作，信息熵也奠定了所有數(shù)據(jù)壓縮算法的理論基礎。從本質(zhì)上講，數(shù)據(jù)壓縮的目的就是要消除信息中的冗余，而信息熵及相關(guān)的定理恰恰用數(shù)學手段精確地描述了信息冗余的程度。利用信息熵公式，人們可以計算出信息編碼的極限，即在一定的概率模型下，無損壓縮的編碼長度不可能小于信息熵公式給出的結(jié)果。 有了完備的理論，接下來的事就是要想辦法實現(xiàn)具體的算法，并盡量使算法的輸出接近信息熵的極限了。當然，大多數(shù)工程技術(shù)人員都知道，要將一種理論從數(shù)學公式發(fā)展成實用技術(shù)，就像僅憑一個 E=mc 2 的公式就要去制造核武器一樣，并不是一件很容易的事。 數(shù)學游戲 1948 年， Shannon 在提出信息熵理論的同時，也給出了一種簡單的編碼方法—— Shannon 編碼。 1952 年， R. M. Fano 又進一步提出了 Fano 編碼。這些早期的編碼方法揭示了變長編碼的基本規(guī)律，也確實可以取得一定的壓縮效果，但離真正實用的壓縮算法還相去甚遠。 第一個實用的編碼方法是由 D. A. Huffman 在 1952 年的論文“最小冗余度代碼的構(gòu)造方法（ A Method for the Construction of Minimum Redundancy Codes ）”中提出的。直到今天，許多《數(shù)據(jù)結(jié)構(gòu)》教材在討論二叉樹時仍要提及這種被后人稱為 Huffman 編碼的方法。 Huffman 編碼在計算機界是如此著名，以至于連編碼的發(fā)明過程本身也成了人們津津樂道的話題。據(jù)說， 1952 年時，年輕的 Huffman 還是麻省理工學院的一名學生，他為了向老師證明自己可以不參加某門功課的期末考試，才設計了這個看似簡單，但卻影響深遠的編碼方法。 Huffman 編碼效率高，運算速度快，實現(xiàn)方式靈活，從 20 世紀 60 年代至今，在數(shù)據(jù)壓縮領(lǐng)域得到了廣泛的應用。例如，早期 UNIX 系統(tǒng)上一個不太為現(xiàn)代人熟知的壓縮程序 COMPACT 實際就是 Huffman 0 階自適應編碼的具體實現(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ù)壓縮算法的全部。 科學家們一直沒有放棄向信息熵極限挑戰(zhàn)的理想。 1968 年前后， P. Elias 發(fā)展了 Shannon 和 Fano 的編碼方法，構(gòu)造出從數(shù)學角度看來更為完美的 Shannon-Fano-Elias 編碼。沿著這一編碼方法的思路， 1976 年， J. Rissanen 提出了一種可以成功地逼近信息熵極限的編碼方法——算術(shù)編碼。 1982 年， Rissanen 和 G. G. Langdon 一起改進了算術(shù)編碼。之后，人們又將算術(shù)編碼與 J. G. Cleary 和 I. H. Witten 于 1984 年提出的部分匹配預測模型（ PPM ）相結(jié)合，開發(fā)出了壓縮效果近乎完美的算法。今天，那些名為 PPMC 、 PPMD 或 PPMZ 并號稱壓縮效果天下第一的通用壓縮算法，實際上全都是這一思路的具體實現(xiàn)。 對于無損壓縮而言， PPM 模型與算術(shù)編碼相結(jié)合，已經(jīng)可以最大程度地逼近信息熵的極限?？雌饋?，壓縮技術(shù)的發(fā)展可以到此為止了。不幸的是，事情往往不像想象中的那樣簡單：算術(shù)編碼雖然可以獲得最短的編碼長度，但其本身的復雜性也使得算術(shù)編碼的任何具體實現(xiàn)在運行時都慢如蝸牛。即使在摩爾定律大行其道， CPU 速度日新月異的今天，算術(shù)編碼程序的運行速度也很難滿足日常應用的需求。沒辦法，如果不是后文將要提到的那兩個猶太人，我們還不知要到什么時候才能用上 WinZIP 這樣方便實用的壓縮工具呢。 異族傳說 按照時間順序， LZ 系列算法的發(fā)展歷程大致是： Ziv 和 Lempel 于 1977 年發(fā)表題為“順序數(shù)據(jù)壓縮的一個通用算法（ A Universal Algorithm for Sequential Data Compression ）”的論文，論文中描述的算法被后人稱為 LZ77 算法。 1978 年，二人又發(fā)表了該論文的續(xù)篇“通過可變比率編碼的獨立序列的壓縮（ Compression of Individual Sequences via Variable Rate Coding ）”，描述了后來被命名為 LZ78 的壓縮算法。 1984 年， T. A. Welch 發(fā)表了名為“高性能數(shù)據(jù)壓縮技術(shù)（ A Technique for High Performance Data Compression ）”的論文，描述了他在 Sperry 研究中心（該研究中心后來并入了 Unisys 公司）的研究成果，這是 LZ78 算法的一個變種，也就是后來非常有名的 LZW 算法。 1990 年后， T. C. Bell 等人又陸續(xù)提出了許多 LZ 系列算法的變體或改進版本。 說實話， LZ 系列算法的思路并不新鮮，其中既沒有高深的理論背景，也沒有復雜的數(shù)學公式，它們只是簡單地延續(xù)了千百年來人們對字典的追崇和喜好，并用一種極為巧妙的方式將字典技術(shù)應用于通用數(shù)據(jù)壓縮領(lǐng)域。通俗地說，當你用字典中的頁碼和行號代替文章中每個單詞的時候，你實際上已經(jīng)掌握了 LZ 系列算法的真諦。這種基于字典模型的思路在表面上雖然和 Shannon 、 Huffman 等人開創(chuàng)的統(tǒng)計學方法大相徑庭，但在效果上一樣可以逼近信息熵的極限。而且，可以從理論上證明， 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ù)方展史上揚名立萬呢。 音畫時尚 讓我們先從圖像數(shù)據(jù)的壓縮講起。通常所說的圖像可以被分為二值圖像、灰度圖像、彩色圖像等不同的類型。每一類圖像的壓縮方法也不盡相同。 傳真技術(shù)的發(fā)明和廣泛使用促進了二值圖像壓縮算法的飛速發(fā)展。 CCITT （國際電報電話咨詢委員會，是國際電信聯(lián)盟 ITU 下屬的一個機構(gòu)）針對傳真類應用建立了一系列圖像壓縮標準，專用于壓縮和傳遞二值圖像。這些標準大致包括 20 世紀 70 年代后期的 CCITT Group 1 和 Group 2 ， 1980 年的 CCITT Group 3 ，以及 1984 年的 CCITT Group 4 。為了適應不同類型的傳真圖像，這些標準所用的編碼方法包括了一維的 MH 編碼和二維的 MR 編碼，其中使用了行程編碼（ RLE ）和 Huffman 編碼等技術(shù)。今天，我們在辦公室或家里收發(fā)傳真時，使用的大多是 CCITT Group 3 壓縮標準，一些基于數(shù)字網(wǎng)絡的傳真設備和存放二值圖像的 TIFF 文件則使用了 CCITT Group 4 壓縮標準。 1993 年， CCITT 和 ISO （國際標準化組織）共同成立的二值圖像聯(lián)合專家組（ Joint Bi-level Image Experts Group ， JBIG ）又將二值圖像的壓縮進一步發(fā)展為更加通用的 JBIG 標準。 實際上，對于二值圖像和非連續(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)勢就不那么明顯了。幸運的是，科學家們發(fā)現(xiàn)，如果在壓縮這一類圖像數(shù)據(jù)時允許改變一些不太重要的像素值，或者說允許損失一些精度（在壓縮通用數(shù)據(jù)時，我們絕不會容忍任何精度上的損失，但在壓縮和顯示一幅數(shù)碼照片時，如果一片樹林里某些樹葉的顏色稍微變深了一些，看照片的人通常是察覺不到的），我們就有可能在壓縮效果上獲得突破性的進展。這一思想在數(shù)據(jù)壓縮領(lǐng)域具有革命性的地位：通過在用戶的忍耐范圍內(nèi)損失一些精度，我們可以把圖像（也包括音頻和視頻）壓縮到原大小的十分之一、百分之一甚至千分之一，這遠遠超出了通用壓縮算法的能力極限。也許，這和生活中常說的“退一步海闊天空”的道理有異曲同工之妙吧。 這種允許精度損失的壓縮也被稱為有損壓縮。在圖像壓縮領(lǐng)域，著名的 JPEG 標準是有損壓縮算法中的經(jīng)典。 JPEG 標準由靜態(tài)圖像聯(lián)合專家組（ Joint Photographic Experts Group ， JPEG ）于 1986 年開始制定， 1994 年后成為國際標準。 JPEG 以離散余弦變換（ DCT ）為核心算法，通過調(diào)整質(zhì)量系數(shù)控制圖像的精度和大小。對于照片等連續(xù)變化的灰度或彩色圖像， JPEG 在保證圖像質(zhì)量的前提下，一般可以將圖像壓縮到原大小的十分之一到二十分之一。如果不考慮圖像質(zhì)量， JPEG 甚至可以將圖像壓縮到“無限小”。 JPEG 標準的最新進展是 1996 年開始制定， 2001 年正式成為國際標準的 JPEG 2000 。與 JPEG 相比， JPEG 2000 作了大幅改進，其中最重要的是用離散小波變換（ DWT ）替代了 JPEG 標準中的離散余弦變換。在文件大小相同的情況下， JPEG 2000 壓縮的圖像比 JPEG 質(zhì)量更高，精度損失更小。作為一個新標準， JPEG 2000 暫時還沒有得到廣泛的應用，不過包括數(shù)碼相機制造商在內(nèi)的許多企業(yè)都對其應用前景表示樂觀， JPEG 2000 在圖像壓縮領(lǐng)域里大顯身手的那一天應該不會特別遙遠。 JPEG 標準中通過損失精度來換取壓縮效果的設計思想直接影響了視頻數(shù)據(jù)的壓縮技術(shù)。 CCITT 于 1988 年制定了電視電話和會議電視的 H.261 建議草案。 H.261 的基本思路是使用類似 JPEG 標準的算法壓縮視頻流中的每一幀圖像，同時采用運動補償?shù)膸g預測來消除視頻流在時間維度上的冗余信息。在此基礎上， 1993 年， ISO 通過了動態(tài)圖像專家組（ Moving Picture Experts Group ， MPEG ）提出的 MPEG-1 標準。 MPEG-1 可以對普通質(zhì)量的視頻數(shù)據(jù)進行有效編碼。我們現(xiàn)在看到的大多數(shù) VCD 影碟，就是使用 MPEG-1 標準來壓縮視頻數(shù)據(jù)的。 為了支持更清晰的視頻圖像，特別是支持數(shù)字電視等高端應用， ISO 于 1994 年提出了新的 MPEG-2 標準（相當于 CCITT 的 H.262 標準）。 MPEG-2 對圖像質(zhì)量作了分級處理，可以適應普通電視節(jié)目、會議電視、高清晰數(shù)字電視等不同質(zhì)量的視頻應用。在我們的生活中，可以提供高清晰畫面的 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 ）、線性預測（ LPC ）、矢量量化（ VQ ）、自適應變換編碼（ 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 標準提供了 Layer I 、 Layer II 和 Layer III 共三種可選的音頻壓縮標準， MPEG-2 又進一步引入了 AAC （ Advanced Audio Coding ）音頻壓縮標準， MPEG-4 標準中的音頻部分則同時支持合成聲音編碼和自然聲音編碼等不同類型的應用。在這許多音頻壓縮標準中，聲名最為顯赫的恐怕要數(shù) MPEG-1 Layer III ，也就是我們常說的 MP3 音頻壓縮標準了。從 MP3 播放器到 MP3 手機，從硬盤上堆積如山的 MP3 文件到 Internet 上版權(quán)糾紛不斷的 MP3 下載， MP3 早已超出了數(shù)據(jù)壓縮技術(shù)的范疇，而成了一種時尚文化的象征了。 很顯然，在多媒體信息日益成為主流信息形態(tài)的數(shù)字化時代里，數(shù)據(jù)壓縮技術(shù)特別是專用于圖像、音頻、視頻的數(shù)據(jù)壓縮技術(shù)還有相當大的發(fā)展空間——畢竟，人們對信息數(shù)量和信息質(zhì)量的追求是永無止境的。 回到未來 談到未來，我們還可以補充一些與數(shù)據(jù)壓縮技術(shù)的發(fā)展趨勢有關(guān)的話題。 1994年， M. Burrows 和 D. J. Wheeler 共同提出了一種全新的通用數(shù)據(jù)壓縮算法。這種算法的核心思想是對字符串輪轉(zhuǎn)后得到的字符矩陣進行排序和變換，類似的變換算法被稱為 Burrows-Wheeler 變換，簡稱 BWT 。與 Ziv 和 Lempel 另辟蹊徑的做法如出一轍， Burrows 和 Wheeler 設計的 BWT 算法與以往所有通用壓縮算法的設計思路都迥然不同。如今， BWT 算法在開放源碼的壓縮工具 bzip 中獲得了巨大的成功， bzip 對于文本文件的壓縮效果要遠好于使用 LZ 系列算法的工具軟件。這至少可以表明，即便在日趨成熟的通用數(shù)據(jù)壓縮領(lǐng)域，只要能在思路和技術(shù)上不斷創(chuàng)新，我們?nèi)匀豢梢哉业叫碌耐黄瓶凇? 分形壓縮技術(shù)是圖像壓縮領(lǐng)域近幾年來的一個熱點。這一技術(shù)起源于 B. Mandelbrot 于 1977 年創(chuàng)建的分形幾何學。 M. Barnsley 在 20 世紀 80 年代后期為分形壓縮奠定了理論基礎。從 20 世紀 90 年代開始， A. Jacquin 等人陸續(xù)提出了許多實驗性的分形壓縮算法。今天，很多人相信，分形壓縮是圖像壓縮領(lǐng)域里最有潛力的一種技術(shù)體系，但也有很多人對此不屑一顧。無論其前景如何，分形壓縮技術(shù)的研究與發(fā)展都提示我們，在經(jīng)過了幾十年的高速發(fā)展之后，也許，我們需要一種新的理論，或是幾種更有效的數(shù)學模型，以支撐和推動數(shù)據(jù)壓縮技術(shù)繼續(xù)向前躍進。 人工智能是另一個可能對數(shù)據(jù)壓縮的未來產(chǎn)生重大影響的關(guān)鍵詞。既然 Shannon 認為，信息能否被壓縮以及能在多大程度上被壓縮與信息的不確定性有直接關(guān)系，假設人工智能技術(shù)在某一天成熟起來，假設計算機可以像人一樣根據(jù)已知的少量上下文猜測后續(xù)的信息，那么，將信息壓縮到原大小的萬分之一乃至十萬分之一，恐怕就不再是天方夜譚了。 回顧歷史之后，人們總喜歡暢想一下未來。但未來終究是未來，如果僅憑你我?guī)拙湓捑涂梢岳砬逦磥淼募夹g(shù)發(fā)展趨勢，那技術(shù)創(chuàng)新的工作豈不就索然無味了嗎？依我說，未來并不重要，重要的是，趕快到 Internet 上下載幾部大片，然后躺在沙發(fā)里，好好享受一下數(shù)據(jù)壓縮為我們帶來的無限快樂吧。 |
|
|
