密碼學(xué) 哈夫曼編碼

哈夫曼編碼

哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長(zhǎng)編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來(lái)構(gòu)造異字頭的平均長(zhǎng)度最短的碼字，有時(shí)稱之為最佳編碼，一般就叫做Huffman編碼（有時(shí)也稱為霍夫曼編碼）。

定理

在變字長(zhǎng)編碼中，如果碼字長(zhǎng)度嚴(yán)格按照對(duì)應(yīng)符號(hào)出現(xiàn)的概率大小逆序排列，則其平 均碼字長(zhǎng)度為最小。 現(xiàn)在通過(guò)一個(gè)實(shí)例來(lái)說(shuō)明上述定理的實(shí)現(xiàn)過(guò)程。設(shè)將信源符號(hào)按出現(xiàn)的概率大小順序排列為 ： U： ( a1 a2 a3 a4 a5 a6 a7 ) [1] 0.20 0.19 0.18 0.17 0.15 0.10 0.01 給概率最小的兩個(gè)符號(hào)a6與a7分別指定為“1”與“0”，然后將它們的概率相加再與原來(lái)的 a1~a5組合并重新排序成新的原為： U′： ( a1 a2 a3 a4 a5 a6′ ) 0.20 0.19 0.18 0.17 0.15 0.11 對(duì)a5與a′6分別指定“1”與“0”后，再作概率相加并重新按概率排序得 U″：（0.26 0.20 0.19 0.18 0.17）… 直到最后得 U″″：（0.61 0.39） 赫夫曼編碼的具體方法：先按出現(xiàn)的概率大小排隊(duì)，把兩個(gè)最小的概率相加，作為新的概率 和剩余的概率重新排隊(duì)，再把最小的兩個(gè)概率相加，再重新排隊(duì)，直到最后變成1。每次相 加時(shí)都將“0”和“1”賦與相加的兩個(gè)概率，讀出時(shí)由該符號(hào)開(kāi)始一直走到最后的“1”， 將路線上所遇到的“0”和“1”按最低位到最高位的順序排好，就是該符號(hào)的赫夫曼編碼。 例如a7從左至右，由U至U″″，其碼字為1000； a6按路線將所遇到的“0”和“1”按最低位到最高位的順序排好，其碼字為1001… 用赫夫曼編碼所得的平均比特率為：Σ碼長(zhǎng)×出現(xiàn)概率 上例為：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit 可以算出本例的信源熵為2.61bit，二者已經(jīng)是很接近了。

例子