霍夫曼編碼及其應(yīng)用

1、精選優(yōu)質(zhì)文檔-傾情為你奉上畢 業(yè) 設(shè) 計(jì)（論文）題 目：霍夫曼編碼及其應(yīng)用學(xué) 院： 數(shù) 理 學(xué) 院 專業(yè)名稱： 信息與計(jì)算科學(xué) 學(xué) 號(hào)： 學(xué)生姓名： 張 浩 指導(dǎo)教師： 韓 海 清 2011 年 4 月 20 日摘要本文首先對(duì)二元霍夫曼編碼進(jìn)行了細(xì)致研究，并對(duì)其算法進(jìn)行擴(kuò)展，得到了適用于多元霍夫曼編碼的算法。然后，對(duì)霍夫曼編碼的前綴性，最優(yōu)性進(jìn)行了證明。最后實(shí)現(xiàn)了霍夫曼編碼在決策論中應(yīng)用。關(guān)鍵詞碼 ； 熵 ； 霍夫曼編碼 ； 決策樹ABSTRACTThis paper first studied binary Huffman coding, and conducted a detailed s

2、tudy on its algorithm suitable for expansion, get multiple Huffman coding algorithm. Meanwhile, Huffman coding prefix sex, optimality proved. Finally realized Huffman coding applied in rigorous.KEYWORDS The Coding； The Entropy； Huffman Coding； Decision tree 目 錄第一章 引言1948年，美國(guó)數(shù)學(xué)家香農(nóng)（C.E.Shannon）在貝爾系統(tǒng)電話

3、雜志發(fā)表了題為“通信的數(shù)學(xué)理論”的長(zhǎng)篇論文。這篇論文以概率論為工具，深刻闡述了通信工程的一系列基本理論問題，給出了計(jì)算信源信息量和信道容量的方法和一般公式，得到了一組表征信息傳遞重要關(guān)系的編碼定理，從而創(chuàng)立了信息論。1959年，香農(nóng)在發(fā)表的“保真度準(zhǔn)則下的離散信源編碼定理” （Coding theorems for a discrete source at the fidelity criterion）一文中系統(tǒng)的提出了信息率失真理論（rate-distortion theory）,為信源壓縮編碼的研究奠定了理論基礎(chǔ)。在信息傳輸過程中，信源序列通過信源編碼器實(shí)現(xiàn)對(duì)信源冗余度的壓縮，變成編碼序列

4、，編碼序列通過信源譯碼器恢復(fù)成信源序列。根據(jù)恢復(fù)序列的效果，可把信源編譯器分為兩類，即無失真信源編碼和限失真信源編碼。在無失真信源編碼的過程中，編、譯碼過程是可逆的，即信源符號(hào)可以通過編碼序列無差錯(cuò)地恢復(fù)。為提高傳輸有效性，我們總是希望在保證無失真的條件下盡量壓縮碼率（編碼后傳輸每信源符號(hào)所需的二元碼符號(hào)數(shù)），但這種壓縮是否有限度是一個(gè)必須要解決的理論問題。香農(nóng)第一定理也就是無失真信源編碼定理對(duì)這個(gè)問題做了明確回答。定理指出，只要信源編碼碼率不小于信源的熵就存在無失真信源編碼，同時(shí)還指出如果信源編碼的碼率大于信源編碼的熵就不存在無失真信源編碼。同時(shí)，定理還給出了進(jìn)行無失真信源編碼的理論極值，論

5、證與指出了理想最佳信源編碼是存在的。但是并沒有給出信源編碼的實(shí)際構(gòu)造方法和實(shí)用碼的結(jié)構(gòu)。編碼的目的就是為了優(yōu)化通信系統(tǒng)。一般來說，通信系統(tǒng)的性能指標(biāo)是有效性、可靠性、安全性和經(jīng)濟(jì)性。隨著科學(xué)技術(shù)的發(fā)展和需求，人們廣泛致力于對(duì)各種文本、圖片、圖形、語(yǔ)言、聲音、活動(dòng)圖像和影視信號(hào)等實(shí)際信源進(jìn)行了實(shí)用壓縮方法和技術(shù)研究，使信源的數(shù)據(jù)壓縮技術(shù)得以蓬勃發(fā)展和逐漸走向成熟。霍夫曼在1952年提出了一種構(gòu)造最佳碼得方法，我們稱之為霍夫曼編碼?；舴蚵幋a適用于多遠(yuǎn)獨(dú)立信源，對(duì)于多元獨(dú)立信源來說它是最佳碼。它充分利用了信源概率分布的特性進(jìn)行編碼，是一種最佳的逐個(gè)符號(hào)的編碼方法。第二章 主要概念 香農(nóng)定理作為信息

