數(shù)據(jù)壓縮的發(fā)展歷程

《數(shù)據(jù)壓縮的發(fā)展歷程》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、數(shù)據(jù)壓縮的發(fā)展歷程[摘要]從最早的莫爾斯電報碼到香農(nóng)第一次用數(shù)學語言闡明了概率與信息冗余度的關系;從第一個實用的編碼方法到算術(shù)編碼;從LZ系列算法到JPEG有損壓縮編碼做了簡要介紹,使讀者了解數(shù)據(jù)壓縮技術(shù)發(fā)展歷程。[關鍵詞]數(shù)據(jù)壓縮;壓縮算法;編碼方法;信息冗余;多媒體信息DataCompressionandItsDevelopmentCourse[Abstract]TherelationshipbetweenprobabilityandinformationredundancydegreehasexpoundedfromearliestMorsetelegraphc

2、odetoShannon.Ithasmadethesimpleintroduction,fromfirstpracticalcodemethodtoarithmeticcode,fromLZseriesalgorithmtoJPEGdamagecompressioncode,whichmakesthereadertounderstandthedatacompressiontechnologicaldevelopmentcourse.[Keywords]datacompression;compressionalgorithm;codemethod;information

3、redundancy;multimediainformation0前言　　在當今的電子信息技術(shù)領域,正發(fā)生著一場有長遠影響的數(shù)字化革命。由于數(shù)字化的多媒體信息尤其是數(shù)字視頻和音頻信號的數(shù)據(jù)量特別龐大,如果不對其進行有效的壓縮就難以得到實際的應用。簡單地說,如果沒有數(shù)據(jù)壓縮技術(shù),我們就沒有辦法壓縮網(wǎng)頁中的圖象,也許打開一個網(wǎng)頁需要半個小時;如果沒有數(shù)據(jù)壓縮技術(shù),從Internet上下載一部電影也許要花半年的時間......,現(xiàn)實中可比這快多了?？墒沁@一切究竟是如何實現(xiàn)的呢?數(shù)據(jù)壓縮技術(shù)又是怎樣從無到有發(fā)展起來的呢?一千多年前的中國學者就知道用“班馬”這樣的縮略語來指代班

4、固和司馬遷,用這種崇尚簡約的風俗一直延續(xù)到了今天的Internet時代:當我們在QQ上用“886”代表“拜拜”的時候,至少應該知道,這其實就是一種最簡單的數(shù)據(jù)壓縮。1　數(shù)據(jù)壓縮的發(fā)展嚴格意義上的數(shù)據(jù)壓縮起源于人們對概率的認識。當我們對文字信息進行編碼時,如果為出現(xiàn)概率較高的字母賦予較短的編碼,為出現(xiàn)概率較低的字母賦予較長的編碼,總的編碼長度就能縮短不少。遠在計算機出現(xiàn)之前,著名的莫爾斯電報碼就已經(jīng)成功地實踐了這一準則[1]。在莫爾斯碼表中,每個字母都對應于一個唯一的點劃組合,出現(xiàn)概率最高的字母e被編碼為一個點“.”,而出現(xiàn)概率較低的字母z則被編碼為“--..”。顯然,

5、這可以有效縮短最終的電碼長度[1]。111　數(shù)據(jù)壓縮的起源信息論之父香農(nóng)第一次用數(shù)學語言闡明了概率與信息冗余度的關系。在1948年發(fā)表的論文“通信的數(shù)學理論”中,香農(nóng)指出,任何信息都存在冗余,冗余大小與信息中每個符號(數(shù)字、字母或單詞)的出現(xiàn)概率或者說不確定性有關。香農(nóng)借鑒了熱力學的概念,把信息中排除了冗余后的平均信息量稱為“信息熵”,并給出了計算信息熵的數(shù)學表達式[2]。這篇偉大的論文后來被譽為信息論的開山之作,信息熵也奠定了所有數(shù)據(jù)壓縮算法的理論基礎。從本質(zhì)上講,數(shù)據(jù)壓縮的目的就是要消除信息中的冗余,而信息熵及相關的定理恰恰用數(shù)學手段精確地描述了信息冗余的程度。利

6、用信息熵公式,人們可以計算出信息編碼的極限,即在一定的概率模型下,無損壓縮的編碼長度不可能小于信息熵公式給出的結(jié)果[3]。1948年香農(nóng)在提出信息熵理論的同時,也給出了一種簡單的編碼方法--香農(nóng)編碼。這些早期的編碼方法揭示了變長編碼的基本規(guī)律,也確實可以取得一定的壓縮效果,但離真正實用的壓縮算法還相差很遠。112　真正的編碼第一個實用的編碼方法是由哈夫曼在1952年的論文“最小冗余度代碼的構(gòu)造方法”中提出的。直到今天,許多《數(shù)據(jù)結(jié)構(gòu)》教材在討論二叉樹時仍要提及這種被后人稱為哈夫曼編碼的方法。哈夫曼編碼在計算機界是如此著名,以至于連編碼的發(fā)明過程本身也成了人們津津樂道的

7、話題。據(jù)說,1952年年輕的哈夫曼還是麻省理工學院的一名學生,他為了向老師證明自己可以不參加某門功課的期末考試,才設計了這個看似簡單,但卻影響深遠的編碼方法。哈夫曼編碼效率高,運算速度快,實現(xiàn)方式靈活,從20世紀60年代至今,在數(shù)據(jù)壓縮領域得到了廣泛的應用。例如,早期UNIX系統(tǒng)上一個不太為現(xiàn)代人熟知的壓縮程序COMPACT實際就是哈夫曼0階自適應編碼的具體實現(xiàn)。20世紀80年代初,哈夫曼編碼又出現(xiàn)在CP/M和DOS系統(tǒng)中,其代表程序叫SQ。今天,在許多知名的壓縮工具和壓縮算法(如WinRAR、gzip)中,都有哈夫曼編碼的身影。不過哈夫曼編碼所得的