您的当前位置:首页正文

Deflate内部实现(LZ77无损压缩算法)超详细图解算法版~

2024-12-01 来源:个人技术集锦

概览

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

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

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

算法介绍

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

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

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

当对序列进行压缩的时候,采用 “滑动窗口” 算法,
结构如下:

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

要使用 LZ77 压缩算法:

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

举例

以微软的例子来理解算法:微软介绍:

显示全文