C++ Huffman树实现文件的压缩与解压

拼搏现实的明天。 2022-03-17 10:10 290阅读 0赞

### 文章目录 ###

*   *  前言
     *  Huffman树 ？
     *  生成Huffman树
     *  生成Huffman编码
     *  Huffman编码压缩的原理
     *  解压缩
     *  遇到的问题
     *   *   *  1. 只压缩字母时成功，压缩文字会崩溃？
             *  2. 为什么存放文字时依然可以找到，不会冲突？
             *  3. 解压大文件时只能解压一部分？？
             *  4. 关于位运算操作
             *  5. 为什么压缩照片的时候会失败？
     *  源码

## 前言 ##

Huffman树在数据结构的时候都了解过，由Huffman树可以生成huffman编码，而Huffman编码在解决文件压缩问题的时候还是一个比较经典的算法。

## Huffman树 ？ ##

**定义：Huffman树，又称最优二叉树，是加权路径长度最短的二叉树**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70]

## 生成Huffman树 ##

假设有这样一组权值 1，3，5，7，Huffman树构建过程如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 1]

## 生成Huffman编码 ##

Huffman树中左子树路径标为0，右子树路径标为1。从根节点到叶子节点经过的路径的组合即为该叶子节点的编码  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 2]

## Huffman编码压缩的原理 ##

1. 统计待压缩文件中每个字符出现的次数

*  构建一个结构体，存放信息：字符，次数，编码
 *  遍历源文件，将每个字符的次数写入对应的结构体信息中

2. 将次数作为权值构建Huffman树

*  采用优先级队列，但优先级队列是大的元素在前面，所以要自行更改一下
 *  普通的二叉树只能通过父结点找子节点，但在获取编码的时候需要通过叶子节点往根节点走，所以构建二叉树时，要有孩子结点指向父结点

3. 通过Huffman数获取每个字符所对应的编码

*  通过叶子节点找根节点是编码是逆序的，所以要reverse

4. 向压缩文件中写入信息

*  压缩文件中不仅仅要存放编码信息
 *  第一行：存放原文件的后缀，因为在解压缩文件的时候会用到
 *  第二行：存放原文件字符的个数n（叶子节点）
 *  接下来的n行：字符，次数（为了解压缩重建Huffman树）
 *  接下来才是压缩编码

例如：原文件名为“1.txt”，存放ABBBCCCCCDDDDDDD“”  
则：压缩文件中存放：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 3][]

## 解压缩 ##

1. 获取后缀  
2. 获取字符以及对应的次数  
3. 重建Huffman树  
4. 解压压缩数据

> a. 从压缩文件中读取一个字节ch  
> b. 从根节点开始，按照ch的8个比特位信息从高到低遍历huﬀman树：
> 
>  *  该比特位是0，取当前节点的左孩子，否则取右孩子
>  *  直到遍历到叶子节点位置，该字符就被解析成功，将解压出的字符写入文件
>  *  如果在遍历huﬀman过程中，8个比特位已经比较完毕还没有到达叶子节点，从a开始执行
> 
> c. 重复以上过程，直到所有的数据解析完毕。

## 遇到的问题 ##

#### 1. 只压缩字母时成功，压缩文字会崩溃？ ####

那是因为刚开始创建存放信息的数据是char类型的，当文件中有文字时，一个文字占两个字节，并且每个字节的范围是128~255，如果是char类型，数组的下标就会变成负数，数字越界了， 需要将存放信息的数据类型变为unsigned char

#### 2. 为什么存放文字时依然可以找到，不会冲突？ ####

一个字节有八个bit位，那么范围也就是0~255，如果文字的第一个字节为65，岂不是和‘A’冲突了。实际上不存在，因为文字的每个字节的范围是128~256， 所以不会发生冲突。

#### 3. 解压大文件时只能解压一部分？？ ####

1.  首先检查压缩后的文件是否正常（可以使用UE）
2.  将压缩文件采用二进制显示， 发现存在好几个FF
3.  一般情况下，文件指针碰到EOF就表示到文件结尾了，因为EOF是 -1，也就是FF，所以只解压了一部分（解压到第一个FF就停止了）
4.  采用 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);
    		}
    	}

## 源码 ##

[源码][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70]: /images/20220317/f9df4ec9a9a74a7485fc67990465b7ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 1]: /images/20220317/8ada9e8eea9048209d4045f391e4ee95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 2]: /images/20220317/58c6f5582ba541ee9276f21e4011aff9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 3]: /images/20220317/69c5e221430145b59f409f3ec7c46307.png
[Link 1]: https://github.com/1792114384/Project/tree/master/FileCompressHuffman