LZ77编码算法图解

LZ77算法2011-09-07 16:39:23| 分类：图像处理| 标签：|字号大中小订阅二．LZ77算法< XMLNAMESPACE PREFIX ="O" />1977年，Jacob Ziv和Abraham Lempel描述了一种基于滑动窗口缓存的技术，该缓存用于保存最近刚刚处理的文本（J. Ziv and A. Lempel, “A Universal Algorithm for Sequential Data Compression”, IEEE Transaction on Information Theory, May 1977）。

这个算法一般称为IZ77。

LZ77和它的变体发现，在正文流中词汇和短语(GIF中的图像模式)很可能会出现重复。

当出现一个重复时，重复的序列可以用一个短的编码来代替。

压缩程序扫描这样的重复，同时生成编码来代替重复序列。

随着时间的过去，编码可以重用来捕获新的序列。

算法必须设计成解压程序能够在编码和原始数据序列推导出当前的映射。

在研究LZ77的细节之前，先看一个简单的例子（J. Weiss and D. Schremp, “Putting Data on a Diet”, IEEE Spectrum, August 1993）。

考虑这样一句话：the brown fox jumped over the brown foxy jumping frog这个短语的长度总共是53个八位组= 424 bit。

算法从左向右处理这个文本。

初始时，每个字符被映射成9 bit的编码，二进制的1跟着该字符的8 bit ASCII码。

在处理进行时，算法查找重复的序列。

当碰到一个重复时，算法继续扫描直到该重复序列终止。

换句话说，每次出现一个重复时，算法包括尽可能多的字符。

碰到的第一个这样的序列是the brown fox。

这个序列被替换成指向前一个序列的指针和序列的长度。

RDP压缩算法是一种用于远程桌面协议（RDP）的压缩技术，它可以有效地减少网络传输的数据量，提高数据传输速度和效率。

RDP压缩算法主要采用两种压缩方式：LZ77和LZ78。

LZ77是一种基于字典的压缩算法，它通过比较输入数据中的重复部分来生成压缩数据。

LZ78则是一种基于滑动窗口的压缩算法，它通过将输入数据分成若干个固定大小的块，并比较相邻块之间的差异来生成压缩数据。

在RDP中，LZ77和LZ78压缩算法被应用于图像、声音和文本等数据的压缩。

其中，对于图像数据的压缩，RDP采用了一种称为“Delta Encoding”的技术，它可以将连续的像素值进行差分编码，从而减少数据量。

对于声音数据的压缩，RDP则采用了一种称为“Wavelet Coding”的技术，它可以将声音信号分解成多个子带，并对每个子带进行独立编码。

对于文本数据的压缩，RDP则采用了一种称为“Rich Text Format”的技术，它可以将文本数据转换为二进制格式，并进行高效的压缩。

除了以上几种压缩技术外，RDP还支持其他的压缩算法，如BZIP2、LZSS等。

这些算法可以根据不同的应用场景和需求进行选择和配置，以达到最佳的压缩效果。

总之，RDP压缩算法是一种非常重要的技术，它可以有效地减少网络传输的数据量，提高数据传输速度和效率。

随着技术的不断发展和完善，相信RDP压缩算法将会在未来得到更加广泛的应用和发展。

常见的⽆损压缩算法⽆损压缩算法LZ77 算法LZ77 算法的关键是搜索，即在已经处理过的符号序列（数据流）中，寻找与待编码符号序列相同的模式，如果找到匹配的模式，就设法对这个模式进⾏索引，也就是⽣成⼀个指针，然后输出该索引即可。

LZ77 算法巧妙地实现了这个处理。

为了帮助读者理解算法原理，我们⽤图 5-8 描述 LZ77 算法的操作过程，其中涉及到算法⽤到的⼏个关键概念。

当前编码位置，即匹配模式的⾸字符下⼀个字符5-8 描述 LZ77 算法的操作过程压缩处理是从整个报⽂的第⼀个字符开始的。

但是，为了使描述不失⼀般性，我们假设压缩过程已经推进到了当前编码位置。

