哈夫曼樹解壓與壓縮.doc

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

1、哈夫曼樹的壓縮與解壓 1. 算法簡要描述 1.哈夫曼算法 1. 哈弗曼算法是根據(jù)給定的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)

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

3、一次產(chǎn)生的新結點就是哈夫曼樹的根結點。 源代碼中創(chuàng)建了一個哈夫曼樹結點類，其中有數(shù)據(jù)成員weight，parent，leftChild，rightChild分別代表了權值，雙親，左孩子，右孩子。 在哈夫曼樹類中有數(shù)據(jù)成員*nodes，*LeafChars，*LeafCharCodes，curPos，num，分別用來存儲結點信息，葉結點字符信息，葉結點字符編碼信息，譯碼時從根結點到葉結點路徑的當前結點，葉結點個數(shù)。哈夫曼樹類中含有多個函數(shù)，有構造函數(shù)，析構函數(shù)等。由函數(shù)HuffmanTree(CharType ch[],WeightType w[],int n)來構造由字符，權值，和字符個

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

5、ode)來求，對編碼串strCode進行譯碼，返回編碼前的字符序列。函數(shù)Compress()用哈夫曼編碼壓縮文件。函數(shù)Decompress()解壓縮用哈夫曼編碼壓縮的文件。 在主函數(shù)中有兩個選項，一個是選擇編碼壓縮，一個是解壓。在函數(shù)中使用了文件輸入輸出流，我們可以選擇要壓縮的文件名輸入，在選出壓縮文件保存的地方和文件類型，將壓縮所得到的文件存儲在另一個文件中，解壓也是如此。 2. 源代碼 #ifndef __HUFFMAN_TREE_NODE_H__ #define __HUFFMAN_TREE_NODE_H__ // 哈夫曼樹結點類模板 template

