霍夫曼編碼在數(shù)據(jù)壓縮中的應(yīng)用

10級電子信息工程《信息論與編碼技術(shù)》學(xué)習(xí)報告霍夫曼編碼在數(shù)據(jù)壓縮中的應(yīng)用姓學(xué)姓學(xué)班成號級績2012年11月現(xiàn)代社會是信息社會，我們無時無刻都在跟信息打交道，如上網(wǎng)查閱圖文資料，瀏覽最新的新聞，QQ聊天或者傳送文件等。人類對信息的要求越來越豐富，希望無論何時何地都能夠方便、快捷、靈活地通過文字、語音、圖像以及視頻等多媒體進(jìn)行通信。在早期的通信領(lǐng)域中，能夠處理和傳輸?shù)闹饕俏淖趾吐曇?，因此，早期的計算機和通信設(shè)備的處理能力跟人類的需求有相當(dāng)大的差距。隨著通信信道及計算機容量和速度的提高，如今信息已成為通信領(lǐng)域市場的熱點之一?？墒?，大數(shù)據(jù)量的信息會給存儲器的存儲容量、通信干線信道的寬度以及計算機的處理速度增加極大的壓力。單純依靠增加存儲器容量、提高通信網(wǎng)絡(luò)帶寬和計算機處理速度來解決問題，在技術(shù)和經(jīng)濟上都不太現(xiàn)實。顯然，在信道寬度、通信鏈路容量一定的前提下，采用編碼壓縮技術(shù)、減少傳輸數(shù)據(jù)量，是提高通信速度的重要手段。在信息化高度發(fā)達(dá)的當(dāng)今社會，我們必須對信息的傳遞有著較高的要求，我們希望信息在傳遞的過程中，能夠保持節(jié)省性、保密性、無損性和高效性，而著名的霍夫曼編碼就能夠達(dá)到這樣的要求。因此研究霍夫曼編碼對信息的壓縮就是相當(dāng)有必要的。一、霍夫曼編碼簡介霍夫曼編碼是一種可變字長編碼的方式?；舴蚵?952年提出這種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的的碼字，是一種構(gòu)造最佳碼的方法?；舴蚵幋a的碼長是變化的，對于出現(xiàn)頻率高的信息，編碼的長度較短；而對于出現(xiàn)頻率低的信息，編碼長度較長。這樣，處理全部信息的總碼長一定小于實際信息的符號長度。霍夫曼編碼是一種根據(jù)字母的使用頻率而設(shè)計的變長碼，能提高信息的傳輸效率,至今仍有廣泛的應(yīng)用。霍夫曼編碼方法的具體過程是：1、首先把信源的各個輸出符號序列按概率遞降的順序排列起來，求其中概率最小的兩個序列的概率之和，并把這個概率之和看做是一個符號序列的概率，再與其他序列依概率遞降順序排列（參與求概率之和的這兩個序列不再出現(xiàn)在新的排列之中）；2、然后，對參與概率求和的兩個符號序列分別賦予二進(jìn)制數(shù)字0和1。繼續(xù)這樣的操作，直到剩下一個以1為概率的符號序列；3、最后，按照與編碼過程相反的順序讀出各個符號序列所對應(yīng)的二進(jìn)制數(shù)字組，就可分別得到各該符號序列的碼字。霍夫曼編碼是一種熵編碼壓縮方式?；舴蚵鼔嚎s是個無損的壓縮算法，一般用來壓縮文本和程序文件?；舴蚵鼔嚎s屬于可變代碼長度算法一族。意思是不同符號（例如，文本文件中的字符）用一個特定長度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號，使用短的位序列，而那些很少出現(xiàn)的符號，則用較長的位序列。在計算機數(shù)據(jù)處理中，霍夫曼編碼使用變長編碼表對源符號進(jìn)行編碼，其中變長編碼表是通過一種評估來源符號出現(xiàn)機率的方法得到的，出現(xiàn)機率高的字母使用較短的編碼，反之出現(xiàn)機率低的則使用較長的編碼，這便使編碼之后的字符串的平均長度、期望值降低，從而達(dá)到無損壓縮數(shù)據(jù)的目的。1951年，霍夫曼發(fā)現(xiàn)了基于有序頻率二叉樹編碼的想法，并很快證明了這個方法是最有效的?；舴蚵褂米缘紫蛏系姆椒?gòu)建二叉樹，避免了次優(yōu)算法Shannon-Fano編碼的最大弊端一自頂向下構(gòu)建樹。二、霍夫曼編碼原理霍夫曼編碼是一種常用的壓縮編碼方法，是霍夫曼于1952年為壓縮文本文件建立的。它的基本原理是頻繁使用的數(shù)據(jù)用較短的代碼代替，較少使用的數(shù)據(jù)用較長的代碼代替，每個數(shù)據(jù)的代碼各不相同。這些代碼都是二進(jìn)制碼，且碼的長度是可變的。舉個例子：假設(shè)一個文件中出現(xiàn)了8種符號S0,S1,S2,S3,S4,S5,S6,S7，那么每種符號要編碼，至少需要3比特。假設(shè)編碼成000,001,010,011,100,101,110,111（稱做碼字），那么符號序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1編碼后變成000001111000001110010010011100101000000001，共用了42比特。我們發(fā)現(xiàn)S0，S1，S2這三個符號出現(xiàn)的頻率比較大，其它符號出現(xiàn)的頻率比較小，如果我們采用一種編碼方案使得S0，S1，S2的碼字短，其它符號的碼字長，這樣就能夠減少占用的比特數(shù)。例如，我們采用這樣的編碼方案：S0到S7的碼字分別01,11,101,0000,0001,0010,0011,100，那么上述符號序列變成011110001110011101101000000010010010111，共用了39比特，盡管有些碼字如S3,S4,S5,S6變長了（由3位變成4位），但使用頻繁的幾個碼字如S0，S1變短了，所以實現(xiàn)了壓縮。上述的編碼是如何得到的呢？隨意亂寫是不行的。編碼必須保證不能出現(xiàn)一個碼字和另一個的前幾位相同的情況，比如說，如果S0的碼字為01，S2的碼字為011，那么當(dāng)序列中出現(xiàn)011時，你不知道是S0的碼字后面跟了個1，還是完整的一個S2的碼字。我們給出的編碼能夠保證這一點。下面給出具體的霍夫曼編碼算法：、首先統(tǒng)計出每個符號出現(xiàn)的頻率，如上例S0到S7的出現(xiàn)頻率分別為4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14；、從左到右把上述頻率按從小到大的順序排列；、每一次選出最小的兩個值，作為二叉樹的兩個葉子節(jié)點，將和作為它們的根節(jié)點，這兩個葉子節(jié)點不再參與比較，新的根節(jié)點參與比較；、重復(fù)(3)，直到最后得到和為1的根節(jié)點；、將形成的二叉樹的左節(jié)點標(biāo)0，右節(jié)點標(biāo)1。把從最上面的根節(jié)點到最下面的葉子節(jié)點途中遇到的0,1序列串起來，就得到了各個符號的編碼。三、霍夫曼編碼步驟、初始化，將信源符號按概率大小由大全小排序；、把概率最小的兩個信源符號組成一個新符號(節(jié)點)，即新符號的概率等于這兩個符號概率之和；、重復(fù)第2步，直到形成一個符號為止(樹)，其概率最后等于1；、從編碼樹的根開始回溯到原始的符號，并將每一下分枝賦值為1，上分枝賦值為0；以下這個簡單例子說明了這一過程。、字母A,B,C,D,E已被編碼，相應(yīng)的出現(xiàn)概率如下：p(A)=0.16,p(B)=0.51,p(C)=0.09,p(D)=0.13,p(E)=0.11、C和E概率最小，被排在第一棵二叉樹中作為樹葉。它們的根節(jié)點CE的組合概率為0.20。從CE到C的一邊被標(biāo)記為1，從CE到E的一邊被標(biāo)記為0。這種標(biāo)記是強制性的。所以，不同的霍夫曼編碼可能由相同的數(shù)據(jù)產(chǎn)生。、各節(jié)點相應(yīng)的概率如下：p(A)=0.16,p(B)=0.51,p(CE)=0.20,p(D)=0.13D和A兩個節(jié)點的概率最小。這兩個節(jié)點作為葉子組合成一棵新的二叉樹。根節(jié)點AD的組合概率為0.29。由AD到A的一邊標(biāo)記為1,由AD到D的一邊標(biāo)記為0。如果不同的二叉樹的根節(jié)點有相同的概率，那么具有從根到節(jié)點最短的最大路徑的二叉樹應(yīng)先生成。這樣能保持編碼的長度基本穩(wěn)定。、剩下節(jié)點的概率如下：p(AD)=0.29,p(B)=0.51,p(CE)=0.20AD和CE兩節(jié)點的概率最小。它們生成一棵二叉樹。其根節(jié)點ADCE的組合概率為0.49。由ADCE到AD一邊標(biāo)記為0，由ADCE到CE的一邊標(biāo)記為1。、剩下兩個節(jié)點相應(yīng)的概率如下：p(ADCE)=0.49,p(B)=0.51它們生成最后一棵根節(jié)點為ADCEB的二叉樹。由ADCEB到B的一邊記為1，由ADCEB到ADCE的一邊記為0。、編碼結(jié)果被存放在一個表中：w(A)=001,w(B)=1,w(C)=011,w(D)=000,w(E)=010四、霍夫曼樹1、有關(guān)霍夫曼樹的相關(guān)概念霍夫曼樹：指所有葉子結(jié)點的二叉樹中帶權(quán)路徑長度最小的二叉樹。節(jié)點的帶權(quán)路徑長度：從樹的根節(jié)點到該節(jié)點的路徑長度與該節(jié)點權(quán)的乘積。樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和。2、霍夫曼算法、根據(jù)給定的n個權(quán)值｛w1,w2,...,wn｝構(gòu)造n棵二叉樹的集合F=｛T1,T2,...,Tn｝，其中每棵二叉樹Ti中只有一個帶權(quán)為wi的根結(jié)點，其左右子樹均空。、在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。、在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。、重復(fù)(2)和(3)，直到F中只含一棵樹為止。這棵樹便是最優(yōu)二叉樹。五、霍夫曼編碼在數(shù)據(jù)壓縮的應(yīng)用假設(shè)有一個包含100000個字符的數(shù)據(jù)文件要壓縮存儲。各字符在該文件中的出現(xiàn)頻度見表1。僅有6種不同字符出現(xiàn)過，字符a出現(xiàn)了45000次。字符abCDef頻度（千次）4513121695可以用很多種方式來表示這樣一個壓縮文件。理所當(dāng)然，我們第一個想到的編碼方式是固定長度編碼：共有6個字符，由于2的3次幕為8,則每個字符可以用3比特的二進(jìn)制編碼來表示：字符abcdef頻度（千次）4513121695固定長度編碼000001010011100101這樣的編碼方式在解壓縮的時候不會出現(xiàn)問題：由于每個字符都是用3比特的二進(jìn)制編碼表示，在解析壓縮文件時，將每3比特當(dāng)作一個字符來解析，那么不會發(fā)生串碼的問題。采用這種方式的壓縮文件其大小是：（45+13+12+16+9+5）*3*1000=300000比特。這是最優(yōu)的壓縮方式嗎？還有沒有別的辦法壓縮得更??？我們換個思路，對頻度高的字符賦予短編碼，對頻度低的字符賦予較長一些的編碼，那么壓縮出來的文件的大小有可能小于300000比特。這就是可變長度編碼方式。可變長度編碼方式既要滿足壓縮文件長度盡量小的條件，也要克服由“可變長度”所代碼的困難：例如a用001表示，b用000表示，當(dāng)a和b緊接在一起時的編碼串為:001000，此時就要求其他字符不能用010，1000，100表示，否則將無法在這串編碼中識別出正確的字符。如果采用霍夫曼編碼的話，上述的困難就迎刃而解:字符abCdef頻度（千次）4513121695霍夫曼編碼010110011111011100此時的壓縮文件長度為：（45*1+13*3+12*3+16*3+9*4+5*4）*1000=224000比特.仔細(xì)觀察上表中的霍夫曼編碼，我們會發(fā)現(xiàn)：任意兩個字符的編碼連接在一起的二進(jìn)制編碼中不會出現(xiàn)其他字符的編碼。這就解決了解壓的問題。六、學(xué)習(xí)心得通過從網(wǎng)上查找有關(guān)資料以及查閱相關(guān)書籍，使我對對霍夫曼編碼的原理有了一個全面而深刻的認(rèn)識，雖然老師在上課的時候已經(jīng)進(jìn)行了全面的講解，但是我對學(xué)習(xí)霍夫曼編碼的意義并沒有一個深刻的認(rèn)識。上完課的時候，我只知道霍夫曼編碼與香農(nóng)編碼、費諾編碼相比，是編碼效率最高的一種方式，但是，它編碼效率高的優(yōu)勢在實際中有哪些作用及應(yīng)用，我從來沒有思考過。由此也可以看出，我們現(xiàn)在的學(xué)習(xí)都太死板，只是為了學(xué)知識而學(xué)知識。通過這次學(xué)習(xí)，使我深刻認(rèn)識到，老師在給我們講完知識之后，我們不僅僅要學(xué)會這種知識，更重要的是，我們要去思考，我們?yōu)槭裁匆獙W(xué)，學(xué)到的知識對我們的生活有什么幫助，我們怎樣在以后的工作中去更好的應(yīng)用它。大學(xué)不僅僅只是學(xué)知識，更重要的是學(xué)會應(yīng)用。在看到老師給我們的課題時，我才意識到了這些問題。信源編碼的應(yīng)用，學(xué)習(xí)信源編碼，不是為了純粹地獲取一種知識，而是它在實際中的應(yīng)用，這才是我們要解決的重點問題。在查閱相關(guān)資料之前，霍夫曼編碼在哪些方面有應(yīng)用，我一無所知。通過查閱相關(guān)知識之后，我才慢慢的對霍夫曼編碼的應(yīng)用有所認(rèn)識。從中我認(rèn)識到，霍夫曼編碼是構(gòu)造最佳碼的一種方法，最重要的是，霍夫曼編碼的效率最高，這就是它之所以應(yīng)用比較廣泛最主要的原因?；舴蚵幋a效率最高，它選擇用較短的碼來編出現(xiàn)頻率比較高的信源符號，用較長的碼來編出現(xiàn)頻率比較低的信源符號，這樣一來，原有數(shù)據(jù)就得到了有效的壓縮可以節(jié)省大量的存儲空間?，F(xiàn)在是信息社會，大量的信息讓計算機應(yīng)接不暇，能使大量信息得到有效的壓縮，無形中為計算機處理速度減小了很大的壓力。因此，我重點學(xué)習(xí)了霍夫曼編碼在數(shù)據(jù)壓縮方面的應(yīng)用。通過學(xué)習(xí)，不僅讓我了解了霍夫曼編碼的歷史、原理和編碼的步驟還有它在數(shù)據(jù)壓縮中的應(yīng)用，也使我對霍夫曼編碼有了重新的認(rèn)識。在沒學(xué)習(xí)之前，聽到數(shù)據(jù)壓縮，我很茫然，但是在學(xué)習(xí)之后，我發(fā)現(xiàn)它其實并沒有我想象中那么復(fù)雜，就是如何更好地編碼，使的原本很復(fù)雜的信息可以得到有效的壓縮。霍夫曼編碼雖然優(yōu)點很突出，編碼效率最高，但是它也有它的缺點。采用霍夫曼編碼時有兩個問題值得我們注意：（1）、變長編碼在理想條件下可以無失真地譯碼，但是當(dāng)變長碼通過信道傳送時，如果有某一個碼兀符號出現(xiàn)了傳輸錯誤，則因為一個碼字中有某一個碼兀發(fā)生了變化，就可能誤認(rèn)為是另一個碼字，結(jié)果會造成后面一系列碼字也譯碼錯誤，這種現(xiàn)象稱為差錯的擴散。當(dāng)然也可以采用一定的措施，是錯了一段以后，能恢復(fù)正確的碼字分割和譯碼。所以，一般要求在傳輸過程中差錯很少，或者添加糾錯用的監(jiān)督碼位，但是這樣一來會降低編碼效率。（2）、霍