6、論的基礎(chǔ)理論，我們有必要對(duì)進(jìn)行簡(jiǎn)要介紹。下面我們給出香農(nóng)三大定理：2.1香農(nóng)三大定理香農(nóng)三大定理是的。香農(nóng)三大定理是存在性定理，雖然并沒有提供具體的編碼實(shí)現(xiàn)方法，但為通信信息的研究指明了方向。4香農(nóng)第一定理是可變長(zhǎng)無失真信源編碼定理。香農(nóng)第二定理是有噪信道編碼定理。香農(nóng)第三定理是保失真度準(zhǔn)則下的有失真信源編碼定理。具體如下:2.1.1香農(nóng)第一定理(可變長(zhǎng)無失真信源編碼定理) 1設(shè)信源S的熵H(S),無噪離散信道的信道容量為C,于是,信源的輸出可以進(jìn)行這樣的編碼,使得信道上傳輸?shù)臑槊棵雮€(gè)信源符號(hào).其中a可以是任意小的正數(shù), 要使傳輸?shù)钠骄俾蚀笥谑遣豢赡艿摹?.1.2香農(nóng)第二定理（有噪信道編碼定

7、理）1設(shè)某信道有r個(gè)輸入符號(hào),s個(gè)輸出符號(hào),信道容量為C,當(dāng)信道的信息傳輸率R碼長(zhǎng)N足夠長(zhǎng),總可以在輸入的集合中(含有rN個(gè)長(zhǎng)度為N的碼符號(hào)序列),找到M （(,a為任意小的正數(shù))個(gè),分別代表M個(gè)等可能性的消息,組成一個(gè)碼以及相應(yīng)的譯碼規(guī)則,使信道輸出端的最小平均錯(cuò)誤譯碼概率Pmin達(dá)到任意小。2.1.3香農(nóng)第三定理（保失真度準(zhǔn)則下的有失真信源編碼定理）1設(shè)R(D)為一離散無記憶信源的信息率失真函數(shù),并且選定有限的失真函數(shù),對(duì)于任意允許平均失真度,和任意小的,以及任意足夠長(zhǎng)的碼長(zhǎng)N,則一定存在一種信源編碼W,其碼字個(gè)數(shù)為，而編碼后碼的平均失真度。 2.2霍夫曼編碼1952年David. A.

8、Huffman提出了一種構(gòu)造最佳碼的方法稱之為霍夫曼碼?；舴蚵a適用于多元獨(dú)立信源，對(duì)于多元獨(dú)立信源來說它是最佳碼。它充分利用了信源概率分布的特性進(jìn)行編碼，是一種最佳的逐個(gè)符號(hào)的編碼方法。2第三章 二元霍夫曼編碼及其算法二元霍夫曼編碼方法的編碼步驟如下：1） 將q個(gè)信源符號(hào)按概率分布的大小，以遞減次序排列起來，設(shè)2） 用0和1碼分別分配給概率最小的兩個(gè)信源符號(hào)，并將這兩個(gè)概率最小的信源符號(hào)合并成一個(gè)新符號(hào)，并用這兩個(gè)最小概率之和作為新符號(hào)的概率，從而得到只包含q-1個(gè)符號(hào)的新信源，稱為S信源的縮減信源。3） 把縮減信源的符號(hào)仍按概率大小以遞減次序排列，再將最后兩個(gè)概率最小的符號(hào)合并成一個(gè)新符號(hào)

9、，并分別用0和1碼表示，這樣又形成q-2個(gè)符號(hào)的縮減信源。4） 依次繼續(xù)下去，直至縮減信源最后只剩兩個(gè)符號(hào)為止。再將最后兩個(gè)新符號(hào)分別用0和1碼符號(hào)表示。最后這兩個(gè)符號(hào)的概率之和比為1.然后從最后一級(jí)縮減信源開始，一編碼路徑右后向前返回，就得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即得對(duì)應(yīng)的碼字?，F(xiàn)在，給出一個(gè)具體的例子來說明這種編碼方法。【例1】設(shè)單符號(hào)離散無記憶信源如下，要求對(duì)其進(jìn)行二元霍夫曼編碼。 =可以計(jì)算出該信源的熵為：H（X）= -=1.978b從而可以計(jì)算出每個(gè)符號(hào)的平均二元字符數(shù)為=10.46+20.30+30.12+40.06+50.03+60.02+60.01 =1.9900b該編

