基于字典的压缩算法LZ77探讨
（一）算法的基本思路
基于字典压缩的基本思想十分简单，很容易理解：我们经常说“世贸”，“CPU”等词，大家都明白这指的是“世界贸易组织”，“中央处理器”，其实这已顺利完成了信息压缩与解压的过程：说的人和听的人头脑中都有一本相同的缩略语字典，说（压缩）和听（解缩）的过程中都对字典进行查询操作，从而实现现压缩和解压。
再看一个例子。假如我们手上有一本英语词典，要对以下一段话进行压缩：dictionary methods are both simple and popular.输出的编码如下：
101.2  388.4  4.6  50.11  470.9  3.8  411.13
编码的意义是第一部分表示词典的页码，第二部分表示该单词是该页中的第几个，如101.2表示dictionary这个单词是第101页的第2个单词。所以这种方法的基本思想就是：有一本压缩者和解压者共同的词典，对要压缩的一段文本进行扫描，对其中的句子进行分词操作，得到的每一个独立的词语，在词典中查它的位置，并输出页码和该词在该页中的序号。解压过程更简单，只要在指定的词典位置查出该词就是了。
这种方法是否真能达到压缩效果呢？看回上面的例子，假设词典共有500页，每页不超过128个单词，则页
码可以用9位二进制位编码，页内序号可以用
7位二进制位编码，每个单词一共用16位编码。上面这段话的编码长度是16×7＝112位二进制位。而还没压缩前，每个单词的ASCII码8位，例子中的那段话一共要用8×46＝368位二进制位。
（二）自适应模型胜于静态模型
字典模型有两种：静态和自适应。在静态字典模型中，字典在压缩开始之前就已经建立，并且不会随着数据的压缩过程而改变。静态字典的优点是不需要
在压缩和解压过程中维护字典，因此压缩和解压的实现可以比较简单。但是，静态字典模型用得很少，因为它存在不少缺点。首先，静态模型的适应性不强，必须为每类不同的信息建立不同的字典，为某类信息建立了字典后，该字典通常不能被其它类型的信息重用；其次，静态模型必须维护信息量并不算小的字典，并且必须解决如何将字典从编码程序传递到解码程序的问题，这一额外的信息量可能会严重影响压缩效果，特别对于小文本。所以目前静态模型只用于特殊目的、独立实现的应用，并不是通用的。
LZ77应用自适应字典模型。自适应模型在压缩前不预先建立字典，而是在压缩过程中建立和维护字典，也就是说，将已经编码过的信息作为字典，如果要编码的字符串曾经出现过，就输出该字符串的出现位置及长度，否则输出新的字符串。过程描述如下：
While (文本还没扫描结束) {
Word = read_word ( ) ;
Look_up ( word, dictionary );
If ( 到匹配短语) {
Output ( word ) ;
Add_to_dictionary ( word );
}else Output ( word _position );
}
（三）算法描述——滑动的窗口
LZ77压缩可以称为滑动窗口压缩，因为它用到的主要数据结构是一个可以滑动的窗口。窗口分成两部分：第一部分是历史窗口（history window），存放最近被编码的一段正文；另一部分是向前看窗口（lookahead window），存放从输入文件中读入，还没编码但正准备编码的一段正文。历史窗口和向前
看窗口都跟随压缩进程滑动，历史窗口作为术语字典，向前看窗口中待压缩的字符串如果在该历史窗口中出现，则输出其出现位置和长度。窗口如下图所示：
| History | lookahead
xxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxx
sliding window
为什么使用固定大小窗口作为字典，而不把所有已经编码的信息作为字典呢？主要基于以下三点考虑：一，匹配算法的时间消耗是不容忽视的，如果字典过于庞大，压缩的速度会变得很慢，必须限制窗口的大小；二，窗口越大，表示匹配串在窗口中的位置的编码所需的位数就会越多，必须选取合适的窗口大小，才能保证算法的压缩效率；三，研究表明，对大多数信息而言，要编码的字符串在最近的上下文中到匹配串的概率比较大，所以随着压缩的进程滑动字典窗口，使其中总包含最近编码过的信息。
| History | lookahead
算法输出三个标记的序列：（1）匹配短语在窗口中的偏移量（off）；（2）匹配短语的长度（len）；（3）向前看窗口中跟在匹配短语后面的第一个符号。用一个三元组（off，len，c）表示以上信息。如上图所示。基本流程如下：从lookahead 开始，考察未编码的数据，遍历历史窗口，尝试在历史窗口中查出最长的匹配字符串；如果到，输出三元符号组( off, len, c )；将整个窗口向后滑动len + 1 个字符。如果不到匹配串，输出三元符号组( 0, 0, c )。将整个窗口向后滑动1个字符。原始算法描述如下：
for ( i=0; i<max_match_len; i++) {
while ( current_ match_len <= max_match_len ){
字符串长度压缩if (window[ i++ ] == window[ lookahead_pointer++ ] )
current_ match_len ++;
else break;
}
if (current_ match_len > len ){
off = i ;
len = current_ match_len;
}
}
output ( off, len, c );
slide_window ( len+1 );
以一个例子来说明算法的具体流程。假如压缩过程中的历史窗口和向前看窗口的内容如下图所示（其中“_”表示空格）：
| History | lookahead
这个例子中，历史窗口的内容是”mother_thinks_Jack’s_brother_does_love”，等待压缩的内容是”_Jack’s_father…”，遍历history窗口，查lookahead所指内容的最长匹配串。如图所示，到的最长匹配串为”_Jack’s_”，匹配串在窗口中的偏移off =13，匹配串长度len ＝8，”_Jack’s_”的下一个字符是”f ”，所以输出三元组（13，8，f）。接下来把整个窗口向后滑动8+1=9个字符。滑动窗口后内容如下所示：
| History | lookahead
mother_thinks_Jack’s_ brother_does_love_ Jack’s_father_xxxxxxxxxx
窗口向后滑动9个字符
LZ77的还原算法非常简单，不需要像压缩时那样，进行查匹配串的比较操作。它只需在解压过程中不断维护好像压缩时那样的滑动窗口，读入三元组，根据三元组给出的偏移off，匹配长度len，在窗口中到相应的匹配串，缀上后继字符，然后输出，即可解压出原始数据。就如上面的例子，读入三元组（13，8，f），根据它的意义，在窗口中偏移13处，读出长度为8的串，结果是”_Jack’s_”，然后缀上字符”f ”，输入”_Jack’s_f ”，这就是正确的解压结果。
（四）  LZ77存在的问题——查匹配串形成性能瓶颈
从上面对LZ77算法的分析可以看到，该算法有一个对其压缩速度有很大影响的性能瓶颈，就是遍历滑动窗口，查待编码文本的最长匹配串。当进行编码时，lookahead窗口中的内容要与history窗口中的每个位置进行逐一比较，LZ77算法中的时间消耗主要集中在对最长匹配串的查上，可以说是算法的核心问题。我们可以粗鲁分析一下查算法的时间复杂度，假设窗口大小是n，平均匹配长度是m，则每次查的时间复杂度将达到O（m*n），而每次滑动窗口之后，都要进行下一个匹配串的查。
算法的这个速度性能瓶颈还会间接限制了压缩比的提高。因为，很明显，如果窗口越大，字典就越大，包含的“词汇量”就越丰富，到匹配串的可能性就越高，平均匹配长度也越长，从这个角度看，压缩效果当然就越好。一方面，增大窗口（字典）可以改进压缩的效果，但另一方面，算法的这个速度性能瓶颈就会更加严重，当窗口增大到一定程度，甚至会另速度下降到无法接受的程度。所以，查最长匹配串这个速度性能瓶颈间接限制了压缩比的提高。
很多通用压缩程序都采取了一些方案来改进LZ77的这个缺陷。其中应用得很多的一种是用二叉搜索树的数据结构来改进。方法是，先设定一个长度len，将窗口中每一个len长的串抽取出来，按照大小顺序组织成二叉搜索树。每次匹配串时在这棵二叉搜索树中进行字符串的查。树结点的结构定义如下：Struct {
Char[ len ] key; // 正文字符串
int off; // 这个串在窗口中的偏移
int left_child; // 左孩子
int right; // 右孩子
}
通过建立二叉搜索树的方法的确对查匹配串的速度有很多的提高。但这种方法主要有以下三个缺点：
1．需要耗费一定的空间去存储这棵二叉树结构。假设上面的len设定为30，窗口的大小window_size为4k，则树的结点有window_size－len＋1≈4k个，

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。