哈夫曼編碼的方法

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

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

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

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

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

6、一個信源集合表示為實數(shù)線上的0到1之間的一個區(qū)間。這個集合中的每個元素都要用來縮短這個區(qū)間。信源集合的元素越多，所得到的區(qū)間就越小，當(dāng)區(qū)間變小時，就需要更多的數(shù)位來表示這個區(qū)間 ，這就是區(qū)間作為代 碼的原理。算術(shù)編碼首先假設(shè)一個信源的概率模型，然后用這些概率來縮小表示 信源集的區(qū)間。3 .舉例說明算術(shù)編碼過程例設(shè)英文元音字母采用固定模式符號概率分配如下.字符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為編碼間隔的長度，rangelow為編

7、碼字符分配的間隔低端，rangehigh 為編碼字符分配的間隔高端。初始 high=1,low=0, range = high-low , 一個字符編碼后新的low 和high按下式計算：low =low + range x rangelowhigh =low + range x rangehigh(1) 在第一個字符 e 被編碼時,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此時分配給e的范圍為0.2,0.5 o(2)第二個字符 a編

8、碼時使用新生成范圍 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)對下一個字符 i 編號,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 這一范圍，它馬上可解得一個字符為e,然后依次得到惟一解a,即最終得到eai 。4 .算術(shù)編碼的特點不必預(yù)先定義概率模型，自適應(yīng)模式具有獨特的優(yōu)點；信源符號概率接近時，建議使用算術(shù)編碼，這種情況下其效率高于huffman 編碼；算術(shù)編碼繞過了用一個特定的代碼替代一個輸入符號的想法，用一