哈夫曼树解压与压缩

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.哈夫曼树的实现函数String EnCode(Char Type ch)：表示哈

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

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

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

5、ress()用哈夫曼编码压缩文件。函数Decompress()解压缩用哈夫曼编码压缩的文件。在主函数中有两个选项，一个是选择编码压缩，一个是解压。在函数中使用了文件输入输出流，我们可以选择要压缩的文件名输入，在选出压缩文件保存的地方和文件类型，将压缩所得到的文件存储在另一个文件中，解压也是如此。2. 源代码#ifndef _HUFFMAN_TREE_NODE_H_#define _HUFFMAN_TREE_NODE_H_/ 哈夫曼树结点类模板template <class WeightType>struct HuffmanTreeNodeWeightType weight;/ 权数

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

7、tChild = rightChild = 0;template <class WeightType>HuffmanTreeNode<WeightType>:HuffmanTreeNode(WeightType w, int p, int lChild, int rChild)/ 操作结果：构造一个权为w,双亲为p,左孩子为lChild,右孩子为rChild的结点weight = w;/ 权parent = p;/ 双亲leftChild = lChild;/ 左孩子rightChild = rChild;/ 右孩子#endif#ifndef _HUFFMAN_TREE

8、_H_#define _HUFFMAN_TREE_H_#include "string.h"/ 串类#include "huffman_tree_node.h"/ 哈夫曼树结点类模板/ 哈夫曼树类模板template <class CharType, class WeightType>class HuffmanTreeprotected:HuffmanTreeNode<WeightType> *nodes;/ 存储结点信息,nodes0未用CharType *LeafChars;/ 叶结点字符信息,LeafChars0未用Stri

9、ng *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);/ 由字符,权值和字符个数构造哈夫曼树public:/ 哈夫曼树方法声明及重载编译系统默认方法声明:HuffmanTree(Ch

10、arType ch, WeightType w, int n);/ 由字符,权值和字符个数构造哈夫曼树virtual HuffmanTree();/ 析构函数模板String Encode(CharType ch);/ 编码LinkList<CharType> Decode(String strCode);/ 译码HuffmanTree(const HuffmanTree<CharType, WeightType> &copy);/ 复制构造函数模板HuffmanTree<CharType, WeightType> &operator=(co

11、nst HuffmanTree<CharType, WeightType>& copy);/ 重载赋值运算符;/ 孩子兄弟表示哈夫曼树类模板的实现部分template <class CharType, class WeightType>void HuffmanTree<CharType, WeightType>:Select(int cur, int &r1, int &r2)/ 操作结果：nodes1 cur中选择双亲为,权值最小的两个结点r1,r2r1 = r2 = 0;/ 0表示空结点for (int pos = 1; pos

12、<= cur; pos+)/ 查找树值最小的两个结点if (nodespos.parent != 0) continue;/ 只处理双亲不为的结点if (r1 = 0)r1 = pos; / r1为空,将pos赋值给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; / nod

13、espos权值比nodesr2更小,将pos赋为r2template <class CharType, class WeightType>void HuffmanTree<CharType, WeightType>:CreatHuffmanTree(CharType ch, WeightType w, int n)/ 操作结果：由字符,权值和字符个数构造哈夫曼树num = n;/ 叶结点个数int m = 2 * n - 1;/ 结点个数nodes = new HuffmanTreeNode<WeightType>m + 1;/ nodes0未用LeafCh

14、ars = 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; pos+)/ 建立哈夫曼树int r1, r2;Select(pos - 1, r1, r2);/ nodes1 pos - 1中

15、选择双亲为,权值最小的两个结点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 = 1; pos <= n; pos+)/ 求n个叶结点字符的编码LinkList<char> charCode;

16、/ 暂存叶结点字符编码信息for (unsigned int child = pos, parent = nodeschild.parent; parent != 0; child = parent, parent = nodeschild.parent)/ 从叶结点到根结点逆向求编码if (nodesparent.leftChild = child) charCode.Insert(1, '0');/ 左分支编码为'0'else charCode.Insert(1, '1');/ 右分支编码为'1'LeafCharCodespo

17、s = charCode;/ charCode中存储字符编码curPos = m;/ 译码时从根结点开始,m为根template <class CharType, class WeightType>HuffmanTree<CharType, WeightType>:HuffmanTree(CharType ch, WeightType w, int n)/ 操作结果：由字符,权值和字符个数构造哈夫曼树CreatHuffmanTree(ch, w, n);/ 由字符,权值和字符个数构造哈夫曼树template <class CharType, class Weigh

