《數(shù)據(jù)壓縮簡(jiǎn)史》PPT課件

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

1、數(shù)據(jù)壓縮簡(jiǎn)史數(shù)據(jù)壓縮簡(jiǎn)史（1）算起來(lái)，數(shù)據(jù)壓縮的起源要比計(jì)算機(jī)的起源早得多，有興趣的讀者可以翻閱一下任何一本成語(yǔ)辭典，查查諸如“二桃三士”、“蕭規(guī)曹隨”之類的短語(yǔ)涵蓋了多少信息內(nèi)容。數(shù)據(jù)壓縮簡(jiǎn)史（2）認(rèn)真一點(diǎn)：數(shù)據(jù)壓縮技術(shù)在計(jì)算機(jī)技術(shù)的萌芽時(shí)期就已經(jīng)被提上了議事日程，有關(guān)信息如何被高效存儲(chǔ)和傳遞的話題不斷被軍事科學(xué)家、數(shù)學(xué)家、電子學(xué)家討論來(lái)、討論去。終于，隨著信息論的產(chǎn)生和發(fā)展，數(shù)據(jù)壓縮也由熱門(mén)話題演變成了真正的技術(shù)。通用無(wú)損數(shù)據(jù)壓縮（1）科學(xué)家在研究中發(fā)現(xiàn)，大多數(shù)信息的表達(dá)都存在著一定的冗余度，通過(guò)采用一定的模型和編碼方法，可以降低這種冗余度。貝爾實(shí)驗(yàn)室的Cl

2、audeShannon和MIT的R.M.Fano幾乎同時(shí)提出了最早的對(duì)符號(hào)進(jìn)行有效編碼從而實(shí)現(xiàn)數(shù)據(jù)壓縮的Shannon-Fano編碼方法。通用無(wú)損數(shù)據(jù)壓縮（2）D.A.Huffman于1952年第一次發(fā)表了他的論文“最小冗余度代碼的構(gòu)造方法”(AMethodfortheConstructionofMinimumRedundancyCodes)。從此，數(shù)據(jù)壓縮開(kāi)始在商業(yè)程序中實(shí)現(xiàn)并被應(yīng)用在許多技術(shù)領(lǐng)域。UNIX系統(tǒng)上一個(gè)不太為現(xiàn)代人熟知的壓縮程序COMPACT就是Huffman0階自適應(yīng)編碼的具體實(shí)現(xiàn)。通用無(wú)損數(shù)據(jù)壓縮（3）80年代初，Huffman編碼又在CP/

3、M和DOS系統(tǒng)中實(shí)現(xiàn)，其代表程序叫SQ。在數(shù)據(jù)壓縮領(lǐng)域，Huffman的這一論文事實(shí)上開(kāi)創(chuàng)了數(shù)據(jù)壓縮技術(shù)一個(gè)值得回憶的時(shí)代，60年代、70年代乃至80年代的早期，數(shù)據(jù)壓縮領(lǐng)域幾乎一直被Huffman編碼及其分支所壟斷。如果不是后面將要提到的那兩個(gè)以色列人，也許Huffman編碼的0和1的組合中仍在壓縮技術(shù)中流連忘返。通用無(wú)損數(shù)據(jù)壓縮（4）讓我們沿著Huffman的軌跡再向后跳躍幾年，80年代，數(shù)學(xué)家們不滿足于Huffman編碼中的某些致命弱點(diǎn)，他們從新的角度入手，遵循Huffman編碼的主導(dǎo)思想，設(shè)計(jì)出另一種更為精確，更能接近信息論中“熵”極限的編碼方法——算術(shù)

4、編碼。憑借算術(shù)編碼的精妙設(shè)計(jì)和卓越表現(xiàn)，人們終于可以向著數(shù)據(jù)壓縮的極限前進(jìn)了。通用無(wú)損數(shù)據(jù)壓縮（5）可以證明，算術(shù)編碼得到的壓縮效果可以最大地減小信息的冗余度，用最少量的符號(hào)精確表達(dá)原始信息內(nèi)容。當(dāng)然，算術(shù)編碼同時(shí)也給程序員和計(jì)算機(jī)帶來(lái)了新的挑戰(zhàn)：要實(shí)現(xiàn)和運(yùn)行算術(shù)編碼，需要更為艱苦的編程勞動(dòng)和更加快速的計(jì)算機(jī)系統(tǒng)。通用無(wú)損數(shù)據(jù)壓縮（6）也就是說(shuō)，在同樣的計(jì)算機(jī)系統(tǒng)上，算術(shù)編碼雖然可以得到最好的壓縮效果，但卻要消耗也許幾十倍的計(jì)算時(shí)間。這就是為什么算術(shù)編碼不能在我們?nèi)粘Ｊ褂玫膲嚎s工具中實(shí)現(xiàn)的主要原因。通用無(wú)損數(shù)據(jù)壓縮（7）那么，能不能既在壓縮效果上超越Huffma

5、n，又不增加程序?qū)ο到y(tǒng)資源和時(shí)間的需求呢？我們必須感謝下面將要介紹的兩個(gè)以色列人。直到1977年，數(shù)據(jù)壓縮的研究工作主要集中于熵、字符和單詞頻率以及統(tǒng)計(jì)模型等方面，研究者們一直在絞盡腦汁為使用Huffman編碼的程序找出更快、更好的改進(jìn)方法。1977年以后，一切都改變了。通用無(wú)損數(shù)據(jù)壓縮（8）1977年，以色列人JacobZiv和AbrahamLempel發(fā)表了論文“順序數(shù)據(jù)壓縮的一個(gè)通用算法”(AUniversalAlogrithemforSequentialDataCompression)。1978年，他們發(fā)表了該論文的續(xù)篇“通過(guò)可變比率編碼的獨(dú)立序列的壓縮

6、”(CompressionofIndividualSequencesviaVariable-RateCoding)。通用無(wú)損數(shù)據(jù)壓縮（9）所有的一切都改變了，在這兩篇論文中提出的兩個(gè)壓縮技術(shù)被稱為L(zhǎng)Z77和LZ78(不知為什么，作者名字的首字母被倒置了)。簡(jiǎn)單地說(shuō)，這兩種壓縮方法的思路完全不同于從Shannon到Huffman到算術(shù)壓縮的傳統(tǒng)思路，倒是和本章開(kāi)頭所舉的成語(yǔ)辭典的例子頗為相似，因此，人們將基于這一思路的編碼方法稱作“字典”式編碼。通用無(wú)損數(shù)據(jù)壓縮（10）字典式編碼不但在壓縮效果上大大超過(guò)了Huffman，而且，對(duì)于好的實(shí)現(xiàn)，其壓縮和解壓縮的速度也異

7、常驚人。通用無(wú)損數(shù)據(jù)壓縮（11）1984年，TerryWelch發(fā)表了名為“高性能數(shù)據(jù)壓縮技術(shù)”(ATechniqueforHigh-PerformanceDataCompression)的論文，描述了他在SperryResearchCenter(現(xiàn)在是Unisys的一部分)的研究成果。他實(shí)現(xiàn)了LZ78算法的一個(gè)變種——LZW。通用無(wú)損數(shù)據(jù)壓縮（12）LZW繼承了LZ77和LZ78壓縮效果好、速度快的優(yōu)點(diǎn)，而且在算法描述上更容易被人們接受（有的研究者認(rèn)為是由于Welch的論文比Ziv和Lempel的更容易理解），實(shí)現(xiàn)也比較簡(jiǎn)單。不久，UNIX上出現(xiàn)了使用LZW算

8、法的Compress程序