当前位置：网站首页>【无标题】基于Huffman和LZ77的GZIP压缩

【无标题】基于Huffman和LZ77的GZIP压缩

2022-08-10 18:42:00 【你好,未来】

Huffman压缩
- Huffman树的概念和创建
  - 从二叉树的根结点到二叉树中所有叶结点的路径长度与相应权值的乘积之和为该二叉树的带权路径长度WPL。而我们将带权路径最小的二叉树称为huffman树。
  - 创建Huffman树的过程也是想当简单:将带创建的节点从小到大排序,每次拿出两个组成一个新节点重新放入集合中,依次类推,直到树中只剩一个节点,这就是Huffman树的根节点
- Huffman压缩的原理
  - 统计每个字符出现的频次,依据频次构建Huffman树
  - 从树的根节点往叶子节点走,路途中经历的数字就是Huffman编码
  - 为什么要使用Huffman树的形式计算每个字符的Huffman编码呢,因为Huffman树能保证出现次数最多的字符所分到的编码位数最小,在大文件下效率体现的会更明显
  - 根据每个字符对应的Huffman编码对文件内容进行改写就能得到压缩文件
  - 解压缩同样时通过读取压缩文件中字符出现的频次构建Huffman树把对应的bite位换成字符即可
LZ77压缩
- LZ77压缩算法时通过在前文中找和当前位置开始的字符串相同的最长的字符串,使用长度距离对表示当前字符
- 那么最小找多长,最大找多长,最小找多远,最大找多远
  - LZ77表示长度的大小为一个字节这样就限制了长度最大255,因为根据局部原理性,超过255长度的词语或者重复语句是很少出现的。即使出现用两个长度距离对即可表示,效率影响不是很大,如果用两个字节表示长度,因为长度超过255的很少,但是每个程度距离对中长度都多了一个字节表示,这是很影响效率的,
  - 距离为两个字节,距离最大65535,如果查找距离大于65535会影响查找的效率.
  - 因为长度距离对大小为3,所以当重复出现的字符长度达到三个就可以替换了
- lz77算法中读取信息涉及到一个窗口的概念。lz77在读取文件中的数据先将数据读到一个空间中，也就是我们的窗口中。窗口分为查找缓冲区和先行缓冲区
  - 先行缓冲区：查找指针指向的位置就是前向缓冲区的开始，随着指针向后移动，我们找当前指针指向的字符以及指针后面的字符在查找缓冲区中出现的最大长度。
  - 查找缓冲区：查找缓冲区就是我们已经查找过的区域，我们从查找缓冲区的开始来查找当前字符的匹配。（这里查找缓冲区大小为32K）
- LZ77采用哈希的方法查找前文中相同的字符串,因为最小匹配长度为三个字符串,所以采用三个字符一组插入插入哈希表
  - 既然字符串要映射成数字,就需要比较灵活切合适的哈希函数
    - 为了使哈希冲突尽可能的少，那么应当使每个字符都参与到哈希地址的计算当中，也就是2^24个哈希地址，而哈希表中用来存储地址的位置占两个字节，那么需要的哈希表大小就要32M。维护这么大的哈希表无疑会让程序的运行效率降低。所以这里哈希函数计算哈希哈希地址的时候让让三个字节的15个比特位来参与哈希地址的计算。那么也就是2^15个地址也就是32K。
  - 哈希表也采用类似窗口
    - 左边prev用来解决哈希冲突,右边用来存放哈希值
  - 存放哈希值和解决哈希冲突的过程
    - 第一个abc
    - 第二个abc
    - 第三个abc
    - 用上面的扫描abc的例子我们来说明：当第一次扫描到abc时，在3位置在哈希中存放的是0，所以在abc之前没有出现过abc，那么也就无法将第一个abc替换为长度距离对。当扫描到第二个abc的时候在哈希表中存放的是1，那么将当前3号空间中存放的1存放到prev空间中的10号位置，此时查看prev中的10位置存放的字符是否是0，这里10位置存放的1那么我们就匹配当前abc字符串后面的字符和1位置abc后面的字符，记录最长匹配长度。然后再查找prev1号位置存放地址是多少发现是0那么此次匹配结束。我们可以将当前abc字符替换为长度距离对。
  - 既然压缩是将字符串替换成长度距离对,那么如何区分元字符和长度距离对呢,采用标记为的形式进行标记,如果时源字符则对应的比特位位0,如果是长度则对应的bite位为1,解压缩时通过比特位信息区分
