个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
25
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章LZ77压缩算法原理的理解由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
LZ77压缩算法原理的理解 。
数据压缩是一个减小数据存储空间的过程，目前被应用在软件工程的各个地方，了解其一些原理，方便我们更好的甄选压缩方案.
压缩方案有很多种，常见的就是有损和无损压缩。霍夫曼编码和LZ77(Lempel-Ziv-1977)都是无损压缩，其中霍夫曼是采用最小冗余编码的算法进行压缩，而LZ77是采用字典的方式进行压缩。关于霍夫曼编码的算法，网上有很多对其详细的讲解，我们本篇幅不在细说，主要图解一下LZ77压缩算法的方式，看看其有哪些优缺点.
信息熵 。
数据为何是可以压缩的，因为数据都会表现出一定的特性，称为熵。绝大多数的数据所表现出来的容量往往大于其熵所建议的最佳容量。比如所有的数据都会有一定的冗余性，我们可以把冗余的数据采用更少的位对频繁出现的字符进行标记，也可以基于数据的一些特性基于字典编码，代替重复多余的短语.
LZ77算法原理 。
LZ77压缩算法采用字典的方式进行压缩，是一个简单但十分高效的数据压缩算法。其方式就是把数据中一些可以组织成短语(最长字符)的字符加入字典，然后再有相同字符出现采用标记来代替字典中的短语，如此通过标记代替多数重复出现的方式以进行压缩。要理解这种算法，我们先了解3个关键词:短语字典，滑动窗口和向前缓冲区.
关键词:
1.前向缓冲区 。
每次读取数据的时候，先把一部分数据预载入前向缓冲区。为移入滑动窗口做准备 。
2.滑动窗口 。
一旦数据通过缓冲区，那么它将移动到滑动窗口中，并变成字典的一部分.
3.短语字典 。
从字符序列S1...Sn，组成n个短语。比如字符(A,B,D) ,可以组合的短语为{(A),(A,B),(A,B,D),(B),(B,D),(D)},如果这些字符在滑动窗口里面，就可以记为当前的短语字典，因为滑动窗口不断的向前滑动，所以短语字典也是不断的变化.
LZ77的主要算法逻辑就是，先通过前向缓冲区预读数据，然后再向滑动窗口移入(滑动窗口有一定的长度)，不断的寻找能与字典中短语匹配的最长短语，然后通过标记符标记。我们还以字符ABD为例子，看如下图
目前从前向缓冲区中可以和滑动窗口中可以匹配的最长短语就是(A,B),然后向前移动的时候再次遇到(A,B)的时候采用标记符代替.
压缩 。
当压缩数据的时候，前向缓冲区与移动窗口之间在做短语匹配的是后会存在2种情况
找不到匹配时：将未匹配的符号编码成符号标记(多数都是字符本身) 。
找到匹配时:将其最长的匹配编码成短语标记.
短语标记包含三部分信息:(滑动窗口中的偏移量(从匹配开始的地方计算)、匹配中的符号个数、匹配结束后的前向缓冲区中的第一个符号).
一旦把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压缩算法的压缩比相当高，当然了也和你选择滑动窗口大小，以及前向缓冲区大小，以及数据熵有关系。其压缩过程是比较耗时的，因为要花费很多时间寻找滑动窗口中的短语匹配，不过解压过程会很快，因为每个标记都明确告知在哪个位置可以读取了.
以上就是LZ77压缩算法原理的理解，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持.
最后此篇关于LZ77压缩算法原理的理解的文章就讲到这里了,如果你想了解更多关于LZ77压缩算法原理的理解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
25
4
0
我有点想做 the reverse of this. 我不想解压缩并将收集文件添加到 S3 应用户要求: 生成一堆xml文件 使用一些图像(托管在 s3 上的预先存在的图像)压缩 xml 文件 下载
将此添加到域的虚拟主机后 AddOutputFilterByType DEFLATE application/javascript text/javascript text/css 响应头不包含任何内
在 Apache Im 中，通过将以下内容添加到我的 .htaccess 文件来启用输出压缩: # compress text, html, javascript, css, xml: AddOutp
是否可以以压缩格式将请求数据从浏览器发送到服务器？ 如果是，我们该怎么做？ 最佳答案 压缩从浏览器发送到服务器的数据是不受 native 支持 在浏览器中。 您必须找到一种解决方法，使用客户端语言(可
我正在寻找可以压缩JavaScript源代码的工具。我发现一些网络工具只能删除空格字符？但也许存在更好的工具，可以压缩用户的函数名称、字段名称、删除未使用的字段等。 最佳答案 经常用来压缩JS代码的工
使用赛马博彩场景，假设我有许多单独的投注来预测比赛的前 4 名选手 (superfecta)。 赌注如下... 1/2/3/4 1/2/3/5 1/2/4/3 1/2/4/5 1/2/5/3
我是一名实习生，被要求对 SQL 2008 数据压缩进行一些研究。我们想将 Outlook 电子邮件的几个部分存储在一个表中。问题是我们想将整个电子邮件正文存储在一个字段中，然后又想压缩它。使用 Ch
我目前有一个系统，用户可以在其中上传 MP4 文件，并且可以在移动设备上下载该文件。但有时，这些视频的大小超过 5MB，在我国，大多数人使用 2G。因此，下载大型视频通常需要 15-20 分钟。 有什
假设我有一个带有类型列的简单文档表: Documents Id Type 1 A 2 A 3 B 4 C 5 C 6 A 7 A 8 A 9 B 10 C 用户
我有一个较大字符串中的(子)字符串位置的 data.frame。数据包含(子)字符串的开头及其长度。可以很容易地计算出(子)字符串的结束位置。 data1 start length end #>
我想知道是否 文件加密算法可以设计成它也可以执行文件压缩的事件(任何活生生的例子？)。 我也可以将它集成到移动短信服务中，我的意思是短信吗？ 另外我想知道二进制文件...如果纯文本文件以二进制编码
关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。 想改善这个问题吗？更新问题，使其成为 on-topic对于堆栈溢出。 7年前关闭。 Improve thi
我们有几个具有大量 JavaScript 的 Java 项目，目前我们使用的是旧版本的 YUICompressor (2.4.2)。然而，我在这篇博文中发现 YUICompressor 正在 depr
从之前关于尝试提高网站性能的文章中，我一直在研究 HTTP 压缩。我读过有关在 IIS 中设置它的信息，但它似乎是所有 IIS 应用程序池的全局事物，我可能不允许这样做，因为还有另一个站点在其上运行。
我有一个 REST 服务，它返回一大块 XML，大约值(value) 150k。 例如http://xmlservice.com/services/RestService.svc/GetLargeXM
我正在尝试获取一个简单的 UglifyJS (v2.3.6) 示例来处理压缩。 具体来说，“未使用”选项，如果从未使用过，变量和函数将被删除。 这是我在命令行上的尝试: echo "function
我正在开发一个项目，如果我的磁盘出现问题，我将在使用 ZLIB 压缩内存块后将其发送到另一个磁盘。然后我计划下载该转储并用于进一步调试。这种压缩和上传将一次完成一个 block - 比如说 1024
LZW 压缩算法在压缩后增加了位大小: 这是压缩函数的代码: // compression void compress(FILE *inputFile, FILE *outputFile) {
我的问题与如何在 3D 地形上存储大量信息有关。这些信息应该是 secret 的，因为它们非常庞大，也应该被压缩。我选择了文件存储，现在我想知道将对象数据加密/压缩(或压缩/加密)到文件的最佳做法。
我使用以下代码来压缩我的文件并且效果很好，但我只想压缩子文件夹而不是在压缩文件中显示树的根。 public boolean zipFileAtPath(String sourcePath, Strin
我是一名优秀的程序员,十分优秀！