图 5-8 中，深⾊（绿⾊）部分代表搜索到的⼀个匹配模式。

当然，搜索过程本⾝还包含⼀些具体技术，实际上也是算法的难点。

通过搜索，还得到了匹配模式的长度（length），以及偏移量（off）。

从图 5-8 可以看出，当前编码位置是指正在处理的匹配模式的第⼀个字符，⽽偏移量是指搜索到的匹配模式的第⼀个字符到当前编码位置的距离，即从匹配模式的⾸字符开始算起，到当前编码位置之前的字符数。

可以想见，在当前编码位置确定的条件下，off 和 length 就可以作为匹配模式的索引（即指针）。

因为在解码的时候，解码程序很容易通过 off 和 length 找到需要还原的模式。

所以，总体上 LZ77 算法就是⼀个搜索匹配模式、输出匹配长度和偏移量的循环过程。

这个整体概念有助于理解算法的基本原理。

有了整体框架，我们还要考虑⼀些细节问题。

第⼀个问题，图 5-8 中的"下⼀个字符"（next_char）有什么⽤？下⼀个字符是紧跟在从当前编码位置开始的匹配模式的后⾯的⼀个字符。

实际上，在搜索不到匹配模式的情况下，我们还是需要将压缩过程往前推进，如果直接输出 next char，就可以往前推进⼀个字符。

否则的话，算法就会原地踏步。

由此可见，next_char 的设计起到了⼀个保证压缩进程不会中途停⽌的作⽤。

ZIP算法详解（转！）zip 的压缩原理与实现（lz77 算法压缩）⽆损数据压缩是⼀件奇妙的事情，想⼀想，⼀串任意的数据能够根据⼀定的规则转换成只有原来 1/2 - 1/5 长度的数据，并且能够按照相应的规则还原到原来的样⼦，听起来真是很酷。

半年前，苦熬过初学 vc 时那段艰难的学习曲线的我，对 MFC、SDK 开始失望和不满，这些虽然不算易学，但和 DHTML 没有实质上的区别，都是调⽤微软提供的各种各样的函数，不需要你⾃⼰去创建⼀个窗⼝，多线程编程时，也不需要你⾃⼰去分配 CPU 时间。

我也做过驱动，同样，有DDK（微软驱动开发包），当然，也有 DDK 的“参考⼿册”，连⼀个最简单的数据结构都不需要你⾃⼰做，⼀切都是函数、函数……微软的⾼级程序员编写了函数让我们这些搞应⽤的去调⽤，我不想在这⾥贬低搞应⽤的⼈，正是这些应⽤⼯程师连接起了科学和社会之间的桥梁，将来可以做销售，做管理，⽤⾃⼰逐渐积累起来的智慧和经验在社会上打拼。

但是，在技术上来说，诚实地说，这并不⾼深，不是吗？第⼀流的公司如微软、Sybase、Oracle 等总是⾯向社会⼤众的，这样才能有巨⼤的市场。

但是他们往往也是站在社会的最顶层的：操作系统、编译器、数据库都值得⼀代代的专家去不断研究。

这些帝国般的企业之所以伟⼤，恐怕不是“有经验”、“能吃苦”这些中国特⾊的概念所能涵盖的，艰深的技术体系、现代的管理哲学、强⼤的市场能⼒都是缺⼀不可的吧。

我们既然有志于技术，并且正在起步阶段，何必急不可耐地要转去做“管理”，做“青年才俊”，那些所谓的“成功⼈⼠”的根底能有⼏何，这样⼦浮躁，胸中的规模和格局能有多⼤？在我发现vc只是⼀个⽤途⼴泛的编程⼯具，并不能代表“知识”、“技术”的时候，我有些失落，⽆所不能的不是我，⽽是 MFC、SDK、DDK，是微软的⼯程师，他们做的，正是我想做的，或者说，我也想成为那种层次的⼈，现在我知道了，他们是专家，但这不会是⼀个梦，有⼀天我会做到的，为什么不能说出我的想法呢。