zlib库剖析(5)：LZ77压缩算法

1、LZ77压缩算法
Zlib压缩使用LZ77压缩算法的一个变种，关于LZ77压缩算法，可参考两篇文章http://www.cnblogs.com/D-T121/archive/2012/05/02/2479838.html，和http://hi.baidu.com/cekytggeaqbgnoe/item/c4c66e0ae3033b25a1312d65，这两篇文章对LZ77已经介绍得很详细了。
本来想翻译一下zlib-1.2.7中的doc/algorithm.txt，看完内容后发现它对算法实现的介绍也是概述性的，站的角度比较高，没有太多细节。
在网上搜到一篇文章<<LZ77压缩算法详解>>，在http://wenku.baidu.com/view/c4ee642bcfc789eb172dc8f5.html，这里分析的是gzip（http://www.gzip.org/）中的LZ77实现，比较详细。看完后发现它跟zlib中的实现如出一辙。实际上gzip和zlib的开发者相同，都是Jean-loup Gailly与Mark Adler，而且gzip 1.2.4中的algorithm.doc与zlib中的algorithm.txt中的很多内容都相同。因此zlib与gzip的实现策略基本上是一样的（实现源码可能会有一些不同），不过gzip使用GNU许可，不太适用于商业应用。由于我们并不分析zlib中的实现源码（对于非常成熟的算法，我更关注它的应用，对实现策略只要了解一下即可，这也是为了能更好的应用zlib库）。因此了解gzip中的LZ77实现也足够了。
只要参考这些文章，就能对zlib的压缩算法实现有一个清晰的轮廓，既不会被淹没于代码中，也能对实现细节有足够多的理解。
2、识别纯文本文件
对于纯文本文件，zlib的压缩过程可以加快（gzip头部信息的首个字段即标记文件是否为文本文件）。这涉及到识别纯文本文件的问题。下面内容整理自zlib-1.2.7的doc/txtvsbin.txt。
给定一个不知来源的文件，有时我们希望识别它是不是纯文本格式。这看起来好像是一项简单的任务，实际上对文件类型的精确识别需要对文件进行高强度的语义分析。然而，通过开发多种启发式算法，可以获得比较满意的识别结果。
以前的PKZip版本和其他一些兼容zip的压缩工具使用一种粗糙的识别方法：如果在某个缓冲区中有80%(4/5)以上的字节在范围[7..127]内，则文件被认为是纯文本的，否则被认为是二进制格式。这种方法的一个明显局限是只限制在拉丁字母范围内。其他的字母，如希腊字母、斯拉夫字母或者亚洲语言字母等，其字节广泛使用[128...255]范围的编码。使用这些字符的文本通常会被前述识别方法错判。也就是说，漏报率有时是非常高的，这意味着召回率很低。这种方法另外一个缺点是识别的精确度比较低，因为误报经常会发生，例如包含大量的文本型字符的二进制文件被误报为文本文件。
zlib使用一种新的、简单的识别方法，它的识别精确度大大提高，且有几乎100%的召回率。这种方法可以工作在ASCII, Unicode和其他源自ASCII的字母表上，能够处理单字节的编码（ISO-8859, MacRoman, KOI8等）和可变大小的编码（ISO-2022, UTF-8等），但不能处理更广泛的编码（UCS-2/UTF-16和UCS-4/UTF-32）。
算法描述：
识别算法把字节码[0...255]分成三大类：
（1）白名单：文本型字节码，包括9(TAB), 10(LF), 13(CR), 32(SPACE)到255。
（2）灰名单：可容忍的字节码，包括7(BEL), 8(BS), 11(VT), 12(FF), 26(SUB), 27(ESC)。
（3）黑名单：不能容忍的、非文本型字节码，包括0(NUL)到6, 14到31。
如果文件至少有一个字节属于白名单且没有字节属于黑名单，则文件被认为是纯文本的，否则是二进制格式。（对于边界条件，当文件为空时，自动识别为二进制格式）。
本算法背后的思想源于两个观察。首先，虽然ASCII标准使用了7-bit编码的完整范围[0...127]，但是大部分[0...31]范围内的控制字符在实践中并没有使用，只有9(TAB), 10(LF)和13(CR)被广泛使用，且普遍可移植。还有几个控制字符在一些小范围的平台上使用：7(BEL), 8(BS), 11(VT), 12(FF), 26(SUB)和27(ESC)，但是这些字节码很少单独使用，一般只是混合于可打印的文本中。即使是更新的、可移植的文本格式如XML，都避免使用这两个名单以外的控制字符。其次，许多二进制文件倾向于包含控制字符，特别是0(NUL)。对于原来的文本文件识别方法，即使把高端范围[128...255]当作文本型字符，在观测这个范围的编码出现时，其识别精确度也很难满意，因为二进制文件都倾向于包含控制字符和高端范围内的字符。另一方面，高端范围确实需要当作文本，因为它实际上被所有的ASCII扩展所使用，特别是用于非拉丁字符的编码。
我们不涉及计算，只是观察一些字节码的出现和不出现，无论使用什么字符集，本算法都产生一致的结果。如果涉及计算，则在一个文本型字符上可能会产生不同的结果，例如使用ISO-8859-16和UTF-8来比较。
有一类被黑名单中的字符“污染”的纯文本文件，要么是因为错误，要么是因为特殊的设计考虑。在这种情况下，容忍一小部分黑名单字符的识别方法将产生比较高的召回率（即正报而不是误报），但是这样会降低整个识别精确度，因为在包含大量文本数据的二进制文件上更有可能发生误报。此外，通过通用的文本识别方法，“污染”了的文本文件应该被识别为二进制文件，但是通用的文本处理算法可能不可用。在这样的前提下，可以安全地说，我们的识别方法提供了几乎100%的召回率。
本算法已经在来自各种平台和应用程序的文件上运行过，我们试验过文本文件、系统日志、源代码文件、有格式的Office文档、编译后的obj文件，等等。结果验证了对本算法能力的乐观设想。

