LZ77字典压缩算法的中心思想是尝试识别当前正在压缩的字符序列中是否已有过相同部分,从而用先前出现的字符串取代重复部分,其输出为指向先前字符串的“索引”。例如:
该算法本质上称为“滑动窗口压缩”,使用一个虚拟窗口作为字典,正在压缩的字符串如在窗口内出现,则输出其位置与长度。使用固定大小窗口进行匹配,而非在全部已编码信息中寻找匹配,是因为匹配算法耗时较多,需限制字典大小以保证算法效率。随着压缩进程移动窗口,确保窗口内总是包含最近编码的信息。对大量信息而言,待编码字符串通常在最近的上下文中更容易找到匹配串。
LZ77压缩算法的基本步骤如下:
以一段字符串为例,我们采用以下步骤进行压缩:
LZ77算法通过输出实际字符解决了窗口内无匹配串的问题,但此方法包含冗余信息。冗余表现在两个方面:一是空索引;二是编码器可能输出额外字符,此类字符可能包含在下一个匹配串中。