10、碼的效率為=（1.9781/1.9900）=99.4%其編碼過程如表3.1所示表3.1 二元霍夫曼編碼（1）概率 碼概率 碼概率 碼概率 碼概率 碼概率 碼0.46 10.30 000.12 0100.06 01100.03 011100.02 0.01 0.46 10.30 000.12 0100.06 01100.03 011100.03 011110.46 10.30 000.12 0100.06 01100.06 01110.46 10.30 000.12 0100.12 0110.46 10.30 000.24 010.54 00.46 1現(xiàn)在將看到霍夫曼編碼不是唯一的?？剂俗钚蓚€(gè)

11、概率的組合（符號(hào)和），它們的和為0.03，等于與符號(hào)對(duì)應(yīng)的下一個(gè)較高的概率。那么第二步，可以選擇使這個(gè)組合搞了（比如說等于符號(hào)）高于或低于符號(hào)。假定把組合搞了放在下面，繼續(xù)進(jìn)行又將發(fā)現(xiàn)和組合后的概率為0.06，等于符號(hào)的概率。我們又一次可以選擇是組合概率高于或低于。每次做出一種選擇時(shí)，最后導(dǎo)致符號(hào)的碼子改變。每次在有兩個(gè)相同概率的情況下要做出一種選擇時(shí)，我們把組合符號(hào)的概率放在上面。該信源的熵為H（X）= -=1.9781b而平均每個(gè)符號(hào)的比特?cái)?shù)為=10.46+20.30+30.12+40.06+50.03+60.02+60.01 =1.990b該編碼的效率為 =（1.9781/1.9900）

12、=99.4%因此兩種編碼同樣有效。 表3.1 二元霍夫曼編碼（2）概率 碼概率 碼概率 碼概率 碼概率 碼概率 碼0.46 10.30 000.12 0110.06 01010.03 010010.02 0.01 0.46 10.30 000.12 0100.06 0110.03 010000.03 010010.46 10.30 000.12 0100.6 01000.06 01010.46 10.30 000.12 0100.12 0110.46 10.30 000.24 010.54 00.46 1第四章 一般霍夫曼編碼及其算法 下面我們?cè)倥e個(gè)例子，討論一下一般情況下霍夫曼編碼算法的步驟

13、。由于信源字母的選取不影響對(duì)應(yīng)編碼方案的平均碼字長(zhǎng)度，它只與信源概率分布有關(guān)，因此在下文中用概率分布=（，）直接表示信源。【例2】已給信源概率分布為=(0.24,0.20,0.18,0.13,0.10,0.06,0.05,0.03,0.01)，信號(hào)字母表U=0,1,2,3求信源的霍夫曼編碼。解 霍夫曼編碼方案的主要運(yùn)算步驟是構(gòu)造霍夫曼數(shù)據(jù)壓縮表與霍夫曼編碼表。它的運(yùn)算步驟如下。1. 參照表4.1構(gòu)造霍夫曼數(shù)據(jù)壓縮表（1）首先把概率分布的概率按降序排列，并把它們作為霍夫曼數(shù)據(jù)壓縮表的第一列，該列長(zhǎng)度為a=9。第二列、第四列、第六列為碼元，暫空。（2）把第一列的三個(gè)最小概率相加，得到新的一列的概率

14、分布，重新安降序排列，成為霍夫曼數(shù)據(jù)壓縮表中的第三列。這時(shí)第三列的長(zhǎng)度為7，相加后的數(shù)為0.09，我們將其用方框標(biāo)出。（3）把第三列的4個(gè)最小的概率相加得到新的一列概率分布，重新安將序排列，成為霍夫曼數(shù)據(jù)壓縮表中的第五列。這時(shí)的長(zhǎng)度為4，相加后的數(shù)為0.38，我們用方框標(biāo)出。這樣霍夫曼數(shù)據(jù)壓縮表構(gòu)造完成，有關(guān)計(jì)算于列表結(jié)果見表4.1表4.1概率 碼概率 碼概率 碼0.240.200.180.130.100.060.050.030.010.240.200.180.130.100.060.240.200.182. 用霍夫曼數(shù)據(jù)壓縮表構(gòu)造霍夫曼編碼表（1）因霍夫曼數(shù)據(jù)壓縮表1的第五列的概率分布只有4

