算術(shù)編碼與哈夫曼編碼

安徽大學(xué)本科畢業(yè)論文（設(shè)計(jì)、創(chuàng)作）題目哈夫曼編碼與算術(shù)編碼壓縮效率比較學(xué)生姓名：李偉學(xué)號(hào)：E20714134院（系）：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)：軟件工程入學(xué)時(shí)間：2007年9 月導(dǎo)師姓名：韓莉職稱/學(xué)位:講師/碩士導(dǎo)師所在單位：安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院完成時(shí)間：2011年5 月哈夫曼編碼與算術(shù)編碼壓縮效率比較摘要算術(shù)編碼和哈夫曼編碼都利用信源符號(hào)的概率分布特性進(jìn)行編碼，使平均碼長逼近信息熵是壓縮編碼算法的第一要求，算術(shù)編碼比哈夫曼編碼逼近信息熵的能力要強(qiáng)，但是編碼效率和實(shí)現(xiàn)往往是一對(duì)矛盾，編碼效率的提高，往往要在實(shí)現(xiàn)上付出代價(jià)，所以，選擇壓縮算要權(quán)衡這兩點(diǎn)。本論文開篇先引入了信息論的一些概念，因?yàn)榫幋a理論發(fā)源于信息論，是各種編碼算法的數(shù)學(xué)基礎(chǔ)。然后在第2章分析了算術(shù)編碼原理，并從無限精度的算術(shù)編碼原理過渡到在計(jì)算機(jī)上能夠?qū)崿F(xiàn)的二進(jìn)制編碼原理。在第3章緊接著介紹了哈夫曼編碼原理，并討論了怎樣把信源符號(hào)映射為對(duì)應(yīng)的碼字，過程中用到的哈夫曼編碼表是編碼與解碼的關(guān)鍵。在第4章對(duì)兩者的編碼效率作了比較，主要是結(jié)合信息論中的一些概念從微觀上對(duì)兩者逼近信息熵的能力作了比較，并在這章最后對(duì)兩者在文本文件的壓縮效果的表現(xiàn)上給出了一些實(shí)驗(yàn)結(jié)果。最后，在5章，主要是對(duì)前面內(nèi)容做了些補(bǔ)充和總結(jié)。關(guān)鍵詞：信息熵；算術(shù)編碼；哈夫曼編碼；編碼效率ThecomparisonofHuffmanCodingandArithmeticCodinginFile

Compression

