LZ77算法

LZ77算法（Lempel-Ziv 77 algorithm），工学-信息与通信工程-信源编码-数据压缩-〔数据压缩经典算法〕-LZ77，基于字典编码的一种无损压缩算法。由以色列计算机科学家A.伦佩尔（Abraham Lempel）和以色列电气工程师Y.齐夫（Yaakov Ziv）在1977发明的。LZ77算法有许多派生算法，如LZW算法和LZMA算法等。这些算法原理上基本相同，无论是哪种派生算法，LZ77算法总会包含一个动态窗口和一个预读缓冲器。动态窗口是个历史缓冲器，它被用来存放输入流的前n个字节的有关信息。一个动态窗口的数据范围可以从0KB到64KB。预读缓冲器是与动态窗口相对应的，它被用来存放输入流的前n个字节。预读缓冲器的大小通常在0～258。在动态窗口中寻找与预读缓冲器中最匹配的数据，如果匹配的数据长度大于最小匹配长度（通常取决于编码器，以及动态窗口的大小，如一个4KB的动态窗口，它的最小匹配长度就是2），那么就输出一对〈长度和距离〉数组。长度是匹配的数据长度，而距离说明了在输入流中向后多少字节这个匹配数据可以被找到。