基本介紹
- 中文名：哈夫曼
- 類型：編碼
- 時間：1850
- 分類：靜態和動態
- 又稱：最優二叉樹
- 特點：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;
如何構造
構成初始集合
選取左右子樹
刪除左右子樹
從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。