15、行，因此他們的編碼正好是0,1,2,3。把這四個(gè)數(shù)填入霍夫曼編碼表的第六列。因此，第六列是一個(gè)碼長(zhǎng)為1的編碼。（2）在第五列中，帶方框的概率為0.38，它對(duì)應(yīng)的第六列的編碼為0，而0.38是由第三列的0.13,0.10,0.09,0.06這四個(gè)數(shù)相加而成。這樣我們構(gòu)造第三列概率分布的編碼為：第三列的0.13,0.10,0.09,0.06這四個(gè)數(shù)的編碼是在0.38的編碼后邊延長(zhǎng)1個(gè)數(shù)，它們分別為00,01,02,03.第三列中0.24, 0.20, 0.18這三個(gè)數(shù)的編碼與第五列的編碼相同，仍為1, 2, 3,不變。把0.24, 0.20, 0.18, 0.13, 0.10, 0.19, 0.0

16、6這7個(gè)數(shù)的編碼1,2,3,00,01,02,03列入霍夫曼編碼表的第四列。（3）在表的第三列中，帶方框的概率為0.09它對(duì)應(yīng)的第四列的編碼為02，而0.09是由第一列的0.05,0.03,0.01這三個(gè)數(shù)相加而成。這樣我們構(gòu)造第一列概率分布的編碼為第一列的前六個(gè)數(shù)的編碼與第三列所對(duì)應(yīng)的編碼相同。第一列中0.05,0.03,0.01這三個(gè)數(shù)的編碼是在第三列的0.09的編碼02后面延長(zhǎng)1個(gè)數(shù)，因此他們分別為020,021,022.把第一列個(gè)概率的編碼列入霍夫曼編碼表的第二列，最終完成霍夫曼編碼表，各項(xiàng)計(jì)算結(jié)果見表4.2表4.2概率 碼概率 碼概率 碼0.24 10.20 20.18 30.13

17、000.10 010.06 030.05 0200.03 0210.01 0220.24 10.20 20.18 30.13 000.10 01 020.06 03 00.24 10.20 20.18 3 下面考慮一般情形。令碼字母表為U=0，1,2,3，r-1，信源概率分布=（，），對(duì)此構(gòu)造霍夫曼編碼的運(yùn)算步驟如下。1) 簡(jiǎn)單情形下的霍夫曼編碼 如果ar，那么稱信源為簡(jiǎn)單情形下的編碼。這時(shí)直接取每個(gè)消息元的編碼為信號(hào)元，如取，這樣我們只考慮ar的情形。2) 霍夫曼數(shù)據(jù)壓縮表a) 設(shè)計(jì)并構(gòu)造霍夫曼壓縮表如下。由ar確定霍夫曼數(shù)據(jù)壓縮表的行、列數(shù)。如記2k+2是數(shù)據(jù)壓縮表的列數(shù)，那么k為使的最大

18、值，因此取，其中Int（z）是正數(shù)z的整數(shù)部分，而數(shù)據(jù)壓縮表的第1,2,3，2k-1，2k+1列的行數(shù)（或列的長(zhǎng)度）分別為a,kr-k+1,(k-1)r-k+2,3r-2,2r-1,r.這時(shí)除了第1,3列之外，后一列比前一列的長(zhǎng)度少r-1，因此它的行數(shù)可用公式表示。b) 霍夫曼壓縮表的第一列由概率分布（，）確定，并按將序排列。c) 霍夫曼壓縮表的第三列由第一列確定，它將第一列的最后a-kr+k-1=0,那么第三列與第一列相同。d) 霍夫曼壓縮表的第五列由第三列確定，它將第三列的最后r-1個(gè)分量相加，并按大小次序重新排列，相加所得到的數(shù)框出。e) 霍夫曼壓縮表的第七列由第五列確定，它將第五列的最

