文档章节

图解LZ77压缩算法

wier
 wier
发布于 2017/08/01 09:48
字数 1581
阅读 4100
收藏 139

数据压缩是一个减小数据存储空间的过程,目前被应用在软件工程的各个地方,了解其一些原理,方便我们更好的甄选压缩方案。

压缩方案有很多种,常见的就是有损和无损压缩。霍夫曼编码和LZ77(Lempel-Ziv-1977)都是无损压缩,其中霍夫曼是采用最小冗余编码的算法进行压缩,而LZ77是采用字典的方式进行压缩。关于霍夫曼编码的算法,网上有很多对其详细的讲解,我们本篇幅不在细说,主要图解一下LZ77压缩算法的方式,看看其有哪些优缺点。

本篇主要内容如下:

  1. 信息熵
  2. LZ77算法原理
  3. 压缩过程
  4. 解压过程
  5. 优缺点

 

信息熵

数据为何是可以压缩的,因为数据都会表现出一定的特性,称为熵。绝大多数的数据所表现出来的容量往往大于其熵所建议的最佳容量。比如所有的数据都会有一定的冗余性,我们可以把冗余的数据采用更少的位对频繁出现的字符进行标记,也可以基于数据的一些特性基于字典编码,代替重复多余的短语。

 

LZ77算法原理

LZ77压缩算法采用字典的方式进行压缩,是一个简单但十分高效的数据压缩算法。其方式就是把数据中一些可以组织成短语(最长字符)的字符加入字典,然后再有相同字符出现采用标记来代替字典中的短语,如此通过标记代替多数重复出现的方式以进行压缩。要理解这种算法,我们先了解3个关键词:短语字典,滑动窗口和向前缓冲区。

关键词:

前向缓冲区

每次读取数据的时候,先把一部分数据预载入前向缓冲区。为移入滑动窗口做准备

 

滑动窗口

一旦数据通过缓冲区,那么它将移动到滑动窗口中,并变成字典的一部分。

 

短语字典

从字符序列S1...Sn,组成n个短语。比如字符(A,B,D) ,可以组合的短语为{(A),(A,B),(A,B,D),(B),(B,D),(D)},如果这些字符在滑动窗口里面,就可以记为当前的短语字典,因为滑动窗口不断的向前滑动,所以短语字典也是不断的变化。

 

LZ77的主要算法逻辑就是,先通过前向缓冲区预读数据,然后再向滑动窗口移入(滑动窗口有一定的长度),不断的寻找能与字典中短语匹配的最长短语,然后通过标记符标记。我们还以字符ABD为例子,看如下图:

目前从前向缓冲区中可以和滑动窗口中可以匹配的最长短语就是(A,B),然后向前移动的时候再次遇到(A,B)的时候采用标记符代替。

 

压缩

当压缩数据的时候,前向缓冲区与移动窗口之间在做短语匹配的是后会存在2种情况:

  1. 找不到匹配时:将未匹配的符号编码成符号标记(多数都是字符本身)
  2. 找到匹配时:将其最长的匹配编码成短语标记。
  3. 短语标记包含三部分信息:(滑动窗口中的偏移量(从匹配开始的地方计算)、匹配中的符号个数、匹配结束后的前向缓冲区中的第一个符号)。

 

一旦把n个符号编码并生成响应的标记,就将这n个符号从滑动窗口的一端移出,并用前向缓冲区中同样数量的符号来代替它们,如此,滑动窗口中始终有最新的短语。

我们采用图例来看:

 

1、开始

2、滑动窗口中没有数据,所以没有匹配到短语,将字符A标记为A

3、滑动窗口中有A,没有从缓冲区中字符(BABC)中匹配到短语,依然把B标记为B

4、缓冲区字符(ABCB)在滑动窗口的位移6位置找到AB,成功匹配到短语AB,将AB编码为(6,2,C)

5、缓冲区字符(BABA)在滑动窗口位移4的位置匹配到短语BAB,将BAB编码为(4,3,A)

6、缓冲区字符(BCAD)在滑动窗口位移2的位置匹配到短语BC,将BC编码为(2,2,A)

7、缓冲区字符D,在滑动窗口中没有找到匹配短语,标记为D

8、缓冲区中没有数据进入了,结束

 

解压

解压类似于压缩的逆向过程,通过解码标记和保持滑动窗口中的符号来更新解压数据。

当解码字符标记:将标记编码成字符拷贝到滑动窗口中

解码短语标记:在滑动窗口中查找响应偏移量,同时找到指定长短的短语进行替换。

 

我们还是采用图例来看下:

1、开始

2、符号标记A解码

3、符号标记B解码

4、短语标记(6,2,C)解码

5、短语标记(4,3,A)解码

6、短语标记(2,2,A)解码

7、符号标记D解码

 

优缺点