AbstractFulluseoftheprobabilitydistributionofsourcesymbolsisthefeatureofthearithmeticencodingandHuffmanencoding.Approachingtheaveragecodelengthtotheinformationentropycomefirstwhendesigningacompressionalgorithm.Tothecapacityofclosingtoinformationentropy,arithmeticencodingisstrongerthanHuffmanencoding.However,thecodingefficiencyandimplementationisoftenacontradiction:toimprovecodingefficiency,whichmeansthealgorithmimplementationprocessneedstopayahigherprice.Therefore,youneedtoweighbothwhenchoosingacompressionalgorithm.Inthebeginningofthisthesis,itfirstintroducedsomeoftheconceptsofinformationtheory.Becauseencodingalgorithmsarederivedfrominformationtheoryandinformationtheoryisthemathematicalfoundationofvariouscodingalgorithms.TheninChapter2,itintroducestheprincipleofarithmeticcoding.Forbettertounderstandthebinaryarithmeticcodingprinciple,itfirstintroducestheunlimitedprecisionarithmeticcoding.InChapter3,itdescribestheHuffmancodingtheory,anddiscusseshowtomapsourcesymboltothecorrespondingcodeword,amongwhichHuffmancodinganddecodingtableisthekey.InChapter4,thecodingefficiencyofthetwoalgorithmsiscompared.Mainlycomparethecapacitiestoapproximateinformationentropywithsomeoftheconceptsininformationtheory.Andthefinalpartinthischapter,someexperimentalresultsaregiventoshowthecompressioneffecttocompressatextfile.Finally,inChapter5,itgivessomeadditionsandsummary.Keywords:InformationEntropy;ArithmeticCoding;HuffmanCoding;CodingEfficiency目錄引言??????????????????????????????1數(shù)據(jù)壓縮概念及技術(shù)分類????????????????????1統(tǒng)計(jì)編碼的數(shù)學(xué)準(zhǔn)備??????????????????????2統(tǒng)計(jì)編碼簡(jiǎn)介?????????????????????????5算術(shù)編碼????????????????????????????5算術(shù)編碼簡(jiǎn)介?????????????????????????5無限精度的算術(shù)編碼??????????????????????6二進(jìn)制編碼??????????????????????????9二進(jìn)制解碼??????????????????????????13哈夫曼編碼???????????????????????????14哈夫曼編碼簡(jiǎn)介????????????????????????14哈夫曼編碼原理????????????????????????14哈夫曼解碼原理????????????????????????16哈夫曼編碼與解碼系統(tǒng)模型???????????????????16哈夫曼編碼形式不唯一?????????????????????17算術(shù)編碼與哈夫曼編碼的比較???????????????????17兩者編碼效率的比較??????????????????????17兩者壓縮率的比較???????????????????????19總結(jié)??????????????????????????????20主要參考文獻(xiàn)???????????????????????????22致謝???????????????????????????????231引言1.1數(shù)據(jù)壓縮概念及技術(shù)分類數(shù)據(jù)壓縮，就是將信息的一種表示方式轉(zhuǎn)換為另一種表示方式，信息的新的表示方式與原有表示方式相比較所含的信息量相同或是在可以承受的范圍內(nèi)有所損失，但是新的表示方式所用到的符號(hào)數(shù)量要比原有表示方式要盡可能的少。數(shù)據(jù)壓縮是必要的，不管是在生物系統(tǒng)中還是在人工系統(tǒng)中都存在數(shù)據(jù)壓縮。尤其是處在這個(gè)信息爆炸的時(shí)代，怎樣更有效的存儲(chǔ)信息和傳遞信息對(duì)于文明進(jìn)步的作用都是顯而易見的。從不同視角看到的數(shù)據(jù)壓縮的益處有：在通信信道上更快的傳輸信息，這就相應(yīng)的減少了信道的占有時(shí)間，這可看作在時(shí)間上進(jìn)行了壓縮；在同一通信信道上并行的傳輸各種頻率的互不干擾的信息，如xDSL技術(shù)在普通電話線上實(shí)現(xiàn)把低端頻譜留給傳統(tǒng)電話使用，把高端頻譜留給上網(wǎng)用戶使用，這可看作在頻率域上進(jìn)行了壓縮；傳輸信號(hào)當(dāng)然需要能量消耗，因此對(duì)數(shù)據(jù)進(jìn)行壓縮也就間接地減少了能量消耗，這可看作是在能量上進(jìn)行了壓縮；各種存儲(chǔ)系統(tǒng)的存儲(chǔ)空間都不是無限的，對(duì)數(shù)據(jù)進(jìn)行壓縮后，就可以在同樣的存儲(chǔ)空間存儲(chǔ)更多的數(shù)據(jù)，這可看作是空間上的壓縮。任何系統(tǒng)，尤其在活動(dòng)時(shí)，都同時(shí)涉及到時(shí)間、空間和能量上的消耗，所以數(shù)據(jù)壓縮就是從這三方面同時(shí)進(jìn)行了壓縮，這樣就使得系統(tǒng)更加的有效的運(yùn)行。既然數(shù)據(jù)壓縮是必要的，那么就要考慮從哪些方面來說數(shù)據(jù)可以被壓縮，一般可從以下幾方面考察：一是，數(shù)據(jù)中通常存在著多余成分，即允余度。例如，存儲(chǔ)在計(jì)算機(jī)上的一份文本文件，內(nèi)容可假設(shè)是一部英文小說，可以想象，26個(gè)英文字母重復(fù)出現(xiàn)，各個(gè)字母出現(xiàn)的頻率有大有小，而且不僅字母重復(fù)出現(xiàn)，字母組成的單詞也重復(fù)出現(xiàn)，進(jìn)一步，某些字母總是在某單詞的一定位置上以高概率重復(fù)出現(xiàn)，某些單詞也總是在一個(gè)特定句式的特定位置以高概率重復(fù)出現(xiàn)等等，計(jì)算機(jī)是以二進(jìn)制形式存儲(chǔ)文件的，那么用二進(jìn)制符號(hào)怎樣有效的表示這個(gè)由英文字符、各種標(biāo)點(diǎn)符號(hào)和控制字符組成的文本文件就是怎樣對(duì)數(shù)據(jù)進(jìn)行壓縮的問題，而壓縮顯然就要利用這些允余度的不同類型，例如，我們賦予高概率字符以相對(duì)少的二進(jìn)制位數(shù)，賦予低概率字符以相對(duì)多的的二進(jìn)制位數(shù)，那么這樣表示后所得的總的二進(jìn)制位數(shù)肯定比不考慮各個(gè)字符出現(xiàn)概率，而給不同字符按照ASCII碼分配二進(jìn)制位數(shù)所得的總的二進(jìn)制位數(shù)要少很多。二是，數(shù)據(jù)中的各個(gè)部分前后之間總是存在著相關(guān)性。例如，電視上顯示的動(dòng)態(tài)畫面，實(shí)際上是由離散的不同畫面（幀）組成的，之所以看似是連續(xù)的只是因?yàn)閹牟シ潘俣瘸^了人類的反應(yīng)速度并且利用了人類的視覺暫留效應(yīng)，但為使畫面看似連續(xù)，不僅要利用人類本身的生物特性，還要保證幀之間的過渡是相對(duì)平滑的，也就是相鄰兩幀之間只有動(dòng)態(tài)上的細(xì)微變化，而大部分畫面在兩幀之間是相同的，很顯然，這種相關(guān)性是可以很好的加以利用的。三是，對(duì)于人而言，我們的感受器只能接受外界中很小一部分的信息。例如，人眼只能感受陽光中的可見光，而對(duì)紫外光不可見，但一些昆蟲如蜜蜂卻能感受紫外光，如果人為的屏蔽掉紫外光部分，對(duì)人眼而言，我們并不能對(duì)屏蔽前與屏蔽后的陽光加以區(qū)分，但蜜蜂就不同了，可能就因?yàn)闊o法感受紫外光，就找不到花蜜了，所以，對(duì)于人而言，并不是數(shù)據(jù)中所有的信息對(duì)我們都是必要的，不必要的部分就可以屏蔽掉。數(shù)據(jù)壓縮可分為無損壓縮和有損壓縮，下面分別簡(jiǎn)要的介紹可逆壓縮和不可逆壓縮：可逆壓縮，是利用數(shù)據(jù)的統(tǒng)計(jì)特性，即數(shù)據(jù)的允余度進(jìn)行壓縮的一類方法，允余度的去除或是減少并不影響原始數(shù)據(jù)無失真的恢復(fù)，即是一個(gè)可逆的過程。但從編碼效率上來講，可逆壓縮受到待編碼數(shù)據(jù)本身的信息熵的限制，無法達(dá)到更高的編碼效率。也就是由于這樣的限制，僅使用可逆壓縮方法是不可能解決多媒體的存儲(chǔ)和傳輸?shù)乃袉栴}的，因此，這類方法一般適用于在壓縮過程中不允許有絲毫損失的情況，如在計(jì)算機(jī)磁盤上存儲(chǔ)文件，數(shù)據(jù)通信等領(lǐng)域。常用的可逆壓縮方法有：哈夫曼編碼、算術(shù)編碼、LZW編碼等。不可逆壓縮，是利用人類對(duì)圖像或聲波中的某些頻率成分的不敏感特性，允許壓縮過程中損失一定的信息，雖然不能完全恢復(fù)原始數(shù)據(jù)，但是所損失的部分對(duì)人類理解理解原始數(shù)據(jù)的影響可承受，好處就是與可逆壓縮相比，能夠獲得更高的編碼效率，因此，廣泛適用與語音、圖像和視頻數(shù)據(jù)的壓縮。不可逆壓縮的方法有很多，這里不列舉。統(tǒng)計(jì)編碼的數(shù)學(xué)準(zhǔn)備統(tǒng)計(jì)編碼某種程度上與可逆壓縮同義，因此可混用。在1.1節(jié)中，我們用到了允余度和信息熵的概念，這兩個(gè)概念都由信息論的開創(chuàng)者香農(nóng)(ClaudeE.shannon)首次提出，因此這一小節(jié)主要介紹信息論中的一些概念，這些概念有助于我們更好的理解統(tǒng)計(jì)編碼。信源空間概念：X: a a a—a信源空間表示為：123mP(X):p(a)p(a)p(a)—123—p(a)m其中，0<p(a)<1(i=1,2,...,m) 區(qū)p(a)二1imi=1符號(hào)a代表信源可能發(fā)出的符號(hào)，p(a)發(fā)符號(hào)a的先驗(yàn)概率。i i i用信源空間表示信源X的必要前提，就是信源可能發(fā)出的各種不同符號(hào)的概率先驗(yàn)可知，或事先可測(cè)定，測(cè)定信源的概率空間是構(gòu)建信源空間的關(guān)鍵。信源符號(hào)的自信息量：數(shù)學(xué)上定義為：I(a)=-logp(a) 說明：TOC\o"1-5"\h\zi r ia為信源所發(fā)符號(hào)，p(a)為信源發(fā)符號(hào)a的概率，概率越大，不確定性越i i i小，概率越小，不確定性越大。而自信息量I(a)既表示收信者確切無誤收到信源符號(hào)a后，從a中獲得的信i i i息量，同時(shí)也表示收到符號(hào)a之前，收信者對(duì)于信源所發(fā)符號(hào)a存在的不確ii定性的度量。自信息量I(a)的單位取決于對(duì)數(shù)的底，即r值，若r=2,則自信息量的單位i為比特(bit)，不指明正整數(shù)r具體值時(shí),則自信息量的單位為r進(jìn)制信息單位。信源的信息熵：數(shù)學(xué)上定義為：r進(jìn)制形式H(X)= p(a)logp(a)TOC\o"1-5"\h\zr irii=12進(jìn)制形式H(X)=-Sp(a)logp(a) 說明：2 i 2 ii=1⑴運(yùn)用對(duì)數(shù)換底公式，可得：H(X)=H(X)logrr 2 2(2)信息熵作為信源X的總體信息測(cè)度，表示信源每發(fā)一個(gè)符號(hào)所能提供的平均信息量，同時(shí)也表示收信者在接收到符號(hào)之前，對(duì)信源X存在的平均不確定性的度量。最大離散熵定理：H(p,p,.,p)<H(p,p.p)1 2mmax1 2m其中，說明：H(p,p,…,p)=H(丄，丄，…,丄)=一區(qū)—log丄=logm

