基于字典編碼的數(shù)據(jù)壓縮技術(shù)的改進(jìn)與實(shí)現(xiàn)

《基于字典編碼的數(shù)據(jù)壓縮技術(shù)的改進(jìn)與實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、畢業(yè)設(shè)計(jì)報(bào)告1.目錄畢業(yè)設(shè)計(jì)報(bào)告11.目錄12.前言13.對(duì)字典編碼的認(rèn)識(shí)23.1.數(shù)據(jù)壓縮簡(jiǎn)史23.1.1.通用無損數(shù)據(jù)壓縮23.1.2.多媒體信息的壓縮33.2.數(shù)據(jù)壓縮的基本理論與分類43.2.1.什么是熵43.2.2.模型43.2.3.編碼53.2.4.壓縮技術(shù)概貌53.3.字典編碼原理64.字典編碼方法的分類與特點(diǎn)64.1.LZ77算法64.2.LZ78算法74.3.LZSS算法74.4.LZW算法85.＂不足＂與改進(jìn)105.1.對(duì)技術(shù)的改進(jìn)105.1.1.零搜索105.1.2.動(dòng)態(tài)編碼長(zhǎng)度105.2.設(shè)計(jì)方法的改進(jìn)106.算法實(shí)現(xiàn)116.1.數(shù)據(jù)結(jié)構(gòu)116

2、.1.1.常量定義：116.1.2.編碼類：116.1.3.解碼類：126.2.編碼算法136.2.1.流程描述136.2.2.核心代碼136.3.解碼算法176.3.1.流程描述176.3.2.核心代碼187.總結(jié)231.前言1946年,第一臺(tái)計(jì)算機(jī)ENIAC誕生.之后的五十多年里,計(jì)算機(jī)領(lǐng)域有了突飛猛進(jìn)的發(fā)展,計(jì)算機(jī)所能處理的數(shù)據(jù)也是成倍的增長(zhǎng).這就對(duì)數(shù)據(jù)存儲(chǔ)設(shè)備有了更高的要求,同時(shí),數(shù)據(jù)壓縮技術(shù)也應(yīng)運(yùn)而生.尤其是近年來的”信息爆炸”概念的提出,使得數(shù)據(jù)壓縮成為人們爭(zhēng)相研究的對(duì)象,因此學(xué)習(xí)一下數(shù)據(jù)壓縮的知識(shí),研究數(shù)據(jù)壓縮的技術(shù)是十分有必要的.2.對(duì)字典編碼的認(rèn)識(shí)2

3、.1.數(shù)據(jù)壓縮簡(jiǎn)史2.1.1.通用無損數(shù)據(jù)壓縮很早以前,科學(xué)家就在研究中發(fā)現(xiàn)，大多數(shù)信息的表達(dá)都存在著一定的冗余度，通過采用一定的模型和編碼方法，可以降低這種冗余度。1948&1949貝爾實(shí)驗(yàn)室的ClaudeShannon(1948)和MIT的R.M.Fano(1949)幾乎同時(shí)提出了最早的對(duì)符號(hào)進(jìn)行有效編碼從而實(shí)現(xiàn)數(shù)據(jù)壓縮的Shannon-Fano編碼方法。1952D.A.Huffman第一次發(fā)表了他的論文“最小冗余度代碼的構(gòu)造方法”(AMethodfortheConstructionofMinimumRedundancyCodes)。從此，數(shù)據(jù)壓縮開始在商業(yè)程序中

4、實(shí)現(xiàn)并被應(yīng)用在許多技術(shù)領(lǐng)域。在數(shù)據(jù)壓縮領(lǐng)域，Huffman的這一論文事實(shí)上開創(chuàng)了數(shù)據(jù)壓縮技術(shù)一個(gè)值得回憶的時(shí)代，60年代、70年代乃至80年代的早期，數(shù)據(jù)壓縮領(lǐng)域幾乎一直被Huffman編碼及其分支所壟斷。如果不是下面的這兩個(gè)以色列人，也許我們今天還要在Huffman編碼的0和1的組合中流連忘返。1977以色列人JacobZiv和AbrahamLempel發(fā)表了論文“順序數(shù)據(jù)壓縮的一個(gè)通用算法”(AUniversalAlogrithemforSequentialDataCompression)。1978他們發(fā)表了該論文的續(xù)篇“通過可變比率編碼的獨(dú)立序列的壓縮”(Com

5、pressionofIndividualSequencesviaVariable-RateCoding)。所有的一切都改變了，在這兩篇論文中提出的兩個(gè)壓縮技術(shù)被稱為L(zhǎng)Z77和LZ78。簡(jiǎn)單地說，這兩種壓縮方法的思路完全不同于從Shannon到Huffman到算術(shù)壓縮的傳統(tǒng)思路，倒是和本章開頭所舉的成語辭典的例子頗為相似，因此，人們將基于這一思路的編碼方法稱作“字典”式編碼。字典式編碼不但在壓縮效果上大大超過了Huffman，而且，對(duì)于好的實(shí)現(xiàn)，其壓縮和解壓縮的速度也異常驚人。1982Storer與Szymanski對(duì)LZ77算法進(jìn)行了改進(jìn)，并提出相應(yīng)的LZSS算法。1

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

7、了UNIX世界的壓縮程序標(biāo)準(zhǔn)。緊隨其后的是MS-DOS環(huán)境下的ARC程序(SystemEnhancementAssociates,1985)，還有象PKWare、PKARC等仿制品。LZ78和LZW一時(shí)間統(tǒng)治了UNIX和DOS兩大平臺(tái)。1985-人們對(duì)LZ77進(jìn)行了改進(jìn)，隨之誕生了一批我們今天還在大量使用的壓縮程序。HaruyasuYoshizaki(Yoshi)的LHarc和RobertJung的ARJ是其中兩個(gè)著名的例子。LZ77得以和LZ78、LZW一起壟斷當(dāng)今的通用數(shù)據(jù)壓縮領(lǐng)域。目前，基于字典方式的壓縮已經(jīng)有了一個(gè)被廣泛認(rèn)可的標(biāo)準(zhǔn)，從古老的P