6、s WeightType> struct HuffmanTreeNode { WeightType weight; // 權數(shù)據(jù)域 unsigned int parent, leftChild, rightChild; // 雙親,左右孩子域 HuffmanTreeNode(); // 無參數(shù)的構造函數(shù)模板 HuffmanTreeNode(WeightType w, int p = 0, int lChild = 0, int rChild = 0); // 已知權,雙親及左右孩子構造結構 }; // 哈夫曼樹結點類模板的實現(xiàn)部分 tem

7、plate HuffmanTreeNode::HuffmanTreeNode()// 操作結果：構造空結點 { parent = leftChild = rightChild = 0; } template HuffmanTreeNode::HuffmanTreeNode(WeightType w, int p, int lChild, int rChild) // 操作結果：構造一個權為w,雙親為p,左孩子為lChild,右孩子為rChild的結點 {

8、 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

9、 CharType, class WeightType> class HuffmanTree { protected: HuffmanTreeNode *nodes; // 存儲結點信息,nodes[0]未用 CharType *LeafChars; // 葉結點字符信息,LeafChars[0]未用 String *LeafCharCodes; // 葉結點字符編碼信息,LeafCharCodes[0]未用 int curPos; // 譯碼時從根結點到葉結點路徑的當前結點 int num;

10、 // 葉結點個數(shù) // 輔助函數(shù)模板: void Select(int cur, int &r1, int &r2); // nodes[1 ~ cur]中選擇雙親為,權值最小的兩個結點r1,r2 void CreatHuffmanTree(CharType ch[], WeightType w[], int n); // 由字符,權值和字符個數(shù)構造哈夫曼樹 public: // 哈夫曼樹方法聲明及重載編譯系統(tǒng)默認方法聲明: HuffmanTree(CharType ch[], WeightType w[], int n); // 由字符,權值和字符個數(shù)構造哈夫曼樹

11、 virtual ~HuffmanTree(); // 析構函數(shù)模板 String Encode(CharType ch); // 編碼 LinkList Decode(String strCode); // 譯碼 HuffmanTree(const HuffmanTree ©); // 復制構造函數(shù)模板 HuffmanTree &operator=(const HuffmanTree& co

12、py); // 重載賦值運算符 }; // 孩子兄弟表示哈夫曼樹類模板的實現(xiàn)部分 template void HuffmanTree::Select(int cur, int &r1, int &r2) // 操作結果：nodes[1 ~ cur]中選擇雙親為,權值最小的兩個結點r1,r2 { r1 = r2 = 0; // 0表示空結點 for (int pos = 1; pos <= cur; pos++) { // 查找樹值最小

13、的兩個結點 if (nodes[pos].parent != 0) continue; // 只處理雙親不為的結點 if (r1 == 0) { r1 = pos; // r1為空,將pos賦值給r1 } else if (r2 == 0) { r2 = pos; // r2為空,將pos賦值給r2 } else if (nodes[pos].weight < nodes[r1].weight) { r1 = pos; // nodes[pos]權值比nodes[r1]更小,將pos賦為r1 } e

14、lse if (nodes[pos].weight < nodes[r2].weight) { r2 = pos; // nodes[pos]權值比nodes[r2]更小,將pos賦為r2 } } } template void HuffmanTree::CreatHuffmanTree(CharType ch[], WeightType w[], int n) // 操作結果：由字符,權值和字符個數(shù)構造哈夫曼樹 { num = n;

15、 // 葉結點個數(shù) int m = 2 * n - 1; // 結點個數(shù) nodes = new HuffmanTreeNode[m + 1]; // nodes[0]未用 LeafChars = new CharType[n + 1]; // LeafChars[0]未用 LeafCharCodes = new String[n + 1]; // LeafCharCodes[0]未用 int pos; // 臨時變量 for (pos = 1; pos <= n; pos++) { //

16、存儲葉結點信息 nodes[pos].weight = w[pos - 1]; // 權值 LeafChars[pos] = ch[pos - 1]; // 字符 } for (pos = n + 1; pos <= m; pos++) { // 建立哈夫曼樹 int r1, r2; Select(pos - 1, r1, r2); // nodes[1 ~ pos - 1]中選擇雙親為,權值最小的兩個結點r1,r2 // 合并以r1,r2為根的樹 nodes[r1].parent = nodes[r2].parent = pos;

17、// r1,r2雙親為pos nodes[pos].leftChild = r1; // r1為pos的左孩子 nodes[pos].rightChild = r2; // r2為pos的右孩子 nodes[pos].weight = nodes[r1].weight + nodes[r2].weight;//pos的權為r1,r2的權值之和 } for (pos = 1; pos <= n; pos++) { // 求n個葉結點字符的編碼 LinkList charCode; // 暫存葉結點字符編碼信息 for (u

18、nsigned int child = pos, parent = nodes[child].parent; parent != 0; child = parent, parent = nodes[child].parent) { // 從葉結點到根結點逆向求編碼 if (nodes[parent].leftChild == child) charCode.Insert(1, 0);// 左分支編碼為0 else charCode.Insert(1, 1); // 右分支編碼為1 } LeafCharCodes[pos] = charCode; /

19、/ charCode中存儲字符編碼 } curPos = m; // 譯碼時從根結點開始,m為根 } template HuffmanTree::HuffmanTree(CharType ch[], WeightType w[], int n) // 操作結果：由字符,權值和字符個數(shù)構造哈夫曼樹 { CreatHuffmanTree(ch, w, n); // 由字符,權值和字符個數(shù)構造哈夫曼樹 } template

20、arType, class WeightType> HuffmanTree::~HuffmanTree() // 操作結果：銷毀哈夫曼樹 { if (nodes != NULL) delete []nodes; // 釋放結點信息 if (LeafChars != NULL) delete []LeafChars; // 釋放葉結點字符信息 if (LeafCharCodes != NULL) delete []LeafCharCodes; // 釋放葉結點字符編碼信息 } template

21、Type, class WeightType> String HuffmanTree::Encode(CharType ch) // 操作結果：返回字符編碼 { for (int pos = 1; pos <= num; pos++) { // 查找字符的位置 if (LeafChars[pos] == ch) return LeafCharCodes[pos];// 找到字符,得到編碼 } throw Error("非法字符,無法編碼!"); // 拋出異常 } template

22、e, class WeightType> LinkList HuffmanTree::Decode(String strCode) // 操作結果：對編碼串strCode進行譯碼,返回編碼前的字符序列 { LinkList charList; // 編碼前的字符序列 for (int pos = 0; pos < strCode.Length(); pos++) { // 處理每位編碼 if (strCode[pos] == 0) curPos = nodes[curPo

23、s].leftChild; // 0表示左分支 else curPos = nodes[curPos].rightChild; // 1表示左分支 if (nodes[curPos].leftChild == 0 && nodes[curPos].rightChild == 0) { // 譯碼時從根結點到葉結點路徑的當前結點為葉結點 charList.Insert(charList.Length() + 1, LeafChars[curPos]); curPos = 2 * num - 1; // curPos回歸根結點 }

