利用哈夫曼樹編碼解碼

哈夫曼編碼 · 發表 2018-12-01 10:25:00

摘要：哈夫曼（Haffman）樹（最優樹）定義：給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。構造過程：以...

哈夫曼（Haffman）樹（最優樹）

定義：

給定n個權值作為n個 ofollow,noindex">葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。

構造過程：

以 1，7，3，4，9，8為例：

第一步：排序，1,3,4,7,8,9

第二步：選出最小的兩個數，1,3（哈夫曼樹是從下往上排列的），用一個樹杈連線上兩個最小的數，在頂點處計算出這兩個數字的和並寫在上面。

第三步：然後再比較剩下的數字和這個和的大小，再取出兩個最小的數字進行排列。

第四步：如果兩個數的和正好是下一步的兩個最小數的其中的一個那麼這個樹直接往上生長就可以了；如果這兩個數的和比較大不是下一步的兩個最小數的其中一個那麼，就並列生長。

注意：（由於並未規定左右子樹，所以哈夫曼樹不唯一，同一層上的結點,位置是可以互換的）

哈夫曼樹的資料結構：

 1 //haffman 樹的結構
 2 typedef struct
 3 {
 4//葉子結點權值
 5float weight;
 6//指向雙親，和孩子結點的指標
 7unsigned int parent;
 8unsigned int lChild;
 9unsigned int rChild;
10 } Node, *HuffmanTree;
11 
12 //動態分配陣列，儲存哈夫曼編碼
13 typedef char *HuffmanCode;

選擇兩個權值最小的結點：

 1 //選擇兩個parent為0，且weight最小的結點s1和s2的方法實現
 2 //n 為葉子結點的總數，s1和 s2兩個指標引數指向要選取出來的兩個權值最小的結點
 3 void select(HuffmanTree *huffmanTree, int n, int *s1, int *s2)
 4 {
 5//標記 i
 6int i = 0;
 7//記錄最小權值
 8int min;
 9//遍歷全部結點，找出單節點
10for(i = 1; i <= n; i++)
11{
12//如果此結點的父親沒有，那麼把結點號賦值給 min，跳出迴圈
13if((*huffmanTree)[i].parent == 0)
14{
15min = i;
16break;
17}
18}
19//繼續遍歷全部結點，找出權值最小的單節點
20for(i = 1; i <= n; i++)
21{
22//如果此結點的父親為空，則進入 if
23if((*huffmanTree)[i].parent == 0)
24{
25//如果此結點的權值比 min 結點的權值小，那麼更新 min 結點，否則就是最開始的 min
26if((*huffmanTree)[i].weight < (*huffmanTree)[min].weight)
27{
28min = i;
29}
30}
31}
32//找到了最小權值的結點，s1指向
33*s1 = min;
34//遍歷全部結點
35for(i = 1; i <= n; i++)
36{
37//找出下一個單節點，且沒有被 s1指向，那麼i 賦值給 min，跳出迴圈
38if((*huffmanTree)[i].parent == 0 && i != (*s1))
39{
40min = i;
41break;
42}
43}
44//繼續遍歷全部結點，找到權值最小的那一個
45for(i = 1; i <= n; i++)
46{
47if((*huffmanTree)[i].parent == 0 && i != (*s1))
48{
49//如果此結點的權值比 min 結點的權值小，那麼更新 min 結點，否則就是最開始的 min
50if((*huffmanTree)[i].weight < (*huffmanTree)[min].weight)
51{
52min = i;
53}
54}
55}
56//s2指標指向第二個權值最小的葉子結點
57*s2 = min;
58 }

