基于哈夫曼樹的資料壓縮算法

計算機科學與技術系

實 驗 報 告

專業名稱 計算機科學與技術

課程名稱 資料結構與算法

班 級 17計科2班

綜合實驗2   基于哈夫曼樹的資料壓縮算法  
           

實驗日期 2019.04.29

綜合實驗二 基于哈夫曼樹的資料壓縮算法

一、實驗目的

1.掌握哈夫曼樹的構造算法

2.掌握哈夫曼編碼的構造算法

二、實驗内容

輸入一串字元串，根據給定的字元串中字元出現的頻率建立相應的哈夫曼樹，構造哈夫曼編碼表，在此基礎上可以對壓縮檔案進行壓縮（即編碼），同時可以對壓縮後的二進制編碼檔案進行解壓（即解碼）

三、實驗要求

1.輸入說明:多組資料，每組資料1行，為一個字元串(隻考慮26個小寫英文字母即可）。檔輸入字元串為“0”時，輸入結束。

2.輸出說明:每組資料輸出2n+3行（n為輸入串中字元類别的個數）。第1行為統計出來的字元出現頻率（隻輸出存在的字元，格式為：字元：頻度），每兩組字元之間用一個空格分隔，字元按照ASCII碼從小到大的順序排列。第2行到第2n行為哈夫曼樹的存儲結構的終态（一行當中的資料用空格分隔）。第2n+1行為每個字元的哈夫曼編碼（隻輸出存在的字元，格式為：字元：編碼），每兩組字元之間用一個空格分隔，字元按照ASCII碼從小到大的順序排列。第2n+2行為編碼後的字元串，第2n+3行為解碼後的字元串（與輸入的字元串相同）。

3.測試用例:

輸入樣例

輸入 輸出

aaaaaaabbbbbccdddd

aabccc

0 a:7 b:5 c:2 d:4

1 7 7 0 0

2 5 6 0 0

3 2 5 0 0

4 4 5 0 0

5 6 6 3 4

6 11 7 2 5

7 18 0 1 6

A:0 b:10 c:110 d:111

00000001010101010110110111111111111

aaaaaaabbbbbccdddd

a:2 b:1 c:3

1 2 4 0 0

2 1 4 0 0

3 3 5 0 0

4 3 5 2 1

5 6 0 3 4

a:11 b:10 c:0

111110000

aabccc

四、實驗分析及設計

1. 問題分析（問題及解決方案）

   本程式要求實作根據給定的字元串中字元出現的頻率建立相應的哈夫曼樹，構造哈夫曼編碼表，在此基礎上可以對壓縮檔案進行壓縮（即編碼），同時可以對壓縮後的二進制編碼檔案進行解壓（即解碼）。

要完成該實驗任務，必須完成如下7個子任務：

①建立一個結構體，其中包含了weight:結點的權值，parent:結點的雙親，lchild:結點的左孩子以及rchild:結點的右孩子；

②統計出來的字元出現頻率（隻輸出存在的字元，格式為：字元：頻度）。

③輸出哈夫曼樹的存儲結構的終态，每一行有五個數字，其中第一個為結點序号，第二個為結點的值，第三個為結點的父節點的序号，第四個為結點左孩子的序号，第五個為結點右孩子的序号。

④設計一個算法，求出每個節點的哈夫曼編碼。

⑤根據每個結點的編碼，寫出字元串的編碼形式。

⑥設計一個算法，進行解碼。

⑦構造一個哈夫曼樹。

最後寫出主函數即可。

1. 概要設計（實作要點）

   1）為了實作上述程式功能，需要：①輸入字元串；②寫出每個字元出現的次數；③根據字元出現的次數構造一個哈夫曼樹；④輸出哈夫曼樹的存儲結構的終态；⑤求出每個節點的哈夫曼編碼；⑥寫出編碼形式的字元串；⑦最後進行解碼。

   2）本程式包含9個函數：

   　　① 主函數main()

   　　② select_yuan_su(a1,maps,n,h);

   ③ CreatHuffmanTree(ht,n,maps);

   ④ shuchu_zhongtai(ht,n);

   ⑤ CreatHuffmanCode(ht,hc,n);

   ⑥ shuchu_bian_ma(hc,n,maps);

   ⑦ string m=bian_ma(a1,h,hc,n);

   ⑧ jie_ma(m,h,hc,n);

   ⑨ Select(HT,i-1,s1,s2)

   各函數間關系如下：

   Main()包含其他函數。

   CreatHuffmanCode(ht,hc,n)包含Select(HT,i-1,s1,s2)。

2. 詳細設計

   1）資料類型定義

   實作概要設計中定義的所有的資料類型，對每個操作給出僞碼算法。對主程式和其他子產品也都需要寫出僞碼算法。

   　　1) 結點類型和指針類型

   　　typedef struct

   {

   int weight;

   int parent,lchild,rchild;

   }HTNode,*HuffmanTree;

   typedef char **HuffmanCode;

2）算法設計

void Select(HuffmanTree HT,int len,int &s1,int &s2)

{

//在構造哈夫曼樹的時候，需要選出兩個最小的結點

循環周遊找出一個最小值，将其指派給s1。

用temp将s1的值儲存下來。

将s1的值改成最大值。

循環周遊找出一個最小值，将其指派給s2。

恢複s1的值。

}

