哈夫曼編碼的方法

1、1 .哈夫曼編碼的方法編碼過程如下：(1)將信源符號(hào)按概率遞減順序排列；(2)把兩個(gè)最小的概率加起來，作為新符號(hào)的概率；重復(fù)步驟(1) 、 (2),直到概率和達(dá)到1為止；(4)在每次合并消息時(shí)，將被合并的消息賦以 1和0或0和1 ;(5)尋找從每個(gè)信源符號(hào)到概率為1處的路徑，記錄下路徑上的1和0;(6)對(duì)每個(gè)符號(hào)寫出1、0序列(從碼數(shù)的根到終節(jié)點(diǎn))。2 .哈夫曼編碼的特點(diǎn) 哈夫曼方法構(gòu)造出來的碼不是唯一的。原因在給兩個(gè)分支賦值時(shí) ，可以是左支(或上支)為0,也可以是右支(或下支)為0,造成 編碼的不唯一。當(dāng)兩個(gè)消息的概率 相等時(shí)，誰前誰后也是隨機(jī)的，構(gòu)造出來的碼字就不是唯一的。 哈夫曼編碼碼字

2、字長(zhǎng)參差不齊，因此硬件實(shí)現(xiàn)起來不大方便。 哈夫曼編碼對(duì)不同的信源的編碼效率是不同的。 當(dāng)信源概率是 2的負(fù)嘉時(shí)，哈夫曼碼的編碼效率達(dá)到 100%; 當(dāng)信源概率相等時(shí)，其編碼效率最低。 只有在概率分布很不均勻時(shí)，哈夫曼編碼才會(huì)收到顯著的效果，而在信源分布均勻的情況下，一般不使用哈夫曼編碼。對(duì)信源進(jìn)行哈夫曼編碼后，形成了一個(gè)哈夫曼編碼表。解碼時(shí) ，必須參照這一哈夫編碼表才能正確譯碼。在信源的存儲(chǔ)與傳輸過程中必須首先存儲(chǔ)或傳輸這一哈夫曼編碼表在實(shí)際計(jì)算壓縮效果時(shí)，必須考慮哈夫曼編碼表占有的比特?cái)?shù)。在某些應(yīng)用場(chǎng)合，信源概率服從于某一分布或存在一定規(guī)律（這主要由大量的統(tǒng)計(jì)得到）,這樣就可以在發(fā)送端和接收

3、端固定哈夫曼編碼表,在傳輸數(shù)據(jù)時(shí)就省去了傳輸哈夫曼編碼表,這種方法稱為哈夫曼編碼表缺省使用。使用缺省的哈夫曼編碼表有兩點(diǎn)好處：降低了編碼的時(shí)間，改變了編碼和解碼的時(shí)間不對(duì)稱性便于用硬件實(shí)現(xiàn)，編碼和解碼電路相對(duì)簡(jiǎn)單。這種方法適用于實(shí)時(shí)性要求較強(qiáng)的場(chǎng)合。雖然這種方法對(duì)某一個(gè)特定應(yīng)用來說不一定最好，但從總體上說，只要哈夫曼編表基于大量概率統(tǒng)計(jì) 其編碼效果是足夠好的。3.哈夫曼編碼舉例現(xiàn)在有8個(gè)待編碼的符號(hào) m0 ,m0它們的概率如下表所示，使用霍夫曼編碼算法求出8個(gè)符號(hào)所分配的代碼。（寫出編碼樹）待編碼的符號(hào)概率m00.2mi0.4m20.1m30.15m40.03m50.04m60.07m70.0

4、1解：為了進(jìn)行哈夫曼編碼，先把這組數(shù)據(jù)由大到小排列 ，再按上方法處理(1 )將信源符號(hào)按概率遞減順序排列。(2)首先將概率最小的兩個(gè)符號(hào)的概率相加，合成一個(gè)新的數(shù)值。(3)把合成的數(shù)值看成是一個(gè)新的組合符號(hào)概率，重復(fù)上述操作，直到剩下最后兩個(gè)符號(hào)。5.4.2 shannon-famo 編碼shannon-famo(s-f) 編碼方法與 huffman的編碼方法略有區(qū)別，但有時(shí)也能編出最佳碼。1 . s-f碼主要準(zhǔn)則符合即時(shí)碼條件；在碼字中,1和0是獨(dú)立的，而且是(或差不多是)等概率的。這樣的準(zhǔn)則一方面能保證無需用間隔區(qū)分碼字，同時(shí)又保證每一位碼字幾乎有1位的信息量2 . s-f碼的編碼過程信源

