下载文档原格式
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。
这个序列被替换成指向前一个序列的指针和序列的长度。
一、介绍LZ77压缩算法是一种常用的无损数据压缩算法，由Abraham Lempel和Jacob Ziv在1977年提出。
该算法通过利用历史数据的重复性，将重复的数据替换为指向历史数据的指针，从而实现对数据的压缩。
在本文中，我们将介绍如何使用Java语言实现LZ77压缩算法，以及对其性能进行分析。
二、实现原理1. 窗口和缓冲区在LZ77压缩算法中，窗口和缓冲区是两个重要的概念。
窗口是一个固定大小的滑动窗口，用于存储历史数据。
缓冲区则是用于存储待压缩的数据。
2. 搜索和编码LZ77算法通过在窗口中搜索与缓冲区匹配的子串，并将匹配的子串用指向窗口中相应位置的指针来表示。
还需要编码匹配长度和偏移量，以实现对数据的压缩。
三、Java语言实现1. 数据结构在Java语言中，我们可以使用字符串来表示待压缩的数据。
我们需要定义一个数据结构来表示LZ77算法中的窗口和缓冲区。
在本文中，我们使用一个双向队列来表示窗口，使用一个字符数组来表示缓冲区。
2. 搜索和匹配在Java语言中，我们可以使用字符串的相关方法来实现在窗口中搜索和匹配子串的功能。
一旦找到匹配的子串，我们就可以得到匹配的长度和偏移量。
3. 编码和解码LZ77算法中的编码过程涉及到将匹配的长度和偏移量转化为指针的形式，并将其与匹配的字符一起输出。
在Java语言中，我们可以利用字符串的拼接和格式化方法来实现编码的过程。
而在解码过程中，我们需要根据指针的形式来还原出原始数据。
四、性能分析1. 时间复杂度在实现LZ77压缩算法时，搜索和匹配是算法的核心步骤。
在Java语言中，字符串的相关操作通常具有较高的时间复杂度。
在实际应用中，我们需要对算法进行优化，以提高搜索和匹配的效率。
2. 空间复杂度在Java语言中，字符串的存储通常占用较多的内存空间。
在LZ77压缩算法中，窗口和缓冲区的存储也会占用一定的内存空间。
在实际应用中，我们需要考虑如何有效地利用内存空间。
引言1.1 文本压缩的概念及必要性文本压缩(text compression) 是数据压缩(data compression) 的一个分支, 属于无损压缩(lossless compression) 。
它的目标是通过对数据施加某种操作或变换使之长度变短的同时, 还必须保证原始数据能够从压缩产生的压缩码中得以精确的还原。
主要的文本压缩编码有：Huffman 编码,算术编码,游程编码,LZ 编码,LZW编码等。
数据压缩的必要性。
采用数字技术（或系统）有许多优越性，但也使数据量大增。
由此可见，信息时代带来了“信息爆炸”。
数据压缩的作用及其社会效益，经济效益将越来越明显。
反之，如果不进行数据压缩，则无论传输或存储抖很难实用化。
而数据压缩的好处在于：①较快地传输各种信源（降低信道占有费用）－时间域地压缩；②在现有通信干线上开通更多的并行业务（如电视，传真，电话，可视图文等）－频率域的压缩；③降低发射功率（这对于依靠电池供电的移动通信终端如手机，个人数字助理（PDA）等尤为重要）－能量域的压缩；④紧缩数据存储容量（降低存储费用）－空间域的压缩。
1.2 文本压缩的发展在50年代初提出的以具有前缀性质的变长码为特征的Huffman编码是数据压缩领域的一个重要里程碑, 曾经统治数据压缩领域达30 年之久, 至今研究它的文章仍旧源源不断。
这种编码技术长期以来一直被许多工程技术人员视为最佳的编码方法。
70 年代后期提出、80 年代末得以迅速流行的算术编码, 无论从编码效率上还是从时间性能上, 大有取代并淘汰Huffman 编码的趋势。
算术编码绕过了用一个代码一一对应一个信源符号的做法, 它用一个单独的浮点输出数值给整个一条消息编码, 从而每个符号对于输出代码的净效应可以是一个小数位数。
算术编码与Huffman 编码本质上都假定信源中符号独立无关, 即信源系零阶Markov 信源。
与事实上下文结构以及符号之间的存在相关性不符合。
无损压缩算法的比较和分析无损压缩算法是一种将文件或数据压缩成较小体积，而又能保持原始数据完整性的技术。
在实际应用中，有多种无损压缩算法可供选择，每种算法都有其独特的优点和适用场景。
以下是对三种常见的无损压缩算法，LZ77、LZ78和LZW算法，的比较和分析。
1.LZ77算法LZ77算法是一种基于滑动窗口的算法，通过将数据中的重复片段替换为指向该片段的指针，来实现数据压缩。
该算法具有简单高效的特点，适用于具有较多重复片段的数据。
LZ77算法在处理图片、视频等文件时表现出色，能够对重复的像素块进行有效压缩，但对于无重复的文件压缩效果较差。
2.LZ78算法LZ78算法是一种基于前缀编码的算法，通过构建一个字典来记录文件中的重复字串，并用索引指向字典中的相应位置，从而实现数据压缩。
与LZ77算法相比，LZ78算法在处理无重复文件时表现更好，由于引入了字典的概念，能够较好地处理无重复字串的情况。
然而，LZ78算法的压缩率相对较低，在对具有大量重复片段的文件进行压缩时，效果不如LZ77算法。
3.LZW算法LZW算法是一种基于字典的算法，与LZ78算法类似，通过构建字典来实现数据压缩。
LZW算法利用一个初始字典来存储单个字符，并逐渐增加字典的大小，以适应不同长度的字串。
该算法具有较好的压缩率和广泛的应用领域，可适用于文本、图像、音频等各类型文件的压缩。
然而，LZW算法的缺点是需要事先构建和传递字典，增加了存储和传输的复杂性。
综上所述，无损压缩算法的选择应考虑文件的特点和需求。
对于具有大量重复片段的文件，LZ77算法能够实现较好的压缩效果；对于无重复文件，LZ78算法表现更佳；而LZW算法则具有较好的通用性，适用于各类型文件的压缩。
当然，还有其他无损压缩算法可供选择，如Huffman编码、Arithmetic编码等，根据实际情况选用最适合的算法能够达到更好的压缩效果。
关于LZ77压缩算法感觉这篇写的还算完整，贴出来分享给⼤家。
关于该算法的资料来源与⽹络，版权归原作者所有，如果侵权，请及时告知。
之所以这样说，是笔者听说在LZ系列算法中还有⼀部分压缩算法有专利，另⼀⽅⾯也是为了尊总知识产权。
以下内容来⾃互联⽹：============================================================================全新的思路我们在第三和第四章中讨论的压缩模型都是基于对信息中单个字符出现频率的统计⽽设计的，直到 70 年代末期，这种思路在数据压缩领域⼀直占据着统治地位。
在我们今天看来，这种情形在某种程度上显得有些可笑，但事情就是这样，⼀旦某项技术在某⼀领域形成了惯例，⼈们就很难创造出在思路上与其⼤相径庭的哪怕是更简单更实⽤的技术来。
我们敬佩那两个在数据压缩领域做出了杰出贡献的以⾊列⼈，因为正是他们打破了 Huffman 编码⼀统天下的格局，带给了我们既⾼效⼜简便的“字典模型”。
⾄今，⼏乎我们⽇常使⽤的所有通⽤压缩⼯具，象ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR……甚⾄许多硬件如⽹络设备中内置的压缩算法，⽆⼀例外，都可以最终归结为这两个以⾊列⼈的杰出贡献。
说起来，字典模型的思路相当简单，我们⽇常⽣活中就经常在使⽤这种压缩思想。
我们常常跟⼈说“奥运会”、“IBM”、“TCP”之类的词汇，说者和听者都明⽩它们指的是“奥林匹克运动会”、“国际商业机器公司”和“传输控制协议”，这实际就是信息的压缩。
我们之所以可以顺利使⽤这种压缩⽅式⽽不产⽣语义上的误解，是因为在说者和听者的⼼中都有⼀个事先定义好的缩略语字典，我们在对信息进⾏压缩（说）和解压缩（听）的过程中都对字典进⾏了查询操作。
字典压缩模型正是基于这⼀思路设计实现的。
最简单的情况是，我们拥有⼀本预先定义好的字典。
linux lz77压缩算法例子LZ77压缩算法是一种常用的字典压缩算法，用于在数据传输或存储时减少数据的大小。
本文将介绍LZ77压缩算法的基本原理和一个使用Linux命令行工具进行压缩的示例。
LZ77压缩算法基本原理是利用重复出现的连续字符串进行压缩。
该算法将输入数据分为字典和未匹配部分。
字典是已经读取的数据的集合，未匹配部分是还未被处理的数据。
算法通过查找字典中与未匹配部分相同的字符串，找到最长的匹配，并将匹配信息作为指针和长度对进行编码和压缩。
下面是一个简单的例子，展示如何在Linux环境中使用LZ77算法进行压缩。
首先，我们需要安装lz77工具。
打开终端，执行以下命令进行安装（前提是已经安装了包管理器，如apt或yum）：```shellsudo apt install lzma```安装完成后，我们可以使用lz77命令进行压缩。
假设我们要压缩一个名为input.txt的文本文件。
执行以下命令进行压缩：```shelllz77 -c input.txt output.lz77```这将生成一个名为output.lz77的压缩文件。
output.lz77是LZ77算法压缩后的结果。
如果想要解压缩已经压缩的文件，可以执行以下命令：```shelllz77 -d output.lz77 output.txt```这将会生成一个名为output.txt的文件，其中包含解压缩后的数据。
LZ77压缩算法在数据压缩领域有广泛应用，它能够在很大程度上减小数据的大小。
通过使用Linux中可用的压缩工具，我们可以轻松地使用LZ77算法进行文件压缩和解压缩。
LZ77算法在文本压缩中的应用LZ77（Lempel-Ziv 77）算法是一种经典的文本压缩算法，于1977年由Jacob Ziv和Abraham Lempel提出。
LZ77算法基于一种称为“滑动窗口”的模式匹配思想。
它通过在滑动窗口内查找重复的字串，并使用指针（offset）和长度（length）来表示这些重复的字串。
使用这些指针和长度信息，可以将原始文本用更短的编码来表示，从而达到压缩数据大小的目的。
在阶段，LZ77算法从输入文本的开头开始，逐个字符进行。
它通过维护一个滑动窗口来最长的匹配字串。
滑动窗口首先是一个固定大小的缓冲区，起始位置为输入文本的开头，滑动窗口的大小可以根据具体的实现进行调整。
然后，LZ77算法逐个字符将输入文本推进滑动窗口，并在滑动窗口内与当前字符相匹配的最长字串。
这一过程可以使用各种字符串匹配算法来实现，常见的有暴力和Knuth-Morris-Pratt算法等。
一旦找到匹配的字串，LZ77算法记录指针和长度信息，并将其添加到输出流中。
指针（offset）表示匹配字串在滑动窗口中的位置，长度（length）表示匹配字串的长度。
然后，LZ77算法将滑动窗口推进到匹配字串的末尾，并继续进行。
如果没有找到匹配的字串，LZ77算法将当前字符作为一个独立的字节（literal）添加到输出流中，并将滑动窗口推进一个字符。
在编码阶段，LZ77算法将阶段产生的指针、长度和字节组合成一个编码对（<offset,length>, byte）的形式，并将其输出。
输出的编码对可以按照具体的格式进行存储，常见的有二进制格式和可打印的ASCII文本格式。
对于非压缩的字节，LZ77算法将其作为literal直接添加到输出流中。
最终，LZ77算法输出的数据流就是压缩后的文本。
LZ77算法的应用非常广泛，特别是在网络传输和存储领域。
由于网络带宽和存储容量的限制，需要对数据进行压缩以减少传输和存储成本。
压缩率高的压缩算法随着信息技术的不断发展，数据的存储和传输需求也越来越大。
为了更高效地利用存储空间和提高网络传输速度，压缩算法应运而生。
压缩算法是通过对数据进行编码和解码，以减少数据的存储空间和传输带宽的占用。
在众多压缩算法中，有一些算法以其高压缩率而著名。
一、LZ77压缩算法LZ77是一种基于字典的压缩算法，它通过利用重复出现的字符串来减少数据的存储空间。
该算法在编码过程中，将字符串分成固定大小的窗口，并在窗口内查找匹配的字符串。
编码时，将匹配的字符串用指针指向之前出现的位置，并记录匹配字符串之后的字符。
解码时，根据指针和记录的字符，可以还原出原始字符串。
LZ77算法在文本和图像等数据中具有较好的压缩效果，能够显著减少存储空间的占用。
二、哈夫曼编码哈夫曼编码是一种变长编码算法，它通过对频率较高的字符使用较短的编码，对频率较低的字符使用较长的编码，从而达到高压缩率的效果。
该算法首先统计字符出现的频率，然后根据频率构建哈夫曼树。
树的叶子节点表示字符，路径上的编码表示字符的编码。
编码时，将字符替换为对应的编码，解码时，根据编码树还原原始字符。
哈夫曼编码在文本和图像等数据中具有较高的压缩率，能够有效减少存储空间的占用。
三、算术编码算术编码是一种连续编码算法，它通过对数据中的每个符号进行编码，从而实现高压缩率的效果。
该算法将数据的范围映射到一个连续的区间，编码时，根据符号在区间中的位置来确定编码。
解码时，根据编码和区间映射关系还原原始数据。
算术编码在文本和图像等数据中具有较高的压缩率，能够极大地减少存储空间的占用。
四、LZW压缩算法LZW是一种基于字典的压缩算法，它通过建立字典来减少数据的存储空间。
该算法在编码过程中，将输入的字符串逐个字符地添加到字典中，并记录对应的编码。
当输入的字符串在字典中已经存在时，将其对应的编码输出，并将其与下一个字符组合成新的字符串添加到字典中。
解码时，根据编码和字典还原原始字符串。
lz77压缩算法c语言LZ77压缩算法（C语言）引言：在信息技术高速发展的今天，数据的传输和存储变得越来越重要。
为了减小数据的体积，提高传输效率，各种压缩算法应运而生。
其中，LZ77压缩算法是一种常用的无损压缩算法，它通过利用数据的重复性来实现数据压缩。
本文将以C语言为例，介绍LZ77压缩算法的原理和实现。
一、LZ77压缩算法简介LZ77压缩算法是由Abraham Lempel和Jacob Ziv于1977年提出的一种无损压缩算法。
它的基本思想是将数据流分解为长度不等的前缀和后缀，并通过记录前缀在历史数据中的位置和后缀的长度来表示数据的重复性。
这样，在传输或存储数据时，只需要记录位置和长度信息，而不需要重复传输或存储重复的数据，从而达到压缩数据的目的。
二、LZ77压缩算法实现下面我们将用C语言实现LZ77压缩算法。
假设我们有一个输入字符串input，压缩后的输出字符串为output。
我们定义一个窗口大小window_size，表示历史数据的长度。
具体实现步骤如下：1. 初始化窗口和缓冲区- 创建一个窗口，大小为window_size，用于存储历史数据。
- 创建一个缓冲区，用于存储当前的前缀和后缀。
2. 遍历输入字符串- 初始化游标index为0，表示当前处理的位置。
- 当index小于输入字符串的长度时，执行以下步骤：- 在窗口中查找与当前前缀匹配的最长子串，记为match。
- 计算match的位置和长度，分别为offset和length。
- 如果找到了匹配的子串，将offset和length记录到缓冲区，并将index移动length个位置。
- 如果未找到匹配的子串，则将当前字符添加到缓冲区，并将index移动一个位置。
3. 输出压缩结果- 遍历缓冲区，将offset、length和字符依次输出到输出字符串output。
三、示例代码下面是使用C语言实现LZ77压缩算法的示例代码：```c#include <stdio.h>#include <string.h>#define WINDOW_SIZE 256void compressLZ77(char* input, char* output) {int index = 0;int length = strlen(input);char window[WINDOW_SIZE];char buffer[WINDOW_SIZE];memset(window, 0, sizeof(window));memset(buffer, 0, sizeof(buffer));while (index < length) {int offset = 0;int maxLength = 0;// 在窗口中查找与当前前缀匹配的最长子串for (int i = 0; i < index; i++) {int len = 0;while (input[i + len] == input[index + len] && index + len < length) {len++;}if (len > maxLength) {maxLength = len;offset = i;}}// 记录匹配的位置和长度sprintf(buffer, "%d %d %c", offset, maxLength, input[index + maxLength]);// 输出到输出字符串strcat(output, buffer);// 移动游标index += (maxLength + 1);}}int main() {char input[] = "abracadabra";char output[256] = "";compressLZ77(input, output);printf("压缩结果：%s\n", output);return 0;}```四、总结通过实现以上代码，我们成功实现了LZ77压缩算法的C语言版本。
LZ77算法实现LZ77算法是一种无损压缩算法，用于将数据进行压缩，以减小存储空间或提高传输速率。
它的核心思想是利用已经出现的字符序列来代替重复出现的字符序列，从而减少需要存储或传输的数据量。
下面将详细介绍LZ77算法的实现。
缓冲区存储待压缩数据的一部分，它的大小可以根据需要进行调整。
已匹配缓冲区用于存储已找到的重复字符序列。
算法从滑动窗口的起始位置开始，逐个字符地比较缓冲区和已匹配缓冲区的内容，以找到最长的重复字符序列。
下面是LZ77算法的具体实现步骤：1.初始化滑动窗口，设置缓冲区的大小。
2.从滑动窗口的起始位置开始，逐个字符地比较缓冲区和已匹配缓冲区的内容。
3.如果在缓冲区中找到一个与已匹配缓冲区完全相同的字符序列，则将匹配长度和向前偏移量写入输出。
4.如果缓冲区中没有与已匹配缓冲区完全相同的字符序列，则将当前字符写入输出。
5.将已匹配的字符序列追加到已匹配缓冲区中，并更新滑动窗口。
6.重复步骤2-5，直到扫描完所有的字符。
7.输出压缩后的数据。
下面是一个简单的LZ77算法的实现示例：```pythonoutput = []position = 0while position < len(data):longest_match = ""match_length = 0match_position = 0for i in range(1, min(position+1, window_size+1)): substring = data[position-i:position]if substring in data[position:position+i]:match_length = imatch_position = data[position:position+i].index(substring) longest_match = substringif match_length > 0:output.append((match_length, match_position))position += match_lengthelse:output.append((0, data[position]))position += 1return outputdata = "ABABABA"window_size = 4```这个示例中的数据为"ABABABA"，滑动窗口的大小为4、输出结果为[(0,'A'),(0,'B'),(0,'A'),(0,'B'),(0,'A'),(0,'B'),(0,'A')]，表示每个字符都没有重复出现。
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。
这个序列被替换成指向前一个序列的指针和序列的长度。
在这种情况下，前一个序列的the brown fox出现在26个字符之前，序列的长度是13个字符。
对于这个例子，假定存在两种编码选项：8 bit的指针和4 bit的长度，或者12 bit的指针和6 bit的长度。
使用2 bit的首部来指示选择了哪种选项，00表示第一种选项，01表示第二种选项。
因此，the brown fox的第二次出现被编码为<00b><26d><13 d >，或者00 00011010 1101。
压缩报文的剩余部分是字母y；序列<00b><27d><5 d >替换了由一个空格跟着jump组成的序列，以及字符序列ing frog。
图03-05-3演示了压缩映射的过程。
压缩过的报文由35个9 bit字符和两个编码组成，总长度为35 x 9 + 2 x 14 = 343比特。
和原来未压缩的长度为424比特的报文相比，压缩比为1.24。
图03-05-3 LZ77模式例（一）压缩算法说明LZ77（及其变体）的压缩算法使用了两个缓存。
滑动历史缓存包含了前面处理过的N个源字符，前向缓存包含了将要处理的下面L个字符(图03-05-4(a))。
算法尝试将前向缓存开始的两个或多个字符与滑动历史缓存中的字符串相匹配。
如果没有发现匹配，前向缓存的第一个字符作为9 bit的字符输出并且移入滑动窗口，滑动窗口中最久的字符被移出。
如果找到匹配，算法继续扫描以找出最长的匹配。
然后匹配字符串作为三元组输出（指示标记、指针和长度）。
对于K个字符的字符串，滑动窗口中最久的K个字符被移出，并且被编码的K个字符被移入窗口。
图03-05-4(b)显示了这种模式对于我们的例子的运行情况。
这里假定了39个字符的滑动窗口和13个字符的前向缓存。
在这个例子的上半部分，已经处理了前面的40个字符，滑动窗口中是未压缩的最近的39个字符。
剩下的源字符串在前向窗口中。
压缩算法确定了下一个匹配，从前向窗口将5个字符移入到滑动窗口中，并且输出了这个匹配字符串的编码。
经过这些操作的缓存的状态显示在这个例子的下半部分。
(a)通用结构(b)例子图03-05-4 LZ77模式尽管LZ77是有效的，对于当前的输入情况也是合适的，但是存在一些不足。
算法使用了有限的窗口在以前的文本中查找匹配，对于相对于窗口大小来说非常长的文本块，很多可能的匹配就会被丢掉。
窗口大小可以增加，但这会带来两个损失：(1)算法的处理时间会增加，因为它必须为滑动窗口的每个位置进行一次与前向缓存的字符串匹配的工作；(2)<指针>字段必须更长，以允许更长的跳转。
（二）压缩算法描述为了更好地说明LZ77算法的原理，首先介绍算法中用到的几个术语：<输入数据流(input stream)：待压缩处理的字符序列。
XMLNAMESPACEPREFIX ="V"/>字符(character)：输入数据流中的基本单元。
编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向缓冲器中的开始字符。
前向缓冲器(lookahead buffer)：存放从编码位置到输入数据流结束的字符序列的存储器。
窗口(Window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。
指针(Pointer)：指向窗口中的匹配串且含长度的指针。
LZ77编码算法的核心是查找从前向缓冲器开始的最长的匹配串。
算法的具体执行步骤如下：把编码位置设置到输入数据流的开始位置。
查找窗口中最长的匹配串。
输出(Pointer，Length) Characters，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲器中的第1个不匹配的字符。
如果前向缓冲器不是空的，则把编码位置和窗口向前移Length+1个字符，然后返回到步骤2。
例：待编码的数据流如表03-05-1所示，编码过程如表03-05-2所示。
现作如下说明：“步骤”栏表示编码步骤。
“位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。
“匹配”栏表示窗口中找到的最长的匹配串。
“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。
“输出”栏以(Back_chars，Chars_length) Explicit_character格式输出。
其中(Back_chars，Chars_length)是指指向匹配串的指针告诉译码器“在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出”，Explicit_character是真实字符。
例如，表3-13中的输出“(5，2) C”告诉译码器回退5个字符，然后拷贝2个字符“AB”表03-05-1 待编码的数据流表03-05-2 编码过程（三）解压算法对于LZ77压缩文本的解压很简单。
解压算法必须保存解压输出的最后N个字符。
当碰到编码字符串时，解压算法使用<指针>，和<长度>，字段将编码替换成实际的正文字符串。
三．LZSS算法LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。
冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符可能包含在下一个匹配串中。
LZSS算法以比较有效的方法解决这个问题，它的思想是如果匹配串的长度比指针本身的长度长就输出指针，否则就输出真实字符。
由于输出的压缩数据流中包含有指针和字符本身，为了区分它们就需要有额外的标志位，即ID位。
LZSS编码算法的具体执行步骤如下：把编码位置置于输入数据流的开始位置。
在前向缓冲器中查找窗口中最长的匹配串①Pointer ：=匹配串指针。
②Length ：=匹配串长度。
判断匹配串长度Length是否大于等于最小匹配串长度(MIN_LENGTH) ，如果“是”：输出指针，然后把编码位置向前移动Length个字符。
如果“否”：输出前向缓冲存储器中的第1个字符，然后把编码位置向前移动一个字符。
如果前向缓冲器不是空的，就返回到步骤2。
例：编码字符串如表03-05-3所示，编码过程如表03-05-4所示。
现说明如下：“步骤”栏表示编码步骤。
“位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。
“匹配”栏表示窗口中找到的最长的匹配串。
“字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。
“输出”栏的输出为：①如果匹配串本身的长度Length >= MIN_LENGTH，输出指向匹配串的指针，格式为(Back_chars，Chars_length)。
该指针告诉译码器“在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出”。
②如果匹配串本身的长度Length >= MIN_LENGTH，则输出真实的匹配串。
表03-05-3 输入数据流表03-05-4在相同的计算环境下，LZSS算法可获得比LZ77更高的压缩比，而译码同样简单。
这也就是为什么这种算法成为开发新算法的基础。
许多后来开发的文档压缩程序都使用了LZSS的思想，例如PKZip，ARJ，LHArc和ZOO等等，其差别仅仅是指针的长短、窗口的大小等有所不同。
LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。
四．LZ78算法在介绍LZ78算法之前，首先说明在算法中用到的几个术语。
字符流(Charstream)：待编码的数据序列。
字符(Character)：字符流中的基本数据单元。
前缀(Prefix)：在一个字符之前的字符序列。
缀-符串(String)：前缀＋字符。
码字(Code word)：码字流中的基本数据单元，代表词典中的一串字符。
码流(Codestream)：码字和字符组成的序列，是编码器的输出。
词典(Dictionary)：缀-符串表。
按照词典中的索引号对每条缀-符串(String)指定一个码字(Code word)。
当前前缀(Current prefix)：在编码算法中使用，指当前正在处理的前缀，用符号P表示。
当前字符(Current character)：在编码算法中使用，指当前前缀之后的字符，用符号C表示。
当前码字(Current code word)：在译码算法中使用，指当前处理的码字，用W表示当前码字，String.W表示当前码字的缀-符串。
(一) 编码算法LZ78的编码思想是不断地从字符流中提取新的“缀-符串(String)”（通俗地理解为新“词条”），然后用“代号”也就是码字(Code word)表示这个“词条”。