24、} return charList; // 返回編碼前的字符序列 } template HuffmanTree::HuffmanTree(const HuffmanTree ©) // 操作結果：由哈夫曼樹copy構造新哈夫曼樹——復制構造函數(shù)模板 { num = copy.num; // 葉結點個數(shù) curPos = copy.curPos; // 譯碼時從根結點

25、到葉結點路徑的當前結點 int m = 2 * num - 1; // 結點總數(shù) nodes = new HuffmanTreeNode[m + 1]; // nodes[0]未用 LeafChars = new CharType[num + 1]; // LeafChars[0]未用 LeafCharCodes = new String[num + 1]; // LeafCharCodes[0]未用 int pos; // 臨時變量 for (pos = 1; pos <= m; pos++) {

26、 // 復制結點信息 nodes[pos] = copy.nodes[pos]; // 結點信息 } for (pos = 1; pos <= num; pos++) { // 復制葉結點字符信息與葉結點字符編碼信息 LeafChars[pos] = copy.LeafChars[pos]; // 葉結點字符信息 LeafCharCodes[pos] = copy.LeafCharCodes[pos];// 葉結點字符編碼信息 } } template HuffmanTr

27、ee &HuffmanTree::operator=(const HuffmanTree& copy) // 操作結果：將哈夫曼樹copy賦值給當前哈夫曼樹——重載賦值運算符 { if (© != this) { if (nodes != NULL) delete []nodes; // 釋放結點信息 if (LeafChars != NULL) delete []LeafChars; // 釋放葉結點字符信息

28、if (LeafCharCodes != NULL) delete []LeafCharCodes; // 釋放葉結點字符編碼信息 num = copy.num; // 葉結點個數(shù) curPos = copy.curPos; // 譯碼時從根結點到葉結點路徑的當前結點 int m = 2 * num - 1; // 結點總數(shù) nodes = new HuffmanTreeNode[m + 1]; // nodes[0]未用 LeafChars = new CharType[num + 1]; // LeafCha

29、rs[0]未用 LeafCharCodes = new String[num + 1]; // LeafCharCodes[0]未用 int pos; // 臨時變量 for (pos = 1; pos <= m; pos++) { // 復制結點信息 nodes[pos] = copy.nodes[pos]; // 結點信息 } for (pos = 1; pos <= num; pos++) { // 復制葉結點字符信息與葉結點字符編碼信息 LeafChars[pos] = copy.LeafChars[

30、pos]; // 葉結點字符信息 LeafCharCodes[pos] = copy.LeafCharCodes[pos];// 葉結點字符編碼信息 } } return *this; } #endif #ifndef __HUFFMAN_COMPRESS_H__ #define __HUFFMAN_COMPRESS_H__ #include "huffman_tree.h" // 哈夫曼樹類 struct BufferType// 字符緩存器 { char ch; // 字符 unsigned int bits;

31、 // 實際比特數(shù) }; class HuffmanCompress// 哈夫曼壓縮類 { protected: HuffmanTree *pHuffmanTree; FILE *infp,*outfp; // 輸入/出文件 BufferType buf; // 字符緩存 void Write(unsigned int bit); // 向目標文件中寫入一個比特 void WriteToOutfp(); // 強行將字符緩存寫入目標文件 public: Huff

32、manCompress(); // 無參數(shù)的構造函數(shù) ~HuffmanCompress(); // 析構函數(shù) void Compress(); // 壓縮算法 void Decompress(); // 解壓縮算法 HuffmanCompress(const HuffmanCompress ©); // 復制構造函數(shù) HuffmanCompress &operator=(const HuffmanCompress& copy);// 賦值運算符 }; HuffmanCompress::HuffmanCompre

