本文共 2069 字，大约阅读时间需要 6 分钟。
文章目录
前言
Huffman树在数据结构的时候都了解过，由Huffman树可以生成huffman编码，而Huffman编码在解决文件压缩问题的时候还是一个比较经典的算法。
Huffman树 ？
定义：Huffman树，又称最优二叉树，是加权路径长度最短的二叉树
生成Huffman树
假设有这样一组权值 1，3，5，7，Huffman树构建过程如下：
生成Huffman编码
Huffman树中左子树路径标为0，右子树路径标为1。从根节点到叶子节点经过的路径的组合即为该叶子节点的编码
Huffman编码压缩的原理
1. 统计待压缩文件中每个字符出现的次数
- 构建一个结构体，存放信息：字符，次数，编码
- 遍历源文件，将每个字符的次数写入对应的结构体信息中
2. 将次数作为权值构建Huffman树
- 采用优先级队列，但优先级队列是大的元素在前面，所以要自行更改一下
- 普通的二叉树只能通过父结点找子节点，但在获取编码的时候需要通过叶子节点往根节点走，所以构建二叉树时，要有孩子结点指向父结点
3. 通过Huffman数获取每个字符所对应的编码
- 通过叶子节点找根节点是编码是逆序的，所以要reverse
4. 向压缩文件中写入信息
- 压缩文件中不仅仅要存放编码信息
- 第一行：存放原文件的后缀，因为在解压缩文件的时候会用到
- 第二行：存放原文件字符的个数n（叶子节点）
- 接下来的n行：字符，次数（为了解压缩重建Huffman树）
- 接下来才是压缩编码
例如：原文件名为“1.txt”，存放ABBBCCCCCDDDDDDD“”
则：压缩文件中存放：
解压缩
1. 获取后缀 2. 获取字符以及对应的次数 3. 重建Huffman树 4. 解压压缩数据
a. 从压缩文件中读取一个字节ch
b. 从根节点开始，按照ch的8个比特位信息从高到低遍历huffman树：
- 该比特位是0，取当前节点的左孩子，否则取右孩子
- 直到遍历到叶子节点位置，该字符就被解析成功，将解压出的字符写入文件
- 如果在遍历huffman过程中，8个比特位已经比较完毕还没有到达叶子节点，从a开始执行
c. 重复以上过程，直到所有的数据解析完毕。
遇到的问题
1. 只压缩字母时成功，压缩文字会崩溃？
那是因为刚开始创建存放信息的数据是char类型的，当文件中有文字时，一个文字占两个字节，并且每个字节的范围是128~255，如果是char类型，数组的下标就会变成负数，数字越界了， 需要将存放信息的数据类型变为unsigned char
2. 为什么存放文字时依然可以找到，不会冲突？
一个字节有八个bit位，那么范围也就是0~255，如果文字的第一个字节为65，岂不是和‘A’冲突了。实际上不存在，因为文字的每个字节的范围是128~256， 所以不会发生冲突。
3. 解压大文件时只能解压一部分？？
-
首先检查压缩后的文件是否正常（可以使用UE）
-
将压缩文件采用二进制显示， 发现存在好几个FF
-
一般情况下，文件指针碰到EOF就表示到文件结尾了，因为EOF是 -1，也就是FF，所以只解压了一部分（解压到第一个FF就停止了）
-
采用 feof()函数，多加一个判断即可，feof()函数就是判断文件末尾，而不仅仅是碰见EOF停止
4. 关于位运算操作
因为在压缩和解压的过程中都用到的位操作，需注意：位操作针对的是每一个bit位，一个字节有8个bit位，在循环到从0~7的时候一定要记得清0
5. 为什么压缩照片的时候会失败？
我自己刚开始在压缩大文件的时候（包含文字）没有任何的问题，但是一旦压缩、解压照片就会出问题。经过几番调试，终于发现是因为 ‘\0’ 的问题,因为如果刚开始把（字节，次数）先写入 buf 中，再由 buf 通过 fwrite 函数写入文件中，一定会出现问题（可能出现 0 字节）。因为 fwrite 的第一个参数要求C格式的字符串，把 buf 转化为C格式的字符串，如果遇见 ‘\0’，就会停止，所以就会崩溃。不要将字节写入 buf 中，而是通过 fputc 直接把字节写入文件中，然后再把 （, 次数）写入 buf 中，再将buf写入文件即可。
注意：buf 一定要定义在循环内，因为每次都要重新往 buf 中写入内容，或者手动把 buf 清空
for (size_t i = 0; i < 256; i++) { if (info[i]._chCount != 0) { string buf; //buf中存放 ，次数 fputc(info[i]._ch, fOut);//必须先把ch放进去，如果把ch作为string的字符最后转换为C的字符，会导致'\0'没有处理 buf = ','; _itoa(info[i]._chCount, countStr, 10); buf += countStr; fputs(buf.c_str(), fOut); fputc('\n', fOut); } } 源码
转载地址：http://fcwdb.baihongyu.com/