Huffman压缩和LZ77压缩的原理
- Huffman压缩就是对字符出现的次数进行统计，根据字符出现次数进行编码,多的字符编码位数较短，出现次数少的字符编码位数较长。然后对文件中的每个字符使用编码进行改写,形成压缩文件。解码时使用每个字符出现的次数重新计算Huffman编码,再进行还原
- LZ77就是把文本中当前字符串用前文出现过的相同的字符串的长度和到当前的距离替换，用长度距离对来表示重复出现的字符串，然后再解压缩的时候遇到长度距离对通过长度距离对来在前文中查找字符串。LZ77需要使用标志位来分辨程度距离对
GZIP压缩的原理
- GZIP压缩算法是LZ77压缩和Huffman压缩结合的压缩算法
- 那么在LZ77压缩之后直接使用Huffman压缩吗?答案是肯定可以,但是效率不高
  - 直接采用Huffman压LZ77的结果存在的问题
    - a.LZ77之后，有接近1/8的大小是标记为，如果直接采用Huffman的方式压缩LZ77的结果，标记为也会参与之后，有接近1/8的大小是标记位，如果直接采用Huffman的方式压缩LZ77的结果，标记位也会参与,
    - b.LZ77之后，压缩文件的结果也会非常大(256个字符加随机长度(最多256个)和随机距离(最大65535))，直接交给huffman压缩，可能会导致huffman树非常高，可能就会导致平均每个字节的编码超过8个比特位，就会导致压缩结果变大或者压缩结果不理想之后，压缩文件的结果也会非常大，直接交给Huffman压缩，可能会导致Huffman树非常高，可能就会导致平均每个字节的编码超过8个比特位，就会导致压缩结果变大或者压缩结果不理想
  - 传统Huffman在GZIP中存在的问题
    - 直接采用huffman树压缩，最终再压缩文件中需要保存解压缩的字节出现的频次信息，这些数据保存到压缩结果中也是非常大的,会影响压缩效率
- GZIP中LZ77和Huffman的改进
  - 传统的Lz77的压缩结果是字符和长度距离对写在一个文件里,标记信息在另一个文件里,但是LZ77的压缩结果需要用Huffman压缩,所以首先需要保存LZ77的结果保存在数组里.把源字符和长度保存在一起,把距离和标记文件单独保存以便后续Huffman压缩解决Huffman树大的问题
  - 通过把LZ77结果的源字符和长度放在一起构建Huffman树,把距离单独构建Huffman树.
  - 怎么能不使用标记位区分源字符和长度距离呢:长度往后偏移257,用来和源字符区分,这样解压缩出超过256的,我们就能知道他是长度,然后读取一个距离就可以了.元字符和长度中间的256用来标记一个块是否结束,在统计一个块中字符信息时会给256对应的出现次数加1,使得256也拥有自己对应的编码,当一个块压缩完后再把256压进去,解压缩到256说明一个块结束
  - 解决Huffman树大的问题:长度和距离对应的数字还是太大,所以对长度和距离表示的范围进行分组,只对分组的编号进行压缩,就能大大解决Huffman树大的问题
    - 把距离距离也分成30个组,这样距离对应的Huffman树就只有30个节点,Huffman树就足够小了,压缩真正距离的时候,找到对应的分组编号,压缩编号和真正距离到区间起始的偏移量,偏移量的比特位个数要满足表格中的Extra列
    - 同样把长度分成29个组,和距离的压缩方式一样,先压缩编号,在压缩偏移量,这个Huffman树中最多就只有256+1+29=286个节点
  - 解决传统Huffman压缩结果中保存字符对应频次信息:采用范式Huffman树,不用保存字符和字符的频次信息,而是只保存对应的编码位长即可->字符长度树只需要保存286个字节,距离树只需要保存30个字节(没有出现的保存0)
    - 范式Huffman树和传统Huffman树的区别:普通Huffman树需要压缩和解压缩都需要通过构建Huffman树获取Huffman编码,范式Huffman树只需要压缩是创建树,得到编码位长,解压缩时只使用编码位长信息通过计算就能得到每个字符对应的编码
    - 如何计算编码位长:将上述普通的Huffman编码通过以编码位长为第一字段,以符号为第二字段进行排序就能得到范式Huffman树,相同编码位长的字符处在同一层,编码位长的大小代表层数
    - 计算规则:
      - 某一层的首位编码=（上一层的首编码+上层的节点个数)<<本层和上层层数差
      - 同一层的编码是通过上一个编码+1得到