33、ss() { pHuffmanTree = NULL; // 空哈夫曼樹 } HuffmanCompress::~HuffmanCompress() { if (pHuffmanTree != NULL) delete []pHuffmanTree; // 釋放空間 } void HuffmanCompress::Write(unsigned int bit) // 操作結果：向目標文件中寫入一個比特 { buf.bits++; // 緩存比特數(shù)自增 buf.ch = (buf.ch << 1) | bit; // 將bi

34、t加入到緩存字符中 if (buf.bits == 8) { // 緩存區(qū)已滿,寫入目標文件 fputc(buf.ch, outfp); // 寫入目標文件 buf.bits = 0; // 初始化bits buf.ch = 0; // 初始化ch } } void HuffmanCompress::WriteToOutfp() // 操作結果：強行將字符緩存寫入目標文件 { unsigned int len = buf.bits; // 緩存實際比特數(shù) if (len > 0) { // 緩存非空, 將緩存的

35、比特個數(shù)增加到, 自動寫入目標文件 for (unsigned int i = 0; i < 8 - len; i++) Write(0); } } void HuffmanCompress::Compress()// 操作結果：用哈夫曼編碼壓縮文件 { char infName[256], outfName[256]; // 輸入(源)/出(目標)文件名 cout << "請輸入源文件名(文件小于GB):"; // 被壓縮文件小于GB cin >> infName; // 輸入源文件名 if ((infp = fopen(

36、infName, "r+b")) == NULL) throw Error("打開源文件失敗!"); // 拋出異常 fgetc(infp); // 取出源文件第一個字符 if (feof(infp)) throw Error("空源文件!"); // 拋出異常 cout << "請輸入目標文件:"; cin >> outfName; if ((outfp = fopen(outfName, "w+b")) == NULL) throw Error("打開目標文件失敗!");

37、 // 拋出異常 cout << "正在處理，請稍候..." << endl; const unsigned long n = 256; // 字符個數(shù) char ch[n]; // 字符數(shù)組 unsigned long w[n]; // 字符出現(xiàn)頻度(權) unsigned long i, size = 0; char cha; for (i = 0; i < n; i++) { // 初始化ch[]和w[] ch[i] = (char)i; // 初始化ch[i] w[i] = 0;

38、 // 初始化w[i] } rewind(infp); // 使源文件指針指向文件開始處 cha = fgetc(infp); // 取出源文件第一個字符 while (!feof(infp)) { // 統(tǒng)計字符出現(xiàn)頻度 w[(unsigned char)cha]++; // 字符cha出現(xiàn)頻度自加 size++; // 文件大小自加 cha=fgetc(infp); // 取出源文件下一個字符 } if (pHuffmanTree != NULL) delete []pHuffmanT

39、ree; // 釋放空間 pHuffmanTree = new HuffmanTree(ch, w, n); // 生成哈夫曼樹 rewind(outfp); // 使目標文件指針指向文件開始處 fwrite(&size, sizeof(unsigned long), 1, outfp); // 向目標文件寫入源文件大小 for (i = 0; i < n; i++) { // 向目標文件寫入字符出現(xiàn)頻度 fwrite(&w[i], sizeof(unsigned long), 1, outfp);

40、 } buf.bits = 0; // 初始化bits buf.ch = 0; // 初始化ch rewind(infp); // 使源文件指針指向文件開始處 cha = fgetc(infp); // 取出源文件的第一個字符 while (!feof(infp)) { // 對源文件字符進行編碼，并將編碼寫入目標文件 String strTmp = pHuffmanTree->Encode(cha);// 字符編碼 for (i = 0; i

41、件寫入編碼 if (strTmp[i] == 0) Write(0); // 向目標文件寫入 else Write(1); // 向目標文件寫入 } cha = fgetc(infp); // 取出源文件的下一個字符 } WriteToOutfp(); // 強行寫入目標文件 fclose(infp); fclose(outfp); // 關閉文件 cout << "處理結束." << endl; } void HuffmanCompress::Decompress()// 操作結果：解壓縮用哈夫曼編碼

