文档章节

图解LZ77压缩算法

wier
 wier
发布于 2017/08/01 09:48
字数 1581
阅读 3881
收藏 139
点赞 16
评论 7

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

压缩方案有很多种,常见的就是有损和无损压缩。霍夫曼编码和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
粉丝 658
博文 46
码字总数 122193
作品 0
东城
高级程序员
加载中

评论(7)

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

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

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

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

JavaGG ⋅ 2009/10/23 ⋅ 3

无损压缩算法--Brotli

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

孔小菜 ⋅ 2015/04/24 ⋅ 0

压缩与归档

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

JyingHZ ⋅ 01/08 ⋅ 0

李景枫/compress

Compress 目录 [TOC] 开源产品介绍(微服务基础设施QQ交流群:191958521) 配置中心(mconf) GITHUB:https://github.com/yu120/mconf 码云:https://git.oschina.net/yu120/mconf 微核心(mi...

李景枫 ⋅ 2017/04/23 ⋅ 0

能不能在这里发一些开源的java的压缩算法的实现

例如lz77算法的java实现,lzw算法的java实现。。。等。 还要j2me平台上的压缩方法

azi ⋅ 2009/06/20 ⋅ 1

【整理】HTTP 协议中的压缩问题

公司因业务需要,要求实现 REST API 的 HTTP 客户端支持 gzip 压缩。那么首先需要回答下面几个问题: gzip 压缩和其他压缩方式有什么不同?或者说优劣在哪里? HTTP 协议中对压缩方式的常规支...

摩云飞 ⋅ 2013/07/05 ⋅ 4

Brotli 压缩算法 Android 库--Brotli-android

Brotli 压缩算法 Android 库。 Brotli 是一个通用的无损压缩算法,它使用了 LZ77 算法的现代变体、Huffman 编码和二阶上下文建模的结合来压缩数据,因而有着媲美当前任何现代通用压缩算法高的...

WolfCS ⋅ 2017/05/25 ⋅ 0

从零开始手敲次世代游戏引擎(PNG特别篇)

在从零开始手敲次世代游戏引擎(三十五)当中我们完成了衣裙贴图的加载和绘制。但是所谓画龙点睛,我们的模型目前仍然是没有👀的。之所以这样,因为眼睛的贴图是PNG格式的,而目前我们只写...

陈文礼 ⋅ 2017/12/23 ⋅ 0

PNG图片文件结构分析

PNG,JPEG,GIF,BMP作为数据压缩文件,有许多重要的信息我们需要区深度解析。 一.PNG的文件结构 1.1数据块构成结构 PNG文件结构很简单,主要有数据块(Chunk Block)组成,最少包含4个数据块。...

IamOkay ⋅ 2016/12/07 ⋅ 0

Java压缩算法性能比较

前言 游戏开发中,经常在玩家进入游戏的时候进行必要的信息初始化,往往这个初始化信息数据包是相对来说还是比较大的,一般在30-40kb左右,还是有必要进行压缩一下再发送消息,刚好前段时间看...

ksfzhaohui ⋅ 2016/12/13 ⋅ 18

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Windows下安装运行phpMyAdmin

首先确保安装了phpMyAdmin,其次要求服务器是打开的。 如果是在Windows下,建议下载安装WampServer,这是一个集成软件,集成了Apache+MySQL+PHP的开发环境,而且也自带了phpMyAdmin这个软件。...

临江仙卜算子 ⋅ 8分钟前 ⋅ 0

jdk1.8 安装及环境变量配置

1.根据jdk 的软件安装包,首先安装,jdk,

kuchawyz ⋅ 8分钟前 ⋅ 0

给Java字节码加上”翅膀“的JIT编译器

给Java字节码加上”翅膀“的JIT编译器 上面文章在介绍Java的内存模型的时候,提到过由于编译器的优化会导致重排序的问题,其中一个比较重要的点地方就是关于JIT编译器的功能。JIT的英文单词是...

九劫散仙 ⋅ 9分钟前 ⋅ 0

PCI简介(二)

1.x86处理器系统地址空间简介 1.1 CPU地址空间 CPU地址空间是指CPU所能寻址的空间大小,比如对于32位CPU来说,其所能寻址的空间大小为0~4G。这是由CPU自身的地址总线数目决定的。这段空间也被...

深山野老 ⋅ 10分钟前 ⋅ 0

spring中的InitializingBean接口

好久没更博了,真有点怀念,前段时间刚和上家公司say bye,这次进的是电商公司,今天刚开始看代码,逻辑很复杂。 今天看的注册功能,里面见到一个知识点,现在记录一下,今天看项目时见到里面...

千元机爱好者 ⋅ 12分钟前 ⋅ 0

机器学习:数据预处理之独热编码(One-Hot)

前言 ———————————————————————————————————————— 在机器学习算法中,我们经常会遇到分类特征,例如:人的性别有男女,祖国有中国,美国,法国等。 ...

NateHuang ⋅ 20分钟前 ⋅ 0

MyBatis之输入与输出(resultType、resultMap)映射

在MyBatis中,我们通过parameterType完成输入映射(指将值映射到sql语句的占位符中,值的类型与dao层响应方法的参数类型一致),通过resultType完成输出映射(从数据库中输出,通过dao层的方法查...

瑟青豆 ⋅ 20分钟前 ⋅ 0

屏蔽运营商广告劫持

在今天早上我查找知乎时再次遇到了恶心的运营商广告劫持,右下角硕大的广告直接让知乎挂掉了,我刷了五次知乎才好,之前休息的时候逛知乎也是多次加载错误,估计也是这劫持的锅,相信各位也遇...

gcudwork ⋅ 24分钟前 ⋅ 0

java web 进度条实现原理

资料路径 https://blog.csdn.net/fengsheng5210/article/details/79305026

zaolonglei ⋅ 25分钟前 ⋅ 0

命令行输出java版本与环境变量配置的不一样问题解决

问题:java10刚出来,本着好奇的心,急切的装了体验一下,然后实际项目需求还是java8,所以体验完了就把环境变量改回来了,但是出现了一个问题,命令行输出java版本与环境变量配置的不一样,...

消散了的诗意 ⋅ 27分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部