哈夫曼編碼方法的選擇及其Python的實現

西北民族大學電氣工程學院 馮興民

隨著人們對圖像和視頻的壓縮存儲和傳輸的要求越來越高，如何提高傳輸速率和如何節省存儲空間顯得更加重要，解決這兩個問題的最根本途徑就是采用圖像壓縮技術。本科課程《信息論與編碼》中指出圖像壓縮的具體實現技術就是壓縮編碼，通過編碼可以減少信息的冗余度從而提高傳輸速率和節省存儲空間。在音視頻編解碼技術快速發展的今天，其實已經有很多的編碼方法。通過實際應用發現，哈夫曼編碼在編碼效率與平均碼長方面都是較好的。本文主要研究哈夫曼編碼及其Python的實現。

1 哈夫曼編碼

哈夫曼編碼是一種典型的無失真編碼，哈夫曼編碼所采用的編碼原理是最佳編碼定理。最佳編碼定理指出，在信息編碼的過程中對于信源符號，如果分配短字長的碼字給出現概率小的信源符號，分配長字長的碼字給出現概率大的信源符號，那么編碼結束之后所得到的平均碼長一定是小于其他任何一種編碼方法所得到的平均碼長的，也就是每個信源符號所得到的碼字長度是嚴格按照符號概率大小的相反順序所排列。

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

（1）將n個信源符號按其概率大小進行降序排序，即：

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

（3）對重排后的序列重復（2）過程，直到只有兩個信源符號為止，再把這兩個信源符號分別配以1和0即可。

（4）最后得出各個符號的碼字。

2 哈夫曼編碼方法的選擇及Python的實現

哈夫曼編碼方法的選擇和Python的實現看似是兩個分離的部分，但其實兩者是有機結合的，因為要對哈夫曼編碼方法做出選擇就要通過Python的實現來分析各種方法的平均碼長和編碼效率。由哈夫曼編碼的具體步驟可以看出來：哈夫曼的編碼結果其實是不唯一的。這是因為：其一，對兩個概率最小的信源符號0和1的分配是任意的；其二，當兩個概率最小的信源符號的概率相加時，所得的概率值有可能與原序列中的其他概率值相等。而這個相加的概率值可以在任意位置放置：放置在概率相同序列的最前端、最末端或者中間都是可以的，那么哪一種方法最好呢？這里主要分析在最前端和末端的情況。

首先進行哈夫曼編碼的Python實現，因為只有用Python實現了哈夫曼編碼才可以通過運行代碼比較上面提到的兩種哈夫曼編碼方法的效率。由于哈夫曼編碼的Python實現較于繁瑣，因此在這里只給出部分核心代碼。采用遞歸思想通過哈夫曼樹來生成哈夫曼編碼的核心代碼如下：

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) #采用遞歸方法來生成哈夫曼編碼

哈夫曼編碼用Python實現之后，用下面這個概率空間為例來進行分析和解釋。已知概率空間，如表1所示。

表1 概率空間

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

第一種：將概率最小的兩個信源符號概率相加后排在其

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

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

表2 編碼方法一

表3 編碼方法二

如表2所示的這一種編碼方法，是概率最小的兩個信源符號概率相加之后排在最前端的情況；并且，從圖中也可以看出信源符號出現的概率和碼長是嚴格對應的，即概率大的符號配以短碼長、概率小的符號配以長碼長。這樣做的原因是既然一個信源符號出現的概率大，也就是說在統計意義上這個信源符號在信息中出現的次數多，那我們就給他短的碼長，這樣既可以節省空間還可以提升傳輸速率。

那么這個方法的編碼效率如何呢？通過運行上面的Python代碼可以得到：其平均碼長為2.2碼元/符號，編碼效率為96.5%，并且由Python代碼運行出來的碼字和表2的碼字嚴格吻合。平均碼長和編碼效率的理論計算如下：

平均碼長：

編碼效率：

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

由上面的分析可以得出：這兩種方法的平均碼長和編碼效率是完全一樣的，因此不能由平均碼長和編碼效率來區分出這兩種編碼的優劣。因此，通過碼方差來判斷這兩種編碼方法的優劣，碼方差的理論計算公式為：

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

總結：通過對上面這個概率空間的分析可以發現：在編碼的過程中，在兩個最小的概率符號相加之后，得到一個新的概率。而在實際應用和理論計算之后發現，這一個新的概率應該盡量放在相同概率的前面，這樣才能保證這次編碼有較好的平均碼長、編碼效率以及碼方差。