void CreatHuffmanTree(HuffmanTree &HT,int n,map<char,int>&maps)

{

初始化哈夫曼樹

通過n-1次的選擇、删除、合并來建立哈夫曼樹

}

void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)

{

從葉子到根逆向求每個字元的哈夫曼編碼，存儲在編碼表HC中

結點c是f的左孩子，則生成代碼0

結點c是f的右孩子，則生成代碼1

}

五、 實驗參考代碼（含注釋）

void Select(HuffmanTree HT,int len,int &s1,int &s2)

{

int i,min1=0x3f3f3f3f,min2=0x3f3f3f3f;//先賦予最大值

for(i=1;i<=len;i++)

{

if(HT[i].weight<min1&&HT[i].parent0)

{

min1=HT[i].weight;

s1=i;

}

}

int temp=HT[s1].weight;//将原值存放起來，然後先賦予最大值，防止s1被重複選擇

HT[s1].weight=0x3f3f3f3f;

for(i=1;i<=len;i++)

{

if(HT[i].weight<min2&&HT[i].parent0)

{

min2=HT[i].weight;

s2=i;

}

}

HT[s1].weight=temp;//恢複原來的值

}

//構造哈夫曼樹

void CreatHuffmanTree(HuffmanTree &HT,int n,map<char,int>&maps)

{

//構造哈夫曼樹HT

int m,s1,s2,i;

if(n<=1) return;

m=2*n-1;

HT=new HTNode[m+1]; //0号單元未用，是以需要動态配置設定m+1個單元，HT[m]表示根結點

for(i=1;i<=m;++i)//将1~m号單元中的雙親、左孩子，右孩子的下标都初始化為0

{ HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; }

map<char,int>::iterator it;

it=maps.begin();

for(i=1;i<=n;++i,it++) //輸入前n個單元中葉子結點的權值

HT[i].weight=it->second;

/――――――――――初始化工作結束，下面開始建立哈夫曼樹――――――――――/

for(i=n+1;i<=m;++i)

{ //通過n-1次的選擇、删除、合并來建立哈夫曼樹

Select(HT,i-1,s1,s2);

//在HTk中選擇兩個其雙親域為0且權值最小的結點,

// 并傳回它們在HT中的序号s1和s2

HT[s1].parent=i;

HT[s2].parent=i;

//得到新結點i，從森林中删除s1，s2，将s1和s2的雙親域由0改為i

HT[i].lchild=s1;

HT[i].rchild=s2 ; //s1,s2分别作為i的左右孩子

HT[i].weight=HT[s1].weight+HT[s2].weight; //i 的權值為左右孩子權值之和

} //for

}

// CreatHuffmanTree

void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)

{

//從葉子到根逆向求每個字元的哈夫曼編碼，存儲在編碼表HC中

int i,start,c,f;

HC=new char*[n+1]; //配置設定n個字元編碼的頭指針矢量

char *cd=new char[n]; //配置設定臨時存放編碼的動态數組空間

cd[n-1]=’\0’; //編碼結束符

for(i=1;i<=n;++i)

{ //逐個字元求哈夫曼編碼

start=n-1; //start開始時指向最後，即編碼結束符位置

c=i;

f=HT[i].parent; //f指向結點c的雙親結點

while(f!=0)

{ //從葉子結點開始向上回溯，直到根結點

–start;//回溯一次start向前指一個位置

if(HT[f].lchild==c)

cd[start]=‘0’; //結點c是f的左孩子，則生成代碼0

else

cd[start]=‘1’; //結點c是f的右孩子，則生成代碼1

c=f;

f=HT[f].parent; //繼續向上回溯

} //求出第i個字元的編碼

HC[i]=new char[n-start]; // 為第i 個字元編碼配置設定空間

strcpy(HC[i], &cd[start]); //将求得的編碼從臨時空間cd複制到HC的目前行中

}

delete cd; //釋放臨時空間

}

六、實驗測試結果（至少兩種測試資料）

輸入ablizzz

輸入dddvvv

七、算法性能分析與總結

1、算法性能分析

從時間性能來看，時間複雜度為O(n^2），因為在CreatHuffmanTree（）函數中調用了Select（）函數，他們兩個裡面每個都包含了一層for循環。

2、實驗總結

可以這麼說，這次實驗是我目前為止遇到最難的一個算法，本來我是想放棄的，在網上随便找一個直接複制過來。但是這次我沒有，盡管不是我自己獨立完成的，但其中有一部分核心代碼，也就是我們這次要掌握的哈夫曼樹的構造以及哈夫曼編碼是我自己實作的，我還是很高興的，但是這個算法還有一點小缺陷，隻能輸入一個字元串，等出結果了才能再輸入下一個字元串。老師強調更要去了解算法的思想。選擇一個更好的算法，能提高程式的效率。其他部分的内容我不是很了解，在課後我又問了同學，查閱了相關的資料。把整個程式的設計思路了解了。雖然說以前不是很了解這門課，在它上面花了好多心血，覺得他還是難，我現在明白了一些代碼，其實每個程式都有一些共同點，通用的結構。我會抓緊時間将沒有吃透的知識點補齊，克服學習中遇到的難關，打牢基礎，向更深的層次進發。