電子發(fā)燒友App
摘要：作為一種常用的編碼方式即哈夫曼編碼，很多人在它的原理即應(yīng)用方面都弄不不清楚，本文主要以哈夫曼編碼原理與應(yīng)用實例及算法流程圖倆進一步說明。
哈夫曼編碼定義
哈夫曼編碼（Huffman Coding），又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼（VLC）的一種。Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼（有時也稱為霍夫曼編碼）。
哈夫曼編碼原理
設(shè)某信源產(chǎn)生有五種符號u1、u2、u3、u4和u5，對應(yīng)概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。首先，將符號按照概率由大到小排隊，如圖所示。編碼時，從最小概率的兩個符號開始，可選其中一個支路為0，另一支路為1。這里，我們選上支路為0，下支路為1。再將已編碼的兩支路的概率合并，并重新排隊。多次重復(fù)使用上述方法直至合并概率歸一時為止。從圖（a）和（b）可以看出，兩者雖平均碼長相等，但同一符號可以有不同的碼長，即編碼方法并不唯一，其原因是兩支路概率合并后重新排隊時，可能出現(xiàn)幾個支路概率相等，造成排隊方法不唯一。一般，若將新合并后的支路排到等概率的最上支路，將有利于縮短碼長方差，且編出的碼更接近于等長碼。這里圖（a）的編碼比（b）好。
赫夫曼碼的碼字（各符號的代碼）是異前置碼字，即任一碼字不會是另一碼字的前面部分，這使各碼字可以連在一起傳送，中間不需另加隔離符號，只要傳送時不出錯，收端仍可分離各個碼字，不致混淆。
實際應(yīng)用中，除采用定時清洗以消除誤差擴散和采用緩沖存儲以解決速率匹配以外，主要問題是解決小符號集合的統(tǒng)計匹配，例如黑（1）、白（0）傳真信源的統(tǒng)計匹配，采用0和1不同長度游程組成擴大的符號集合信源。游程，指相同碼元的長度（如二進碼中連續(xù)的一串0或一串1的長度或個數(shù)）。按照CCITT標(biāo)準(zhǔn)，需要統(tǒng)計2×1728種游程（長度），這樣，實現(xiàn)時的存儲量太大。事實上長游程的概率很小，故CCITT還規(guī)定：若l表示游程長度，則l=64q+r。其中q稱主碼，r為基碼。編碼時，不小于64的游程長度由主碼和基碼組成。而當(dāng)l為64的整數(shù)倍時，只用主碼的代碼，已不存在基碼的代碼。
長游程的主碼和基碼均用赫夫曼規(guī)則進行編碼，這稱為修正赫夫曼碼，其結(jié)果有表可查。該方法已廣泛應(yīng)用于文件傳真機中。
哈夫曼編碼算法流程圖
哈夫曼編碼的算法是查找最優(yōu)路徑的一種算法，首先在所有未分配parent域的節(jié)點中找出最小的兩個節(jié)點，將他們的全值相加，組成新的節(jié)點，并且將它標(biāo)記為原來兩個最小節(jié)點的parent。這樣調(diào)用遞歸，最后就能夠成一顆完整的哈夫曼樹。然后對 每個節(jié)點進行遍歷編碼，得到最終的哈夫曼編碼庫。流程圖如下：
基于哈夫曼編碼原理的壓縮算法
哈夫曼算法的過程為：統(tǒng)計原始數(shù)據(jù)中各字符出現(xiàn)的頻率；所有字符按頻率降序排列；建立哈夫曼樹：將哈夫曼樹存入結(jié)果數(shù)據(jù)；重新編碼原始數(shù)據(jù)到結(jié)果數(shù)據(jù)。哈夫曼算法實現(xiàn)流程如圖3所示。
哈夫曼算法的實質(zhì)是針對統(tǒng)計結(jié)果對字符本身重新編碼，而不是對重復(fù)字符或重復(fù)子串編碼。實用中．符號的出現(xiàn)頻率不能預(yù)知，需要統(tǒng)計和編碼兩次處理，所以速度較慢，無法實用。而自適應(yīng)（或動態(tài)）哈夫曼算法取消了統(tǒng)計，可在壓縮數(shù)據(jù)時動態(tài)調(diào)整哈夫曼樹，這樣可提高速度。因此，哈夫曼編碼效率高，運算速度快，實現(xiàn)方式靈活。
采用哈夫曼編碼時需注意的問題：
?。?）哈夫曼碼無錯誤保護功能，譯碼時，碼串若無錯就能正確譯碼；若碼串有錯應(yīng)考慮增加編碼，提高可靠性。
?。?）哈夫曼碼是可變長度碼，因此很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼，這就需要在存儲代碼之前加以考慮。
?。?）哈夫曼樹的實現(xiàn)和更新方法對設(shè)計非常關(guān)鍵。
哈夫曼編碼應(yīng)用實例
哈夫曼編碼，主要用途是實現(xiàn)數(shù)據(jù)壓縮。
設(shè)給出一段報文：CAST CAST SAT AT A TASA。字符集合是 { C， A， S， T }，各個字符出現(xiàn)的頻度（次數(shù)）是 W＝{ 2， 7， 4， 5 }。若給每個字符以等長編碼A ： 00 T ： 10 C ： 01 S ： 11，則總編碼長度為 （ 2+7+4+5 ） * 2 = 36。
若按各個字符出現(xiàn)的概率不同而給予不等長編碼，可望減少總編碼長度。各字符出現(xiàn)概率為{ 2/18， 7/18， 4/18， 5/18 }，化整為 { 2， 7， 4， 5 }。以它們?yōu)楦魅~結(jié)點上的權(quán)值， 建立霍夫曼樹。左分支賦 0，右分支賦 1，得霍夫曼編碼（變長編碼）。A ： 0 T ： 10 C ： 110 S ： 111。它的總編碼長度：7*1+5*2+（ 2+4 ）*3 = 35。比等長編碼的情形要短?；舴蚵幋a是一種無前綴編碼。解碼時不會混淆。帶權(quán)路徑長度達到最小的二叉樹即為霍夫曼樹。在霍夫曼樹中，權(quán)值大的結(jié)點離根最近。
霍夫曼算法
1.由給定的 n 個權(quán)值 {w0， w1， w2， …， wn-1}，構(gòu)造具有 n 棵擴充二叉樹的森林 F = { T0， T1， T2， …， Tn-1 }，其中每棵擴充二叉樹 Ti 只有一 個帶權(quán)值 wi 的根結(jié)點， 其左、右子樹均為空。
2.重復(fù)以下步驟， 直到 F 中僅剩下一棵樹為止：
?、?在 F 中選取兩棵根結(jié)點的權(quán)值最小的擴充二叉樹，做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。
?、?在 F 中刪去這兩棵二叉樹。
③ 把新的二叉樹加入 F。
#include 《stdio.h》
#include 《stdlib.h》
#include 《string.h》
#define MAX 32767
typedef char *HuffmanCode;
typedef struct
{
int Weight;//字母的權(quán)
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）//選擇還沒有父親的節(jié)點
{
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;//總的節(jié)點數(shù)
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）;//這個函數(shù)是從0到n-1中選兩個權(quán)最小的節(jié)點
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）;//用來臨時存放一個字母的編碼結(jié)果
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）//判斷該節(jié)點是父節(jié)點的左孩子還是右孩子
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（“l(fā)etters：%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(chǎn)’，‘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;
}
推薦閱讀：
工商網(wǎng)監(jiān)
評論