你的浏览器还没开启 Javascript 功能!

GZip(二)压缩算法LZ77

GZip(二)压缩算法LZ77

LZ77算法是无损压缩算法,由以色列人Abraham Lempel发表于1977年。LZ77是典型的基于字典的压缩算法,现在很多压缩技术都是基于LZ77。

前言

LZ77算法的核心:数据重复结构 信息进行压缩。举个例子,如:

what’s you name ? my name is jack, and you ?

nameyou,这些单词(字符串),都重复出现过,为了指明出现的位置,我们需要定义一个相对位置。

what’s you name ? my (|||) name is jack, and you ?

so:我们先这样定义

P = “what’s you name ? my”
N = “name is jack, and you ?”

相对位置(|||)之后的字符串 N 为 name is jack, and you ?,如果可以匹配之前的字符串 P ,则替换 N 中的字符串为 P 中的字符串起始坐标;如果没有匹配上,则不做处理。结果如下:

what’s you name ? my (|||) name is jack, and you ?

N 中 字符串 name 匹配上了 P 中第12-15单词(从1开始算),所以用下标替换:

what’s you name ? my (|||) (P[12-15]) is jack, and you ?

之后我们再处理 you 等字符,最终得到的 N:

N = [(12-15), (is jack, and )(8-10), ( ?)]]

以上就是用索引值来表示出现过的字符串,来达到压缩的目的。LZ77核心思想亦是如此,而真正的压缩过程做了更多处理。

那怎么不处理问号和空格啊?LZ77算法如果处理3个长度以下的字符反而会增加复杂度,想想为什么?

压缩算法原理

关于LZ77算法性质,本文只做探究和摘抄,其逻辑证明请参考论文。

介绍

首先介绍用到的专业术语:

  • lookahead buffer:待编码区
  • search buff:搜索缓冲区
  • 滑动窗口:指定大小的窗,包含“搜索缓冲区”(左) + “待编码区”(右)

主要步骤为:  

  1. 设置编码位置为输入流的开始  
  2. 在滑窗的待编码区查找搜索区中的最大匹配字符串  
  3. 如果找到字符串,输出(偏移值, 匹配长度), 窗口向前滑动“匹配长度”  
  4. 如果没有找到,输出(0, 0, 待编码区的第一个字符),窗口向前滑动一个单位
  5. 如果待编码区不为空,回到步骤2
实例

现在有字符串“AABCBBABC”,现在对其进行编码。

一开始,窗口滑入如图位置

由图可见,待编码缓冲区有“AAB”三个字符,此时搜索缓冲区还是空的。所以编码第一个字符,由于搜索区为空,故找不到匹配串,输出(0,0, A),窗口右移一个单位,如下图

此时待编码区有“ABC”。开始编码。最先编码”A”,在搜索区找到”A”。由于没有超过待编码区,故开始编码”AB”,但在搜索区没有找到匹配字符串,故无法编码。因此只能编码”A”。输出(1, 1)。即为相对于待编码区,偏移一个单位,匹配长度为1。窗口右滑动匹配长度,即移动1个单位。如下图

一样,没找到,输出(0, 0, B),右移1个单号,如下图

输出(0, 0, C),右移1个单位,如下图

输出(2, 1),右移1个单位,如下图

输出(3, 1), 右移1个单位,如下图

开始编码”A”,在搜索缓冲区查找到匹配字符串。由于待编码缓冲区没有超过,继续编码。开始编码”AB”,也搜索到。不要停止,继续编码“ABC”,找到匹配字符串。由于继续编码,则超过了窗口,故只编码“ABC”,输出(5, 3),偏移5,长度3。右移3个单位,如下图

此时待编码缓冲区为空,停止编码。  
最终输出结果如下

参考文章:

【数据压缩】LZ77算法原理及实现
LZ77压缩算法编码原理详解(结合图片和简单代码)