《哈夫曼樹解壓與壓縮.doc》由會員分享，可在線閱讀，更多相關《哈夫曼樹解壓與壓縮.doc（14頁珍藏版）》請在裝配圖網上搜索。

1、哈夫曼樹的壓縮與解壓1. 算法簡要描述1.哈夫曼算法1. 哈弗曼算法是根據給定的n個權值w1，w2，w3.wn，構造由n棵二叉樹構成的深林F=T1,T2,。Tn，其中每個二叉樹Ti分別都是只含有一個權值wi的根結點，其左右子樹為空（i=1，,2）。2. 在深林F中選取其根結點的權值最小的兩棵二叉樹，分別作其左右子樹構造一顆新的二叉樹，并置這棵新的二叉樹根結點的權值為其左右子樹的根結點之和。3. 從F中刪去這兩棵二叉樹，同時剛新生成的二叉樹加入到深林F中。4. 重復2,3,步驟，直至深林F中只含有一顆二叉樹為止。2.哈夫曼樹的實現(xiàn)函數String EnCode(Char Type ch)：表示哈

2、夫曼樹已存在，返回字符ch的編碼。函數LinkListUnCode(String strCode)：表示對哈夫曼樹進行譯碼，返回編碼前的字符序列。根據算法可以看出，在具有n個結點權值的哈夫曼樹的構造過程中 ，每次都是從F中刪去兩棵樹，增加一棵樹，即每次結束后減少一棵樹，經過n-1次處理后，F(xiàn)中就只剩下一棵樹了。另外，每次合并都要產生一個新的結點，合并n-1次后共產生了n-1個新結點，并且這n-1個新節(jié)點都是具有左右子樹的分支結點。則最終得到的哈夫曼樹中共有2n-1個結點，并且其中沒有度為1的分支結點，最后一次產生的新結點就是哈夫曼樹的根結點。源代碼中創(chuàng)建了一個哈夫曼樹結點類，其中有數據成員we

3、ight，parent，leftChild，rightChild分別代表了權值，雙親，左孩子，右孩子。在哈夫曼樹類中有數據成員*nodes，*LeafChars，*LeafCharCodes，curPos，num，分別用來存儲結點信息，葉結點字符信息，葉結點字符編碼信息，譯碼時從根結點到葉結點路徑的當前結點，葉結點個數。哈夫曼樹類中含有多個函數，有構造函數，析構函數等。由函數HuffmanTree(CharType ch,WeightType w,int n)來構造由字符，權值，和字符個數構造哈夫曼樹，在根據哈夫曼算法很容易實現(xiàn)哈夫曼類的函數以及構造函數。在在算法中，求葉結點字符的編碼時，需要

4、從葉結點出發(fā)走一條從高葉結點到根結點的路徑，而編碼卻是從根結點出發(fā)到葉結點的路徑，由左分支為編碼0，右分支為編碼1，得到的編碼，因此從葉結點出發(fā)到根結點的路徑得到的編碼是實際編碼的逆序，并且編碼長度不確定，又由于可以再線性鏈表中構造串，因此將編碼的信息儲存在一個線性立案標準，每得到一位編碼都將其插入在線性鏈表的最前面。在求某個字符的編碼是由函數EnCode(CharType ch)來求，返回字符編碼。在進行譯碼時，用一個線性鏈表存儲字符序列，由函數Decode(String strCode)來求，對編碼串strCode進行譯碼，返回編碼前的字符序列。函數Compress()用哈夫曼編碼壓縮文件

5、。函數Decompress()解壓縮用哈夫曼編碼壓縮的文件。在主函數中有兩個選項，一個是選擇編碼壓縮，一個是解壓。在函數中使用了文件輸入輸出流，我們可以選擇要壓縮的文件名輸入，在選出壓縮文件保存的地方和文件類型，將壓縮所得到的文件存儲在另一個文件中，解壓也是如此。2. 源代碼#ifndef _HUFFMAN_TREE_NODE_H_#define _HUFFMAN_TREE_NODE_H_/ 哈夫曼樹結點類模板template struct HuffmanTreeNodeWeightType weight;/ 權數據域unsigned int parent, leftChild, rightC

