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

《數(shù)據(jù)壓縮技術(shù)簡(jiǎn)史》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、數(shù)據(jù)壓縮技術(shù)簡(jiǎn)史來(lái)源:2003年9月《CSDN開(kāi)發(fā)高手》作者:王詠剛?????電腦里的數(shù)據(jù)壓縮其實(shí)類(lèi)似于美眉們的瘦身運(yùn)動(dòng)，不外有兩大功用。第一，可以節(jié)省空間。拿瘦身美眉來(lái)說(shuō)，要是八個(gè)美眉可以擠進(jìn)一輛出租車(chē)?yán)?，那該有多省錢(qián)?。〉诙?，可以減少對(duì)帶寬的占用。例如，我們都想在不到100Kbps的GPRS網(wǎng)上觀(guān)看DVD大片，這就好比瘦身美眉們總希望用一尺布裁出七件吊帶衫，前者有待于數(shù)據(jù)壓縮技術(shù)的突破性進(jìn)展，后者則取決于美眉們的恒心和毅力。?????簡(jiǎn)單地說(shuō)，如果沒(méi)有數(shù)據(jù)壓縮技術(shù)，我們就沒(méi)法用WinRAR為Email中的附件瘦身；如果沒(méi)有數(shù)據(jù)壓縮技術(shù)，市

2、場(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è)贐BS上用“7456”代表“氣死我了”，或是用“B4”代表“Before”的時(shí)候，我們至少應(yīng)該知道，這其實(shí)就是一種最簡(jiǎn)單的數(shù)據(jù)壓縮呀。?????嚴(yán)格意義上的數(shù)據(jù)壓縮起源于人們對(duì)概率的認(rèn)識(shí)。當(dāng)

3、我們對(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é)理論（AMathematicalTheoryofC

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

5、小于信息熵公式給出的結(jié)果。?????有了完備的理論，接下來(lái)的事就是要想辦法實(shí)現(xiàn)具體的算法，并盡量使算法的輸出接近信息熵的極限了。當(dāng)然，大多數(shù)工程技術(shù)人員都知道，要將一種理論從數(shù)學(xué)公式發(fā)展成實(shí)用技術(shù)，就像僅憑一個(gè)E=mc2的公式就要去制造核武器一樣，并不是一件很容易的事。?????數(shù)學(xué)游戲?????設(shè)計(jì)具體的壓縮算法的過(guò)程通常更像是一場(chǎng)數(shù)學(xué)游戲。開(kāi)發(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)模型

6、、自適應(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)造方法（AMethodfortheConstructionofMinimu

7、mRedundancyCodes）”中提出的。直到今天，許多《數(shù)據(jù)結(jié)構(gòu)》教材在討論二叉樹(shù)時(shí)仍要提及這種被后人稱(chēng)為Huffman編碼的方法。Huffman編碼在計(jì)算機(jī)界是如此著名，以至于連編碼的發(fā)明過(guò)程本身也成了人們津津樂(lè)道的話(huà)題。據(jù)說(shuō)，1952年時(shí)，年輕的Huffman還是麻省理工學(xué)院的一名學(xué)生，他為了向老師證明自己可以不參加某門(mén)功課的期末考試，才設(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)

8、代人熟知的壓縮程序COMPACT實(shí)際就是Huffman0階自適應(yīng)編碼的具體實(shí)現(xiàn)。20世紀(jì)80年代初，Huffman編碼又出現(xiàn)在CP/M和DOS系統(tǒng)中，其代表程序叫S