19、后r-1個(gè)分量相加，并按大小次序重新排列，相加所得到的數(shù)框出。f) 以此類推，由此得到霍夫曼壓縮表的第九，十一，列，最后一列長(zhǎng)度為r，它由前一列確定。依次構(gòu)成霍夫曼壓縮表。3) 霍夫曼壓縮表的有關(guān)記號(hào)由以上霍夫曼壓縮表的構(gòu)造，引進(jìn)一下記號(hào)。記 ， （4.01）為霍夫曼壓縮表的第2j-1列概率分布，其中前面已給定。且記 （4.02）是2j-1列的最后r-1個(gè)分量之和，在第j列的行上。4) 霍夫曼編碼表由霍夫曼壓縮表及以上式子，用遞推法可以構(gòu)造霍夫曼編碼表，在霍夫曼編碼表中，奇數(shù)列為概率分布列，已由霍夫曼壓縮表確定，因此只要確定霍夫曼編碼表中的偶數(shù)列即可。3遞推運(yùn)算步驟如下。a) 霍夫曼壓縮表的最

20、后一列r個(gè)分量，因此賦予他們的編碼是（0,1,，r-1），而且可自上而下排列，并填寫在第2k+2列的空格內(nèi)，因此霍夫曼編碼表的第2k+1，2k+2列確定。b) 如果第2j+1，2j+2列確定，其中2j+1列是概率分布列，而2j+2列是編碼列，記第2j+2列的碼元分別為，其中是不定長(zhǎng)碼元。c) 在2j+1列中，是由式（1.02）所給定的數(shù)，他相應(yīng)的編碼確定為，這時(shí)第2j列的編碼確定為前個(gè)的碼元與第2j+2列說對(duì)應(yīng)的概率的碼元相同。最后r個(gè)的碼元分別為（，0），（，1），.，（，r-1）。其中（，u）表示在碼元后面增加一個(gè)信號(hào)字符u。這樣第2j-1,2j列的概率分布與它的編碼完全確定。d) 以此類

21、推，得到霍夫曼編碼表中的全體編碼，這時(shí)第二列的編碼由第四列的編碼確定，他的最后b個(gè)概率的碼元由做延伸，相應(yīng)的碼元為 （，0），（，1），.（，b-1）其中b=a-(kr-k+1)。第五章 霍夫曼編碼的性能分析5.1霍夫曼編碼的前綴性定理4.1（霍夫曼碼的前綴性）由霍夫曼編碼算法所得到的霍夫曼碼是前綴碼。證明 由霍夫曼編碼算法中的各步驟所知，第2k+2列中各碼元各不相同，且第2k列中各碼元與第2k+2列中碼元相同或是某各碼元的延伸，因此第2k列中各碼元互不相同，且每個(gè)碼元不能成為另一碼元的前綴。一般情形，如果第t列中各碼元各不相同，且第t-1列中各碼元與第t列中碼元相同或是某個(gè)碼元的延伸，那么第

22、t-1列中各碼元互不相同，且每個(gè)碼元不能成為另一個(gè)碼元的前綴。由此遞推，最后得到第一列中各碼元互不能成為另一碼元的前綴。由此定理得證。5.2 霍夫曼編碼的最優(yōu)性定理定理4.2 （霍夫曼編碼的最優(yōu)性定理）由霍夫曼編碼算法所得到的霍夫曼編碼一定是最優(yōu)碼。對(duì)同一信源，分別是霍夫曼碼與任一前綴碼，那么必有成立。4第六章 霍夫曼編碼的應(yīng)用上面討論了霍夫曼碼，并且證明了霍夫曼碼是最佳碼。當(dāng)N不是很大時(shí)，它能使無失真編碼的效率接近于1.但霍夫曼碼是分組碼（或稱塊碼），在實(shí)際應(yīng)用時(shí)設(shè)備較復(fù)雜。首先，每個(gè)信源符號(hào)所對(duì)應(yīng)的碼長(zhǎng)不同。一般情況下，信源符號(hào)以恒速輸出，信道也是恒速傳輸?shù)?。通過編碼后，會(huì)造成編碼輸出每秒

23、的比特?cái)?shù)不是常量，因而不能直接由信道來傳送。其次，信源符號(hào)與碼字之間不能用某種有規(guī)律的數(shù)學(xué)方法對(duì)應(yīng)起來。在對(duì)信源進(jìn)行霍夫曼編碼后，形成一個(gè)霍夫曼編碼表，必須通過查表的方法來進(jìn)行編、譯碼5。在信源存儲(chǔ)與傳輸過程中必須首先存儲(chǔ)這一霍夫曼編碼表，這樣就會(huì)影響實(shí)際信源的壓縮效率。有時(shí)為了實(shí)用，嘗嘗先基于大量概率統(tǒng)計(jì)，建好霍夫曼編碼表。這樣編碼時(shí)不需進(jìn)行概率統(tǒng)計(jì)和建立編碼表；另外在接收端和發(fā)送端可以先固定建好的霍夫曼碼表，傳輸時(shí)也不用傳輸編碼表。但當(dāng)N增大時(shí)，信源符號(hào)數(shù)目增多，所需存儲(chǔ)碼表的容量增大，使設(shè)備復(fù)雜化，同時(shí)也是編、譯碼時(shí)查表搜索時(shí)間增大。6盡管如此，霍夫曼方法還是一種較具體和有效的無失真信源

