哈夫曼編碼的方法

1、1哈夫曼編碼的方法編碼過程如下 :(1) 將信源符號(hào)按概率遞減順序排列 ;(2) 把兩個(gè)最小的概率加起來 , 作為新符號(hào)的概率 ;(3) 重復(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

2、, 造成編碼的不唯一。·當(dāng)兩個(gè)消息的概率 相等時(shí), 誰前誰后也是隨機(jī)的 , 構(gòu)造出來的碼字就不是唯一的。哈夫曼編碼碼字字長(zhǎng)參差不齊 , 因此硬件實(shí)現(xiàn)起來不大方便。哈夫曼編碼對(duì)不同的信源的編碼效率是不同的。 · 當(dāng)信源概率是 2 的負(fù)冪時(shí) , 哈夫曼碼的編碼效率達(dá)到 100%;· 當(dāng)信源概率相等時(shí) , 其編碼效率最低。· 只有在概率分布很不均勻時(shí) , 哈夫曼編碼才會(huì)收到顯著的效果 , 而在信源分布均勻的情況下 , 一般不使用哈夫曼編碼。對(duì)信源進(jìn)行哈夫曼編碼后 , 形成了一個(gè)哈夫曼編碼表。解碼時(shí) , 必須參照這一哈夫編碼表才能正確譯碼。 ·在信源的

3、存儲(chǔ)與傳輸過程中必須首先存儲(chǔ)或傳輸這一哈夫曼編碼表在實(shí)際計(jì)算壓縮效果時(shí) , 必須考慮哈夫曼編碼表占有的比特?cái)?shù)。在某些應(yīng)用場(chǎng)合, 信源概率服從于某一分布或存在一定規(guī)律 ( 這主要由大量的統(tǒng)計(jì)得到 ), 這樣就可以在發(fā)送端和接收端固定哈夫曼編碼表 , 在傳輸數(shù)據(jù)時(shí)就省去了傳輸哈夫曼編碼表 , 這種方法稱為哈夫曼編碼表缺省使用。使用缺省的哈夫曼編碼表有兩點(diǎn)好處:· 降低了編碼的時(shí)間 , 改變了編碼和解碼的時(shí)間不對(duì)稱性 ;· 便于用硬件實(shí)現(xiàn) , 編碼和解碼電路相對(duì)簡(jiǎn)單。這種方法適用于實(shí)時(shí)性要求較強(qiáng)的場(chǎng)合。雖然這種方法對(duì)某一個(gè)特定應(yīng)用來說不一定最好 , 但從總體上說 , 只要哈夫曼編

4、表基于大量概率統(tǒng)計(jì),其編碼效果是足夠好的。3 哈夫曼編碼舉例現(xiàn)在有8個(gè)待編碼的符號(hào) M0，.，M0 它們的概率如下表所示，使用霍夫曼編碼算法求出8個(gè)符號(hào)所分配的代碼。（寫出編碼樹） 待編碼的符號(hào)概率M00.2M10.4M20.1M30.15M40.03M50.04M60.07M70.01解： 為了進(jìn)行哈夫曼編碼 , 先把這組數(shù)據(jù)由大到小排列 , 再按上方法處理（1） 將信源符號(hào)按概率遞減順序排列。（2） 首先將概率最小的兩個(gè)符號(hào)的概率相加，合成一個(gè)新的數(shù)值。（3） 把合成的數(shù)值看成是一個(gè)新的組合符號(hào)概率，重復(fù)上述操作，直到剩下最后兩個(gè)符號(hào)。  542 Shannon-Fam

5、o編碼Shannon-Famo(S-F) 編碼方法與 Huffman 的編碼方法略有區(qū)別 , 但有時(shí)也能編出最佳碼。1SF碼主要準(zhǔn)則 符合即時(shí)碼條件 ; 在碼字中 ,1 和 0 是獨(dú)立的 , 而且是 ( 或差不多是 )等概率的。這樣的準(zhǔn)則一方面能保證無需用間隔區(qū)分碼字,同時(shí)又保證每一位碼字幾乎有1位的信息量。2SF碼的編碼過程信源符號(hào)按概率遞減順序排列 ;把符號(hào)集分成兩個(gè)子集 , 每個(gè)子集的概率和相等或近似相等 ;對(duì)第一個(gè)子集賦編碼 "0", 對(duì)第二個(gè)子集賦編碼 "1"重復(fù)上述步驟 , 直到每個(gè)子集只包含一個(gè)信源符號(hào)為止。 543 游程編碼游程編碼(簡(jiǎn)寫

6、為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 等 , 都使用了這種壓縮。 544 算術(shù)編碼1算術(shù)編碼算術(shù)編碼把一個(gè)信源集合表示為實(shí)數(shù)線上的 0 到 1 之間的一個(gè)區(qū)間。這個(gè)集合中的每個(gè)元素都要用來縮短這個(gè)區(qū)間。信源集合的元素越多,所得到的區(qū)間就越小,當(dāng)區(qū)間變小時(shí),就需

7、要更多的數(shù)位來表示這個(gè)區(qū)間,這就是區(qū)間作為代碼的原理。算術(shù)編碼首先假設(shè)一個(gè)信源的概率模型,然后用這些概率來縮小表示信源集的區(qū)間。2舉例說明算術(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 。令 high 為編碼間隔的高端 ,low 為編碼間隔的低端 , range 為編碼間隔的長(zhǎng)度 ,rangelow 為編碼字符分配的間隔低端 ,rangehigh 為編碼字符分配的間隔高端。初始 high=1,low=0,rangehigh-low, 一個(gè)

8、字符編碼后新的 low 和 high 按下式計(jì)算 :·low =lowrange × rangelow·high =lowrange×rangehigh(1) 在第一個(gè)字符 e 被編碼時(shí) ,e 的 rangelow0.2,rangehigh=0.5, 因此 :low0 + 1 × 0.2 0.2high=0 + 1 × 0.5 0.5range=highlow=0.50.2=0.3此時(shí)分配給 e 的范圍為 0.2,0.5 。(2)第二個(gè)字符 a 編碼時(shí)使用新生成范圍 0.2,0.5,a 的 rangelow=0, rangehigh=

9、0.2, 因此：low=0.2 十 0.3 × 0=0.2 high=0.2 0.3 × 0.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 × 0.5=0.23high=0.2 0.06 × 0.6=0.236即用 0.23,0.236 表示數(shù)據(jù)串 eai, 如果解碼器知道最后范圍是 0.23,0.236 這一范 圍 , 它馬上可解得一個(gè)字符為 e, 然后依次得到惟一解 a, 即最終得到 eai 。3.算術(shù)編碼的特點(diǎn)不必預(yù)先定義概率模型 , 自適應(yīng)模式具有獨(dú)特的優(yōu)點(diǎn);信源符號(hào)概率接近時(shí) , 建議使用算術(shù)編碼 , 這種情況下其效率高于 Huffman 編碼;算術(shù)編碼繞過了用一個(gè)特定的代碼替代一個(gè)輸入符號(hào)的想法 ,