數(shù)據(jù)壓縮技術(shù)簡史

《數(shù)據(jù)壓縮技術(shù)簡史》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、數(shù)據(jù)壓縮技術(shù)簡史來源:2003年9月《CSDN開發(fā)高手》作者:王詠剛?????電腦里的數(shù)據(jù)壓縮其實類似于美眉們的瘦身運動，不外有兩大功用。第一，可以節(jié)省空間。拿瘦身美眉來說，要是八個美眉可以擠進(jìn)一輛出租車?yán)铮窃撚卸嗍″X?。〉诙?，可以減少對帶寬的占用。例如，我們都想在不到100Kbps的GPRS網(wǎng)上觀看DVD大片，這就好比瘦身美眉們總希望用一尺布裁出七件吊帶衫，前者有待于數(shù)據(jù)壓縮技術(shù)的突破性進(jìn)展，后者則取決于美眉們的恒心和毅力。?????簡單地說，如果沒有數(shù)據(jù)壓縮技術(shù)，我們就沒法用WinRAR為Email中的附件瘦身；如果沒有數(shù)據(jù)壓縮技術(shù)，市場上的數(shù)碼錄音筆就只能記錄不到20分鐘的語音；如果

2、沒有數(shù)據(jù)壓縮技術(shù)，從Internet上下載一部電影也許要花半年的時間……可是這一切究竟是如何實現(xiàn)的呢？數(shù)據(jù)壓縮技術(shù)又是怎樣從無到有發(fā)展起來的呢？??????概率奇緣?????一千多年前的中國學(xué)者就知道用“班馬”這樣的縮略語來指代班固和司馬遷，這種崇尚簡約的風(fēng)俗一直延續(xù)到了今天的Internet時代：當(dāng)我們在BBS上用“7456”代表“氣死我了”，或是用“B4”代表“Before”的時候，我們至少應(yīng)該知道，這其實就是一種最簡單的數(shù)據(jù)壓縮呀。?????嚴(yán)格意義上的數(shù)據(jù)壓縮起源于人們對概率的認(rèn)識。當(dāng)我們對文字信息進(jìn)行編碼時，如果為出現(xiàn)概率較高的字母賦予較短的編碼，為出現(xiàn)概率較低的字母賦予較長的編碼

3、，總的編碼長度就能縮短不少。遠(yuǎn)在計算機(jī)出現(xiàn)之前，著名的Morse電碼就已經(jīng)成功地實踐了這一準(zhǔn)則。在Morse碼表中，每個字母都對應(yīng)于一個唯一的點劃組合，出現(xiàn)概率最高的字母e被編碼為一個點“.”，而出現(xiàn)概率較低的字母z則被編碼為“--..”。顯然，這可以有效縮短最終的電碼長度。?????信息論之父C.E.Shannon第一次用數(shù)學(xué)語言闡明了概率與信息冗余度的關(guān)系。在1948年發(fā)表的論文“通信的數(shù)學(xué)理論（AMathematicalTheoryofCommunication）”中，Shannon指出，任何信息都存在冗余，冗余大小與信息中每個符號（數(shù)字、字母或單詞）的出現(xiàn)概率或者說不確定性有關(guān)。Sh

4、annon借鑒了熱力學(xué)的概念，把信息中排除了冗余后的平均信息量稱為“信息熵”，并給出了計算信息熵的數(shù)學(xué)表達(dá)式。這篇偉大的論文后來被譽為信息論的開山之作，信息熵也奠定了所有數(shù)據(jù)壓縮算法的理論基礎(chǔ)。從本質(zhì)上講，數(shù)據(jù)壓縮的目的就是要消除信息中的冗余，而信息熵及相關(guān)的定理恰恰用數(shù)學(xué)手段精確地描述了信息冗余的程度。利用信息熵公式，人們可以計算出信息編碼的極限，即在一定的概率模型下，無損壓縮的編碼長度不可能小于信息熵公式給出的結(jié)果。?????有了完備的理論，接下來的事就是要想辦法實現(xiàn)具體的算法，并盡量使算法的輸出接近信息熵的極限了。當(dāng)然，大多數(shù)工程技術(shù)人員都知道，要將一種理論從數(shù)學(xué)公式發(fā)展成實用技術(shù)，就

5、像僅憑一個E=mc2的公式就要去制造核武器一樣，并不是一件很容易的事。?????數(shù)學(xué)游戲?????設(shè)計具體的壓縮算法的過程通常更像是一場數(shù)學(xué)游戲。開發(fā)者首先要尋找一種能盡量精確地統(tǒng)計或估計信息中符號出現(xiàn)概率的方法，然后還要設(shè)計一套用最短的代碼描述每個符號的編碼規(guī)則。統(tǒng)計學(xué)知識對于前一項工作相當(dāng)有效，迄今為止，人們已經(jīng)陸續(xù)實現(xiàn)了靜態(tài)模型、半靜態(tài)模型、自適應(yīng)模型、Markov模型、部分匹配預(yù)測模型等概率統(tǒng)計模型。相對而言，編碼方法的發(fā)展歷程更為曲折一些。?????1948年，Shannon在提出信息熵理論的同時，也給出了一種簡單的編碼方法——Shannon編碼。1952年，R.M.Fano又進(jìn)一

6、步提出了Fano編碼。這些早期的編碼方法揭示了變長編碼的基本規(guī)律，也確實可以取得一定的壓縮效果，但離真正實用的壓縮算法還相去甚遠(yuǎn)。?????第一個實用的編碼方法是由D.A.Huffman在1952年的論文“最小冗余度代碼的構(gòu)造方法（AMethodfortheConstructionofMinimumRedundancyCodes）”中提出的。直到今天，許多《數(shù)據(jù)結(jié)構(gòu)》教材在討論二叉樹時仍要提及這種被后人稱為Huffman編碼的方法。Huffman編碼在計算機(jī)界是如此著名，以至于連編碼的發(fā)明過程本身也成了人們津津樂道的話題。據(jù)說，1952年時，年輕的Huffman還是麻省理工學(xué)院的一名學(xué)生，他

7、為了向老師證明自己可以不參加某門功課的期末考試，才設(shè)計了這個看似簡單，但卻影響深遠(yuǎn)的編碼方法。?????Huffman編碼效率高，運算速度快，實現(xiàn)方式靈活，從20世紀(jì)60年代至今，在數(shù)據(jù)壓縮領(lǐng)域得到了廣泛的應(yīng)用。例如，早期UNIX系統(tǒng)上一個不太為現(xiàn)代人熟知的壓縮程序COMPACT實際就是Huffman0階自適應(yīng)編碼的具體實現(xiàn)。20世紀(jì)80年代初，Huffman編碼又出現(xiàn)在CP/M和DOS系統(tǒng)中，其代表程序叫S