24、編碼方法，它便于硬件實(shí)現(xiàn)和計(jì)算機(jī)上軟件實(shí)現(xiàn)。所以它仍應(yīng)用于文件傳真，語(yǔ)聲處理和圖像處理的數(shù)據(jù)壓縮中。（霍夫曼編碼在線性表中的編程實(shí)現(xiàn)見附錄1）而今，霍夫曼編碼還可以用來做決策樹。如果有n個(gè)互斥隨機(jī)事件，概率分別為，現(xiàn)用某種測(cè)試方法分步對(duì)所選擇的目標(biāo)事件進(jìn)行識(shí)別，要求具有最小的決策平均次數(shù)，可以通過對(duì)這些事件進(jìn)行霍夫曼編碼來實(shí)現(xiàn)，因?yàn)榛舴蚵幋a具有最小平均碼長(zhǎng)?；舴蚵幋a形成的碼樹可以視為決策樹，方向從根到葉，其中每個(gè)節(jié)點(diǎn)都是決策節(jié)點(diǎn)。決策樹被廣泛應(yīng)用在企業(yè)數(shù)據(jù)處理、系統(tǒng)分析以及數(shù)據(jù)挖掘等領(lǐng)域中。下面我們舉個(gè)例子說明。【例3】甲手中有4張紙牌，點(diǎn)數(shù)分別為1,2,3,4，要求乙猜：乙可以向甲提問題

25、，甲只能用是否來回答。求乙平均最少問幾個(gè)問題可以猜到紙牌的點(diǎn)數(shù)和相應(yīng)的策略。（1）1,2,3,4,的概率均為1/4的決策樹（2）1,2,3,4,的概率分別為1/2,1/4，1/8,1/8的決策樹。解對(duì)于決策樹問題，我們要首先進(jìn)行霍夫曼編碼，然后將霍夫曼編碼碼樹變成決策樹決策的設(shè)計(jì)方法：沒步?jīng)Q策結(jié)果應(yīng)該與節(jié)點(diǎn)分支的概率匹配。（1） 由于各點(diǎn)數(shù)概率相同，因此得到如圖6.1所示的決策樹（2） 各點(diǎn)數(shù)概率不同，依據(jù)霍夫曼編碼得到如圖6.2所示的決策樹。n2? n3? n1? n=1 n=2 n=3 n=4N(1/2)Y(1/2)N(1/4)Y(1/4)N(1/4)Y(1/4)圖6.1決策樹n2? n3

26、? n1? n=1 n=2 n=3 n=4Y(1/2)Y(1/8)N(1/2)N(1/4)N(1/8)Y(1/8)圖6.2決策樹第七章 總結(jié)與展望本文先通過對(duì)二元霍夫曼編碼進(jìn)行研究，得出了二元霍夫曼編碼算法：將q個(gè)信源符號(hào)按概率分布的大小，以遞減次序排列起來，設(shè)；用0和1碼分別分配給概率最小的兩個(gè)信源符號(hào)，并將這兩個(gè)概率最小的信源符號(hào)合并成一個(gè)新符號(hào)，并用這兩個(gè)最小概率之和作為新符號(hào)的概率，從而得到只包含q-1個(gè)符號(hào)的新信源，稱為S信源的縮減信源。把縮減信源的符號(hào)仍按概率大小以遞減次序排列，再將最后兩個(gè)概率最小的符號(hào)合并成一個(gè)新符號(hào)，并分別用0和1碼表示，這樣又形成q-2個(gè)符號(hào)的縮減信源。依次

