哈夫曼編碼方法的選擇及其Python的實(shí)現(xiàn)

西北民族大學(xué)電氣工程學(xué)院 馮興民

隨著人們對(duì)圖像和視頻的壓縮存儲(chǔ)和傳輸?shù)囊笤絹?lái)越高，如何提高傳輸速率和如何節(jié)省存儲(chǔ)空間顯得更加重要，解決這兩個(gè)問(wèn)題的最根本途徑就是采用圖像壓縮技術(shù)。本科課程《信息論與編碼》中指出圖像壓縮的具體實(shí)現(xiàn)技術(shù)就是壓縮編碼，通過(guò)編碼可以減少信息的冗余度從而提高傳輸速率和節(jié)省存儲(chǔ)空間。在音視頻編解碼技術(shù)快速發(fā)展的今天，其實(shí)已經(jīng)有很多的編碼方法。通過(guò)實(shí)際應(yīng)用發(fā)現(xiàn)，哈夫曼編碼在編碼效率與平均碼長(zhǎng)方面都是較好的。本文主要研究哈夫曼編碼及其Python的實(shí)現(xiàn)。

1 哈夫曼編碼

哈夫曼編碼是一種典型的無(wú)失真編碼，哈夫曼編碼所采用的編碼原理是最佳編碼定理。最佳編碼定理指出，在信息編碼的過(guò)程中對(duì)于信源符號(hào)，如果分配短字長(zhǎng)的碼字給出現(xiàn)概率小的信源符號(hào)，分配長(zhǎng)字長(zhǎng)的碼字給出現(xiàn)概率大的信源符號(hào)，那么編碼結(jié)束之后所得到的平均碼長(zhǎng)一定是小于其他任何一種編碼方法所得到的平均碼長(zhǎng)的，也就是每個(gè)信源符號(hào)所得到的碼字長(zhǎng)度是嚴(yán)格按照符號(hào)概率大小的相反順序所排列。

哈夫曼編碼具體步驟如下：

（1）將n個(gè)信源符號(hào)按其概率大小進(jìn)行降序排序，即：

（2）取兩個(gè)概率最小的信源符號(hào)分別配以1和0兩個(gè)碼元，然后將這兩個(gè)信源符號(hào)概率相加作為一個(gè)新符號(hào)的概率，與未分配的二進(jìn)符號(hào)重新進(jìn)行降序排序。

（3）對(duì)重排后的序列重復(fù)（2）過(guò)程，直到只有兩個(gè)信源符號(hào)為止，再把這兩個(gè)信源符號(hào)分別配以1和0即可。

（4）最后得出各個(gè)符號(hào)的碼字。

2 哈夫曼編碼方法的選擇及Python的實(shí)現(xiàn)

哈夫曼編碼方法的選擇和Python的實(shí)現(xiàn)看似是兩個(gè)分離的部分，但其實(shí)兩者是有機(jī)結(jié)合的，因?yàn)橐獙?duì)哈夫曼編碼方法做出選擇就要通過(guò)Python的實(shí)現(xiàn)來(lái)分析各種方法的平均碼長(zhǎng)和編碼效率。由哈夫曼編碼的具體步驟可以看出來(lái)：哈夫曼的編碼結(jié)果其實(shí)是不唯一的。這是因?yàn)椋浩湟唬瑢?duì)兩個(gè)概率最小的信源符號(hào)0和1的分配是任意的；其二，當(dāng)兩個(gè)概率最小的信源符號(hào)的概率相加時(shí)，所得的概率值有可能與原序列中的其他概率值相等。而這個(gè)相加的概率值可以在任意位置放置：放置在概率相同序列的最前端、最末端或者中間都是可以的，那么哪一種方法最好呢？這里主要分析在最前端和末端的情況。

首先進(jìn)行哈夫曼編碼的Python實(shí)現(xiàn)，因?yàn)橹挥杏肞ython實(shí)現(xiàn)了哈夫曼編碼才可以通過(guò)運(yùn)行代碼比較上面提到的兩種哈夫曼編碼方法的效率。由于哈夫曼編碼的Python實(shí)現(xiàn)較于繁瑣，因此在這里只給出部分核心代碼。采用遞歸思想通過(guò)哈夫曼樹來(lái)生成哈夫曼編碼的核心代碼如下：