更多0

1、LZ77压缩算法
Zlib压缩使用LZ77压缩算法的一个变种，关于LZ77压缩算法，可参考两篇文章http://www.cnblogs.com/D-T121/archive/2012/05/02/2479838.html，和http://hi.baidu.com/cekytggeaqbgnoe/item/c4c66e0ae3033b25a1312d65，这两篇文章对LZ77已经介绍得很详细了。
本来想翻译一下zlib-1.2.7中的doc/algorithm.txt，看完内容后发现它对算法实现的介绍也是概述性的，站的角度比较高，没有太多细节。
在网上搜到一篇文章<<LZ77压缩算法详解>>，在http://wenku.baidu.com/view/c4ee642bcfc789eb172dc8f5.html，这里分析的是gzip（http://www.gzip.org/）中的LZ77实现，比较详细。看完后发现它跟zlib中的实现如出一辙。实际上gzip和zlib的开发者相同，都是Jean-loup Gailly与Mark Adler，而且gzip 1.2.4中的algorithm.doc与zlib中的algorithm.txt中的很多内容都相同。因此zlib与gzip的实现策略基本上是一样的（实现源码可能会有一些不同），不过gzip使用GNU许可，不太适用于商业应用。由于我们并不分析zlib中的实现源码（对于非常成熟的算法，我更关注它的应用，对实现策略只要了解一下即可，这也是为了能更好的应用zlib库）。因此了解gzip中的LZ77实现也足够了。
只要参考这些文章，就能对zlib的压缩算法实现有一个清晰的轮廓，既不会被淹没于代码中，也能对实现细节有足够多的理解。
2、识别纯文本文件
对于纯文本文件，zlib的压缩过程可以加快（gzip头部信息的首个字段即标记文件是否为文本文件）。这涉及到识别纯文本文件的问题。下面内容整理自zlib-1.2.7的doc/txtvsbin.txt。
给定一个不知来源的文件，有时我们希望识别它是不是纯文本格式。这看起来好像是一项简单的任务，实际上对文件类型的精确识别需要对文件进行高强度的语义分析。然而，通过开发多种启发式算法，可以获得比较满意的识别结果。
以前的PKZip版本和其他一些兼容zip的压缩工具使用一种粗糙的识别方法：如果在某个缓冲区中有80%(4/5)以上的字节在范围[7..127]内，则文件被认为是纯文本的，否则被认为是二进制格式。这种方法的一个明显局限是只限制在拉丁字母范围内。其他的字母，如希腊字母、斯拉夫字母或者亚洲语言字母等，其字节广泛使用[128...255]范围的编码。使用这些字符的文本通常会被前述识别方法错判。也就是说，漏报率有时是非常高的，这意味着召回率很低。这种方法另外一个缺点是识别的精确度比较低，因为误报经常会发生，例如包含大量的文本型字符的二进制文件被误报为文本文件。
zlib使用一种新的、简单的识别方法，它的识别精确度大大提高，且有几乎100%的召回率。这种方法可以工作在ASCII, Unicode和其他源自ASCII的字母表上，能够处理单字节的编码（ISO-8859, MacRoman, KOI8等）和可变大小的编码（ISO-2022, UTF-8等），但不能处理更广泛的编码（UCS-2/UTF-16和UCS-4/UTF-32）。
算法描述：
识别算法把字节码[0...255]分成三大类：
（1）白名单：文本型字节码，包括9(TAB), 10(LF), 13(CR), 32(SPACE)到255。
（2）灰名单：可容忍的字节码，包括7(BEL), 8(BS), 11(VT), 12(FF), 26(SUB), 27(ESC)。
（3）黑名单：不能容忍的、非文本型字节码，包括0(NUL)到6, 14到31。
如果文件至少有一个字节属于白名单且没有字节属于黑名单，则文件被认为是纯文本的，否则是二进制格式。（对于边界条件，当文件为空时，自动识别为二进制格式）。
本算法背后的思想源于两个观察。首先，虽然ASCII标准使用了7-bit编码的完整范围[0...127]，但是大部分[0...31]范围内的控制字符在实践中并没有使用，只有9(TAB), 10(LF)和13(CR)被广泛使用，且普遍可移植。还有几个控制字符在一些小范围的平台上使用：7(BEL), 8(BS), 11(VT), 12(FF), 26(SUB)和27(ESC)，但是这些字节码很少单独使用，一般只是混合于可打印的文本中。即使是更新的、可移植的文本格式如XML，都避免使用这两个名单以外的控制字符。其次，许多二进制文件倾向于包含控制字符，特别是0(NUL)。对于原来的文本文件识别方法，即使把高端范围[128...255]当作文本型字符，在观测这个范围的编码出现时，其识别精确度也很难满意，因为二进制文件都倾向于包含控制字符和高端范围内的字符。另一方面，高端范围确实需要当作文本，因为它实际上被所有的ASCII扩展所使用，特别是用于非拉丁字符的编码。
我们不涉及计算，只是观察一些字节码的出现和不出现，无论使用什么字符集，本算法都产生一致的结果。如果涉及计算，则在一个文本型字符上可能会产生不同的结果，例如使用ISO-8859-16和UTF-8来比较。
有一类被黑名单中的字符“污染”的纯文本文件，要么是因为错误，要么是因为特殊的设计考虑。在这种情况下，容忍一小部分黑名单字符的识别方法将产生比较高的召回率（即正报而不是误报），但是这样会降低整个识别精确度，因为在包含大量文本数据的二进制文件上更有可能发生误报。此外，通过通用的文本识别方法，“污染”了的文本文件应该被识别为二进制文件，但是通用的文本处理算法可能不可用。在这样的前提下，可以安全地说，我们的识别方法提供了几乎100%的召回率。
本算法已经在来自各种平台和应用程序的文件上运行过，我们试验过文本文件、系统日志、源代码文件、有格式的Office文档、编译后的obj文件，等等。结果验证了对本算法能力的乐观设想。