哈夫曼树解压与压缩

《哈夫曼树解压与压缩》由会员分享，可在线阅读，更多相关《哈夫曼树解压与压缩（14页珍藏版）》请在装配图网上搜索。

1、word哈夫曼树的压缩与解压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中只含有一颗二叉树为止。函数String EnCode(Char Type ch)：表示哈夫曼树已存在，返回字符c

2、h的编码。函数LinkListUnCode(String strCode)：表示对哈夫曼树进行译码，返回编码前的字符序列。根据算法可以看出，在具有n个结点权值的哈夫曼树的构造过程中 ，每次都是从F中删去两棵树，增加一棵树，即每次结束后减少一棵树，经过n-1次处理后，F中就只剩下一棵树了。另外，每次合并都要产生一个新的结点，合并n-1次后共产生了n-1个新结点，并且这n-1个新节点都是具有左右子树的分支结点。则最终得到的哈夫曼树中共有2n-1个结点，并且其中没有度为1的分支结点，最后一次产生的新结点就是哈夫曼树的根结点。源代码中创建了一个哈夫曼树结点类，其中有数据成员weight，parent，

3、leftChild，rightChild分别代表了权值，双亲，左孩子，右孩子。在哈夫曼树类中有数据成员*nodes，*LeafChars，*LeafCharCodes，curPos，num，分别用来存储结点信息，叶结点字符信息，叶结点字符编码信息，译码时从根结点到叶结点路径的当前结点，叶结点个数。哈夫曼树类中含有多个函数，有构造函数，析构函数等。由函数HuffmanTree(CharType ch,WeightType w,int n)来构造由字符，权值，和字符个数构造哈夫曼树，在根据哈夫曼算法很容易实现哈夫曼类的函数以及构造函数。在在算法中，求叶结点字符的编码时，需要从叶结点出发走一条从高叶

4、结点到根结点的路径，而编码却是从根结点出发到叶结点的路径，由左分支为编码0，右分支为编码1，得到的编码，因此从叶结点出发到根结点的路径得到的编码是实际编码的逆序，并且编码长度不确定，又由于可以再线性链表中构造串，因此将编码的信息储存在一个线性立案标准，每得到一位编码都将其插入在线性链表的最前面。在求某个字符的编码是由函数EnCode(CharType ch)来求，返回字符编码。在进行译码时，用一个线性链表存储字符序列，由函数Decode(String strCode)来求，对编码串strCode进行译码，返回编码前的字符序列。函数press()用哈夫曼编码压缩文件。函数Depress()解压缩

5、用哈夫曼编码压缩的文件。在主函数中有两个选项，一个是选择编码压缩，一个是解压。在函数中使用了文件输入输出流，我们可以选择要压缩的文件名输入，在选出压缩文件保存的地方和文件类型，将压缩所得到的文件存储在另一个文件中，解压也是如此。2. 源代码#ifndef _HUFFMAN_TREE_NODE_H_#define _HUFFMAN_TREE_NODE_H_/ 哈夫曼树结点类模板template struct HuffmanTreeNodeWeightType weight;/ 权数据域unsignedint parent, leftChild, rightChild;/ 双亲,左右孩子域Huff

6、manTreeNode();/ 无参数的构造函数模板HuffmanTreeNode(WeightType w, int p = 0, int lChild = 0, int rChild = 0);/ 已知权,双亲及左右孩子构造结构;/ 哈夫曼树结点类模板的实现部分template HuffmanTreeNode:HuffmanTreeNode()/ 操作结果：构造空结点parent = leftChild = rightChild = 0;template HuffmanTreeNode:HuffmanTreeNode(WeightType w, int p, int lChild, int

7、 rChild)/ 操作结果：构造一个权为w,双亲为p,左孩子为lChild,右孩子为rChild的结点weight = w;/ 权parent = p;/ 双亲leftChild = lChild;/ 左孩子rightChild = rChild;/ 右孩子#endif#ifndef _HUFFMAN_TREE_H_#define _HUFFMAN_TREE_H_#includestring.h/ 串类#includehuffman_tree_node.h/ 哈夫曼树结点类模板/ 哈夫曼树类模板template class HuffmanTreeprotected:HuffmanTreeNo

8、de *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, WeightType w, int n)