6、hild;/ 雙親,左右孩子域HuffmanTreeNode();/ 無參數的構造函數模板HuffmanTreeNode(WeightType w, int p = 0, int lChild = 0, int rChild = 0);/ 已知權,雙親及左右孩子構造結構;/ 哈夫曼樹結點類模板的實現(xiàn)部分template HuffmanTreeNode:HuffmanTreeNode()/ 操作結果：構造空結點parent = leftChild = rightChild = 0;template HuffmanTreeNode:HuffmanTreeNode(WeightType w, int

7、 p, int lChild, int rChild)/ 操作結果：構造一個權為w,雙親為p,左孩子為lChild,右孩子為rChild的結點weight = w;/ 權parent = p;/ 雙親leftChild = lChild;/ 左孩子rightChild = rChild;/ 右孩子#endif#ifndef _HUFFMAN_TREE_H_#define _HUFFMAN_TREE_H_#include string.h/ 串類#include huffman_tree_node.h/ 哈夫曼樹結點類模板/ 哈夫曼樹類模板template class HuffmanTreepr

8、otected:HuffmanTreeNode *nodes;/ 存儲結點信息,nodes0未用CharType *LeafChars;/ 葉結點字符信息,LeafChars0未用String *LeafCharCodes;/ 葉結點字符編碼信息,LeafCharCodes0未用int curPos;/ 譯碼時從根結點到葉結點路徑的當前結點int num;/ 葉結點個數/輔助函數模板:void Select(int cur, int &r1, int &r2);/ nodes1 cur中選擇雙親為,權值最小的兩個結點r1,r2void CreatHuffmanTree(CharType ch,

9、 WeightType w, int n);/ 由字符,權值和字符個數構造哈夫曼樹public:/ 哈夫曼樹方法聲明及重載編譯系統(tǒng)默認方法聲明:HuffmanTree(CharType ch, WeightType w, int n);/ 由字符,權值和字符個數構造哈夫曼樹virtual HuffmanTree();/ 析構函數模板String Encode(CharType ch);/ 編碼LinkList Decode(String strCode);/ 譯碼HuffmanTree(const HuffmanTree ©);/ 復制構造函數模板HuffmanTree &operat

10、or=(const HuffmanTree& copy);/ 重載賦值運算符;/ 孩子兄弟表示哈夫曼樹類模板的實現(xiàn)部分template void HuffmanTree:Select(int cur, int &r1, int &r2)/ 操作結果：nodes1 cur中選擇雙親為,權值最小的兩個結點r1,r2r1 = r2 = 0;/ 0表示空結點for (int pos = 1; pos = cur; pos+)/ 查找樹值最小的兩個結點if (nodespos.parent != 0) continue;/ 只處理雙親不為的結點if (r1 = 0)r1 = pos; / r1為空,將p

11、os賦值給r1else if (r2 = 0)r2 = pos; / r2為空,將pos賦值給r2else if(nodespos.weight nodesr1.weight)r1 = pos; / nodespos權值比nodesr1更小,將pos賦為r1else if (nodespos.weight nodesr2.weight)r2 = pos; / nodespos權值比nodesr2更小,將pos賦為r2template void HuffmanTree:CreatHuffmanTree(CharType ch, WeightType w, int n)/ 操作結果：由字符,權值和

12、字符個數構造哈夫曼樹num = n;/ 葉結點個數int m = 2 * n - 1;/ 結點個數nodes = new HuffmanTreeNodem + 1;/ nodes0未用LeafChars = new CharTypen + 1;/ LeafChars0未用LeafCharCodes = new Stringn + 1;/ LeafCharCodes0未用 int pos;/ 臨時變量for (pos = 1; pos = n; pos+)/ 存儲葉結點信息nodespos.weight = wpos - 1;/ 權值LeafCharspos = chpos - 1;/ 字符fo

13、r (pos = n + 1; pos = m; pos+)/ 建立哈夫曼樹int r1, r2;Select(pos - 1, r1, r2);/ nodes1 pos - 1中選擇雙親為,權值最小的兩個結點r1,r2/ 合并以r1,r2為根的樹nodesr1.parent = nodesr2.parent = pos;/ r1,r2雙親為posnodespos.leftChild = r1;/ r1為pos的左孩子nodespos.rightChild = r2;/ r2為pos的右孩子nodespos.weight = nodesr1.weight + nodesr2.weight;/p