max1 2mmmm m2m2其中，說明：i=1(1)熵函數(shù)H(p,p，…,p)是信源X的信息熵的另一種表示方法，其中p.代表1 2m ip(a)。(2)熵函數(shù)具有上凸性，所以熵函數(shù)具有極大值，此極大值就是其最大值H，max最大值在pi=1/m時(shí)，即信源符號(hào)等概率分布時(shí)取得。離散信源信息熵的最大值只取決于信源的符號(hào)種類數(shù)m值，m值越大，其信息熵的最大值越大。信源X所含有的允余度：:=H(X)-H(X)=logm-H(X) 說明：max2信源符號(hào)等概率分布時(shí)，允余度匚二0,因此離散獨(dú)立信源的允余度隱含在信源符號(hào)的非等概率分布之中。也就是說，只要信源符號(hào)不是等概率分布，就存在能夠?qū)π旁磾?shù)據(jù)進(jìn)行數(shù)據(jù)壓縮的可能性，允余度的存在是能夠進(jìn)行統(tǒng)計(jì)編碼的前提。對(duì)信源編碼所得平均碼長：n=np(a)+np(a)H Fnp(a)=￡np(a) 說明：1 1 2 2 mm iii=1n是信源符號(hào)a的碼字長度。ii平均碼長n是各個(gè)信源符號(hào)的碼字長度ni在信源X的概率空間!p(a),p(a),???,p(a)｝上的統(tǒng)計(jì)平均值。1 2 m編碼效率：n=H(X”n 說明：n值越大，表示每一個(gè)碼符號(hào)所攜帶的平均信息量越多，反之，就越少。對(duì)于給定的待編碼信源，由于各個(gè)信源符號(hào)的概率已經(jīng)經(jīng)過統(tǒng)計(jì)確定，所以信源熵的值也就固定不變了，所以編碼效率的高低只取決于平均碼長n，所以提高信源編碼的效率，就是要設(shè)法減小平均碼長n。平均碼長n存在下限：n>h(X) 說明：r⑴在證明過程中，得到：當(dāng)且僅當(dāng)對(duì)所有i(i=1,2,…,m)，都有p(a)=1rni時(shí)，in=H(X)才成立，其中n是信源符號(hào)a的碼字長度。r i i(2)單義可譯碼的平均碼長n，再小也不會(huì)小于信源熵。所以一旦信源確定，其信源熵也就隨之確定，平均碼長的下限值也隨之確定，在這個(gè)范疇內(nèi)編碼效率不可能超過1(100%)，要想進(jìn)一步提高編碼效率，只有通過改變信源本身才能做到。1.3統(tǒng)計(jì)編碼簡(jiǎn)介1.2節(jié)的內(nèi)容是設(shè)計(jì)統(tǒng)計(jì)編碼的理論基礎(chǔ)，所以有了1.2節(jié)的介紹，統(tǒng)計(jì)編碼這類方法就可簡(jiǎn)單表述為：利用信源符號(hào)的概率分布特性，尋找每個(gè)信源符號(hào)的出現(xiàn)概率與其碼字長度之間的最優(yōu)匹配，這種最優(yōu)匹配就是要做到平均碼長最小，也即平均碼長要最大程度的趨近信息熵值。怎么利用信源符號(hào)的概率分布特性，來為每個(gè)信源符號(hào)分配碼字，達(dá)到最大程度趨近信息熵值的目的在具體介紹哈夫曼編碼和算術(shù)編碼時(shí)會(huì)清楚地了解到。算術(shù)編碼2.1算術(shù)編碼簡(jiǎn)介很明顯，各種統(tǒng)計(jì)編碼都是變字長編碼方法，但變字長的含義對(duì)于哈夫曼編碼和算術(shù)編碼是有些區(qū)別的，哈夫曼編碼獨(dú)立的為每個(gè)符號(hào)依據(jù)其概率大小分配相應(yīng)長度的碼字，碼字長度都是整數(shù)個(gè)比特（bit）,而算術(shù)編碼無需為一個(gè)符號(hào)設(shè)定一個(gè)碼字，它直接對(duì)整個(gè)輸入符號(hào)序列進(jìn)行編碼，并輸出一個(gè)碼字來代表整個(gè)符號(hào)序列，編碼過程也自然是遞推形式的和連續(xù)的，這樣在衡量平均每個(gè)符號(hào)所對(duì)應(yīng)的碼字長度時(shí)，會(huì)知道碼字長度都是以分?jǐn)?shù)形式的比特（bit）來分配的，精確度可以很趨近于logp（a），這樣算術(shù)編碼與哈夫曼編碼相比就能夠更大程度地i趨近信源（整個(gè)符號(hào)序列）的信息熵。稍具體的來講，算術(shù)編碼不是將單個(gè)的信源符號(hào)映射成一個(gè)碼字，而是將整個(gè)輸入符號(hào)映射為左閉右開區(qū)間［0,1）內(nèi)的一個(gè)子區(qū)間，這一子區(qū)間的寬度等于整個(gè)符號(hào)序列的概率（整個(gè)符號(hào)序列的概率又等于輸入符號(hào)的概率之積），可以想象在編碼過程中，每編碼一個(gè)信源符號(hào)，都會(huì)相應(yīng)得到新的區(qū)間，新的區(qū)間作為編碼下一個(gè)信源符號(hào)所要待劃分的區(qū)間，就這樣一直對(duì)后續(xù)的符號(hào)依次編碼，直到所有的符號(hào)被編碼，即編碼完畢，最后得到的區(qū)間內(nèi)的任何一個(gè)小數(shù)都能代表整個(gè)符號(hào)序列，但一般選擇一個(gè)容易變成二進(jìn)制數(shù)字的小數(shù)作為實(shí)際的編碼輸出。上述闡述過程可能有點(diǎn)抽象，在2.2節(jié)將更加詳細(xì)的加以說明?；仡櫵阈g(shù)編碼的發(fā)展歷程會(huì)發(fā)現(xiàn)，算術(shù)編碼的發(fā)展不是一蹴而就的，其思想的源頭可追溯到香農(nóng)（shannon），再由P.Elias正式提出其完整思想（但還不實(shí)用），后來又由R.Pasco、J.Rissanen、G.G.Langdon和Written等人將其實(shí)用化，一直到算術(shù)編碼家族中的一些成員成為如H.263視頻壓縮標(biāo)準(zhǔn)和JPEG2000圖像壓縮標(biāo)