- 所以GZIP压缩的流程为
  - 1.使用LZ77保存在vector中的压缩结果,构造GZIP的频次信息,分别保存到GZIP的长度和距离结果中
  - 2.创建Huffman树
  - 3.通过Huffman树获取长度和距离对应的编码位长
  - 4.用长度和距离对应的编码位长计算编码
  - 5.写入解压用到的编码位长信息
  - 6.通过LZ77压缩结果中标记位的信息,对LZ77的压缩结果进行改写
  - 7.压一个256表示块结束
- 解压流程
  - 1.读取文件前286+30个字节,分别对应长度和距离的编码位长,保存起来
  - 2.使用编码位长生成解码表,把保存的编码位长以编码位长为第一字段,字符为第二字段生成符号位长表
  - 3.解码(之前所说的不用构建Huffman树就能解码的方法)
    - 以下过程循环
    - a.获取一个字符
      - 1.在压缩文件中获取和解码表第i行编码位长等长的比特信息.i=0;
      - 2.将读取的数据和第i行的首编码相减结果假设为num,
      - 如果num>=第i行的符号数量再将从压缩文件中获取到和第i+1行编码长度相等bite,循环上去再判断
      - 如过<,则num+当前符号索引就是在符号位长表中的下标
      - 例如，输入数据“11110”。令i = 0，此时编码位长为2。读取2位的数据“11”与首编码相减等于3。3大于等于符号数量，于是i = i + 1等于1。此时编码位长为3。读取3位的数据“111”与首编码相减等于1。1大于等于符号数量，于是i = i + 1等于2。此时编码位长为5。读取5位的数据“11110”与首编码相减等于2。2小于符号数量，2加符号索引4等于6。从表2.3中可以查到序号为6的符号是“E”。从而解码出符号“E”。跳过当前已经解码的5位数据，可以重新开始解码下一个符号。
    - b.判断字符是长度还是距离,还是块结束标记位
      - 1.如果在0~255范围内,则是字符直接写入文件
      - 2.如果是256,块结束标志位,结束循环
      - 3.如果>256,是长度,长度包含起始长度和偏移量,再解压距离,距离也包含起始距离和偏移量.有了长度距离对,在前面解压出来的数据中找就行了
- 分块技术
  - GZIP是通过Huffman压缩LZ77的结果,所以要是等LZ77压缩完再使用Huffman效率就底了,所以将LZ77压缩一部分就交给Huffman压缩
  - 在压缩统计频次信息时会给256也统计一次,目的时能让256也参与到获取Huffman编码中,每个块在压缩结束时会压入一个256,解压缩时如果解析到256,说明一个块结束了
  - 在每个压缩文件的第一个字节会写一个标记位:标记LZ77的压缩结果是不是最后一个块
GZIP压缩总流程
源码:yf1228/Linux - Gitee.com