14、os的權為r1,r2的權值之和for (pos = 1; pos = n; pos+)/ 求n個葉結點字符的編碼LinkList charCode;/ 暫存葉結點字符編碼信息for (unsigned int child = pos, parent = nodeschild.parent; parent != 0; child = parent, parent = nodeschild.parent)/ 從葉結點到根結點逆向求編碼if (nodesparent.leftChild = child) charCode.Insert(1, 0);/ 左分支編碼為0else charCode.Ins

15、ert(1, 1);/ 右分支編碼為1LeafCharCodespos = charCode;/ charCode中存儲字符編碼curPos = m;/ 譯碼時從根結點開始,m為根template HuffmanTree:HuffmanTree(CharType ch, WeightType w, int n)/ 操作結果：由字符,權值和字符個數構造哈夫曼樹CreatHuffmanTree(ch, w, n);/ 由字符,權值和字符個數構造哈夫曼樹template HuffmanTree:HuffmanTree()/ 操作結果：銷毀哈夫曼樹if (nodes != NULL) delete n

16、odes;/ 釋放結點信息if (LeafChars != NULL) delete LeafChars;/ 釋放葉結點字符信息if (LeafCharCodes != NULL) delete LeafCharCodes;/ 釋放葉結點字符編碼信息template String HuffmanTree:Encode(CharType ch)/ 操作結果：返回字符編碼for (int pos = 1; pos = num; pos+)/ 查找字符的位置if (LeafCharspos = ch) return LeafCharCodespos;/ 找到字符,得到編碼throw Error(非法

17、字符,無法編碼!);/ 拋出異常template LinkList HuffmanTree:Decode(String strCode)/ 操作結果：對編碼串strCode進行譯碼,返回編碼前的字符序列LinkList charList;/ 編碼前的字符序列for (int pos = 0; pos strCode.Length(); pos+)/ 處理每位編碼if (strCodepos = 0) curPos = nodescurPos.leftChild;/ 0表示左分支else curPos = nodescurPos.rightChild;/ 1表示左分支if (nodescurPo

18、s.leftChild = 0 & nodescurPos.rightChild = 0)/ 譯碼時從根結點到葉結點路徑的當前結點為葉結點charList.Insert(charList.Length() + 1, LeafCharscurPos);curPos = 2 * num - 1;/ curPos回歸根結點return charList;/ 返回編碼前的字符序列template HuffmanTree:HuffmanTree(const HuffmanTree ©)/ 操作結果：由哈夫曼樹copy構造新哈夫曼樹復制構造函數模板num = copy.num;/ 葉結點個數cur

19、Pos = copy.curPos;/ 譯碼時從根結點到葉結點路徑的當前結點int m = 2 * num - 1;/ 結點總數nodes = new HuffmanTreeNodem + 1;/ nodes0未用LeafChars = new CharTypenum + 1;/ LeafChars0未用LeafCharCodes = new Stringnum + 1;/ LeafCharCodes0未用int pos;/ 臨時變量for (pos = 1; pos = m; pos+)/ 復制結點信息nodespos = copy.nodespos;/ 結點信息for (pos = 1;

20、pos = num; pos+)/ 復制葉結點字符信息與葉結點字符編碼信息LeafCharspos = copy.LeafCharspos;/ 葉結點字符信息LeafCharCodespos = copy.LeafCharCodespos;/ 葉結點字符編碼信息template HuffmanTree &HuffmanTree:operator=(const HuffmanTree& copy)/ 操作結果：將哈夫曼樹copy賦值給當前哈夫曼樹重載賦值運算符if (© != this)if (nodes != NULL) delete nodes;/ 釋放結點信息if (LeafCha

21、rs != NULL) delete LeafChars;/ 釋放葉結點字符信息if (LeafCharCodes != NULL) delete LeafCharCodes;/ 釋放葉結點字符編碼信息num = copy.num;/ 葉結點個數curPos = copy.curPos;/ 譯碼時從根結點到葉結點路徑的當前結點int m = 2 * num - 1;/ 結點總數nodes = new HuffmanTreeNodem + 1;/ nodes0未用LeafChars = new CharTypenum + 1;/ LeafChars0未用LeafCharCodes = new S