18、tType>HuffmanTree<CharType, WeightType>:HuffmanTree()/ 操作结果：销毁哈夫曼树if (nodes != NULL) delete nodes;/ 释放结点信息if (LeafChars != NULL) delete LeafChars;/ 释放叶结点字符信息if (LeafCharCodes != NULL) delete LeafCharCodes;/ 释放叶结点字符编码信息template <class CharType, class WeightType>String HuffmanTree<Ch

19、arType, WeightType>:Encode(CharType ch)/ 操作结果：返回字符编码for (int pos = 1; pos <= num; pos+)/ 查找字符的位置if (LeafCharspos = ch) return LeafCharCodespos;/ 找到字符,得到编码throw Error("非法字符,无法编码!");/ 抛出异常template <class CharType, class WeightType>LinkList<CharType> HuffmanTree<CharType,

20、 WeightType>:Decode(String strCode)/ 操作结果：对编码串strCode进行译码,返回编码前的字符序列LinkList<CharType> charList;/ 编码前的字符序列for (int pos = 0; pos < strCode.Length(); pos+)/ 处理每位编码if (strCodepos = '0') curPos = nodescurPos.leftChild;/ '0'表示左分支else curPos = nodescurPos.rightChild;/ '1

21、9;表示左分支if (nodescurPos.leftChild = 0 && nodescurPos.rightChild = 0)/ 译码时从根结点到叶结点路径的当前结点为叶结点charList.Insert(charList.Length() + 1, LeafCharscurPos);curPos = 2 * num - 1;/ curPos回归根结点return charList;/ 返回编码前的字符序列template <class CharType, class WeightType>HuffmanTree<CharType, WeightTyp

22、e>:HuffmanTree(const HuffmanTree<CharType, WeightType> &copy)/ 操作结果：由哈夫曼树copy构造新哈夫曼树复制构造函数模板num = copy.num;/ 叶结点个数curPos = copy.curPos;/ 译码时从根结点到叶结点路径的当前结点int m = 2 * num - 1;/ 结点总数nodes = new HuffmanTreeNode<WeightType>m + 1;/ nodes0未用LeafChars = new CharTypenum + 1;/ LeafChars0未

23、用LeafCharCodes = new Stringnum + 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;/ 叶结点字符编码信息template <

24、class CharType, class WeightType>HuffmanTree<CharType, WeightType> &HuffmanTree<CharType, WeightType>:operator=(const HuffmanTree<CharType, WeightType>& copy)/ 操作结果：将哈夫曼树copy赋值给当前哈夫曼树重载赋值运算符if (&copy != this)if (nodes != NULL) delete nodes;/ 释放结点信息if (LeafChars != NU

25、LL) delete LeafChars;/ 释放叶结点字符信息if (LeafCharCodes != NULL) delete LeafCharCodes;/ 释放叶结点字符编码信息num = copy.num;/ 叶结点个数curPos = copy.curPos;/ 译码时从根结点到叶结点路径的当前结点int m = 2 * num - 1;/ 结点总数nodes = new HuffmanTreeNode<WeightType>m + 1;/ nodes0未用LeafChars = new CharTypenum + 1;/ LeafChars0未用LeafCharCod

26、es = new Stringnum + 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#ifnde

27、f _HUFFMAN_COMPRESS_H_#define _HUFFMAN_COMPRESS_H_#include "huffman_tree.h"/ 哈夫曼树类struct BufferType/ 字符缓存器char ch;/ 字符unsigned int bits;/ 实际比特数 ;class HuffmanCompress/ 哈夫曼压缩类protected:HuffmanTree<char, unsigned long> *pHuffmanTree;FILE *infp,*outfp;/ 输入/出文件BufferType buf;/ 字符缓存void W

28、rite(unsigned int bit);/ 向目标文件中写入一个比特void WriteToOutfp();/ 强行将字符缓存写入目标文件public:HuffmanCompress();/ 无参数的构造函数HuffmanCompress();/ 析构函数void Compress();/ 压缩算法void Decompress();/ 解压缩算法HuffmanCompress(const HuffmanCompress &copy);/ 复制构造函数HuffmanCompress &operator=(const HuffmanCompress& copy);/