def iscoding(self,tree,length):

node=tree

if (not node):

return

elif node._name:

print (node._name + ‘ encoding:’,end=’’),

for i in range(length):

print (self.Buffer[i],end=’’)

print (‘ ’)

return

self.Buffer[length]=0

self.iscoding(node._left,length+1)

self.Buffer[length]=1

self.iscoding(node._right,length+1)

def get_code(self):

self.iscoding(self.root,0) #采用遞歸方法來(lái)生成哈夫曼編碼

哈夫曼編碼用Python實(shí)現(xiàn)之后，用下面這個(gè)概率空間為例來(lái)進(jìn)行分析和解釋。已知概率空間，如表1所示。

表1 概率空間

表1所示的概率空間已經(jīng)按照信源符號(hào)概率大小的降序進(jìn)行排序，因此直接進(jìn)行上面所提到的兩種哈夫曼編碼。

第一種：將概率最小的兩個(gè)信源符號(hào)概率相加后排在其

如表3所示的這一種編碼方法，是將概率最小的兩個(gè)信源符號(hào)的概率相加所得的概率排在最末端的情況。

那么這一種方法的編碼效率如何呢？還是和第一種方法一樣通過(guò)運(yùn)行Python代碼，這兒的代碼要進(jìn)行一下修改以達(dá)到讓兩個(gè)信源符號(hào)概率和排到末端的目的。運(yùn)行之后可以得到：其平均碼長(zhǎng)為2.2碼元/符號(hào)，編碼效率為96.5%，并且由Python代碼運(yùn)行出來(lái)的碼字和表3的碼字嚴(yán)格吻合。他相同概率序列的前面，其編碼過(guò)程如表2所示。

表2 編碼方法一

表3 編碼方法二

如表2所示的這一種編碼方法，是概率最小的兩個(gè)信源符號(hào)概率相加之后排在最前端的情況；并且，從圖中也可以看出信源符號(hào)出現(xiàn)的概率和碼長(zhǎng)是嚴(yán)格對(duì)應(yīng)的，即概率大的符號(hào)配以短碼長(zhǎng)、概率小的符號(hào)配以長(zhǎng)碼長(zhǎng)。這樣做的原因是既然一個(gè)信源符號(hào)出現(xiàn)的概率大，也就是說(shuō)在統(tǒng)計(jì)意義上這個(gè)信源符號(hào)在信息中出現(xiàn)的次數(shù)多，那我們就給他短的碼長(zhǎng)，這樣既可以節(jié)省空間還可以提升傳輸速率。

那么這個(gè)方法的編碼效率如何呢？通過(guò)運(yùn)行上面的Python代碼可以得到：其平均碼長(zhǎng)為2.2碼元/符號(hào)，編碼效率為96.5%，并且由Python代碼運(yùn)行出來(lái)的碼字和表2的碼字嚴(yán)格吻合。平均碼長(zhǎng)和編碼效率的理論計(jì)算如下：

平均碼長(zhǎng)：

編碼效率：

第二種：將概率最小的兩個(gè)信源符號(hào)概率相加后排在其他相同概率序列的后面，其編碼過(guò)程如表3所示。

由上面的分析可以得出：這兩種方法的平均碼長(zhǎng)和編碼效率是完全一樣的，因此不能由平均碼長(zhǎng)和編碼效率來(lái)區(qū)分出這兩種編碼的優(yōu)劣。因此，通過(guò)碼方差來(lái)判斷這兩種編碼方法的優(yōu)劣，碼方差的理論計(jì)算公式為：

計(jì)算得到：第一種方法的碼方差為0.16，第二種方法的碼方差為1.36。由此可見，第一種編碼方法的碼方差較小，因此第一種編碼方法更好。

總結(jié)：通過(guò)對(duì)上面這個(gè)概率空間的分析可以發(fā)現(xiàn)：在編碼的過(guò)程中，在兩個(gè)最小的概率符號(hào)相加之后，得到一個(gè)新的概率。而在實(shí)際應(yīng)用和理論計(jì)算之后發(fā)現(xiàn)，這一個(gè)新的概率應(yīng)該盡量放在相同概率的前面，這樣才能保證這次編碼有較好的平均碼長(zhǎng)、編碼效率以及碼方差。