構造哈夫曼樹：

 1 //建立哈夫曼樹並求哈夫曼編碼的演算法如下，w陣列存放已知的n個權值
 2 void createHuffmanTree(HuffmanTree *huffmanTree, float w[], int n)
 3 {
 4//m 為哈夫曼樹總共的結點數，n 為葉子結點數
 5int m = 2 * n - 1;
 6//s1 和 s2 為兩個當前結點裡，要選取的最小權值的結點
 7int s1;
 8int s2;
 9//標記
10int i;
11// 建立哈夫曼樹的結點所需的空間，m+1，代表其中包含一個頭結點
12*huffmanTree = (HuffmanTree)malloc((m + 1) * sizeof(Node));
13//1--n號存放葉子結點，初始化葉子結點，結構陣列來初始化每個葉子結點，初始的時候看做一個個單個結點的二叉樹
14for(i = 1; i <= n; i++)
15{
16 
17//其中葉子結點的權值是 w【n】陣列來儲存
18(*huffmanTree)[i].weight = w[i];
19//初始化葉子結點（單個結點二叉樹）的孩子和雙親，單個結點，也就是沒有孩子和雙親，==0
20(*huffmanTree)[i].lChild = 0;
21(*huffmanTree)[i].parent = 0;
22(*huffmanTree)[i].rChild = 0;
23}// end of for
24//非葉子結點的初始化
25for(i = n + 1; i <= m; i++)
26{
27(*huffmanTree)[i].weight = 0;
28(*huffmanTree)[i].lChild = 0;
29(*huffmanTree)[i].parent = 0;
30(*huffmanTree)[i].rChild = 0;
31}
32 
33printf("\n HuffmanTree: \n");
34//建立非葉子結點，建哈夫曼樹
35for(i = n + 1; i <= m; i++)
36{
37
38select(huffmanTree,i-1,&s1,&s2);
39(*huffmanTree)[s1].parent=i;
40(*huffmanTree)[s2].parent=i;
41(*huffmanTree)[i].lChild=s1;
42(*huffmanTree)[i].rChild=s2;
43(*huffmanTree)[i].weight=(*huffmanTree)[s1].weight+(*huffmanTree)[s2].weight;
44printf("%f (%f, %f)\n", (*huffmanTree)[i].weight, (*huffmanTree)[s1].weight, (*huffmanTree)[s2].weight);
45}
46printf("\n");
47 }

求每個節點的哈弗曼編碼：

 1 //哈夫曼樹建立完畢，從 n 個葉子結點到根，逆向求每個葉子結點對應的哈夫曼編碼
 2 void creatHuffmanCode(HuffmanTree *huffmanTree, HuffmanCode *huffmanCode, int n)
 3 {
 4//指示biaoji
 5int i;
 6//編碼的起始指標
 7int start;
 8//指向當前結點的父節點
 9int p;
10//遍歷 n 個葉子結點的指示標記 c
11unsigned int c;
12//分配n個編碼的頭指標
13huffmanCode = (HuffmanCode *)malloc((n + 1) * sizeof(char *));
14//分配求當前編碼的工作空間
15char *cd = (char *)malloc(n * sizeof(char));
16//從右向左逐位存放編碼，首先存放編碼結束符
17cd[n - 1] = '\0';
18//求n個葉子結點對應的哈夫曼編碼
19for(i = 1; i <= n; i++)
20{
21//初始化編碼起始指標
22start = n - 1;
23//從葉子到根結點求編碼
24for(c = i, p = (*huffmanTree)[i].parent; p != 0; c = p, p = (*huffmanTree)[p].parent)
25{
26if( (*huffmanTree)[p].lChild == c)
27{
28//從右到左的順序編碼入陣列內
29cd[--start] = '0';//左分支標0
30}
31else
32{
33cd[--start] = '1';//右分支標1
34}
35}// end of for
36//為第i個編碼分配空間
37huffmanCode[i] = (char *)malloc((n - start) * sizeof(char));
38strcpy(huffmanCode[i], &cd[start]);
39}
40 
41free(cd);
42//列印編碼序列
43for(i = 1; i <= n; i++)
44{
45printf("HuffmanCode of %d is %s\n", i, huffmanCode[i]);
46}
47 
48printf("\n");
49 }