準(zhǔn)的核心，共經(jīng)歷了約40多年的時(shí)間，直到現(xiàn)在算術(shù)編碼的研究改進(jìn)也沒有停止。無限精度的算術(shù)編碼由P.Elias正式提出的算術(shù)編碼需要無限精度的浮點(diǎn)運(yùn)算，隨著符號(hào)序列的輸入，計(jì)算精度將無限制的增加，相應(yīng)的編碼位數(shù)也無限制的增加，而這樣的要求是在當(dāng)前計(jì)算機(jī)上無法實(shí)現(xiàn)的。雖然如此，但無限精度的算術(shù)編碼可用來更清楚地說明算術(shù)編碼的基本原理，同時(shí)通向?qū)嵱没挠邢蘧?、不做乘法的二進(jìn)制算術(shù)編碼也是基于此而改進(jìn)得到的。如果我們把編碼過程中得到的每一區(qū)間的下限作為碼字，并用C表示，區(qū)間大小用A表示，那么算術(shù)編碼原理可表述如下：設(shè)輸入符號(hào)序列s設(shè)輸入符號(hào)序列s取自信源空間X: aaa a123mP(X):p(a)p(a)p(a) p(a)123m后接符號(hào)a(aeX)，那么就擴(kuò)展為符號(hào)序列sa，空符號(hào)序列記作Q，只有一個(gè)iii符號(hào)a的序列就是0a，那么算術(shù)編碼的兩個(gè)迭代關(guān)系可表示為：ii碼字更新：C(sa)=C(s)+P(a)xA(s)ii區(qū)間更新：A(sa)=p(a)xA(s)ii其中P(a)=p(a)+p(a)+…+p(a)被稱為符號(hào)a的累積概率。i 1 2 i-1 i如果初始區(qū)間為實(shí)數(shù)區(qū)間［0,1),那么初始條件為：C(0)=0,A(0)=1和P(0)=0,p(0)=1。可見，在編碼任何符號(hào)之前，初始區(qū)間為lc(0),C(0)+A(0))=b,l),從上述描述的迭代關(guān)系可看出每次編碼符號(hào)a，區(qū)間寬度都依據(jù)符號(hào)a的出現(xiàn)概率而變ii窄，隨著編碼的符號(hào)序列越來越長，相應(yīng)的區(qū)間寬度也隨之變得越來越窄，那么表示區(qū)間所需的數(shù)字位數(shù)也會(huì)越來越多，而且，我們還會(huì)發(fā)現(xiàn)，大概率符號(hào)比小概率符號(hào)使區(qū)間變窄的幅度要小，所增加的數(shù)字位數(shù)也較之更少，這是符合統(tǒng)計(jì)編碼原理的。下面的實(shí)例追蹤這一編碼過程，有助于我們理解算術(shù)編碼工作的細(xì)節(jié)。實(shí)例1：設(shè)待編碼符號(hào)來自信源空間：X:a bcde!實(shí)例1：設(shè)待編碼符號(hào)來自信源空間：p(X):0.20.10.10.30.20.1符號(hào)!作為結(jié)束符，作為編碼和解碼結(jié)束的標(biāo)識(shí)，就像中文中句號(hào)的作用，若待編碼的符號(hào)串為一英文單詞“dead!”，當(dāng)然編碼和解碼過程都是從初始區(qū)間（0,1）開始的。注意:上述信源X的各符號(hào)的概率值來自某一統(tǒng)計(jì)模型，統(tǒng)計(jì)模型得到的各符號(hào)的概率值獨(dú)立于特編碼的符號(hào)串中各符號(hào)的概率值，是大量統(tǒng)計(jì)的產(chǎn)物，能比較真實(shí)的預(yù)測(cè)一個(gè)字符在待編碼的整個(gè)符號(hào)序列中的概率值，例如一本英文小說中各字符的概率值是確定的，但是在編碼時(shí)可能不允許事先統(tǒng)計(jì)其符號(hào)概率分布，但是我們事先經(jīng)過某些方法統(tǒng)計(jì)過大量其他英文小說的字符概率分布，那么就用之前已知的字符概率分布來預(yù)測(cè)未知待編碼字符串的字符概率分布。如果讓aaaaaa分別依次對(duì)應(yīng)abcde!,那么就能用算術(shù)編碼原理中介紹123456的兩個(gè)迭代關(guān)系實(shí)現(xiàn)算術(shù)編碼。開始時(shí)得到一張表，反映了開始時(shí)各個(gè)字符的累積概率和區(qū)間劃分情況：下標(biāo)F宇符込槪率貿(mào)Q累執(zhí)規(guī)率P匹）區(qū)間范國1aQ200[0.0,0.2)2b0102[0.2,0.3)3c0103[03,04)4d0304[0電0刀Q020.7[0.7,0.9)610109[09,1.0)表1：信源X中字符的分布概率、累積分布概率和初始區(qū)間劃分情況好，現(xiàn)在開始編碼：編碼第1個(gè)字符d:C(0d)二C(0)+P(d)xA(0)二0+0.4x1.0二0.4A(ed)二p(d)xA(e)二0.3x1.0二0.3區(qū)間范圍由[0,1)更新為\c(Qd),C(Qd)+A(Qd))=b.4,0.7)；編碼第2個(gè)字符e:C(Qde)二C(Qd)+P(e)xA(Qd)二0.4+0.7x0.3二0.61A(Qde)二p(e)xA(Qd)二0.2x0.3二0.06區(qū)間由b.4,0.7)更新為lc(Qde),C(Qde)+A(Qde))=b.61,0.67)；編碼第3個(gè)字符a:過程類似；編碼第4個(gè)字符d:過程類似；編碼第5個(gè)字符!:C(Qdead!)二C(Qdead)+P(!)xA(Qdead)二0.6148+0.9x0.0036二0.61804A(Qdead!)二p(!)xA(Qdead)二0.1x0.0036二0.00036至此，所有字符都已編碼，最后得到的區(qū)間為：Ic(Qdead!),C(Qdead!)+A(Qdead!))=b.61804,0.61840)。然后從此區(qū)間內(nèi)選擇一個(gè)數(shù)位較短的實(shí)數(shù)作為最后的碼字輸出給解碼器上述編碼過程如圖1所示：解碼原理可以看作是編碼原理的逆過程，解碼器開始也按照編碼時(shí)各個(gè)字符的概率分布(來自統(tǒng)計(jì)模型)對(duì)初始區(qū)間〔0,1)進(jìn)行劃分，然后解碼器把從編碼器接收到的碼字與各字符相對(duì)應(yīng)的概率區(qū)間作比較，比較的意思是說看碼字屬于哪個(gè)字符對(duì)應(yīng)的概率區(qū)間，比如選擇編碼得到的最后區(qū)間的左端點(diǎn)實(shí)數(shù)0.61804作為碼字，解碼器就會(huì)發(fā)現(xiàn)碼字0.61804屬于字符d所對(duì)應(yīng)的概率區(qū)間〔0.4,0.7)，然后就解碼出第一個(gè)字符d,為了避免一次又一次的為字符分配區(qū)間，減少計(jì)算量，在解碼出第一個(gè)字符后，比如解碼出字符d后，按照表1就把區(qū)間更新為d所對(duì)應(yīng)的區(qū)間［0.4,0.7)，區(qū)間大小A=0.3,然后開始解碼下一個(gè)字符，用原碼字0.61804減去字符d對(duì)應(yīng)區(qū)間的左端點(diǎn)值L=0.4,得到的值再除以d對(duì)應(yīng)區(qū)間的大小A=0.3即計(jì)算式：(0.61804-L)A二(0.61804-0.4”0.3二0.7268，然后把0.7268作為新的碼字，通過查找表1發(fā)現(xiàn)0.7268屬于字符e對(duì)應(yīng)的區(qū)間［0.7,0.9)，這就解碼出第二個(gè)字符e,并把e對(duì)應(yīng)的區(qū)間［0.7,0.9)作為新區(qū)間，左端點(diǎn)L=0.7，區(qū)間大小A=0.2，不斷重復(fù)上述過程，直到解碼出結(jié)束符!，解碼過程宣告完畢。需要說明的是作為結(jié)束符的!是不可見的，嚴(yán)格說并不屬于被編碼字符串，是人為附加上去的，作用只是為了在解碼器解碼出全部字符之后作為標(biāo)識(shí)來停止解碼器的運(yùn)行，如果沒有結(jié)束符，解碼器將無法判斷何時(shí)結(jié)束解碼。2.3二進(jìn)制編碼上節(jié)無限精度的算術(shù)編碼理論由于當(dāng)前計(jì)算機(jī)基于二進(jìn)制的設(shè)計(jì)而無法直接編程實(shí)現(xiàn)，而計(jì)算機(jī)能做到的就是對(duì)無限精度的實(shí)數(shù)進(jìn)行近似模擬，這種近似對(duì)大量數(shù)據(jù)的壓縮效果的影響很小，而算術(shù)編碼在理論上能夠很大程度上趨近信息熵的優(yōu)越性使得其有很大的現(xiàn)實(shí)意義。通過上節(jié)可知，算術(shù)編碼每次編碼和解碼都要做乘法，而且必須在規(guī)定的時(shí)間內(nèi)完成(信源符號(hào)周期限制)，有時(shí)就難以實(shí)現(xiàn)，但若被編碼對(duì)象本身或是被映射成二元序列(如01符號(hào)序列)，且其符號(hào)概率較小者(用L表示)的概率為p(L)=2-q，其中Q為整數(shù)，則上節(jié)介紹的無限精度的算術(shù)編碼原理的兩個(gè)迭代關(guān)系就可以在計(jì)算機(jī)上用移位和單純的加減運(yùn)算來實(shí)現(xiàn)，從而避免乘法。另外，隨著輸入符號(hào)序列s長度的增長，碼字C(s)的數(shù)位也隨之相應(yīng)增加，而這樣精度的碼字在計(jì)算機(jī)上是無法表示的(寄存器位數(shù)有限)，這就要求將寄存器中存儲(chǔ)的已編碼的碼字高位及時(shí)輸出。而當(dāng)寄存器中為輸出部分高位均為1時(shí)，則低位運(yùn)算略有增加，就可能進(jìn)位到已輸出部分，特別是當(dāng)這種連續(xù)的1很長時(shí)。這一問題就是有限精度算術(shù)編碼所固有的進(jìn)位問題。JRissanen和G.G.Langdon利用插入一個(gè)額外的0(即填充位)來隔斷進(jìn)位的擴(kuò)展，這會(huì)對(duì)編碼略有影響，但由于影響很小，所以下面仍用填充位來隔斷進(jìn)位的擴(kuò)展。類似碼字的情況，區(qū)間大小A(s)也只能基于有限位數(shù)的寄存器來實(shí)現(xiàn)更新。有限精度的算術(shù)編碼原理所用到的迭代關(guān)系與上節(jié)介紹的相同，但由于這次的編碼對(duì)象是二進(jìn)制序列，并且用2-q來估計(jì)小概率符號(hào)的出現(xiàn)概率，所以能夠進(jìn)一步得到如下迭代關(guān)系：設(shè)待編碼符號(hào)來自符號(hào)集掃,厶｝,并且若p(L)=2-q，那么p(H)=1-p(L)=1-2-Q；而人為讓P(H)=0，那么P(L)=p(H)=1-2-Q。上述對(duì)初始區(qū)間〔0,1)的最初劃分情況可用下圖表示：H L0 1-嚴(yán) 1.0圖2：大概率符號(hào)H與小概率符號(hào)L在初始區(qū)間中的分布情況從而，有限精度、不作乘法且將設(shè)變量Q已經(jīng)估計(jì)出的二進(jìn)制算術(shù)編碼順序步驟如下：1.初始化步驟：C他)=0.00…0,A(?)=0.11…1，C和A小數(shù)點(diǎn)后的位數(shù)由參數(shù)q確定。2?對(duì)區(qū)間寬度A(s)更新：當(dāng)編碼小概率符號(hào)L時(shí)：A(sL)=p(L)x2-Q(相當(dāng)于A(s)右移Q位)當(dāng)編碼大概率符號(hào)H時(shí)：A(sH)=p(H)xA(s)=(1-2-q)xA(s)=A(s)-A(s)x2-q=A(s)-A(sL)3?對(duì)碼字C(s)更新：當(dāng)編碼大概率符號(hào)H時(shí)：C(sH)=C(s)+P(H)xA(s)=C(s)當(dāng)編碼小概率符號(hào)L時(shí)：C(sL)=C(s)+P(L)xA(s)=C(s)+(1-2-q)xA(s)=C(s)+A(sH)4?如果發(fā)現(xiàn)A(s)<0.10…0，則A(s)重復(fù)左移，直到A(s)>0.10…0為止，而若A(s)左移，那么C(s)也需要左移同樣位數(shù)。如果緊靠碼字C(s)的小數(shù)點(diǎn)前有連續(xù)v個(gè)1,則緊靠小數(shù)點(diǎn)前的位置插入一填充位0，來隔斷進(jìn)位擴(kuò)展。按上述步驟對(duì)字符序列中的所有字符進(jìn)行上述處理過程，編碼完畢后輸出最后的碼字C(s)。步驟1中初始區(qū)間寬度在多大程度上趨近于1取決于參數(shù)q，而參數(shù)q值大小又一般依據(jù)p(L)而定，而p(L)是統(tǒng)計(jì)模型對(duì)下一位是小概率符號(hào)L可能出現(xiàn)的概率預(yù)測(cè)，例如如果有p(L)的最小值為2-15，那么參數(shù)q值就一般取16。如果沒有步驟4，那么區(qū)間A當(dāng)縮小到很小時(shí)，就必須用很高的精度才能把它和0區(qū)分開來，而步驟4的作用就是，當(dāng)發(fā)現(xiàn)區(qū)間小到某一程度時(shí)，就將區(qū)間左移若干位，直到區(qū)間大于某種程度，而區(qū)間A加倍后，碼字C也須隨之加倍。實(shí)例2：編碼二元符號(hào)串“01000101”，統(tǒng)計(jì)出大概率符號(hào)H是‘0'，小概率符號(hào)是‘1'，某一統(tǒng)計(jì)模型提供的對(duì)這個(gè)長度為8的字符串各個(gè)位置出現(xiàn)小概率符號(hào)L的概率預(yù)測(cè)分別為2-2,2-1,2-2,2-2,2-3,2-1,2-2,2-2，最大的Q值為3，那么就取q=4,v=3?，F(xiàn)在對(duì)其進(jìn)行編碼：編碼第1個(gè)符號(hào)‘0'統(tǒng)計(jì)模型預(yù)測(cè)p(1)=2-2A(Q1)=A(e)xp⑴=0.1111x2-2=0.0011A(?0)=A(?)xp(0)=A?)—A(?1)=0.1111-0.0011=0.1100C(00)=C(0)=0.0000編碼第2個(gè)符號(hào)‘1'統(tǒng)計(jì)模型預(yù)測(cè)p(1)=2-1A(01)=A(0)xp⑴=0.1100x2-i=0.0110A(00)=A(0)-A(01)=0.1100-0.0110=0.0110C(01)=C(0)+A(00)=0.0000+0.0110=0.0110此時(shí)，由于C(01)<0.1000,因此A(01)與C(01)須左移1位，得：A(01)=0.1100，C(01)=0.1100編碼第3個(gè)符號(hào)‘0'：過程類似，得到：A(010)=0.1001,C(010)=0.1100編碼第4個(gè)符號(hào)‘0'：過程類似，得到：A(0100)=0.1110,C(0100)=1.1000編碼第5個(gè)符號(hào)‘0'：過程類似，得到：A(01000)=0.1101,C(01000)=1.1000編碼第6個(gè)符號(hào)‘1'：過程類似，得到：A(010001)=0.1100,C(010001)=11.1110編碼第7個(gè)符號(hào)‘0'統(tǒng)計(jì)模型預(yù)測(cè)p(1)=2-2此次遇到了新的情況，下面是完整的過程：A(0100011)=A(010001)xp⑴=0.1100x2-2=0.0011A(0100010)=A(010001)-A(0100011)=0.1100-0.0011=0.0110C(0100010)=C(010001)=11.1110此時(shí)，由于A(0100010)<0.1000，因此A(0100010)與C(0100010)須左移1位，得:A(01000010)=0.1100，C(0100010)=111.1100此時(shí)又發(fā)現(xiàn)，C(0100010)緊靠小數(shù)點(diǎn)前有v=3個(gè)連續(xù)1,因此還需在C(0100010)緊靠其小數(shù)點(diǎn)前插入一填充位0，那么C(0100010)=1110.1100編碼最后一個(gè)符號(hào)‘1'統(tǒng)計(jì)模型預(yù)測(cè)p(1)=2-2A(01000101)=A(0100010)xp⑴=0.1100x2-2=0.0011A(01000100)=A(0100010)-A(01000101)=0.1100-0.0011=0.1001C(01000101)=C(0100010)+A(01000100)=1110.1100+0.1001=1111.0101此時(shí)，由于A(01000101)v0.1000,因此，須將A(01000101)和C(01000101)左移兩位，得：A(01000101)=0.1100，C(01000101)=111101.0100上述編碼過程如圖所示：