27、繼續(xù)下去，直至縮減信源最后只剩兩個(gè)符號(hào)為止。再將最后兩個(gè)新符號(hào)分別用0和1嘛符號(hào)表示。最后這兩個(gè)符號(hào)的概率之和比為1.然后從最后一級(jí)縮減信源開始，一編碼路徑右后向前返回，就得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即得對(duì)應(yīng)的碼字。再推廣至一般霍夫曼編碼即多元霍夫曼編碼并得到多元霍夫曼編碼算法：將q個(gè)信源符號(hào)按概率分布的大小，以遞減次序排列起來，設(shè)；用0，1,2.m-1碼分別分配給概率最小的m個(gè)信源符號(hào)，并將這兩個(gè)概率最小的信源符號(hào)合并成一個(gè)新符號(hào)，并用這m個(gè)最小概率之和作為新符號(hào)的概率，從而得到只包含q-（m-1）個(gè)符號(hào)的新信源，稱為S信源的縮減信源。把縮減信源的符號(hào)仍按概率大小以遞減次序排列，再將最

28、后m個(gè)概率最小的符號(hào)合并成一個(gè)新符號(hào)，并分別用0，1,2.m-1碼表示，這樣又形成q-2（m-1）個(gè)符號(hào)的縮減信源。依次繼續(xù)下去，直至縮減信源最后只剩m個(gè)符號(hào)為止。再將最后兩個(gè)新符號(hào)分別用0，1,2.m-1嘛符號(hào)表示。最后這m個(gè)符號(hào)的概率之和比為1.然后從最后一級(jí)縮減信源開始，一編碼路徑右后向前返回，就得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即得對(duì)應(yīng)的碼字?；舴蚵幋a廣泛應(yīng)用于文件傳真，語(yǔ)聲處理和圖像處理的數(shù)據(jù)壓縮中。但是霍夫曼算法的應(yīng)用卻更為廣泛，例如上面提到的霍夫曼編碼在決策中的應(yīng)用，以及我最初的設(shè)想：將霍夫曼編碼應(yīng)用到生命科學(xué)中，使有上百萬(wàn)個(gè)脫氧核糖核酸構(gòu)成的DNA序列存儲(chǔ)起來更為迅速，更為節(jié)

29、約空間，但是由于種種原因只停留在設(shè)想階段。未來如有幸接觸到這方面的工作，我將努力將這個(gè)設(shè)想變?yōu)楝F(xiàn)實(shí)。參考文獻(xiàn)1 Shannon, Claude. A Mathematical Theory of Communication. Bell System Technical Journal 27 (July and October, 1948): 379-423 and 623-656.2陳運(yùn). 信息論與編碼M. 北京：電子工業(yè)出版社，20073 Richard B Wells. Applied Coding and Information Theory for EngineersM. Person

30、 Education North Asia Limited and China Machine Press, 20034關(guān)可，王建新，亓淑敏. 信息論與編碼技術(shù)M.北京：清華大學(xué)出版社，20095曹雪虹，張宗橙.信息論與編碼M.北京：清華大學(xué)出版社20096田寶玉，楊潔，賀志強(qiáng)，王曉湘.信息論基礎(chǔ)M.北京：人民郵電出版社，20087 沈世鎰，陳魯生. 編碼理論基礎(chǔ)M.北京：科學(xué)出版社，20028 Robort J.McEliece. Information theory and coding theory . Beijing publishing house of electronics in

31、dustry .2007附錄1#include#include#include#include#include#define LIST_INT_SIZE 100/線性表儲(chǔ)存空間的初始分配量#define LISTINCREMENT 10/線性表儲(chǔ)存空間的分配增量typedef struct/讀取的字母的結(jié)構(gòu)體，包含字母及頻率char data;int ASCII;int rate;ELEM;char RFC; /保存文件中所有內(nèi)容的字符串double CD=0;/*=讀取文件=*/void readfile()FILE *fp;fp=fopen(RFCdoc.txt,r);char ch;in