29、 赋值运算符;HuffmanCompress:HuffmanCompress()pHuffmanTree = NULL;/ 空哈夫曼树HuffmanCompress:HuffmanCompress()if (pHuffmanTree != NULL) delete pHuffmanTree;/ 释放空间void HuffmanCompress:Write(unsigned int bit)/ 操作结果：向目标文件中写入一个比特buf.bits+;/ 缓存比特数自增buf.ch = (buf.ch << 1) | bit;/ 将bit加入到缓存字符中if (buf.bits = 8)

30、/ 缓存区已满,写入目标文件fputc(buf.ch, outfp);/ 写入目标文件buf.bits = 0;/ 初始化bitsbuf.ch = 0;/ 初始化chvoid HuffmanCompress:WriteToOutfp()/ 操作结果：强行将字符缓存写入目标文件unsigned int len = buf.bits;/ 缓存实际比特数if (len > 0)/ 缓存非空, 将缓存的比特个数增加到, 自动写入目标文件for (unsigned int i = 0; i < 8 - len; i+) Write(0);void HuffmanCompress:Compre

31、ss()/ 操作结果：用哈夫曼编码压缩文件char infName256, outfName256;/ 输入(源)/出(目标)文件名cout << "请输入源文件名(文件小于GB):"/ 被压缩文件小于GBcin >> infName;/ 输入源文件名if (infp = fopen(infName, "r+b") = NULL)throw Error("打开源文件失败!");/ 抛出异常 fgetc(infp);/ 取出源文件第一个字符if (feof(infp)throw Error("空源文件!

32、");/ 抛出异常cout << "请输入目标文件:"cin >> outfName; if (outfp = fopen(outfName, "w+b") = NULL)throw Error("打开目标文件失败!");/ 抛出异常cout << "正在处理，请稍候." << endl;const unsigned long n = 256;/ 字符个数 char chn;/ 字符数组unsigned long wn;/ 字符出现频度(权)unsigned

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

34、Tree;/ 释放空间pHuffmanTree = new HuffmanTree<char, unsigned long>(ch, w, n); / 生成哈夫曼树 rewind(outfp);/ 使目标文件指针指向文件开始处fwrite(&size, sizeof(unsigned long), 1, outfp);/ 向目标文件写入源文件大小for (i = 0; i < n; i+)/ 向目标文件写入字符出现频度fwrite(&wi, sizeof(unsigned long), 1, outfp);buf.bits = 0;/ 初始化bitsbuf.c

35、h = 0;/ 初始化chrewind(infp);/ 使源文件指针指向文件开始处cha = fgetc(infp);/ 取出源文件的第一个字符 while (!feof(infp)/ 对源文件字符进行编码，并将编码写入目标文件String strTmp = pHuffmanTree->Encode(cha);/ 字符编码for (i = 0; i<strTmp.Length(); i+)/ 向目标文件写入编码if (strTmpi = '0') Write(0);/ 向目标文件写入else Write(1);/ 向目标文件写入 cha = fgetc(infp);

36、/ 取出源文件的下一个字符WriteToOutfp();/ 强行写入目标文件fclose(infp); fclose(outfp);/ 关闭文件cout << "处理结束." << endl;void HuffmanCompress:Decompress()/ 操作结果：解压缩用哈夫曼编码压缩的文件char infName256, outfName256;/ 输入(压缩)/出(目标)文件名cout << "请输入压缩文件名:"cin >> infName; if (infp = fopen(infName,

37、 "r+b") = NULL)throw Error("打开压缩文件失败!");/ 抛出异常 fgetc(infp);/ 取出压缩文件第一个字符if (feof(infp)throw Error("压缩文件为空!");/ 抛出异常cout << "请输入目标文件名:"cin >> outfName; if (outfp = fopen(outfName, "w+b") = NULL)throw Error("打开目标文件失败!");/ 抛出异常cout

38、 << "正在处理，请稍候." << endl;const unsigned long n = 256;/ 字符个数 char chn;/ 字符数组unsigned long 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,

39、 sizeof(unsigned long), 1, infp);/ 读取字符频度if (pHuffmanTree != NULL) delete pHuffmanTree;/ 释放空间pHuffmanTree = new HuffmanTree<char, unsigned long>(ch, w, n); / 生成哈夫曼树unsigned long len = 0;/ 解压的字符数cha = fgetc(infp);/ 取出源文件的第一个字符while (!feof(infp)/ 对压缩文件字符进行解码，并将解码的字符写入目标文件String strTmp = "&q

40、uot;/ 将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(strTmp, "1");/ 最高位为c = c << 1;/ 左移一位LinkList<char> lkText = pHuffmanTree->Decode(strTmp);/ 译码String strTemp(lkText);for (i = 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 << "处理结束