輸入一串資料（資料為1—9之間從小到大連續的數），編譯成哈夫曼編碼：

 1 HuffmanCode *creatHuffmanCode1(HuffmanTree *huffmanTree,char *Huffman, int n,int data[],float num){
 2//該函式通過改寫creatHuffmanCode函式，來實現譯碼（即是通過匹配即新增字串的方式來實現） 
 3HuffmanCode *huffmanCode;
 4huffmanCode = (HuffmanCode *)malloc((n + 1) * sizeof(char *));
 5int i;
 6int start;
 7int p;
 8unsigned int c;
 9char *cd = (char *)malloc(n * sizeof(char));
10cd[n - 1] = '\0';
11for(i = 1; i <= n; i++)
12{
13start = n - 1;
14for(c = i, p = (*huffmanTree)[i].parent; p != 0; c = p, p = (*huffmanTree)[p].parent)
15{
16if( (*huffmanTree)[p].lChild == c)
17{
18cd[--start] = '0';
19}
20else
21{
22cd[--start] = '1';
23}
24}
25huffmanCode[i] = (char *)malloc((n - start) * sizeof(char));
26strcpy(huffmanCode[i], &cd[start]);
27}
28free(cd);
29//列印編碼序列
30int num1=int(num);
31int l=0;
32char s[10]="";
33itoa(n,s,10);
34huffmanCode[0] = (char *)malloc((10) * sizeof(char));
35strcpy(huffmanCode[0],s);
36for(int i=1;i<=num1;i++){
37int z=data[i];
38strcat(Huffman,huffmanCode[z]);
39}
40printf("HuffmanCode of this String is %s\n",Huffman);
41printf("\n");
42return huffmanCode;
43 }
44 
45 
46 HuffmanCode *dataToHuffmanCode(char *Huffman, int data[]){
47//data陣列是原資料（0—9），Huffman存放編譯後的 Huffman編碼 
48HuffmanTree huffmanTree;
49int k=1;
50int q=0;
51while(data[k]!=-99){
52k++;
53}
54float num=float(k-1);
55float val[10];
56for(int j=1;j<10;j++){
57int i=1;
58int n=0;
59while(data[i]!=-99){
60if(data[i]==j){
61n++;
62}
63i++;
64}
65val[j]=n/num;
66}
67for(int i=1;i<10;i++){
68if(val[i]!=0){
69q++;//q為葉子結點數 
70}
71}
72float *val2; 
73val2 = (float *)malloc((q+1) * sizeof(float));
74int m=1;
75for(int i=1;i<10;i++){
76if(val[i]!=0){
77val2[m]=val[i];
78}
79m++;//val2[]儲存不同元素的權值 
80}
81createHuffmanTree(&huffmanTree,val2,q);
82HuffmanCode *huffmanCode=creatHuffmanCode1(&huffmanTree,Huffman,q,data,num);//呼叫上面的 creatHuffmanCode1函式 
83return huffmanCode;
84 }

將一串哈夫曼編碼，還原成原來的資料（此時哈弗曼樹已經構造完成）：

 1 void HuffmanCodeTodata(char *Huffman, int data[],HuffmanCode *huffmanCode){
 2//huffmanCode為已經構造好的一顆Huffman樹，Huffman存放已經編譯好的 Huffman編碼 ，data陣列存放解碼後的原資料（0—9） 
 3
 4printf("Huffman:%s\n",Huffman);
 5printf("1:%s\n",huffmanCode[1]);
 6printf("2:%s\n",huffmanCode[2]);
 7printf("3:%s\n",huffmanCode[3]);
 8printf("4:%s\n",huffmanCode[4]);
 9//這幾行是顯示功能，和實現無關 
10
11int num=atoi(huffmanCode[0]);
12char Huffman1[100]="";
13int k1=0;
14int k2=0;
15int x=1;
16int y=1;
17while(Huffman[k1]=='1'||Huffman[k1]=='0'){
18Huffman1[k2]=Huffman[k1];
19for(int i=1;i<=num;i++){
20if(strcmp(huffmanCode[i],Huffman1)==0){
21k2=-1;
22data[x]=i;
23x++;
24//strcpy(Huffman1,"");
25memset(Huffman1,0,sizeof(Huffman1));
26break;
27}
28}
29k1++;
30k2++;
31}
32data[x]=-99;
33for(int i=1;i<100;i++){
34if(data[i]!=-99){
35printf("%d",data[i]);
36}
37else{
38break;
39}
40}
41 }