32、t i=0;while(!feof(fp)ch=fgetc(fp);RFCi=ch;i+;CD+;fclose(fp);/*=線性表=*/typedef structELEM *elem; /儲(chǔ)存空間基址int length; /當(dāng)前長(zhǎng)度int listsize; /當(dāng)前分配的儲(chǔ)存容量Sqlist;int SearchBin(Sqlist ST,int key,int &flag) /折半查找int low,high,mid;low=0;high=ST.length-1;mid=(low+high)/2;while(lowkey)high=mid-1;else if(ST.elemmid.AS

33、CIIkey)low=mid+1;return low;void CreatList(Sqlist &L) /創(chuàng)建一個(gè)順序表int flag,xb,asc;char ch;L.elem=(ELEM *)malloc(LIST_INT_SIZE*sizeof(ELEM);if(!L.elem)printf(分配空間失敗!);exit(0);L.length=0; /空表長(zhǎng)度為0L.listsize=LIST_INT_SIZE;for(int i=0;i=L.listsize)/判斷空間是否足夠ELEM *newbase=(ELEM *)realloc(L.elem,(L.listsize+LIS

34、TINCREMENT)*sizeof(ELEM);if(!newbase)printf(分配空間失敗!);exit(0);L.elem=newbase;L.listsize+=LISTINCREMENT;Elsefor(int j=L.length-1;j=xb;j-)L.elemj+1=L.elemj;L.elemxb.data=ch; L.elemxb.ASCII=asc;L.elemxb.rate=1;L.length+;ElseL.elemxb.rate+;void PrintList(Sqlist L) /輸出順序表for(int i=0;iL.length;i+)printf( %

35、c,%d ,L.elemi.data,L.elemi.rate);/*=赫夫曼編碼=*/typedef structchar data;int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode;void Select(HuffmanTree HT,int n,int &s1,int &s2)int i,j;int temp;for(j=1;j=n;j+)for(i=1;iHTi+1.weight)temp=HTi.weight;HTi.weight=HTi+1.weight;HTi+1.w

36、eight=temp;for(i=1,j=1;i0)，構(gòu)造哈夫曼樹HT， / 并求出n個(gè)字符的哈夫曼編碼HC int i, j, n,m, s1, s2, start; char *cd; int c, f; n=L.length; if (n=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); / 0號(hào)單元未用 for (i=1; i=n; i+) /初始化HTi.weight=L.elemi-1.rate;HTi.data=L.elemi-1.data; HTi.parent=0; HTi.lc

37、hild=0; HTi.rchild=0; for (i=n+1; i=m; i+) /初始化 HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; printf(n哈夫曼樹的構(gòu)造過程如下所示：n); printf(HT初態(tài):n 結(jié)點(diǎn) weight parent lchild rchild); for (i=1; i=m; i+) printf(n%4d%8d%8d%8d%8d,i,HTi.weight, HTi.parent,HTi.lchild, HTi.rchild); printf( 按任意鍵，繼續(xù) .); getch(); f

38、or (i=n+1; i=m; i+) / 建哈夫曼樹 / 在HT1.i-1中選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn)， / 其序號(hào)分別為s1和s2。 Select(HT, i-1, s1, s2); HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; printf(nselect: s1=%d s2=%dn, s1, s2); printf( 結(jié)點(diǎn) weight parent lchild rchild); for (j=

39、1; ji; j+) printf(n%4d%8d%8d%8d%8d%8c,j,HTj.weight, HTj.parent,HTj.lchild, HTj.rchild,HTj.data); printf( 按任意鍵，繼續(xù) .); getch(); /- 從葉子到根逆向求每個(gè)字符的哈夫曼編碼 - HC=(HuffmanCode)malloc(n+1)*sizeof(char *); cd = (char *)malloc(n*sizeof(char); / 分配求編碼的工作空間 cdn-1 = 0; / 編碼結(jié)束符。 for (i=1; i=n; +i) / 逐個(gè)字符求哈夫曼編碼start

40、= n-1; / 編碼結(jié)束符位置 for (c=i, f=HTi.parent; f!=0; c=f, f=HTf.parent) / 從葉子到根逆向求編碼 if (HTf.lchild=c) cd-start = 0; else cd-start = 1; HCi = (char *)malloc(n-start)*sizeof(char); / 為第i個(gè)字符編碼分配空間 strcpy(HCi, &cdstart); / 從cd復(fù)制編碼(串)到HC free(cd); / 釋放工作空間 / HuffmanCoding/*=保存編碼=*/typedef struct/讀取的字母的結(jié)構(gòu)體，包含字

41、母及頻率char data;char *code;int ASCII;CODE;CODE *list;int Search(Sqlist ST,int key)int low,high,mid;low=0;high=ST.length-1;mid=(low+high)/2;while(lowkey)high=mid-1;else if(listmid.ASCIIkey)low=mid+1;return -1;void save(HuffmanTree HT, HuffmanCode HC,Sqlist L)int i,n,k;list=(CODE *)malloc(L.length*sizeof(CODE);for(i=0;iL.length;i+)/初始化listi.data=L.elemi.data;listi.ASCII=L.elemi.ASCII;for(i=1;i=L.length;i+)k=(int)HTi.data;n=Search