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

安徽大學本科畢業(yè)論文（設(shè)計、創(chuàng)作）題目哈夫曼編碼與算術(shù)編碼壓縮效率比較學生姓名：李偉學號：E20714134院（系）：計算機科學與技術(shù)專業(yè)：軟件工程入學時間：2007年9 月導師姓名：韓莉職稱/學位:講師/碩士導師所在單位：安徽大學計算機科學與技術(shù)學院完成時間：2011年5 月哈夫曼編碼與算術(shù)編碼壓縮效率比較摘要算術(shù)編碼和哈夫曼編碼都利用信源符號的概率分布特性進行編碼，使平均碼長逼近信息熵是壓縮編碼算法的第一要求，算術(shù)編碼比哈夫曼編碼逼近信息熵的能力要強，但是編碼效率和實現(xiàn)往往是一對矛盾，編碼效率的提高，往往要在實現(xiàn)上付出代價，所以，選擇壓縮算要權(quán)衡這兩點。本論文開篇先引入了信息論的一些概念，因為編碼理論發(fā)源于信息論，是各種編碼算法的數(shù)學基礎(chǔ)。然后在第2章分析了算術(shù)編碼原理，并從無限精度的算術(shù)編碼原理過渡到在計算機上能夠?qū)崿F(xiàn)的二進制編碼原理。在第3章緊接著介紹了哈夫曼編碼原理，并討論了怎樣把信源符號映射為對應的碼字，過程中用到的哈夫曼編碼表是編碼與解碼的關(guān)鍵。在第4章對兩者的編碼效率作了比較，主要是結(jié)合信息論中的一些概念從微觀上對兩者逼近信息熵的能力作了比較，并在這章最后對兩者在文本文件的壓縮效果的表現(xiàn)上給出了一些實驗結(jié)果。最后，在5章，主要是對前面內(nèi)容做了些補充和總結(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)計編碼的數(shù)學準備??????????????????????2統(tǒng)計編碼簡介?????????????????????????5算術(shù)編碼????????????????????????????5算術(shù)編碼簡介?????????????????????????5無限精度的算術(shù)編碼??????????????????????6二進制編碼??????????????????????????9二進制解碼??????????????????????????13哈夫曼編碼???????????????????????????14哈夫曼編碼簡介????????????????????????14哈夫曼編碼原理????????????????????????14哈夫曼解碼原理????????????????????????16哈夫曼編碼與解碼系統(tǒng)模型???????????????????16哈夫曼編碼形式不唯一?????????????????????17算術(shù)編碼與哈夫曼編碼的比較???????????????????17兩者編碼效率的比較??????????????????????17兩者壓縮率的比較???????????????????????19總結(jié)??????????????????????????????20主要參考文獻???????????????????????????22致謝???????????????????????????????231引言1.1數(shù)據(jù)壓縮概念及技術(shù)分類數(shù)據(jù)壓縮，就是將信息的一種表示方式轉(zhuǎn)換為另一種表示方式，信息的新的表示方式與原有表示方式相比較所含的信息量相同或是在可以承受的范圍內(nèi)有所損失，但是新的表示方式所用到的符號數(shù)量要比原有表示方式要盡可能的少。數(shù)據(jù)壓縮是必要的，不管是在生物系統(tǒng)中還是在人工系統(tǒng)中都存在數(shù)據(jù)壓縮。尤其是處在這個信息爆炸的時代，怎樣更有效的存儲信息和傳遞信息對于文明進步的作用都是顯而易見的。從不同視角看到的數(shù)據(jù)壓縮的益處有：在通信信道上更快的傳輸信息，這就相應的減少了信道的占有時間，這可看作在時間上進行了壓縮；在同一通信信道上并行的傳輸各種頻率的互不干擾的信息，如xDSL技術(shù)在普通電話線上實現(xiàn)把低端頻譜留給傳統(tǒng)電話使用，把高端頻譜留給上網(wǎng)用戶使用，這可看作在頻率域上進行了壓縮；傳輸信號當然需要能量消耗，因此對數(shù)據(jù)進行壓縮也就間接地減少了能量消耗，這可看作是在能量上進行了壓縮；各種存儲系統(tǒng)的存儲空間都不是無限的，對數(shù)據(jù)進行壓縮后，就可以在同樣的存儲空間存儲更多的數(shù)據(jù)，這可看作是空間上的壓縮。任何系統(tǒng)，尤其在活動時，都同時涉及到時間、空間和能量上的消耗，所以數(shù)據(jù)壓縮就是從這三方面同時進行了壓縮，這樣就使得系統(tǒng)更加的有效的運行。既然數(shù)據(jù)壓縮是必要的，那么就要考慮從哪些方面來說數(shù)據(jù)可以被壓縮，一般可從以下幾方面考察：一是，數(shù)據(jù)中通常存在著多余成分，即允余度。例如，存儲在計算機上的一份文本文件，內(nèi)容可假設(shè)是一部英文小說，可以想象，26個英文字母重復出現(xiàn)，各個字母出現(xiàn)的頻率有大有小，而且不僅字母重復出現(xiàn)，字母組成的單詞也重復出現(xiàn)，進一步，某些字母總是在某單詞的一定位置上以高概率重復出現(xiàn)，某些單詞也總是在一個特定句式的特定位置以高概率重復出現(xiàn)等等，計算機是以二進制形式存儲文件的，那么用二進制符號怎樣有效的表示這個由英文字符、各種標點符號和控制字符組成的文本文件就是怎樣對數(shù)據(jù)進行壓縮的問題，而壓縮顯然就要利用這些允余度的不同類型，例如，我們賦予高概率字符以相對少的二進制位數(shù)，賦予低概率字符以相對多的的二進制位數(shù)，那么這樣表示后所得的總的二進制位數(shù)肯定比不考慮各個字符出現(xiàn)概率，而給不同字符按照ASCII碼分配二進制位數(shù)所得的總的二進制位數(shù)要少很多。二是，數(shù)據(jù)中的各個部分前后之間總是存在著相關(guān)性。例如，電視上顯示的動態(tài)畫面，實際上是由離散的不同畫面（幀）組成的，之所以看似是連續(xù)的只是因為幀的播放速度超過了人類的反應速度并且利用了人類的視覺暫留效應，但為使畫面看似連續(xù)，不僅要利用人類本身的生物特性，還要保證幀之間的過渡是相對平滑的，也就是相鄰兩幀之間只有動態(tài)上的細微變化，而大部分畫面在兩幀之間是相同的，很顯然，這種相關(guān)性是可以很好的加以利用的。三是，對于人而言，我們的感受器只能接受外界中很小一部分的信息。例如，人眼只能感受陽光中的可見光，而對紫外光不可見，但一些昆蟲如蜜蜂卻能感受紫外光，如果人為的屏蔽掉紫外光部分，對人眼而言，我們并不能對屏蔽前與屏蔽后的陽光加以區(qū)分，但蜜蜂就不同了，可能就因為無法感受紫外光，就找不到花蜜了，所以，對于人而言，并不是數(shù)據(jù)中所有的信息對我們都是必要的，不必要的部分就可以屏蔽掉。數(shù)據(jù)壓縮可分為無損壓縮和有損壓縮，下面分別簡要的介紹可逆壓縮和不可逆壓縮：可逆壓縮，是利用數(shù)據(jù)的統(tǒng)計特性，即數(shù)據(jù)的允余度進行壓縮的一類方法，允余度的去除或是減少并不影響原始數(shù)據(jù)無失真的恢復，即是一個可逆的過程。但從編碼效率上來講，可逆壓縮受到待編碼數(shù)據(jù)本身的信息熵的限制，無法達到更高的編碼效率。也就是由于這樣的限制，僅使用可逆壓縮方法是不可能解決多媒體的存儲和傳輸?shù)乃袉栴}的，因此，這類方法一般適用于在壓縮過程中不允許有絲毫損失的情況，如在計算機磁盤上存儲文件，數(shù)據(jù)通信等領(lǐng)域。常用的可逆壓縮方法有：哈夫曼編碼、算術(shù)編碼、LZW編碼等。不可逆壓縮，是利用人類對圖像或聲波中的某些頻率成分的不敏感特性，允許壓縮過程中損失一定的信息，雖然不能完全恢復原始數(shù)據(jù)，但是所損失的部分對人類理解理解原始數(shù)據(jù)的影響可承受，好處就是與可逆壓縮相比，能夠獲得更高的編碼效率，因此，廣泛適用與語音、圖像和視頻數(shù)據(jù)的壓縮。不可逆壓縮的方法有很多，這里不列舉。統(tǒng)計編碼的數(shù)學準備統(tǒng)計編碼某種程度上與可逆壓縮同義，因此可混用。在1.1節(jié)中，我們用到了允余度和信息熵的概念，這兩個概念都由信息論的開創(chuàng)者香農(nóng)(ClaudeE.shannon)首次提出，因此這一小節(jié)主要介紹信息論中的一些概念，這些概念有助于我們更好的理解統(tǒng)計編碼。信源空間概念：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符號a代表信源可能發(fā)出的符號，p(a)發(fā)符號a的先驗概率。i i i用信源空間表示信源X的必要前提，就是信源可能發(fā)出的各種不同符號的概率先驗可知，或事先可測定，測定信源的概率空間是構(gòu)建信源空間的關(guān)鍵。信源符號的自信息量：數(shù)學上定義為：I(a)=-logp(a) 說明：TOC\o"1-5"\h\zi r ia為信源所發(fā)符號，p(a)為信源發(fā)符號a的概率，概率越大，不確定性越i i i小，概率越小，不確定性越大。而自信息量I(a)既表示收信者確切無誤收到信源符號a后，從a中獲得的信i i i息量，同時也表示收到符號a之前，收信者對于信源所發(fā)符號a存在的不確ii定性的度量。自信息量I(a)的單位取決于對數(shù)的底，即r值，若r=2,則自信息量的單位i為比特(bit)，不指明正整數(shù)r具體值時,則自信息量的單位為r進制信息單位。信源的信息熵：數(shù)學上定義為：r進制形式H(X)= p(a)logp(a)TOC\o"1-5"\h\zr irii=12進制形式H(X)=-Sp(a)logp(a) 說明：2 i 2 ii=1⑴運用對數(shù)換底公式，可得：H(X)=H(X)logrr 2 2(2)信息熵作為信源X的總體信息測度，表示信源每發(fā)一個符號所能提供的平均信息量，同時也表示收信者在接收到符號之前，對信源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ù)m值，m值越大，其信息熵的最大值越大。信源X所含有的允余度：:=H(X)-H(X)=logm-H(X) 說明：max2信源符號等概率分布時，允余度匚二0,因此離散獨立信源的允余度隱含在信源符號的非等概率分布之中。也就是說，只要信源符號不是等概率分布，就存在能夠?qū)π旁磾?shù)據(jù)進行數(shù)據(jù)壓縮的可能性，允余度的存在是能夠進行統(tǒng)計編碼的前提。對信源編碼所得平均碼長：n=np(a)+np(a)H Fnp(a)=￡np(a) 說明：1 1 2 2 mm iii=1n是信源符號a的碼字長度。ii平均碼長n是各個信源符號的碼字長度ni在信源X的概率空間!p(a),p(a),???,p(a)｝上的統(tǒng)計平均值。1 2 m編碼效率：n=H(X”n 說明：n值越大，表示每一個碼符號所攜帶的平均信息量越多，反之，就越少。對于給定的待編碼信源，由于各個信源符號的概率已經(jīng)經(jīng)過統(tǒng)計確定，所以信源熵的值也就固定不變了，所以編碼效率的高低只取決于平均碼長n，所以提高信源編碼的效率，就是要設(shè)法減小平均碼長n。平均碼長n存在下限：n>h(X) 說明：r⑴在證明過程中，得到：當且僅當對所有i(i=1,2,…,m)，都有p(a)=1rni時，in=H(X)才成立，其中n是信源符號a的碼字長度。r i i(2)單義可譯碼的平均碼長n，再小也不會小于信源熵。所以一旦信源確定，其信源熵也就隨之確定，平均碼長的下限值也隨之確定，在這個范疇內(nèi)編碼效率不可能超過1(100%)，要想進一步提高編碼效率，只有通過改變信源本身才能做到。1.3統(tǒng)計編碼簡介1.2節(jié)的內(nèi)容是設(shè)計統(tǒng)計編碼的理論基礎(chǔ)，所以有了1.2節(jié)的介紹，統(tǒng)計編碼這類方法就可簡單表述為：利用信源符號的概率分布特性，尋找每個信源符號的出現(xiàn)概率與其碼字長度之間的最優(yōu)匹配，這種最優(yōu)匹配就是要做到平均碼長最小，也即平均碼長要最大程度的趨近信息熵值。怎么利用信源符號的概率分布特性，來為每個信源符號分配碼字，達到最大程度趨近信息熵值的目的在具體介紹哈夫曼編碼和算術(shù)編碼時會清楚地了解到。算術(shù)編碼2.1算術(shù)編碼簡介很明顯，各種統(tǒng)計編碼都是變字長編碼方法，但變字長的含義對于哈夫曼編碼和算術(shù)編碼是有些區(qū)別的，哈夫曼編碼獨立的為每個符號依據(jù)其概率大小分配相應長度的碼字，碼字長度都是整數(shù)個比特（bit）,而算術(shù)編碼無需為一個符號設(shè)定一個碼字，它直接對整個輸入符號序列進行編碼，并輸出一個碼字來代表整個符號序列，編碼過程也自然是遞推形式的和連續(xù)的，這樣在衡量平均每個符號所對應的碼字長度時，會知道碼字長度都是以分數(shù)形式的比特（bit）來分配的，精確度可以很趨近于logp（a），這樣算術(shù)編碼與哈夫曼編碼相比就能夠更大程度地i趨近信源（整個符號序列）的信息熵。稍具體的來講，算術(shù)編碼不是將單個的信源符號映射成一個碼字，而是將整個輸入符號映射為左閉右開區(qū)間［0,1）內(nèi)的一個子區(qū)間，這一子區(qū)間的寬度等于整個符號序列的概率（整個符號序列的概率又等于輸入符號的概率之積），可以想象在編碼過程中，每編碼一個信源符號，都會相應得到新的區(qū)間，新的區(qū)間作為編碼下一個信源符號所要待劃分的區(qū)間，就這樣一直對后續(xù)的符號依次編碼，直到所有的符號被編碼，即編碼完畢，最后得到的區(qū)間內(nèi)的任何一個小數(shù)都能代表整個符號序列，但一般選擇一個容易變成二進制數(shù)字的小數(shù)作為實際的編碼輸出。上述闡述過程可能有點抽象，在2.2節(jié)將更加詳細的加以說明?；仡櫵阈g(shù)編碼的發(fā)展歷程會發(fā)現(xiàn)，算術(shù)編碼的發(fā)展不是一蹴而就的，其思想的源頭可追溯到香農(nóng)（shannon），再由P.Elias正式提出其完整思想（但還不實用），后來又由R.Pasco、J.Rissanen、G.G.Langdon和Written等人將其實用化，一直到算術(shù)編碼家族中的一些成員成為如H.263視頻壓縮標準和JPEG2000圖像壓縮標

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

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

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