11000111110符號(hào)0A和C頃左移2IV.得:111101.01000.00000.01100.11000.11000.1100111110111110011000111110符號(hào)0A和C頃左移2IV.得:111101.01000.00000.01100.11000.11000.110011111011111001110.1100111101010.0000+0.1100.,A和O：：貝左移一應(yīng)，得:0.1100+0.1100A和C須左移1位，得:圖3：編碼“01000101”過程注：上圖中的箭頭是為了更清楚的表明左移的過程，每一區(qū)間只標(biāo)明了兩端點(diǎn)的值，右端點(diǎn)由碼字C和區(qū)間A的和組成，在圖的最右部分標(biāo)明的符號(hào)是為了說明各個(gè)符號(hào)所最終對(duì)應(yīng)的區(qū)間。此時(shí)，編碼就宣告結(jié)束了，編碼器最后一項(xiàng)工作就是從最后得到的區(qū)間中選擇一個(gè)代表性的二進(jìn)制小數(shù)作為碼字輸出，最后得到的區(qū)間為：[C(01000101),C(01000101)+A(01000101))=[111101.0100,111110.0000)回想在編碼過程中共做了5次左移處理(在圖3中用箭頭標(biāo)識(shí))，碼字C和區(qū)間A共左移(1+1+1+1+2)=6比特位，因此，要考慮碼字C和區(qū)間A實(shí)際的小數(shù)點(diǎn)位置，須將代表區(qū)間的數(shù)值右移6位，那么，最后得到的區(qū)間就變?yōu)閇0.1111010100,0.1111100000)，此區(qū)間信息可作為編碼輸出信息給解碼器，但是只要從此區(qū)間內(nèi)選擇一個(gè)位數(shù)比較短的值并且省略掉小數(shù)點(diǎn)和小數(shù)點(diǎn)前的0作為輸出碼字就可以，例如將1111011作為最后的碼字輸出。這個(gè)最終碼字的碼字長度有7位，比用ASCII表示的被編碼二元字符串的長度要小很多。2.4二進(jìn)制解碼二進(jìn)制解碼是二進(jìn)制編碼的逆過程。解碼器從編碼器接收到的碼字，去掉了小數(shù)點(diǎn)和小數(shù)點(diǎn)之前的0，并且這個(gè)碼字中可能還包括填充位，如果有填充位的話，在開始解碼前還要除去填充位的影響，回想，在二進(jìn)制編碼步驟5中，如果發(fā)現(xiàn)碼字C的小數(shù)點(diǎn)前有v個(gè)連續(xù)1，那么就在緊靠小數(shù)點(diǎn)前插入填充位0，那么，解碼時(shí)，當(dāng)發(fā)現(xiàn)碼字整數(shù)部分的高位有v個(gè)連續(xù)1，就要檢測(cè)第v+1位，第v+1為可能為0可能為1，0的情況說明當(dāng)編碼計(jì)算碼字時(shí)，沒有向第v+1位有進(jìn)位，1的情況說明編碼計(jì)算碼字時(shí)，有向第v+1位有進(jìn)位，使得填充位位置的0變?yōu)榱?，所以解碼前去掉填充的影響要分別考慮這兩種情況。解碼器也從區(qū)間大小為A(s)=0.11…1的區(qū)間作為開始解碼的初始區(qū)間，女口果當(dāng)前未解碼字符表示為X,在字符x之前已經(jīng)被解碼的字符串表示為s，，有了以上討論和假設(shè)，二進(jìn)制解碼步驟可表述如下：1初始化區(qū)間：A(s')=0.11…1解碼器檢測(cè)碼字C的高位部分的v位的二進(jìn)制位值：如果發(fā)現(xiàn)v位二進(jìn)制位都是1，那么接著檢測(cè)第v+1位即填充位的值：若第v+1位為0，說明沒有向第v+1位進(jìn)位，填充位的位置還是0，那么就直接去掉第v+1位的0，即除去了填充位的影響。若第v+1位為1，說明又向第v+1位進(jìn)位，填充位位置的0由于進(jìn)位的影響由0變?yōu)榱?，那么去掉此位后，由于后面有進(jìn)位，還要對(duì)碼字進(jìn)行加1處理，加1的位置是第v位。子區(qū)間寬度A更新：對(duì)小概率符號(hào)L：A(sZ)=A(sr)x2-q對(duì)大概率符號(hào)H：A(s'H)=A(s')-A(sZ)判斷解碼字符：如果C(s)<A(s'H):則解碼出字符為H,并置A(s')=A(s'H)如果C(s)>A(s'H):則解碼出字符為L,并置C(s)=C(s)-A(s'H),A(s')=A(s'L)5如果A(sx)v0.10???0,則A與C重復(fù)左移，直到A(sx)>0.10…0回到步驟2，接著解碼下一個(gè)字符，直到解碼出所有字符。哈夫曼編碼哈夫曼編碼簡(jiǎn)介哈夫曼編碼是一種變字長編碼方法，對(duì)出現(xiàn)概率較大的信源符號(hào)賦予較短的碼字，對(duì)出現(xiàn)概率較小的信源符號(hào)賦予較長的碼字，但哈夫曼編碼被稱為最佳碼并不僅僅如此，重要的是按照什么方法去為信源符號(hào)分配碼字，哈夫曼編碼通過構(gòu)造哈夫曼編碼表來達(dá)到最佳性，哈夫曼編碼對(duì)信源符號(hào)進(jìn)行編碼，能夠保證各碼字的碼長嚴(yán)格按照所對(duì)應(yīng)的信源符號(hào)的出現(xiàn)概率大小逆序排列，使得在變字長分組碼范疇內(nèi)，使其得到的平均碼長最小。哈夫曼編碼原理因?yàn)樾旁炊喾N多樣，那么不妨在編碼時(shí)把普通的計(jì)算機(jī)文件作為信源，如一個(gè)文本文件且此文本文件中字符由ASCII碼表示，那么此種文件都是由一個(gè)個(gè)的字節(jié)組成，每字節(jié)都是一個(gè)字符，當(dāng)然每個(gè)字符的ASCII碼表示都是8位，共256種，因此，這樣的文件最多含有256種字符。這樣，文件中的所包含的字符都可看作一個(gè)信源符號(hào)。哈夫曼編碼事先要統(tǒng)計(jì)文件中各個(gè)字符的出現(xiàn)概率，如果文件允許編碼器統(tǒng)計(jì)字符，那么通過統(tǒng)計(jì)文件中包含的總字符數(shù)和每種字符在文件中出現(xiàn)的次數(shù)，就很容易計(jì)算得到每種字符在文件中出現(xiàn)的概率。構(gòu)造一個(gè)文件的哈夫曼編碼表是文件編碼與解碼的關(guān)鍵。設(shè)某個(gè)文件中含有q種字符：s,s,s,…,s，并且統(tǒng)計(jì)出每種字符在文件中123q的出現(xiàn)概率分別為：p(s),p(s),p(s),…,p(s)，則編碼的具體步驟為：123q將q個(gè)信源符號(hào)s,s,s，…,s，按其概率分布p(s),p(s),p(s)，…,p(s)的大123q123q小，以遞減次序，由大到小進(jìn)行排序。用字符‘0'和‘1'分別代表概率最小的兩個(gè)信源符號(hào)，并把這兩個(gè)概率最小的信源符號(hào)的概率相加，所得的概率和值用一個(gè)虛擬信源符號(hào)代表，與余下的(q-2)個(gè)信源符號(hào)組成含有(q-1)個(gè)信源符號(hào)的新信源，稱作第一次縮減信源X。1把縮減信源X中的符號(hào)仍按照相應(yīng)概率大小以遞減次序進(jìn)行排列，再將其中1兩個(gè)概率最小的信源符號(hào)分別用‘0'和‘1'表示，并把這兩個(gè)符號(hào)的概率相加，所得的概率和值用另一個(gè)虛擬信源符號(hào)代表，這樣又形成了含有(q-2)個(gè)信源符號(hào)的第二次縮減信源X。2按照上述步驟，依次繼續(xù)下去，直到信源中只剩下兩個(gè)信源符號(hào)為止，將這最后兩個(gè)信源符號(hào)分別用‘0'和‘1'表示，這兩個(gè)信源符號(hào)的概率之和必定等于1，也用一虛擬信源符號(hào)代表。然后從最后得到的概率為1的信源符號(hào)開始，進(jìn)行回推，把回推過程中所遇到的‘0'和‘1'按先后順序排列成字符串，這樣的字符串對(duì)應(yīng)著各個(gè)不同字符，因?yàn)檫@樣的‘0'和‘1'組成的字符串并不是計(jì)算機(jī)中的二進(jìn)制，所以不妨稱為偽碼字。上述編碼過程，就是為文件中的字符建立了一一映射的關(guān)系f:sTc,i=1,2,……，q，其中s代表不同的字符，c代表對(duì)應(yīng)字符s的偽碼字。iiiii為了將偽碼字替換為真正的碼字，還必須建立一個(gè)映射關(guān)系 g:cTw，iii=1,2,……,q,其中c與映射關(guān)系f中同義，w代表對(duì)應(yīng)字符的碼字。映射gii的作用就是將由字符串組成的偽碼字替換成碼字，從而通過映射g(f(s))=w，ii建立了哈夫曼編碼表。下面具體說明一下怎樣把偽碼字替換為碼字，在此用一種間接的方法解決這個(gè)問題，具體做法為：將源文件中每個(gè)字符通過查找哈夫曼編碼表的辦法用偽碼字作替換，將替換的結(jié)果保存在一個(gè)臨時(shí)文件temporary.txt中，臨時(shí)文件temporary.txt就是一個(gè)由字符‘0'和‘1'組成的字符串。一般來說，這個(gè)臨時(shí)文件要比原文件大得多，比如，原文件中的字符‘a(chǎn)'用偽碼字“001110010”替換，前者只占一個(gè)字節(jié)，而后者最少占10個(gè)字節(jié)，臨時(shí)文件當(dāng)然不是最終得到的壓縮文件，只是為了便于實(shí)現(xiàn)壓縮與解壓。接下來是將臨時(shí)文件temporary.txt變?yōu)橛纱a字組成的文件。方法是，相當(dāng)于建立一個(gè)映射關(guān)系h:strTd，i=1,2，……，256，其中str是由字符‘0'和iii‘1'組成的字符數(shù)為8的字符串，d是介于0和266之間的整數(shù)。臨時(shí)文件從結(jié)構(gòu)上說是由不等長的偽碼字組成的，由偽碼字映射后的碼字也是不等長的，而計(jì)算機(jī)中的存儲(chǔ)單位一般都是單字節(jié)的倍數(shù)，如字節(jié)，雙字節(jié)，四字節(jié)，因此很難用一個(gè)準(zhǔn)確的存儲(chǔ)空間單位來存儲(chǔ)碼字，如果空間太大，對(duì)碼字長度短的碼字來說是一種空間浪費(fèi)，而空間太小，對(duì)碼字長度長的碼字來說又無法存放，因此，為了壓縮與解壓的方便，不如將temporary.txt進(jìn)行等長劃分，使得連續(xù)的8個(gè)字符為一組，組成str，用一整數(shù)d做替換，替換的ii結(jié)果是得到由整數(shù)d即二進(jìn)制組成的壓縮文件。i上述碼字替換偽碼字的過程，可能會(huì)出現(xiàn)最后一組‘0'和‘1'組成的字

