哈夫曼編碼的設計與應用

問題需求分析

用哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，該方法完全依據字符出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼(有時也稱為霍夫曼編碼)。
霍夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度之和，記為WPL=（W1L1+W2L2+W3L3+…+WnLn），N個權值Wi（i=1,2,…n）構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li（i=1,2,…n）。

數據結構的定義

哈夫曼樹結構體包含如下內容：節點權重，當前節點的父節點，左右子樹，節點信息。
哈夫曼編碼結構體包含如下內容：存編碼的數組，編碼數組的開始標志。

功能詳細設計

構建哈夫曼樹：使用一維數組，每個節點存儲權重，父節點，左子樹，右子樹，以及數值的信息。遍歷整個數組，根據每個節點的權重去找到最小以及第二小的節點，然后對各自的父節點，左右子樹賦值，建立兩個節點的聯系將他們的聯系填入該結構體數組中。
哈夫曼樹如下圖:
a權重45; b權重15; c權重12; d權重16; e權重9; f權重5

哈夫曼樹結構體數組如下圖(使用a, b, 58舉例):

根據哈夫曼樹建立哈夫曼編碼：從樹的根節點開始，根據每個葉子節點與父節點之間的聯系，使用哈夫曼編碼結構體中的編碼數組儲存樹種每個葉子節點的編碼, 往左邊遍歷是0, 往右邊遍歷是1, 舉例: a, 由建立好的哈夫曼樹可得, 當遍歷查找到a的時候, a到root的路徑是: 100->86->58->a, 所以可得編碼就是000;

根據哈夫曼編碼將指定的編碼轉化為字符串：讀取到哈夫曼編碼后，當編碼為0表示節點是左子樹，當編碼為1的時候表示右子樹，根據已經建立好的哈夫曼樹，利用順序遍歷的方式，根據左0右1，尋找哈夫曼樹中的葉子節點，當某一節點在哈夫曼樹中左右子樹都為空的時候，表示該節點即使葉子節點，然后輸出對應葉子節點在哈夫曼編碼數組中的位置, 其原理與編碼的方式恰恰相符, 而是根據01數字查找對應的葉子節點.

函數調用圖:

編寫代碼體會

遇到的問題是數組下標沒有弄好,導致建立哈夫曼樹時出現各種錯誤, 進行編碼過程沒有將lchild與rchild的”變化寫在一起”導致出現錯誤,其實最大的問題是:沒有將代碼的邏輯思路考慮清楚,還有邊界條件值,最蠢的是沒有打一下草稿,寫一下偽代碼,把程序的思想理解,導致編程的過程中出現各種問題,以后寫代碼之前還是把邏輯理清楚再動手寫代碼,最后再將代碼寫到電腦上測試。

完整代碼

#include<iostream> #include<string> #include<fstream> using namespace std; struct Htnode{int weight,parent,lchild,rchild;char c; }; struct Htcode{int bit[25],start; }; int type(int a[]){string s;int sum = 0; cout<<"輸入需要編碼的字符串"<<endl;cin>>s;for(int i = 0; i < s.size(); i++){a[s[i]-'a']++;}cout<<"出現的字母種類以及頻率:"<<endl; for(int i = 0; i < 26; i++){if(a[i] != 0){char c = char(i+'a');cout<<"i:"<<i<<" c:"<<c<<":"<<a[i]/(s.size()*1.0)<<endl;sum++; }}return sum; } //通過數組的方式構建哈夫曼樹 void HufmanTree(Htnode h[],int n, int a[]){int i,j,max1,max2,x1,x2;for(i=0;i<2*n;i++){h[i].weight=0;h[i].parent=-1;h[i].lchild=-1;h[i].rchild=-1;h[i].c='\0';}for(i=0;i<26;i++){if(a[i] != 0){h[i].c = i + 'a';h[i].weight = a[i]; }}for(i=0;i<n-1;i++){max1=1000,max2=1000;x1=-1,x2=-1; for(j=0;j<n+i;j++){if(h[j].weight<max1 && h[j].parent==-1){max2=max1;x2=x1;max1=h[j].weight;x1=j;}else if(h[j].weight<max2 && h[j].parent==-1){max2=h[j].weight;x2=j;}}//根據每個節點信息, 將其信息存儲到節點數組中h[x1].parent=n+i; h[x2].parent=n+i; h[n+i].weight=h[x1].weight+h[x2].weight;h[n+i].lchild=x1;h[n+i].rchild=x2;}for (i=0;i<2*n-1;i++){cout<<h[i].weight<<" "<<h[i].parent<<" "<<h[i].lchild<<" "<<h[i].rchild<<" "<<h[i].c<<endl; } } //哈夫曼編碼 //根據葉子節點的位置, 將其path路徑01數字填充到編碼數組中 void HuffmandeCode(Htnode h[], int n, int a[], Htcode hcode[]){HufmanTree(h, n, a);ofstream out;out.open("HuffmandeCode.txt", ios::out);int i,j;for(i=0;i<n;i++){j=0;int parent=h[i].parent;//記錄當前節點的父親 int c=i;while(c!=-1){//parent造成根節點不會被訪問 hcode[i].bit[j++]=h[parent].lchild==c?0:1;//從葉子節點到根節點, 應該使用棧結構 c=parent;parent=h[parent].parent;}hcode[i].start=j-1;}for(i=0;i<n;i++){cout<<h[i].c<<":";for(j=hcode[i].start-1;j>=0;j--){cout<<hcode[i].bit[j];out<<hcode[i].bit[j];}cout<<endl;}out.close(); } string load(){ifstream in("HuffmandeCode.txt");string str;char buffer[256];if(!in.is_open()){cout<<"加載文件錯誤"<<endl; return NULL;} cout << "載入編碼文件" << endl;in.getline(buffer, 100, ' ');return string(buffer); }//哈夫曼譯碼 void HuffmanenCode(string s,int n,Htnode h[]){int i=0,j=0,lchild=2*n-2,rchild=2*n-2;while(s[i]!='\0'){if(s[i]=='0'){//出現的問題是,最初將lchild,rchild分開計算,導致在左右子樹間相互變化出現//lchild,rchild不同同時表示同一個節點,最后想到lchild=rchild就能解決問題lchild=h[lchild].lchild;rchild=j=lchild;}if(s[i]=='1'){rchild=h[rchild].rchild;lchild=j=rchild;}if(h[lchild].lchild==-1 && h[rchild].rchild==-1){cout<<h[j].c;lchild=rchild=2*n-2;j=0;}i++;} } int main(){Htnode h[30];Htcode hcode[10];int a[26]={0};string s;int n = type(a);cout<<"n:"<<n<<endl;HuffmandeCode(h, n, a, hcode);HuffmanenCode(load(),n,h);return 0; }

上面有錯, 還請指出, 如果認為我寫的還不錯, 還請點個贊, 多多支持一下, O(∩_∩)O~~

總結

以上是生活随笔為你收集整理的哈夫曼树编码与译码(完整C/C++实现代码)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。