平武建站

huffman的压缩原理和压缩过程-创新互联

压缩原因
1.文件太大，节省空间
2.提高数据在网络上传输的效率
3.对数据起到保护作用---加密
文件压缩类型
无损压缩：源文件被压缩之后，可以通过解压缩还原成与源文件相同的格式
有损压缩：源文件被压缩之后，解压缩无法还原成与源文件相同，但识别其内容没有影响，多用于语音，图片，视频压缩
基于Huffman树的压缩如何实现
通过Huffman编码实现，字符一般都是以字节存储的，通过编码转换为二进制编码（1字节=8比特位）
首先，什么是Huffman树
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
例如：给定权值为1（A）,3（B）,5（C）,7（D）四个节点，构建Huffman树
huffman的压缩原理和压缩过程
Huffman压缩原理--基于Huffman编码
以字符串中每个字符出现的次数为权值构建Huffman树
从根节点开始，左分支为0，右分支为1，如上图
所有权值节点都在叶子节点位置，遍历每条到叶子节点的路径获取字符的编码

创新互联建站10多年企业网站制作服务;为您提供网站建设,网站制作,网页设计及高端网站定制服务,企业网站制作及推广,对成都办公空间设计等多个方面拥有丰富的网站运维经验的网站建设公司。

举个栗子：ABBBCCCCCDDDDDDD
Huffman编码：
A:100
B:101
C:11
D:0

原理就是这么简单，一个字符占一个字节，现在用二进制编码代替之后，一个字符只占三位，也就是说一个字节可以表示两三个字符，所以说一次压缩，就会节省很多字节，也就起到了压缩的作用。
项目中最重要的是三点
创建Huffman树

1 先用权值创建n棵只有根节点的二叉树森林【意思是先创建n个节点】
2 选取根节点权值最小的二叉树构建新的二叉树【建小堆，新二叉树根节点权值为左右子树的根节点权值之和】【用到了priority_queue优先级队列】
3 删除使用的两棵根节点权值较小的二叉树
4 将新创建的二叉树添加到二叉树森林中
接下来2-4循环继续，直到二叉树森林中只有一棵二叉树则Huffman树创建成

文件压缩过程：

1读取源文件，读取源文件中每个字符出现的次数
2 以每个字符出现的次数作为权值，创建huffman树：小堆--优先级队列
3 通过huffman树找每个字符对应的编码
4 用每个字符的新编码重新对源文件进行改写【翻译的过程】

文件解压缩的过程：

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

写代码当中碰到的一些主要的问题，我将这些总结起来：

1.编译的时候：
刚开始写的时候测试发现如果压缩文件中出现了中文，程序就会崩溃，最后发现是数组越界的错误，因为如果只是字符，它的范围是-128~127，程序中使用char类型为数组下标(0~127)，所以字符没有问题. 但是汉字的编码是两个字节，所以可能会出现越界，

解决方法：就是将char类型强转为unsigned char，下标可表示范围为0~255.

2.解压缩的时候
有些特殊字符在处理需要注意一下，比如'\n'，我的程序中Getline()函数就是读取一行字符，但是若是该字符本身就是一个'\n'呢？ 这就非常的棘手了. 因为解压缩之后出现了乱码

解决方法：读取压缩文件时若读到了'\n',则说明该字符就是'\n'，应该继续读取它的次数

3.运行的时候：
发现文件篇幅很长的时候，只能压缩和解压缩一部分，是因为字符长度的设定太小

解决方法：_count长度设为unsigned long long类型

4.还有许多大大小小的问题等等
压缩率

文件类型源文件大小压缩后大小压缩率
word文档31.5KB32.1KB1.02
音频文件29.8 MB29.8MB0.99
视频文件20.7MB20.7MB0.99

另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。


名称栏目：huffman的压缩原理和压缩过程-创新互联
文章URL：http://pwwzsj.com/article/eipig.html

其他资讯