符串不足8個(gè)字符，那么就保持不變，不做替換，附加到壓縮文件中。3.3哈夫曼解碼原理哈夫曼解碼過程是文件編碼過程的逆過程，由于哈夫曼編碼可即時(shí)解碼，因此只要得到一個(gè)碼字w,則通過查找哈夫曼編碼表得到相應(yīng)的字符，映射過程是i編碼時(shí)映射的逆過程：f-1(g-1(W))。因此，每從壓縮文件中讀出一個(gè)碼字，就i從通過查找哈夫曼編碼表用字符替換相應(yīng)的碼字，當(dāng)壓縮文件中所有的碼字被字符替換掉，也就宣告解壓過程完成了。雖然解壓是壓縮的逆過程，但是還不能直接通過對(duì)哈夫曼編碼表反向查找將壓縮文件解壓。首先，在壓縮文件中除了最后字符數(shù)不滿8的字符串作為附加數(shù)據(jù)沒有壓縮外，其他的每個(gè)字節(jié)都對(duì)應(yīng)著一個(gè)長度為8的字符串。因此，通過映射h的逆映射h-1將壓縮文件中的整數(shù)替換為8位字符串str，全部替換完畢后不i要忘了將沒有壓縮的字符串附加到臨時(shí)文件temporary.txt中去，這樣就得到了完整的臨時(shí)文件temporary.txt。由于臨時(shí)文件是由偽碼字組成的，通過映射f的逆映射f-i：cTs，實(shí)現(xiàn)用字符s替換偽碼字c，全部都替換完畢后，就實(shí)現(xiàn)了解iiii壓。3.4哈夫曼編碼與解碼系統(tǒng)模型有了上述討論，哈夫曼編碼與解碼系統(tǒng)模型可以簡(jiǎn)單如圖所示：圖4：哈夫曼編碼系解碼系統(tǒng)模型哈夫曼編碼形式不唯一按照哈夫曼編碼原理構(gòu)造的哈夫曼編碼表不唯一，這主要由于兩個(gè)原因，一是在為兩個(gè)最小概率的信源符號(hào)指定字符‘0'和‘1'的的順序上不唯一。二是對(duì)信源符號(hào)按概率大小遞減排序時(shí)，所得到的形式也不唯一，這是由于可能有出現(xiàn)概率相等的信源符號(hào)，對(duì)于兩個(gè)和兩個(gè)以上概率相等的信源符號(hào)排序的結(jié)果顯然是不唯一的雖然哈夫曼編碼形式不唯一，但是各種編碼形式所得到的平均碼長被證明是大小相同的，所以并不影響壓縮效果。算術(shù)編碼與哈夫曼編碼的比較4.1兩者編碼效率的比較統(tǒng)計(jì)編碼，利用信源符號(hào)的概率分布特性，尋找每個(gè)信源符號(hào)的出現(xiàn)概率與其碼長之間的最優(yōu)匹配，這種最優(yōu)匹配是要做到平均碼長最小，也就是說要使平均碼長最大程度的趨近信息熵值。哈夫曼編碼和算術(shù)編碼都屬于統(tǒng)計(jì)編碼，因此，兩者的編碼方法自然具有統(tǒng)計(jì)編碼的特性，但從理論上就能說明很多情況中算術(shù)編碼比哈夫曼編碼編碼效率要高，所以兩者編碼效率的不同原因就在于“最優(yōu)匹配”的方法不同，結(jié)果就造成兩者各自使其平均碼長趨近信息熵值的程度不同。在1.2節(jié)統(tǒng)計(jì)編碼的數(shù)學(xué)準(zhǔn)備中，有自信息量的概念，定義為：I(a)=-logp(a),其含義不贅述，統(tǒng)計(jì)編碼就是要做到為信源符號(hào)a分配的碼i2ii字的碼字長度要趨近或等于信源中該字符的自信息量I(a)，如果每個(gè)信源符號(hào)i的碼字都能符合這個(gè)要求，那么平均碼長就能很好的趨近甚至等于信息熵值，這樣編碼效率就能接近甚至等于100%。自信息量可以作為信源中某個(gè)字符編碼效率的衡量指標(biāo)。例如，信源中某符號(hào)a的出現(xiàn)概率為p(a)=0.8，那么其自信息ii量I(a)=-log0.8=0.322(bit),這說明若要使符號(hào)a的編碼效率達(dá)到100%，那i2i么只需要為其分配長度為0.322bit的碼字，但哈夫曼編碼只能為此符號(hào)分配長度為1bit的0或1，幾乎是理想碼字長度的3倍，編碼效率很低?？梢园炎孕畔⒘靠醋髯宰兞繛閜(a)的函數(shù)，稱作自信息量函數(shù)，不難發(fā)現(xiàn)，自信息量函數(shù)i是個(gè)單調(diào)遞減函數(shù)，p(a)越大，I(a)就越小，也就是說當(dāng)某個(gè)符號(hào)的概率接近ii于1時(shí)，自信息量函數(shù)至接近0，那么哈夫曼編碼的效率將降到最低。哈夫曼編碼雖然能夠保證各碼字的碼長嚴(yán)格按照所對(duì)應(yīng)的信源符號(hào)的出現(xiàn)概率大小逆序排列，但由于碼字長度都是整數(shù)個(gè)比特(bit),對(duì)某個(gè)符號(hào)而言，哈夫曼編碼只能以整數(shù)個(gè)比特(bit)趨近其自信息量，對(duì)所有信源符號(hào)而言，哈夫曼編碼只能以整數(shù)個(gè)比特(bit)趨近信息熵，這樣的性質(zhì)，限制了哈夫曼編碼趨近信息熵的能力。雖然，從上述的例子中哈夫曼的編碼效率很低，但是對(duì)于實(shí)際的文本文件，不可能有哪個(gè)字符達(dá)到0.8這么大的出現(xiàn)概率，一般，信源符號(hào)的出現(xiàn)概率都很低，因?yàn)閷?shí)際的文件中字符數(shù)很多，因此用哈夫曼編碼實(shí)際文件，是能夠獲得可觀的壓縮效率的。在1.2節(jié)統(tǒng)計(jì)編碼的理論基礎(chǔ)中，平均碼長等于下限信息熵的條件是：當(dāng)且僅當(dāng)對(duì)所有信源符號(hào)a，都有p(a)二1/2ni，其中n是信源符號(hào)a的碼字長度。i i i i就是說各信源符號(hào)的出現(xiàn)概率與1/2ni相比有較明顯的出入時(shí)，哈夫曼編碼不能很好的趨近信息熵。這個(gè)定理與上面用自信息量I(a)來討論編碼效率，本質(zhì)上i是相同的。當(dāng)信源所含有的允余度比較小時(shí)，也就是說，信源符號(hào)的概率分布比較接近等概率分布式時(shí)，用哈夫曼編碼方法就更加不能得到可觀的編碼效率，因?yàn)榇藭r(shí)對(duì)信源符號(hào)進(jìn)行哈夫曼編碼，得到的各符號(hào)對(duì)應(yīng)的碼字將接近等長碼，如，對(duì)本來就用等長的ASCII編碼的文本文件，當(dāng)文件內(nèi)符號(hào)概率分布接近等概率分布時(shí)，就根本起不到多少壓縮效果。算術(shù)編碼可以克服哈夫曼編碼的上述缺點(diǎn)，原因在于算術(shù)編碼跳出了分組編碼的范疇，它只輸出一個(gè)代表整個(gè)符號(hào)序列的碼字，并且該碼字長度是精確地與整個(gè)符號(hào)序列的概率大小相對(duì)應(yīng)的。雖然算術(shù)編碼沒有一個(gè)符號(hào)對(duì)應(yīng)一個(gè)碼字的概念，但平均碼長的概念是可用的，可以用代表整個(gè)符號(hào)序列的碼字的長度除以符號(hào)總數(shù)作為平均碼長，這樣一來，可以說用平均碼長來衡量平均意義上的每個(gè)符號(hào)所對(duì)應(yīng)的碼字長度。但每種符號(hào)的概率大小不同，對(duì)平均碼長的貢獻(xiàn)是不同的，算術(shù)編碼也像哈夫曼編碼一樣，概率大的符號(hào)對(duì)平均碼長的貢獻(xiàn)相對(duì)小，概率小的符號(hào)對(duì)平均碼長的貢獻(xiàn)相對(duì)大，但關(guān)鍵一點(diǎn)是，某符號(hào)a對(duì)平均碼長的貢i獻(xiàn)很接近-p(a)logp(a)，因?yàn)槭前捶謹(jǐn)?shù)比特接近的。算術(shù)編碼得到的平均碼長ii可以按分?jǐn)?shù)比特(bit)趨近信息熵，這就突破了哈夫曼編碼以整數(shù)比特(bit)趨近信息熵的限制。回想，在2.2節(jié)無限精度的算術(shù)編碼原理和2.3節(jié)二進(jìn)制編碼原理中，在進(jìn)行算術(shù)編碼之前，都對(duì)信源符號(hào)的概率作了預(yù)測(cè)，比如，在2.2節(jié)無限精度的算術(shù)編碼原理討論中的實(shí)例1，對(duì)可能出現(xiàn)的各個(gè)字符都作了概率預(yù)測(cè)，并按照這個(gè)概率估計(jì)值為不同字符分配相應(yīng)區(qū)間，而且在接下來的區(qū)間劃分中也保持各個(gè)字符被分配的區(qū)間比例不變，就是說一直都是用這個(gè)概率預(yù)測(cè)值作為分配區(qū)間的依據(jù)，可以想象，對(duì)信源符號(hào)的概率預(yù)測(cè)值，必定不同于被編碼信源符號(hào)的出現(xiàn)概率，但是采用這種模式進(jìn)行編碼就好像忽略掉了實(shí)際的符號(hào)出現(xiàn)概率，再結(jié)合算術(shù)編碼原理，大概率符號(hào)比小概率符號(hào)使區(qū)間縮窄的范圍要小，所增加的編碼位數(shù)就更少，所以如何預(yù)測(cè)各符號(hào)的出現(xiàn)概率，作為分配區(qū)間的依據(jù)，直接影響到算術(shù)編碼的編碼效率。如果概率預(yù)測(cè)值與實(shí)際符號(hào)出現(xiàn)概率偏差很大，編碼效率將受到很大影響，相比哈夫曼編碼也將沒有了優(yōu)勢(shì)，甚至不如哈夫曼編碼。介紹2.3節(jié)二進(jìn)制編碼原理中，對(duì)小概率符號(hào)L作了概率預(yù)測(cè)，并2-q表示，其中Q是整數(shù)，那么對(duì)小概率符號(hào)L作概率預(yù)測(cè)就是確定整數(shù)Q值，如果Q值能夠讓2-Q與小概率符號(hào)的出現(xiàn)概率p相等，那么編碼效率就是100%。確定Q值是保證算術(shù)編碼編碼效率的關(guān)鍵，使大部分小概率符號(hào)L的出現(xiàn)概率等于2-q，那么平均碼長將很好的趨近信息熵。兩者壓縮率的比較4.1節(jié)兩者編碼效率的比較中的“編碼效率”是基于1.2節(jié)編碼效率的定義：耳二H(Xn，即編碼效率為信息熵與平均碼長之比，為了在宏觀上衡量文件的壓縮效果，引入“壓縮率”的概念，壓縮率等于壓縮前后文件大小之差與壓縮前文件大小之比，那么，編碼效率越高，壓縮率就越大，所以壓縮率越大越好。用完全由ASCII編碼的txt文件為例，并理想化的把它作為離散無記憶信源處理，編碼三個(gè)主要由小寫英文字母組成的英文名著txt文件得到：哈夫曼編碼源文件容壓縮前擔(dān)(Byte)壓縮后大小(Byte)壓縮率a.txt2204080123