大多数情况下LZ77压缩算法的压缩比相当高,当然了也和你选择滑动窗口大小,以及前向缓冲区大小,以及数据熵有关系。其压缩过程是比较耗时的,因为要花费很多时间寻找滑动窗口中的短语匹配,不过解压过程会很快,因为每个标记都明确告知在哪个位置可以读取了。

 

-----------------------------------------------------------------------------

想看更多有趣原创的技术文章,扫描关注公众号。

关注个人成长和游戏研发,推动国内游戏社区的成长与进步。

© 著作权归作者所有

共有 人打赏支持
wier
粉丝 746
博文 50
码字总数 134184
作品 0
东城
技术主管
加载中

评论(7)

哈库纳
哈库纳
讲的生动,且言简意赅。
谁偷了我的名字
谁偷了我的名字
感谢分享 希望有一天我看得懂 惭愧
wier
wier

引用来自“开源中国首席辣条代理”的评论

学习了,虽然学会了也没什么用。。。 :)
基础知识很重要,有应用场景会更重要
开源中国首席辣条代理
开源中国首席辣条代理
学习了,虽然学会了也没什么用。。。 :)
简约_bolin
简约_bolin
解释的简单移动,没基础的也看明白了。
netkiller-
netkiller-
羡慕,从毕业后,就没有开发过二进制处理的程序,全字符串处理。都忘了位移,异或怎么用了。
Feng_Yu
Feng_Yu
图解不错。当年学数据结构的时候,讲过LZW算法,对照着文字和伪代码在理解LZW,十分生涩
数据压缩算法---LZ77算法 的分析与实现

原文出处:IDreamo LZ77简介 Ziv和Lempel于1977年发表题为“顺序数据压缩的一个通用算法(A Universal Algorithm for Sequential Data Compression )”的论文,论文中描述的算法被后人称为L...

IDreamo
07/17
0
0
简单聊聊 GZIP 的压缩原理与日常应用

前言 在基于 HTTP 协议的网络传输中 GZip 经常被使用,Nginx 中也可以使用半行代码开启 GZip。GZip 压缩的原理是什么呢?本篇文章是我在网上阅读了一些文档后做的简单总结。 从 RFC 1952 看起...

rccoder
08/19
0
0
几个常见的压缩算法

再学习了haffman算法之后发现压缩算法很有意思,上网查了点资料,这是做好的一篇(主要是我能理解)。前面几种都能看懂,关键是那个LZ77算法。这个是很强大的压缩算法,zip,rar用得都是这种...

JavaGG
2009/10/23
53.5K
3
无损压缩算法--Brotli

Brotli 是一个通用目的的无损压缩算法,它通过用变种的 LZ77 算法,Huffman 编码和二阶文本建模进行数据压缩,是一种压缩比很高的压缩方法。在压缩速度上跟 Deflate 差不多,但是提供了更密集...

孔小菜
2015/04/24
3.6K
0
压缩与归档

 压缩与归档,这是两种不同的概念,其用途也不一样,压缩是通过压缩算法对文件进行压缩,其体积会根据算法减少;归档则是将文件打包,相当与给文件加了个“盒子”,体积还有可能增大。  压...

JyingHZ
01/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

可爱的python测试开发库(python测试开发工具库汇总)

欢迎转载,转载请注明来源: github地址 谢谢点赞 本文地址 相关书籍下载 测试开发 Web UI测试自动化 splinter - web UI测试工具,基于selnium封装。 链接 selenium - web UI自动化测试。 链...

python测试开发人工智能安全
55分钟前
2
0
Shiro | 实现权限验证完整版

写在前面的话 提及权限,就会想到安全,是一个十分棘手的话题。这里只是作为学校Shiro的一个记录,而不是,权限就应该这样设计之类的。 Shiro框架 1、Shiro是基于Apache开源的强大灵活的开源...

冯文议
今天
1
0
linux 系统的运行级别

运行级别 运行级别 | 含义 0 关机 1 单用户模式,可以想象为windows 的安全模式,主要用于修复系统 2 不完全的命令模式,不含NFS服务 3 完全的命令行模式,就是标准的字符界面 4 系统保留 5 ...

Linux学习笔记
今天
2
0
学习设计模式——命令模式

任何模式的出现,都是为了解决一些特定的场景的耦合问题,以达到对修改封闭,对扩展开放的效果。命令模式也不例外: 命令模式是为了解决命令的请求者和命令的实现者之间的耦合关系。 解决了这...

江左煤郎
今天
3
0
字典树收集(非线程安全,后续做线程安全改进)

将500W个单词放进一个数据结构进行存储,然后进行快速比对,判断一个单词是不是这个500W单词之中的;来了一个单词前缀,给出500w个单词中有多少个单词是该前缀. 1、这个需求首先需要设计好数据结...

算法之名
昨天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部