9、;/ 由字符,权值和字符个数构造哈夫曼树public:/ 哈夫曼树方法声明及重载编译系统默认方法声明:HuffmanTree(CharType ch, WeightType w, int n);/ 由字符,权值和字符个数构造哈夫曼树virtual HuffmanTree();/ 析构函数模板String Encode(CharType ch);/ 编码LinkList Decode(String strCode);/ 译码HuffmanTree(const HuffmanTree ©);/ 复制构造函数模板HuffmanTree &operator=(const HuffmanTree

10、& copy);/ 重载赋值运算符;/ 孩子兄弟表示哈夫曼树类模板的实现部分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为空,将pos赋值给r1elseif (r2 = 0

11、)r2 = pos; / r2为空,将pos赋值给r2elseif(nodespos.weight nodesr1.weight)r1 = pos; / nodespos权值比nodesr1更小,将pos赋为r1elseif (nodespos.weight nodesr2.weight)r2 = pos; / nodespos权值比nodesr2更小,将pos赋为r2template void HuffmanTree:CreatHuffmanTree(CharType ch, WeightType w, int n)/ 操作结果：由字符,权值和字符个数构造哈夫曼树num = n;/ 叶结点个

12、数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;/ 字符for (pos = n + 1; pos = m;

13、 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;/pos的权为r1,r2的权值之和for (pos

14、= 1; pos = n; pos+)/ 求n个叶结点字符的编码LinkList charCode;/ 暂存叶结点字符编码信息for (unsignedint child = pos, parent = nodeschild.parent; parent != 0; child = parent, parent = nodeschild.parent)/ 从叶结点到根结点逆向求编码if (nodesparent.leftChild = child) charCode.Insert(1, 0);/ 左分支编码为0else charCode.Insert(1, 1);/ 右分支编码为1LeafCh

15、arCodespos = 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 nodes;/ 释放结点信息if (LeafChar

16、s != 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(非法字符,无法编码!);/ 抛出异常template

17、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 (nodescurPos.leftChild = 0 & nodescu

18、rPos.rightChild = 0)/ 译码时从根结点到叶结点路径的当前结点为叶结点charList.Insert(charList.Length() + 1, LeafCharscurPos);curPos = 2 * num - 1;/ curPos回归根结点return charList;/ 返回编码前的字符序列template HuffmanTree:HuffmanTree(const HuffmanTree ©)/ 操作结果：由哈夫曼树copy构造新哈夫曼树复制构造函数模板num = copy.num;/ 叶结点个数curPos = copy.curPos;/ 译码时从根

19、结点到叶结点路径的当前结点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; pos = num; pos+)/ 复制叶结点字符

20、信息与叶结点字符编码信息LeafCharspos = copy.LeafCharspos;/ 叶结点字符信息LeafCharCodespos = copy.LeafCharCodespos;/ 叶结点字符编码信息template HuffmanTree &HuffmanTree:operator=(const HuffmanTree& copy)/ 操作结果：将哈夫曼树copy赋值给当前哈夫曼树重载赋值运算符if (© != this)if (nodes != NULL) delete nodes;/ 释放结点信息if (LeafChars != NULL) delete LeafCh

21、ars;/ 释放叶结点字符信息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 Stringnum + 1;/ LeafCharCo

22、des0未用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_PRESS_H_#define _HUFFMAN_PRESS_H

23、_#includehuffman_tree.h/ 哈夫曼树类struct BufferType/ 字符缓存器char ch;/ 字符unsignedint bits;/ 实际比特数;class Huffmanpress/ 哈夫曼压缩类protected:HuffmanTree *pHuffmanTree;FILE *infp,*outfp;/ 输入/出文件BufferType buf;/ 字符缓存void Write(unsignedint bit);/ 向目标文件中写入一个比特void WriteToOutfp();/ 强行将字符缓存写入目标文件public:Huffmanpress();/

24、 无参数的构造函数Huffmanpress();/ 析构函数void press();/ 压缩算法void Depress();/ 解压缩算法Huffmanpress(const Huffmanpress ©);/ 复制构造函数Huffmanpress &operator=(const Huffmanpress& copy);/ 赋值运算符;Huffmanpress:Huffmanpress()pHuffmanTree = NULL;/ 空哈夫曼树Huffmanpress:Huffmanpress()if (pHuffmanTree != NULL) delete pHuffmanTr

25、ee;/ 释放空间void Huffmanpress:Write(unsignedint bit)/ 操作结果：向目标文件中写入一个比特buf.bits+;/ 缓存比特数自增buf.ch = (buf.ch 0)/ 缓存非空, 将缓存的比特个数增加到, 自动写入目标文件for (unsignedint i = 0; i 8 - len; i+) Write(0);void Huffmanpress:press()/ 操作结果：用哈夫曼编码压缩文件char infName256, outfName256;/ 输入(源)/出(目标)文件名cout infName;/ 输入源文件名if (infp

26、= 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;constunsignedlong n = 256;/ 字符个数char chn;/ 字符数组unsignedlong wn;/ 字符出现频度(权)u

27、nsignedlong 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)/ 统计字符出现频度w(unsignedchar)cha+;/ 字符cha出现频度自加size+;/ 文件大小自加cha=fgetc(infp);/ 取出源文件下一个字符if (pHuffmanTree != NULL) delete pHuffman

28、Tree;/ 释放空间pHuffmanTree = new HuffmanTree(ch, w, n); / 生成哈夫曼树 rewind(outfp);/ 使目标文件指针指向文件开始处fwrite(&size, sizeof(unsignedlong), 1, outfp);/ 向目标文件写入源文件大小for (i = 0; i Encode(cha);/ 字符编码for (i = 0; istrTmp.Length(); i+)/ 向目标文件写入编码if (strTmpi = 0) Write(0);/ 向目标文件写入else Write(1);/ 向目标文件写入 cha = fgetc(i

29、nfp);/ 取出源文件的下一个字符WriteToOutfp();/ 强行写入目标文件fclose(infp); fclose(outfp);/ 关闭文件cout 处理结束. endl;void Huffmanpress:Depress()/ 操作结果：解压缩用哈夫曼编码压缩的文件char infName256, outfName256;/ 输入(压缩)/出(目标)文件名cout infName; if (infp = fopen(infName, r+b) = NULL)throw Error(打开压缩文件失败!);/ 抛出异常 fgetc(infp);/ 取出压缩文件第一个字符if (fe

30、of(infp)throw Error(压缩文件为空!);/ 抛出异常cout outfName; if (outfp = fopen(outfName, w+b) = NULL)throw Error(打开目标文件失败!);/ 抛出异常cout 正在处理，请稍候. endl;constunsignedlong n = 256;/ 字符个数char chn;/ 字符数组unsignedlong wn;/ 权unsignedlong i, size = 0;char cha;rewind(infp);/ 使源文件指针指向文件开始处fread(&size, sizeof(unsignedlong)

31、, 1, infp);/ 读取目标文件的大小for (i = 0; i n; i+)chi = (char)i;/ 初始化chifread(&wi, sizeof(unsignedlong), 1, infp);/ 读取字符频度if (pHuffmanTree != NULL) delete pHuffmanTree;/ 释放空间pHuffmanTree = new HuffmanTree(ch, w, n); / 生成哈夫曼树unsignedlong len = 0;/ 解压的字符数cha = fgetc(infp);/ 取出源文件的第一个字符while (!feof(infp)/ 对压缩文

32、件字符进行解码，并将解码的字符写入目标文件String strTmp = ;/ 将cha转换二进制形式的串unsignedchar c = (unsignedchar)cha;/ 将cha转换成unsigned char类型for (i = 0; i 8; i+)/ 将c转换成二进制串if (c 128) Concat(strTmp, 0);/ 最高位为else Concat(strTmp, 1);/ 最高位为c = c 1;/ 左移一位LinkList lkText = pHuffmanTree-Decode(strTmp);/ 译码String strTemp(lkText);for (i

33、 = 1; i=strTemp.Length(); i+)/ 向目标文件写入字符len+;/ 目标文件长度自加fputc(strTempi-1, outfp);/ 将字符写入目标文件中if (len = size) break;/ 解压完毕退出循环 if (len = size) break;/ 解压完毕退出外循环cha = fgetc(infp);/ 取出源文件的下一个字符fclose(infp); fclose(outfp);/ 关闭文件cout 处理结束. endl;Huffmanpress:Huffmanpress(const Huffmanpress ©)/ 操作结果：由哈夫

34、曼压缩类对象copy构造新哈夫曼压缩类对象复制构造函数if (copy.pHuffmanTree != NULL)/ copy为非空哈夫曼压缩类对象pHuffmanTree = new HuffmanTree(*copy.pHuffmanTree);/ 生成哈夫曼树else pHuffmanTree = NULL;/ 生成空哈夫曼压缩类对象Huffmanpress &Huffmanpress:operator=(const Huffmanpress& copy)/ 操作结果：将哈夫曼压缩类对象copy赋值给当前哈夫曼压缩类对象赋值运算符if (© != this)if (pHuffma

35、nTree != NULL) delete pHuffmanTree;/ 释放空间if (copy.pHuffmanTree != NULL)/ copy为非空哈夫曼压缩类对象pHuffmanTree = new HuffmanTree(*copy.pHuffmanTree);/ 生成哈夫曼树else pHuffmanTree = NULL;/ 生成空哈夫曼压缩类对象return *this;#endif#includeutility.h/ 实用程序软件包#includehuffman_press.h/ 哈夫曼压缩算法int main(void)try/ 用try封装可能出现异常的代码Huff

36、manpress 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.press();/ 压缩break;case 2:obj.Depress();/ 解压缩catch (Error err)/ 捕捉并处理异常err.Show();/ 显示异常信息system(PAUSE); / 调用库函数system()return 0; / 返回值, 返回操作系统3. 测试结果由于测试的文件字符太多，则就截下来一部分的压缩后的编码。下面的是压缩过后的编码截图。下面为解压后的文件截图，解压后与压缩前的是一样的。14 / 14