22、tringnum + 1;/ LeafCharCodes0未用int pos;/ 臨時變量for (pos = 1; pos = m; pos+)/ 復制結點信息nodespos = copy.nodespos;/ 結點信息for (pos = 1; pos = num; pos+)/ 復制葉結點字符信息與葉結點字符編碼信息LeafCharspos = copy.LeafCharspos;/ 葉結點字符信息LeafCharCodespos = copy.LeafCharCodespos;/ 葉結點字符編碼信息return *this;#endif#ifndef _HUFFMAN_COMPRES

23、S_H_#define _HUFFMAN_COMPRESS_H_#include huffman_tree.h/ 哈夫曼樹類struct BufferType/ 字符緩存器char ch;/ 字符unsigned int bits;/ 實際比特數 ;class HuffmanCompress/ 哈夫曼壓縮類protected:HuffmanTree *pHuffmanTree;FILE *infp,*outfp;/ 輸入/出文件BufferType buf;/ 字符緩存void Write(unsigned int bit);/ 向目標文件中寫入一個比特void WriteToOutfp();

24、/ 強行將字符緩存寫入目標文件public:HuffmanCompress();/ 無參數的構造函數HuffmanCompress();/ 析構函數void Compress();/ 壓縮算法void Decompress();/ 解壓縮算法HuffmanCompress(const HuffmanCompress ©);/ 復制構造函數HuffmanCompress &operator=(const HuffmanCompress& copy);/ 賦值運算符;HuffmanCompress:HuffmanCompress()pHuffmanTree = NULL;/ 空哈夫曼樹Hu

25、ffmanCompress:HuffmanCompress()if (pHuffmanTree != NULL) delete pHuffmanTree;/ 釋放空間void HuffmanCompress:Write(unsigned int bit)/ 操作結果：向目標文件中寫入一個比特buf.bits+;/ 緩存比特數自增buf.ch = (buf.ch 0)/ 緩存非空, 將緩存的比特個數增加到, 自動寫入目標文件for (unsigned int i = 0; i 8 - len; i+) Write(0);void HuffmanCompress:Compress()/ 操作結果：