5、符號(hào)按概率遞減順序排列 ；,把符號(hào)集分成兩個(gè)子集，每個(gè)子集的概率和相等或近似相等對(duì)第一個(gè)子集賦編碼0,對(duì)第二個(gè)子集賦編碼1;重復(fù)上述步驟，直到每個(gè)子集只包含一個(gè)信源符號(hào)為止。1 .4.3游程編碼游程編碼（簡(jiǎn)寫為rle或rlc ）是一種十分簡(jiǎn)單的壓縮方法，它將數(shù)據(jù)流中連續(xù)出現(xiàn)的字符（稱為游程）用單一的記號(hào)來表示。例如，字符串a(chǎn) b a c c c b b a a a a可以壓縮為a b a 3c 2b 4a游程編碼的壓縮效果不太好，但由于簡(jiǎn)單，編碼/解碼的速度非常快，因此仍然得到廣 泛的應(yīng)用。許多圖形和視頻文件，如.bmp,.tif 及.avi等，都使用了這種壓縮。2 .4.4算術(shù)編碼算術(shù)編碼把

6、一個(gè)信源集合表示為實(shí)數(shù)線上的0到1之間的一個(gè)區(qū)間。這個(gè)集合中的每個(gè)元素都要用來縮短這個(gè)區(qū)間。信源集合的元素越多，所得到的區(qū)間就越小，當(dāng)區(qū)間變小時(shí)，就需要更多的數(shù)位來表示這個(gè)區(qū)間 ，這就是區(qū)間作為代 碼的原理。算術(shù)編碼首先假設(shè)一個(gè)信源的概率模型，然后用這些概率來縮小表示 信源集的區(qū)間。3 .舉例說明算術(shù)編碼過程例設(shè)英文元音字母采用固定模式符號(hào)概率分配如下.字符aeiou概率0.20.30.10.20.2范圍0,0.20.2,0.50.5,0.60.6,0.80.8,1.0設(shè)編碼的數(shù)據(jù)串為eai o令high為編碼間隔的高端，low為編碼間隔的低端，range為編碼間隔的長(zhǎng)度，rangelow為編

7、碼字符分配的間隔低端，rangehigh 為編碼字符分配的間隔高端。初始 high=1,low=0, range = high-low , 一個(gè)字符編碼后新的low 和high按下式計(jì)算：low =low + range x rangelowhigh =low + range x rangehigh(1) 在第一個(gè)字符 e 被編碼時(shí),e 的 rangelow = 0.2,rangehigh=0.5,因此：low =0 + 1x0.2 = 0.2high=0 + 1x0.5 = 0.5range=high low=0.5 0.2=0.3此時(shí)分配給e的范圍為0.2,0.5 o(2)第二個(gè)字符 a編

8、碼時(shí)使用新生成范圍 0.2,0.5,a 的rangelow=0,rangehigh=0.2, 因此：low=0.2十 0.3x0=0.2high=0.2 +0.3 x0.2=0.26range=0.06范圍變成0.2,0.26(3)對(duì)下一個(gè)字符 i 編號(hào),i 的 rangelow=0.5,rangehigh=0.6,則：low=0.2+ 0.06 x 0.5=0.23high=0.2 + 0.06 x0.6=0.236即用0.23,0.236表示數(shù)據(jù)串eai,如果解碼器知道最后范圍是0.23,0.236 這一范圍，它馬上可解得一個(gè)字符為e,然后依次得到惟一解a,即最終得到eai 。4 .算術(shù)編碼的特點(diǎn)不必預(yù)先定義概率模型，自適應(yīng)模式具有獨(dú)特的優(yōu)點(diǎn)；信源符號(hào)概率接近時(shí)，建議使用算術(shù)編碼，這種情況下其效率高于huffman 編碼；算術(shù)編碼繞過了用一個(gè)特定的代碼替代一個(gè)輸入符號(hào)的想法，用一