資源描述：
《數(shù)據(jù)壓縮的發(fā)展歷程》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、數(shù)據(jù)壓縮的發(fā)展歷程[摘要]從最早的莫爾斯電報碼到香農(nóng)第一次用數(shù)學(xué)語言闡明了概率與信息冗余度的關(guān)系;從第一個實(shí)用的編碼方法到算術(shù)編碼;從LZ系列算法到JPEG有損壓縮編碼做了簡要介紹,使讀者了解數(shù)據(jù)壓縮技術(shù)發(fā)展歷程。[關(guān)鍵詞]數(shù)據(jù)壓縮;壓縮算法;編碼方法;信息冗余;多媒體信息DataCompressionandItsDevelopmentCourse[Abstract]Therelationshipbetweenprobabilityandinformationredundancydegreehasexpoundedfromearli
2、estMorsetelegraphcodetoShannon.Ithasmadethesimpleintroduction,fromfirstpracticalcodemethodtoarithmeticcode,fromLZseriesalgorithmtoJPEGdamagecompressioncode,whichmakesthereadertounderstandthedatacompressiontechnologicaldevelopmentcourse.[Keywords]datacompression;compres
3、sionalgorithm;codemethod;informationredundancy;multimediainformation0前言 在當(dāng)今的電子信息技術(shù)領(lǐng)域,正發(fā)生著一場有長遠(yuǎn)影響的數(shù)字化革命。由于數(shù)字化的多媒體信息尤其是數(shù)字視頻和音頻信號的數(shù)據(jù)量特別龐大,如果不對其進(jìn)行有效的壓縮就難以得到實(shí)際的應(yīng)用。簡單地說,如果沒有數(shù)據(jù)壓縮技術(shù),我們就沒有辦法壓縮網(wǎng)頁中的圖象,也許打開一個網(wǎng)頁需要半個小時;如果沒有數(shù)據(jù)壓縮技術(shù),從Internet上下載一部電影也許要花半年的時間......,現(xiàn)實(shí)中可比這快多了?？墒沁@一切究竟是如何
4、實(shí)現(xiàn)的呢?數(shù)據(jù)壓縮技術(shù)又是怎樣從無到有發(fā)展起來的呢?一千多年前的中國學(xué)者就知道用“班馬”這樣的縮略語來指代班固和司馬遷,用這種崇尚簡約的風(fēng)俗一直延續(xù)到了今天的Internet時代:當(dāng)我們在QQ上用“886”代表“拜拜”的時候,至少應(yīng)該知道,這其實(shí)就是一種最簡單的數(shù)據(jù)壓縮。1 數(shù)據(jù)壓縮的發(fā)展嚴(yán)格意義上的數(shù)據(jù)壓縮起源于人們對概率的認(rèn)識。當(dāng)我們對文字信息進(jìn)行編碼時,如果為出現(xiàn)概率較高的字母賦予較短的編碼,為出現(xiàn)概率較低的字母賦予較長的編碼,總的編碼長度就能縮短不少。遠(yuǎn)在計算機(jī)出現(xiàn)之前,著名的莫爾斯電報碼就已經(jīng)成功地實(shí)踐了這一準(zhǔn)則[1]。在
5、莫爾斯碼表中,每個字母都對應(yīng)于一個唯一的點(diǎn)劃組合,出現(xiàn)概率最高的字母e被編碼為一個點(diǎn)“.”,而出現(xiàn)概率較低的字母z則被編碼為“--..”。顯然,這可以有效縮短最終的電碼長度[1]。111 數(shù)據(jù)壓縮的起源信息論之父香農(nóng)第一次用數(shù)學(xué)語言闡明了概率與信息冗余度的關(guān)系。在1948年發(fā)表的論文“通信的數(shù)學(xué)理論”中,香農(nóng)指出,任何信息都存在冗余,冗余大小與信息中每個符號(數(shù)字、字母或單詞)的出現(xiàn)概率或者說不確定性有關(guān)。香農(nóng)借鑒了熱力學(xué)的概念,把信息中排除了冗余后的平均信息量稱為“信息熵”,并給出了計算信息熵的數(shù)學(xué)表達(dá)式[2]。這篇偉大的論文后來
6、被譽(yù)為信息論的開山之作,信息熵也奠定了所有數(shù)據(jù)壓縮算法的理論基礎(chǔ)。從本質(zhì)上講,數(shù)據(jù)壓縮的目的就是要消除信息中的冗余,而信息熵及相關(guān)的定理恰恰用數(shù)學(xué)手段精確地描述了信息冗余的程度。利用信息熵公式,人們可以計算出信息編碼的極限,即在一定的概率模型下,無損壓縮的編碼長度不可能小于信息熵公式給出的結(jié)果[3]。1948年香農(nóng)在提出信息熵理論的同時,也給出了一種簡單的編碼方法--香農(nóng)編碼。這些早期的編碼方法揭示了變長編碼的基本規(guī)律,也確實(shí)可以取得一定的壓縮效果,但離真正實(shí)用的壓縮算法還相差很遠(yuǎn)。112 真正的編碼第一個實(shí)用的編碼方法是由哈夫曼在
7、1952年的論文“最小冗余度代碼的構(gòu)造方法”中提出的。直到今天,許多《數(shù)據(jù)結(jié)構(gòu)》教材在討論二叉樹時仍要提及這種被后人稱為哈夫曼編碼的方法。哈夫曼編碼在計算機(jī)界是如此著名,以至于連編碼的發(fā)明過程本身也成了人們津津樂道的話題。據(jù)說,1952年年輕的哈夫曼還是麻省理工學(xué)院的一名學(xué)生,他為了向老師證明自己可以不參加某門功課的期末考試,才設(shè)計了這個看似簡單,但卻影響深遠(yuǎn)的編碼方法。哈夫曼編碼效率高,運(yùn)算速度快,實(shí)現(xiàn)方式靈活,從20世紀(jì)60年代至今,在數(shù)據(jù)壓縮領(lǐng)域得到了廣泛的應(yīng)用。例如,早期UNIX系統(tǒng)上一個不太為現(xiàn)代人熟知的壓縮程序COMPA
8、CT實(shí)際就是哈夫曼0階自適應(yīng)編碼的具體實(shí)現(xiàn)。20世紀(jì)80年代初,哈夫曼編碼又出現(xiàn)在CP/M和DOS系統(tǒng)中,其代表程序叫SQ。今天,在許多知名的壓縮工具和壓縮算法(如WinRAR、gzip)中,都有哈夫曼編碼的身影。不過哈夫曼編碼所得的
