無(wú)損數(shù)據(jù)壓縮算法歷史

《無(wú)損數(shù)據(jù)壓縮算法歷史》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、無(wú)損數(shù)據(jù)壓縮算法的歷史引言有兩種主要的壓縮算法：有損和無(wú)損。有損壓縮算法通過(guò)移除在保真情形下需要大量的數(shù)據(jù)去存儲(chǔ)的小細(xì)節(jié)，從而使文件變小。在有損壓縮里，因某些必要數(shù)據(jù)的移除，恢復(fù)原文件是不可能的。有損壓縮主要用來(lái)存儲(chǔ)圖像和音頻文件，同時(shí)通過(guò)移除數(shù)據(jù)可以達(dá)到一個(gè)比較高的壓縮率，不過(guò)本文不討論有損壓縮。無(wú)損壓縮，也使文件變小，但對(duì)應(yīng)的解壓縮功能可以精確的恢復(fù)原文件，不丟失任何數(shù)據(jù)。無(wú)損數(shù)據(jù)壓縮被廣泛的應(yīng)用在計(jì)算機(jī)領(lǐng)域，從節(jié)省你個(gè)人電腦的空間，到通過(guò)web發(fā)送數(shù)據(jù)。使用SecureShell交流，查看PNG或GIF圖片。無(wú)損壓縮算法

2、可行的基本原理是，任意一個(gè)非隨機(jī)文件都含有重復(fù)數(shù)據(jù)，這些重復(fù)數(shù)據(jù)可以通過(guò)用來(lái)確定字符或短語(yǔ)出現(xiàn)概率的統(tǒng)計(jì)建模技術(shù)來(lái)壓縮。統(tǒng)計(jì)模型可以用來(lái)為特定的字符或者短語(yǔ)生成代碼，基于它們出現(xiàn)的頻率，配置最短的代碼給最常用的數(shù)據(jù)。這些技術(shù)包括熵編碼(entropyencoding)、游程編碼(run-lengthencoding)以及字典壓縮。運(yùn)用這些技術(shù)以及其它技術(shù)，一個(gè)8-bit長(zhǎng)度的字符或者字符串可以用很少的bit來(lái)表示，從而大量的重復(fù)數(shù)據(jù)被移除。歷史直到20世紀(jì)70年代，數(shù)據(jù)壓縮才在計(jì)算機(jī)領(lǐng)域開始扮演重要角色，那時(shí)互聯(lián)網(wǎng)變得更加流行

3、，Lempel-Ziv算法被發(fā)明出來(lái)，但壓縮算法在計(jì)算機(jī)領(lǐng)域之外有著更悠久的歷史。發(fā)明于1838年的Morsecode，是最早的數(shù)據(jù)壓縮實(shí)例，為英語(yǔ)中最常用的字母比如”e”和”t”分配更短的Morsecode。之后，隨著大型機(jī)的興起，ClaudeShannon和RobertFano發(fā)明了Shannon-Fano編碼算法。他們的算法基于符號(hào)(symbol)出現(xiàn)的概率來(lái)給符號(hào)分配編碼(code)。一個(gè)符號(hào)出現(xiàn)的概率大小與對(duì)應(yīng)的編碼成反比，從而用更短的方式來(lái)表示符號(hào)。兩年后，DavidHuffman在MIT學(xué)習(xí)信息理論并上了一門Ro

4、bertFano老師的課，F(xiàn)ano給班級(jí)的同學(xué)兩個(gè)選項(xiàng)，寫一篇學(xué)期論文或者參加期末考試。Huffman選擇的是寫學(xué)期論文，題目是尋找二叉編碼的最優(yōu)算法。經(jīng)過(guò)幾個(gè)月的努力后依然沒有任何成果，Huffman決定放棄所有論文相關(guān)的工作，開始學(xué)習(xí)為參加期末考試做準(zhǔn)備。正在那時(shí)，靈感爆發(fā)，Huffman找到一個(gè)與Shannon-Fano編碼相類似但是更有效的編碼算法。Shannon-Fano編碼和Huffman編碼的主要區(qū)別是構(gòu)建概率樹的過(guò)程不同，前者是自下而上，得到一個(gè)次優(yōu)結(jié)果，而后者是自上而下。早期的Shannon-Fano編碼和H

5、uffman編碼算法實(shí)現(xiàn)是使用硬件和硬編碼完成的。直到20世紀(jì)70年代互聯(lián)網(wǎng)以及在線存儲(chǔ)的出現(xiàn)，軟件壓縮才被實(shí)現(xiàn)為Huffman編碼依據(jù)輸入數(shù)據(jù)動(dòng)態(tài)產(chǎn)生。隨后，1977年AbrahamLempel和JacobZiv發(fā)表了他們獨(dú)創(chuàng)性的LZ77算法，第一個(gè)使用字典來(lái)壓縮數(shù)據(jù)的算法。特別的，LZ77使用了一個(gè)叫做slidingwindow的動(dòng)態(tài)字典。1978年，這對(duì)搭檔發(fā)表了同樣使用字典的LZ78算法。與LZ77不同，LZ78解析輸入數(shù)據(jù)，生成一個(gè)靜態(tài)字典，不像LZ77動(dòng)態(tài)產(chǎn)生。法律問(wèn)題LZ77和LZ78都快速的流行開來(lái)，衍生出多個(gè)

6、下圖中所示的壓縮算法。其中的大多數(shù)已經(jīng)沉寂了，只有那么幾個(gè)現(xiàn)在被大范圍的使用，包括DEFLATE，LZMA以及LZX。絕大多數(shù)常用的壓縮算法都衍生于LZ77，這不是因?yàn)長(zhǎng)Z77技術(shù)更好，只是由于Sperry在1984年申請(qǐng)了LZ78衍生算法LZW的專利，從而發(fā)展受到了專利的阻礙，Sperry開始因?qū)＠謾?quán)而起訴軟件提供商，服務(wù)器管理員，甚至是使用GIF格式但沒有License的終端用戶。同時(shí)，UNIX壓縮工具使用了一個(gè)叫LZC的LZW算法微調(diào)整版本，之后由于專利問(wèn)題而被棄用。其他的UNIX開發(fā)者也開始放棄使用LZW。這導(dǎo)致UN

7、IX社區(qū)采用基于DEFLATE的gzip和基于Burrows-WheelerTransform的bzip2算法。長(zhǎng)遠(yuǎn)來(lái)說(shuō)，對(duì)于UNIX社區(qū)這是有好處的，因?yàn)間zip和bzip2格式幾乎總是比LZW有更好的壓縮比。圍繞LZW的專利問(wèn)題已經(jīng)結(jié)束，因?yàn)長(zhǎng)ZW的專利2003年就到期了。盡管這樣，LZW算法已經(jīng)很大程度上被替代掉了，僅僅被使用于GIF壓縮中。自那以后，也有一些LZW的衍生算法，不過(guò)都沒有流行開來(lái)，LZ77算法仍然是主流。另外一場(chǎng)法律官司發(fā)生于1993，關(guān)于LZS算法。LZS是由StacElectronics開發(fā)的，用于硬

8、盤壓縮軟件，如Stacker。微軟在開發(fā)影片壓縮軟件時(shí)使用了LZS算法，開發(fā)的軟件隨著MS-DOS6.0一起發(fā)布，聲稱能夠使硬盤容量翻倍。當(dāng)StacElectronics發(fā)現(xiàn)自己的知識(shí)財(cái)產(chǎn)被使用后，起訴了微軟。微軟隨后被判專利侵權(quán)并賠償StacElectronics1億200