電子發燒友App
摘要：作為一種常用的編碼方式即哈夫曼編碼，很多人在它的原理即應用方面都弄不不清楚，本文主要以哈夫曼編碼原理與應用實例及算法流程圖倆進一步說明。
哈夫曼編碼定義
哈夫曼編碼（Huffman Coding），又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼（VLC）的一種。Huffman于1952年提出一種編碼方法，該方法完全依據字符出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼（有時也稱為霍夫曼編碼）。
哈夫曼編碼原理
設某信源產生有五種符號u1、u2、u3、u4和u5，對應概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。首先，將符號按照概率由大到小排隊，如圖所示。編碼時，從最小概率的兩個符號開始，可選其中一個支路為0，另一支路為1。這里，我們選上支路為0，下支路為1。再將已編碼的兩支路的概率合并，并重新排隊。多次重復使用上述方法直至合并概率歸一時為止。從圖（a）和（b）可以看出，兩者雖平均碼長相等，但同一符號可以有不同的碼長，即編碼方法并不唯一，其原因是兩支路概率合并后重新排隊時，可能出現幾個支路概率相等，造成排隊方法不唯一。一般，若將新合并后的支路排到等概率的最上支路，將有利于縮短碼長方差，且編出的碼更接近于等長碼。這里圖（a）的編碼比（b）好。
赫夫曼碼的碼字（各符號的代碼）是異前置碼字，即任一碼字不會是另一碼字的前面部分，這使各碼字可以連在一起傳送，中間不需另加隔離符號，只要傳送時不出錯，收端仍可分離各個碼字，不致混淆。
實際應用中，除采用定時清洗以消除誤差擴散和采用緩沖存儲以解決速率匹配以外，主要問題是解決小符號集合的統計匹配，例如黑（1）、白（0）傳真信源的統計匹配，采用0和1不同長度游程組成擴大的符號集合信源。游程，指相同碼元的長度（如二進碼中連續的一串0或一串1的長度或個數）。按照CCITT標準，需要統計2×1728種游程（長度），這樣，實現時的存儲量太大。事實上長游程的概率很小，故CCITT還規定：若l表示游程長度，則l=64q+r。其中q稱主碼，r為基碼。編碼時，不小于64的游程長度由主碼和基碼組成。而當l為64的整數倍時，只用主碼的代碼，已不存在基碼的代碼。
長游程的主碼和基碼均用赫夫曼規則進行編碼，這稱為修正赫夫曼碼，其結果有表可查。該方法已廣泛應用于文件傳真機中。
哈夫曼編碼算法流程圖
哈夫曼編碼的算法是查找最優路徑的一種算法，首先在所有未分配parent域的節點中找出最小的兩個節點，將他們的全值相加，組成新的節點，并且將它標記為原來兩個最小節點的parent。這樣調用遞歸，最后就能夠成一顆完整的哈夫曼樹。然后對 每個節點進行遍歷編碼，得到最終的哈夫曼編碼庫。流程圖如下：
基于哈夫曼編碼原理的壓縮算法
哈夫曼算法的過程為：統計原始數據中各字符出現的頻率；所有字符按頻率降序排列；建立哈夫曼樹：將哈夫曼樹存入結果數據；重新編碼原始數據到結果數據。哈夫曼算法實現流程如圖3所示。
哈夫曼算法的實質是針對統計結果對字符本身重新編碼，而不是對重復字符或重復子串編碼。實用中．符號的出現頻率不能預知，需要統計和編碼兩次處理，所以速度較慢，無法實用。而自適應（或動態）哈夫曼算法取消了統計，可在壓縮數據時動態調整哈夫曼樹，這樣可提高速度。因此，哈夫曼編碼效率高，運算速度快，實現方式靈活。
采用哈夫曼編碼時需注意的問題：
（1）哈夫曼碼無錯誤保護功能，譯碼時，碼串若無錯就能正確譯碼；若碼串有錯應考慮增加編碼，提高可靠性。
（2）哈夫曼碼是可變長度碼，因此很難隨意查找或調用壓縮文件中間的內容，然后再譯碼，這就需要在存儲代碼之前加以考慮。
（3）哈夫曼樹的實現和更新方法對設計非常關鍵。
哈夫曼編碼應用實例
哈夫曼編碼，主要用途是實現數據壓縮。
設給出一段報文：CAST CAST SAT AT A TASA。字符集合是 { C， A， S， T }，各個字符出現的頻度（次數）是 W＝{ 2， 7， 4， 5 }。若給每個字符以等長編碼A ： 00 T ： 10 C ： 01 S ： 11，則總編碼長度為 （ 2+7+4+5 ） * 2 = 36。
若按各個字符出現的概率不同而給予不等長編碼，可望減少總編碼長度。各字符出現概率為{ 2/18， 7/18， 4/18， 5/18 }，化整為 { 2， 7， 4， 5 }。以它們為各葉結點上的權值， 建立霍夫曼樹。左分支賦 0，右分支賦 1，得霍夫曼編碼（變長編碼）。A ： 0 T ： 10 C ： 110 S ： 111。它的總編碼長度：7*1+5*2+（ 2+4 ）*3 = 35。比等長編碼的情形要短。霍夫曼編碼是一種無前綴編碼。解碼時不會混淆。帶權路徑長度達到最小的二叉樹即為霍夫曼樹。在霍夫曼樹中，權值大的結點離根最近。
霍夫曼算法
1.由給定的 n 個權值 {w0， w1， w2， …， wn-1}，構造具有 n 棵擴充二叉樹的森林 F = { T0， T1， T2， …， Tn-1 }，其中每棵擴充二叉樹 Ti 只有一 個帶權值 wi 的根結點， 其左、右子樹均為空。
2.重復以下步驟， 直到 F 中僅剩下一棵樹為止：
① 在 F 中選取兩棵根結點的權值最小的擴充二叉樹，做為左、右子樹構造一棵新的二叉樹。置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。
② 在 F 中刪去這兩棵二叉樹。
③ 把新的二叉樹加入 F。
#include 《stdio.h》
#include 《stdlib.h》
#include 《string.h》
#define MAX 32767
typedef char *HuffmanCode;
typedef struct
{
int Weight;//字母的權
int Parent，Leftchild，Rightchild;
}HuffmanTree;
void Select（HuffmanTree *HT，int n，int *s1，int *s2）
{
int min1=MAX;
int min2=MAX;
int pos1， pos2;
int i;
for（i=0;i《n;i++）
{
if（HT［i］.Parent==-1）//選擇還沒有父親的節點
{
if（HT［i］.Weight《=min1）
{
pos2 = pos1; min2 = min1;
pos1 = i; min1=HT［i］.Weight;
}
else if（HT［i］.Weight《=min2）
{
pos2 = i; min2=HT［i］.Weight;
}
}
}
*s1=pos1;*s2=pos2;
}
void CreateTree（HuffmanTree *HT，int n，int *w）
{
int m=2*n-1;//總的節點數
int s1，s2;
int i;
for（i=0;i《m;i++）
{
if（i《n）
HT［i］.Weight=w［i］;
else
HT［i］.Weight=-1;
HT［i］.Parent=-1;
HT［i］.Leftchild=-1;
HT［i］.Rightchild=-1;
}
for（i=n;i《m;i++）
{
Select（HT，i，&s1，&s2）;//這個函數是從0到n-1中選兩個權最小的節點
HT［i］.Weight=HT［s1］.Weight+HT［s2］.Weight;
HT［i］.Leftchild=s1;
HT［i］.Rightchild=s2;
HT［s1］.Parent=i;
HT［s2］.Parent=i;
}
}
void Print（HuffmanTree *HT，int m）
{
if（m！=-1）
{
printf（“%d ”，HT［m］.Weight）;
Print（HT，HT［m］.Leftchild）;
Print（HT，HT［m］.Rightchild）;
}
}
void Huffmancoding（HuffmanTree *HT，int n，HuffmanCode *hc，char *letters）
{
char *cd;
int start;
int Current，parent;
int i;
cd=（char*）malloc（sizeof（char）*n）;//用來臨時存放一個字母的編碼結果
cd［n-1］=‘\0’;
for（i=0;i《n;i++）
{
start=n-1;
for（Current=i，parent=HT［Current］.Parent; parent！=-1; Current=parent，parent=HT［parent］.Parent）
if（Current==HT［parent］.Leftchild）//判斷該節點是父節點的左孩子還是右孩子
cd［--start］=‘0’;
else
cd［--start］=‘1’;
hc［i］=（char*）malloc（sizeof（char）*（n-start））;
strcpy（hc［i］，&cd［start］）;
}
free（cd）;
for（i=0;i《n;i++）
{
printf（“letters：%c，weight：%d，編碼為 %s\n”，letters［i］，HT［i］.Weight，hc［i］）;
printf（“\n”）;
}
}
void Encode（HuffmanCode *hc，char *letters，char *test，char *code）
{
int len=0;
int i，j;
for（i=0;test［i］！=‘\0’;i++）
{
for（j=0;letters［j］！=test［i］;j++）{}
strcpy（code+len，hc［j］）;
len=len+strlen（hc［j］）;
}
printf（“The Test ： %s \nEncode to be ：”，test）;
printf（“%s”，code）;
printf（“\n”）;
}
void Decode（HuffmanTree *HT，int m，char *code，char *letters）
{
int position=0，i;
printf（“The Code： %s \nDecode to be ：”，code）;
while（code［position］！=‘\0’）
{
for（i=m-1;HT［i］.Leftchild！=-1&&HT［i］.Rightchild！=-1;position++）
{
if（code［position］==‘0’）
i=HT［i］.Leftchild;
else
i=HT［i］.Rightchild;
}
printf（“%c”，letters［i］）;
}
}
int main（）
{
int n=27;
int m=2*n-1;
char letters［28］={‘a’，‘b’，‘c’，‘d’，‘e’，‘f’，‘g’，‘h’，‘i’，‘j’，‘k’，‘l’，‘m’，
‘n’，‘o’，‘p’，‘q’，‘r’，‘s’，‘t’，‘u’，‘v’，‘w’，‘x’，‘y’，‘z’，‘ ’};
int w［28］={64，13，22，32，103，21，15，47，57，1，5，32，20，
57，63，15，1，48，51，80，23，8，18，1，16，1，168};
char code［200］;
char test［50］={“this is about build my life”};
HuffmanTree *HT;
HuffmanCode *hc;
HT=（HuffmanTree *）malloc（m*sizeof（HuffmanTree））;
hc=（HuffmanCode *）malloc（n*sizeof（char*））;
CreateTree（HT，n，w）;
Print（HT，m-1）;
printf（“\n”）;
Huffmancoding（HT，n，hc，letters）;
Encode（hc，letters，test，code）;
Decode（HT，m，code，letters）;
printf（“\n”）;
return 0;
}
推薦閱讀：
工商網監
評論