樹 - 哈夫曼樹及其應用 - 哈夫曼編碼 （二）

　　根據最優二叉樹構造哈夫曼編碼

　　利用哈夫曼樹很容易求出給定字符集及其概率(或頻度)分布的最優前綴碼哈夫曼編碼正是一種應用廣泛且非常有效的數據壓縮

　　技術該技術一般可將數據文件壓縮掉%至%其壓縮效率取決於被壓縮文件的特征

　　 具體做法

　　()用字符c i 作為葉子p i 或f i 做為葉子c i 的權構造一棵哈夫曼樹並將樹中左分支和右分支分別標記為和;

　　()將從根到葉子的路徑上的標號依次相連作為該葉子所表示字符的編碼該編碼即為最優前綴碼(也稱哈夫曼編碼)

　　 哈夫曼編碼為最優前綴碼

　　由哈夫曼樹求得編碼為最優前綴碼的原因

　　① 每個葉子字符c i 的碼長恰為從根到該葉子的路徑長度l i 平均碼長(或文件總長)又是二叉樹的帶權路徑長度WPL而哈

　　夫曼樹是WPL最小的二叉樹因此編碼的平均碼長(或文件總長)亦最小

　　② 樹中沒有一片葉子是另一葉子的祖先每片葉子對應的編碼就不可能是其它葉子編碼的前綴即上述編碼是二進制的前綴碼

　　

　　 求哈夫曼編碼的算法

　　()思想方法

　　給定字符集的哈夫曼樹生成後求哈夫曼編碼的具體實現過程是依次以葉子T[i](≤i≤n)為出發點向上回溯至根為止

　　上溯時走左分支則生成代碼走右分支則生成代碼

　　注意

　　① 由於生成的編碼與要求的編碼反序將生成的代碼先從後往前依次存放在一個臨時向量中並設一個指針start指示編碼在

　　該向量中的起始位置(start初始時指示向量的結束位置)

　　② 當某字符編碼完成時從臨時向量的start處將編碼復制到該字符相應的位串bits中即可

　　③ 因為字符集大小為n故變長編碼的長度不會超過n加上一個結束符\bits的大小應為n+

　　()字符集編碼的存儲結構及其算法描述

　　typedef struct {

　　char ch; //存儲字符

　　char bits[n+]; //存放編碼位串

　　}CodeNode;

　　typedef CodeNode HuffmanCode[n];

　　void CharSetHuffmanEncoding(HuffmanTree THuffmanCode H)

　　{//根據哈夫曼樹T求哈夫曼編碼表H

　　int cpi;//c和p分別指示T中孩子和雙親的位置

　　char cd[n+]; //臨時存放編碼

　　int start; //指示編碼在cd中的起始位置

　　cd[n]=\; //編碼結束符

　　for(i=i

　　H[i].ch=getchar();//讀入葉子T[i]對應的字符

　　start=n; //編碼起始位置的初值

　　c=i; //從葉子T[i]開始上溯

　　while((p=T[c].parent)>=0){//直至上溯到T[c]是樹根為止

　　//若T[c]是T[p]的左孩子，則生成代碼0;否則生成代碼1

　　cd[--start]=(T[p).1child==C)?'0'：'1';

　　c=p; //繼續上溯

　　}

　　strcpy(H[i].bits，&cd[start]); //復制編碼位串

　　}//endfor

　　}//CharSetHuffmanEncoding

　　文件的編碼和解碼

　　有了字符集的哈夫曼編碼表之後，對數據文件的編碼過程是：依次讀人文件中的字符c，在哈夫曼編碼表H中找到此字符，若

　　H[i].ch=c，則將字符c轉換為H[i].bits中存放的編碼串。tW.WIngwIT.COM

　　對壓縮後的數據文件進行解碼則必須借助於哈夫曼樹T，其過程是：依次讀人文件的二進制碼，從哈夫曼樹的根結點(即T[m-

　　1])出發，若當前讀人0，則走向左孩子，否則走向右孩子。一旦到達某一葉子T[i]時便譯出相應的字符H[i].ch。然後重新從根出發

　　繼續譯碼，直至文件結束。

　　文件的編碼和解碼算法【參見練習】。

From:http://tw.wingwit.com/Article/program/sjjg/201311/23862.html