輸入一個文字，統計文字中各字串的數目，計算相應的權重，使用該權重構建哈夫曼編碼，使用該編碼編譯原檔案

（即是在編碼的基礎上加上檔案操作）：

 1 void fileHuff(){
 2FILE *in;
 3char Huffman2[1000]="";
 4int data[100];
 5char file[10];
 6int k = 1;
 7printf("輸入讀取的檔名：（輸入aaa.txt）");
 8scanf("%s",file);
 9if((in=fopen(file,"r+"))==NULL){
10printf("無法開啟此檔案！\n");
11exit(0);
12}
13while(!feof(in)){
14fscanf(in,"%d",&data[k++]);
15}
16for(int i=1;i<k;i++){
17printf("\n%d\n",data[i]);
18}
19data[k]=-99;
20dataToHuffmanCode(Huffman2,data);
21fprintf(in,"\n");
22fprintf(in,"解碼後的碼為：\n");
23fprintf(in,"%s",Huffman2);
24fflush(in);
25fclose(in);
26 }

主函式：

 1 int main()
 2 {
 3HuffmanTree HT;
 4HuffmanCode HC;
 5char Huffman[1000]="";
 6char Huffman1[1000]="";
 7HuffmanCode *huffmanCode;
 8int i, n;
 9float *w, wei;
10int choice;
11for (;;)
12{
13printf("\n哈夫曼編碼 \n");
14printf("1.哈夫曼編碼實現\n");
15printf("2.輸入一串資料（資料為1—9之間從小到大連續的數），編譯成哈夫曼編碼\n");
16printf("3.將一串哈夫曼編碼，還原成原來的資料\n");
17printf("4.輸入一個文字，統計文字中各字串的數目，計算相應的權重，使用該權重構建哈夫曼編碼，使用該編碼編譯原檔案\n");
18printf("5.退出系統\n");
19printf("請選擇：");
20scanf("%d", &choice);
21switch (choice)
22{
23case 1:
24printf("\n 需要建立的檔案有多少個碼元 = " );
25scanf("%d", &n);
26w = (float *)malloc((n + 1) * sizeof(float));
27printf("\ninput the %d element's weight:\n", n);
28for(i = 1; i <= n; i++)
29{
30printf("%d: ", i);
31fflush(stdin);
32scanf("%f", &wei);
33w[i] = wei;
34}
35createHuffmanTree(&HT, w, n);
36creatHuffmanCode(&HT, &HC, n);
37break;
38case 2:
39printf("\n輸入資料為：(以-99結束)");
40int data[100];
41for(int i=1;i<100;i++){
42scanf("%d",&data[i]);
43if(data[i]==-99){
44break;
45}
46}
47huffmanCode=dataToHuffmanCode(Huffman,data);
48break;
49case 3:
50int data1[100];
51printf("\n哈夫曼編碼解碼後為：\n");
52HuffmanCodeTodata(Huffman,data1,huffmanCode);
53break;
54case 4:
55printf("\n需要實現將aaa.txt檔案放在桌面上！\n");
56fileHuff();
57break;
58case 5:
59printf("請退出系統!\n");
60exit(0);
61break;
62}
63}
64return 1;
65 }