哈夫曼編碼的方法

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

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

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

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

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

6、為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游程編碼的壓縮效果不太好, 但由于簡單, 編碼 / 解碼的速度非?？?, 因此仍然得到廣 泛的應用。許多圖形和視頻文件, 如 .BMP,.TIF 及 .AVI 等 , 都使用了這種壓縮。 544 算術編碼1算術編碼算術編碼把一個信源集合表示為實數(shù)線上的 0 到 1 之間的一個區(qū)間。這個集合中的每個元素都要用來縮短這個區(qū)間。信源集合的元素越多,所得到的區(qū)間就越小,當區(qū)間變小時,就需

7、要更多的數(shù)位來表示這個區(qū)間,這就是區(qū)間作為代碼的原理。算術編碼首先假設一個信源的概率模型,然后用這些概率來縮小表示信源集的區(qū)間。2舉例說明算術編碼過程 例 設英文元音字母采用固定模式符號概率分配如下:字符aeiou概率0.20.30.10.20.2范圍0,0.20.2,0.50.5,0.60.6,0.80.8,1.0設編碼的數(shù)據(jù)串為 eai 。令 high 為編碼間隔的高端 ,low 為編碼間隔的低端 , range 為編碼間隔的長度 ,rangelow 為編碼字符分配的間隔低端 ,rangehigh 為編碼字符分配的間隔高端。初始 high=1,low=0,rangehigh-low, 一個

8、字符編碼后新的 low 和 high 按下式計算 :·low =lowrange × rangelow·high =lowrange×rangehigh(1) 在第一個字符 e 被編碼時 ,e 的 rangelow0.2,rangehigh=0.5, 因此 :low0 + 1 × 0.2 0.2high=0 + 1 × 0.5 0.5range=highlow=0.50.2=0.3此時分配給 e 的范圍為 0.2,0.5 。(2)第二個字符 a 編碼時使用新生成范圍 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) 對下一個字符 i 編號,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 這一范 圍 , 它馬上可解得一個字符為 e, 然后依次得到惟一解 a, 即最終得到 eai 。3.算術編碼的特點不必預先定義概率模型 , 自適應模式具有獨特的優(yōu)點;信源符號概率接近時 , 建議使用算術編碼 , 這種情況下其效率高于 Huffman 編碼;算術編碼繞過了用一個特定的代碼替代一個輸入符號的想法 ,