26、用哈夫曼編碼壓縮文件char infName256, outfName256;/ 輸入(源)/出(目標)文件名cout infName;/ 輸入源文件名if (infp = fopen(infName, r+b) = NULL)throw Error(打開源文件失敗!);/ 拋出異常 fgetc(infp);/ 取出源文件第一個字符if (feof(infp)throw Error(空源文件!);/ 拋出異常cout outfName; if (outfp = fopen(outfName, w+b) = NULL)throw Error(打開目標文件失敗!);/ 拋出異常cout 正在處理，

27、請稍候. endl;const unsigned long n = 256;/ 字符個數 char chn;/ 字符數組unsigned long wn;/ 字符出現(xiàn)頻度(權)unsigned long i, size = 0;char cha;for (i = 0; i n; i+)/ 初始化ch和wchi = (char)i;/ 初始化chiwi = 0;/ 初始化wirewind(infp);/ 使源文件指針指向文件開始處cha = fgetc(infp);/ 取出源文件第一個字符while (!feof(infp)/ 統(tǒng)計字符出現(xiàn)頻度w(unsigned char)cha+;/ 字符c

28、ha出現(xiàn)頻度自加size+;/ 文件大小自加cha=fgetc(infp);/ 取出源文件下一個字符if (pHuffmanTree != NULL) delete pHuffmanTree;/ 釋放空間pHuffmanTree = new HuffmanTree(ch, w, n); / 生成哈夫曼樹 rewind(outfp);/ 使目標文件指針指向文件開始處fwrite(&size, sizeof(unsigned long), 1, outfp);/ 向目標文件寫入源文件大小for (i = 0; i Encode(cha);/ 字符編碼for (i = 0; istrTmp.Leng

29、th(); i+)/ 向目標文件寫入編碼if (strTmpi = 0) Write(0);/ 向目標文件寫入else Write(1);/ 向目標文件寫入 cha = fgetc(infp);/ 取出源文件的下一個字符WriteToOutfp();/ 強行寫入目標文件fclose(infp); fclose(outfp);/ 關閉文件cout 處理結束. endl;void HuffmanCompress:Decompress()/ 操作結果：解壓縮用哈夫曼編碼壓縮的文件char infName256, outfName256;/ 輸入(壓縮)/出(目標)文件名cout infName; i

30、f (infp = fopen(infName, r+b) = NULL)throw Error(打開壓縮文件失敗!);/ 拋出異常 fgetc(infp);/ 取出壓縮文件第一個字符if (feof(infp)throw Error(壓縮文件為空!);/ 拋出異常cout outfName; if (outfp = fopen(outfName, w+b) = NULL)throw Error(打開目標文件失敗!);/ 拋出異常cout 正在處理，請稍候. endl;const unsigned long n = 256;/ 字符個數 char chn;/ 字符數組unsigned long

31、 wn;/ 權unsigned long i, size = 0;char cha;rewind(infp);/ 使源文件指針指向文件開始處fread(&size, sizeof(unsigned long), 1, infp);/ 讀取目標文件的大小for (i = 0; i n; i+)chi = (char)i;/ 初始化chifread(&wi, sizeof(unsigned long), 1, infp);/ 讀取字符頻度if (pHuffmanTree != NULL) delete pHuffmanTree;/ 釋放空間pHuffmanTree = new HuffmanTre

32、e(ch, w, n); / 生成哈夫曼樹unsigned long len = 0;/ 解壓的字符數cha = fgetc(infp);/ 取出源文件的第一個字符while (!feof(infp)/ 對壓縮文件字符進行解碼，并將解碼的字符寫入目標文件String strTmp = ;/ 將cha轉換二進制形式的串unsigned char c = (unsigned char)cha;/ 將cha轉換成unsigned char類型for (i = 0; i 8; i+)/ 將c轉換成二進制串if (c 128) Concat(strTmp, 0);/ 最高位為else Concat(st

33、rTmp, 1);/ 最高位為c = c 1;/ 左移一位LinkList lkText = pHuffmanTree-Decode(strTmp);/ 譯碼String strTemp(lkText);for (i = 1; i=strTemp.Length(); i+)/ 向目標文件寫入字符len+;/ 目標文件長度自加fputc(strTempi-1, outfp);/ 將字符寫入目標文件中if (len = size) break;/ 解壓完畢退出內循環(huán) if (len = size) break;/ 解壓完畢退出外循環(huán)cha = fgetc(infp);/ 取出源文件的下一個字符fc

34、lose(infp); fclose(outfp);/ 關閉文件cout 處理結束. endl;HuffmanCompress:HuffmanCompress(const HuffmanCompress ©)/ 操作結果：由哈夫曼壓縮類對象copy構造新哈夫曼壓縮類對象復制構造函數if (copy.pHuffmanTree != NULL)/ copy為非空哈夫曼壓縮類對象pHuffmanTree = new HuffmanTree(*copy.pHuffmanTree);/ 生成哈夫曼樹else pHuffmanTree = NULL;/ 生成空哈夫曼壓縮類對象HuffmanComp

35、ress &HuffmanCompress:operator=(const HuffmanCompress& copy)/ 操作結果：將哈夫曼壓縮類對象copy賦值給當前哈夫曼壓縮類對象賦值運算符if (© != this)if (pHuffmanTree != NULL) delete pHuffmanTree;/ 釋放空間if (copy.pHuffmanTree != NULL)/ copy為非空哈夫曼壓縮類對象pHuffmanTree = new HuffmanTree(*copy.pHuffmanTree);/ 生成哈夫曼樹else pHuffmanTree = NULL;/

36、 生成空哈夫曼壓縮類對象return *this;#endif#include utility.h/ 實用程序軟件包#include huffman_compress.h/ 哈夫曼壓縮算法int main(void) try/ 用try封裝可能出現(xiàn)異常的代碼HuffmanCompress obj;int select = 0;while (select != 3) cout endl 1. 壓縮;cout endl 2. 解壓;cout endl 3. 退出;cout endl select;/ 輸入選擇while (cin.get() != n);/ 忽略用戶輸入的其他字符switch (select)case 1: obj.Compress();/ 壓縮break;case 2:obj.Decompress();/ 解壓縮catch (Error err)/ 捕捉并處理異常err.Show();/ 顯示異常信息system(PAUSE); / 調用庫函數system()return 0; / 返回值, 返回操作系統(tǒng)3. 測試結果由于測試的文件字符太多，則就截下來一部分的壓縮后的編碼。下面的是壓縮過后的編碼截圖。下面為解壓后的文件截圖，解壓后與壓縮前的是一樣的。