-
哈夫曼
鎖定
- 中文名
- 哈夫曼
- 別 名
- 最優二叉樹
- 類 型
- 編碼
- 分 類
- 靜態和動態
- 特 點
- WPL最小
哈夫曼編碼簡介
哈夫曼在上世紀五十年代初就提出這種編碼時,根據字符出現的概率來構造平均長度最短的編碼。它是一種變長的編碼。在編碼中,若各碼字長度嚴格按照碼字所對應符號出現概率的大小的逆序排列,則編碼的平均長度是最小的。(注:碼字即為符號經哈夫曼編碼後得到的編碼,其長度是因符號出現的概率而不同,所以説哈夫曼編碼是變長的編碼。) 而且哈夫曼編碼是按照子樹到父親,而其讀碼則是完全相反的。
靜態編碼
這種編碼方法是靜態的哈夫曼編碼,它對需要編碼的數據進行兩遍掃描:第一遍統計原數據中各字符出現的頻率,利用得到的頻率值創建哈夫曼樹,並必須把樹的信息保存起來,即把字符0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來,(用4Bytes的長度存儲頻率值,頻率值的表示範圍為0--2^32-1,這已足夠表示大文件中字符出現的頻率了)以便解壓時創建同樣的哈夫曼樹進行解壓;第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼,並把編碼後得到的碼字存儲起來。 靜態哈夫曼編碼方法有一些缺點:一、對於過短的文件進行編碼的意義不大,因為光以4BYTES的長度存儲哈夫曼樹的信息就需1024Bytes的存儲空間;二、進行哈夫曼編碼,存儲編碼信息時,若用與通訊網絡,就會引起較大的延時;三、對較大的文件進行編碼時,頻繁的磁盤讀寫訪問會降低數據編碼的速度。
動態編碼
因此,後來有人提出了一種動態的哈夫曼編碼方法。動態哈夫曼編碼使用一棵動態變化的哈夫曼樹,對第t+1個字符的編碼是根據原始數據中前t個字符得到的哈夫曼樹來進行的,編碼和解碼使用相同的初始哈夫曼樹,每處理完一個字符,編碼和解碼使用相同的方法修改哈夫曼樹,所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字符所需的時間與該字符的編碼長度成正比,所以動態哈夫曼編碼可實時進行。動態哈夫曼編碼比靜態哈夫曼編碼複雜的多,有興趣的讀者可參考有關數據結構與算法的書籍。
前面提到的JPEG中用到了哈夫曼編碼,並不是説JPEG就只用哈夫曼編碼就可以了,而是一幅圖片經過多個步驟後得到它的一列數值,對這些數值進行哈夫曼編碼,以便存儲或傳輸。哈夫曼編碼方法比較易懂,大家可以根據它的編碼方法,自己編寫哈夫曼編碼和解碼的程序。
const maxvalue= 10000; {定義最大權值}
maxleat=30; {定義哈夫曼樹中葉子結點個數}
maxnode=maxleaf*2-1;
type HnodeType=record
weight: integer;
parent: integer;
lchild: integer;
rchild: integer;
end;
HuffArr:array[0..maxnode] of HnodeType;
var ……
procedure CreatHaffmanTree(var HuffNode: HuffArr); {哈夫曼樹的構造算法}
var i,j,m1,m2,x1,x2,n: integer;
begin
readln(n); {輸入葉子結點個數}
for i:=0 to 2*n-1 do {數組HuffNode[ ]初始化}
begin
HuffNode.weight=0;
HuffNode.parent=-1;
HuffNode.lchild=-1;
HuffNode.rchild=-1;
end;
for i:=0 to n-1 do read(HuffNode.weight); {輸入n個葉子結點的權值}
for i:=0 to n-1 do {構造哈夫曼樹}
begin
m1:=MAXVALUE; m2:=MAXVALUE;
x1:=0; x2:=0;
for j:=0 to n+i-1 do
if (HuffNode[j].weight<m1) and (HuffNode[j].parent=-1) then
begin m2:=m1; x2:=x1;
m1:=HuffNode[j].weight; x1:=j;
end
else if (HuffNode[j].weight<m2) and (HuffNode[j].parent=-1) then
begin m2:=HuffNode[j].weight; x2:=j; end;
{將找出的兩棵子樹合併為一棵子樹}
HuffNode[x1].parent:=n+i; HuffNode[x2].parent:=n+i;
HuffNode[n+i].weight:= HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild:=x1; HuffNode[n+i].rchild:=x2;
end;
end;
哈夫曼構造方式
構成初始集合
對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉樹Ti中只有一個權值為Wi的根結點,它的左右子樹均為空。(為方便在計算機上實現算法,一般還要求以Ti的權值Wi的升序排列。)
選取左右子樹
刪除左右子樹
從F中刪除這兩棵樹,並把這棵新的二叉樹同樣以升序排列加入到集合F中。
重複二和三兩步
重複二和三兩步,直到集合F中只有一棵二叉樹為止。
用C語言實現上述算法,可用靜態的二叉樹或動態的二叉樹。若用動態的二叉樹可用以下數據結構: struct tree{
float weight; /*權值*/
union{
char leaf; /*葉結點信息字符*/
struct tree *left; /*樹的左結點*/
};
struct tree *right; /*樹的右結點*/
};
struct forest{ /*F集合,以鏈表形式表示*/
struct tree *ti; /* F中的樹*/
struct forest *next; /* 下一個結點*/
};
例:若字母A,B,C,D出現的概率為:0.75,0.54,0.28,0.43;則相應的權值為:75,54,28,43。