Deflate内部实现（LZ77无损压缩算法）超详细图解算法版～

无损压缩算法

• 第一阶段：重复消除 — LZ77无损压缩算法
• • 算法介绍
  • • 举例
    • 压缩算法思路
    • 图解压缩过程
    • 第二阶段：位减少
    • • huffman
      • 位减少

        概览

        • Gzip
          • Deflate 编码（LZ77+哈夫曼）
          • Brotli
            • LZ77+哈夫曼+二阶上下文建模

              Deflate 分两个阶段压缩数据：重复消除和位减少

              第一阶段：重复消除 — LZ77无损压缩算法

              算法介绍

              基于字典的无损压缩算法，它搜索重复的未压缩序列并用引用指针替换它们。

              引用指针由 2 个元素定义：

              • offset距离（或偏移量）：原始未压缩数据中出现的第一个现有字节的相对返回。
              • Length：重复的字节长度。

                当对序列进行压缩的时候，采用 “滑动窗口” 算法，

                结构如下：

                • 查找缓冲区（Search buffer），也称字典（已编码部分）
                • 先行缓冲区（Look ahead buffer），包括即将进行编码序列的一部分。每次读取数据的时候，先把一部分数据预载入前向缓冲区。为移入滑动窗口做准备。

                  由于缓冲区具有固定的长度，所以，当算法（编码器）在运行时候，它看起来像在文件中“滑动”，所以这个缓冲区被称为“滑动窗口”。
                  

                  滑动窗的尺寸是影响压缩性能的关键因素之一。如果滑动窗口太小，则压缩器可能会发现较少的重复数据序列，结果，压缩文件的大小将更大。如果滑动窗口太大，则压缩器可能需要花费更长的时间来查找重复的数据序列，因此压缩速度将变慢。

                  要使用 LZ77 压缩算法：

                  1. 将编码位置设置为输入流的开头。
                  2. 在查找缓冲区的窗口中找到最长的匹配项。
                  3. 如果找到匹配，则输出指针 P。将编码位置（和窗口）向前移动 L个字节。
                  4. 如果未找到匹配项，则输出空指针和先行缓冲区中的第一个字节。将编码位置（和窗口）向前移动一个字节。
                  5. 如果先行缓冲区不为空，则返回步骤 2。

                  主要逻辑 ：

                  通过先行缓冲区预读取数据，然后向字典中移入， 不断搜索字典中与先行缓冲区连续相匹配的最长序列，然后输出metadata标记。

                  举例

                  以微软的例子来理解算法：微软介绍：LZ77压缩算法

                  Input stream

                  Position    1    2    3    4    5    6    7    8    9
                  Byte        A    A    B    C    B    B    A    B    C
                  

                  Output 期望压缩后得到的结果：

                  压缩后怎么能读取到原文呢？
                  

                  答：需要将output进行解码，如：

                  （0，0）‘X’：直接推入X

                  （o，l）：找到offset=o的位置，往后复制l个字符

                  看来最重要的一环就是如何压缩啦！让我们一起看看这个算法的思路和图解吧～

                  压缩算法思路

                  AABCBBABC串，将重复的子串用指针进行替换，

                  对于其中的每个元素 x 有两种情况：

                       1. 前文没有任何重复的子串：输出（0，0）x

                       2. 在前文能找到重复的子串：输出（offset = x和匹配子串的的距离，length = 匹配子串的长度）

                  图解压缩过程

                  字符序列移动方向：从右往左
                  

                  简称：

                  • buffer区：先行缓存区（未编码），这是需要匹配的字符串
                  • Dictionary：查找缓存区（已编码），用来匹配buffer的字典区域

                  1. 初始字符串从右往左滑动，直至占满所有buffer区，如图1

                                     （图1）

                  2. 开始遍历 图1 buffer的第一个字符’A’，因Dictionary空，未匹配到’A’ => 往左移一格（如图2），输出(0,0)A。

                     （offset = A无匹配子串，距离=0，length：0，无重复子串）                （图2）

                  3. 遍历 图3 buffer第一个字符"A"，在Dictionary找到"A"，未超过buffer黄色长度，往后遍历到编码"AB"，Dictionary没有匹配到“AB”字符串，于是只编码"A"，输出(1, 1)。

                                     （图3）
                     

                     如 图4，匹配长度为1，所以字符串向左偏移一个单位：

                                     （图4）

                  4. 匹配buffer区第一个字符’B’，Dictionary内未匹配，同步骤1，输出(0,0)B，左移一格。

                  5. 匹配buffer区第一个字符’C’，Dictionary内未匹配，同上，输出(0,0)C，左移一格，如 图5 ：

                                     （图5）

                  6. 匹配 图6 buffer区第一个字符’B’，offset（'B’与Dictionary中匹配的’B’的距离）=2，两个查找指针同时往后移1（如图6），比较'C'vs'B'不匹配，终止，length=1，输出（2，1）

                                     （图6）
                     

                     得到结果：

                                     （图7）

                  7. 匹配 图7 buffer区第一个字符’B’，Dictionary匹配到‘B’，分别是offset=1和offset=3，但offset=3下一字节'C'vs'A'不匹配，就近原则选择offset=1，length=1，输出（1，1）。

                                     （图8）

                     此时已编码序列长度大于Dictionary区，有序列滑出了窗口，如图8。

                  8. 匹配 图8 BUFFER第一个字符 ‘A’，在DICTIONARY匹配到，offset=5，往后遍历直到匹配"ABC"，length=3，此时不能再往后编码否则超过BUFFER区域长度，故输出(5, 3)，往左移动3格，如图：

                  第二阶段：位减少

                  huffman

                  通过哈夫曼树，我们可以将原本需要120bit（15*8）的位减少到 28bit

                  位减少

                  范式huffman树：在普通huffman树的基础上只要保存编码位长，利用位长反推编码