基于哈夫曼树的文件压缩项目 - 行业资讯 - 肥雀云

<强>压缩原因
1。文件太大,节省空间
2。提高数据在网络上传输的效率
3。对数据起到保护作用- - - - - -加密
<强>文件压缩类型
无损压缩:源文件被压缩之后,可以通过解压缩还原成与源文件相同的格式
有损压缩:源文件被压缩之后,解压缩无法还原成与源文件相同,但识别其内容没有影响,多用于语音、图片,视频压缩
<>强基于哈夫曼树的压缩如何实现
通过霍夫曼编码实现,字符一般都是以字节存储的,通过编码转换为二进制编码(1字节=8比特位)
<强>首先,什么是霍夫曼树
给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
例如:给定权值为1 (A), 3 (B)、5 (C), 7 (D)四个节点,构建霍夫曼树
$基于哈夫曼树的文件压缩项目”> <强>霍夫曼压缩原理</强>——基于霍夫曼编码 以字符串中每个字符出现的次数为权值构建霍夫曼树 从根节点开始,左分支为0,右分支为1,如上图 所有权值节点都在叶子节点位置,遍历每条到叶子节点的路径获取字符的编码 　　<blockquote> 　　举个栗子:ABBBCCCCCDDDDDDD 霍夫曼编码: : 100 B: 101 C: 11 D: 0 　　</引用> 　　原理就是这么简单,一个字符占一个字节,现在用二进制编码代替之后,一个字符只占三位,也就是说一个字节可以表示两三个字符,所以说一次压缩,就会节省很多字节,也就起到了压缩的作用。 <强>项目中最重要的是三点</强> 创建霍夫曼树 　　<blockquote> 　　 1先用权值创建n棵只有根节点的二叉树森林【意思是先创建n个节点】 2选取根节点权值最小的二叉树构建新的二叉树【建小堆,新二叉树根节点权值为左右子树的根节点权值之和】【用到了priority_queue优先级队列】 3删除使用的两棵根节点权值较小的二叉树 4将新创建的二叉树添加到二叉树森林中 接下来2 - 4循环继续,直到二叉树森林中只有一棵二叉树则霍夫曼树创建成 　　</引用> 　　文件压缩过程: 　　<blockquote> 　　<pre> <代码> 1读取源文件,读取源文件中每个字符出现的次数　　2以每个字符出现的次数作为权值,创建哈夫曼树:小堆,优先级队列　　3通过霍夫曼树找每个字符对应的编码　　4用每个字符的新编码重新对源文件进行改写【翻译的过程】</代码> </pre> 　　</引用> 　　文件解压缩的过程: 　　<blockquote> 　　<ol> 　　<李>从压缩文件中获取源文件的后缀李</> 　　<李>从压缩文件中获取字符次数的总行数</李> 　　<李>获取每个字符出现的次数</李> 　　<李>重建霍夫曼树李</> 　　<李>解压压缩数据 。从压缩文件中读取一个字节的获取压缩数据ch b。从根节点开始,按照ch的8个比特位信息从高到低遍历哈夫曼树:该比特位是0,取当前节点的左孩子,否则取右孩子,直到遍历到叶子节点位置,该字符就被解析成功,将解压出的字符写入文件,如果在遍历霍夫曼过程中,8个比特位已经比较完毕还没有到达叶子节点,从一开始执行 c。重复以上过程,直到所有的数据解析完毕。</李> 　　</ol> 　　</引用> 　　写代码当中碰到的一些主要的问题,我将这些总结起来: 　　<blockquote> 　　 1。编译的时候: 刚开始写的时候测试发现如果压缩文件中出现了中文,程序就会崩溃,最后发现是数组越界的错误,因为如果只是字符,它的范围是-128 ~ 127年,程序中使用char类型为数组下标(0 ~ 127),所以字符没有问题。但是汉字的编码是两个字节,所以可能会出现越界, 　　</引用> 　　 解决方法:就是将<强>字符类型强转为无符号字符</>强,下标可表示范围为0 ~ 255。 　　<blockquote> 　　 2。解压缩的时候 有些特殊字符在处理需要注意一下,比如' \ n ',我的程序中Getline()函数就是读取一行字符,但是若是该字符本身就是一个“\ n”呢?这就非常的棘手了。因为解压缩之后出现了乱码 　　</引用> 　　 解决方法:读取压缩文件时若读到了' \ n ',则说明该字符就是“\ n”,应该继续读取它的次数 　　<blockquote> 　　 3。运行的时候: 发现文件篇幅很长的时候,只能压缩和解压缩一部分,是因为字符长度的设定太小<h2 class=$ 基于哈夫曼树的文件压缩项目