42、壓縮的文件 { char infName[256], outfName[256]; // 輸入(壓縮)/出(目標)文件名 cout << "請輸入壓縮文件名:"; cin >> infName; if ((infp = fopen(infName, "r+b")) == NULL) throw Error("打開壓縮文件失敗!"); // 拋出異常 fgetc(infp); // 取出壓縮文件第一個字符 if (feof(infp)) throw Error("壓縮文件為空

43、!"); // 拋出異常 cout << "請輸入目標文件名:"; cin >> outfName; if ((outfp = fopen(outfName, "w+b")) == NULL) throw Error("打開目標文件失敗!"); // 拋出異常 cout << "正在處理，請稍候..." << endl; const unsigned long n = 256; // 字符個數(shù) char ch[n]; // 字符數(shù)組 unsigned long w[n];

44、 // 權 unsigned long i, size = 0; char cha; rewind(infp); // 使源文件指針指向文件開始處 fread(&size, sizeof(unsigned long), 1, infp); // 讀取目標文件的大小 for (i = 0; i < n; i++) { ch[i] = (char)i; // 初始化ch[i] fread(&w[i], sizeof(unsigned long), 1, infp); // 讀取字符頻度 } if (pHuf

45、fmanTree != NULL) delete []pHuffmanTree; // 釋放空間 pHuffmanTree = new HuffmanTree(ch, w, n); // 生成哈夫曼樹 unsigned long len = 0; // 解壓的字符數(shù) cha = fgetc(infp); // 取出源文件的第一個字符 while (!feof(infp)) { // 對壓縮文件字符進行解碼，并將解碼的字符寫入目標文件 String strTmp = ""; // 將cha

46、轉(zhuǎn)換二進制形式的串 unsigned char c = (unsigned char)cha; // 將cha轉(zhuǎn)換成unsigned char類型 for (i = 0; i < 8; i++) { // 將c轉(zhuǎn)換成二進制串 if (c < 128) Concat(strTmp, "0"); // 最高位為 else Concat(strTmp, "1"); // 最高位為 c = c << 1; // 左移一位 } LinkList lkText = pHuffmanTree->Decode(strTmp);/

47、/ 譯碼 String strTemp(lkText); for (i = 1; i<=strTemp.Length(); i++) { // 向目標文件寫入字符 len++; // 目標文件長度自加 fputc(strTemp[i-1], outfp); // 將字符寫入目標文件中 if (len == size) break; // 解壓完畢退出內(nèi)循環(huán) } if (len == size) break; // 解壓完畢退出外循環(huán) cha = fgetc(infp); // 取出源文件的下

48、一個字符 } fclose(infp); fclose(outfp); // 關閉文件 cout << "處理結束." << endl; } HuffmanCompress::HuffmanCompress(const HuffmanCompress ©) // 操作結果：由哈夫曼壓縮類對象copy構造新哈夫曼壓縮類對象——復制構造函數(shù) { if (copy.pHuffmanTree != NULL) { // copy為非空哈夫曼壓縮類對象 pHuffmanTree = new HuffmanTree

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

50、.pHuffmanTree != NULL) { // copy為非空哈夫曼壓縮類對象 pHuffmanTree = new HuffmanTree(*copy.pHuffmanTree); // 生成哈夫曼樹 } else pHuffmanTree = NULL; // 生成空哈夫曼壓縮類對象 } return *this; } #endif #include "utility.h" // 實用程序軟件包 #include "huffman_compress.h" // 哈夫曼壓縮算法 int ma

51、in(void) { try // 用try封裝可能出現(xiàn)異常的代碼 { HuffmanCompress obj; int select = 0; while (select != 3) { cout << endl << "1. 壓縮"; cout << endl << "2. 解壓"; cout << endl << "3. 退出"; cout << endl << "請選擇:"; cin >> select; // 輸入選擇 while (cin.get() != \n); /

52、/ 忽略用戶輸入的其他字符 switch (select) { case 1: obj.Compress(); // 壓縮 break; case 2: obj.Decompress(); // 解壓縮 } } } catch (Error err) // 捕捉并處理異常 { err.Show(); // 顯示異常信息 } system("PAUSE"); // 調(diào)用庫函數(shù)system() return 0; // 返回值, 返回操作系統(tǒng) } 3. 測試結果 由于測試的文件字符太多，則就截下來一部分的壓縮后的編碼。下面的是壓縮過后的編碼截圖。 下面為解壓后的文件截圖，解壓后與壓縮前的是一樣的。