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文件,等等。结果验证了对本算法能力的乐观设想。
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文件,等等。结果验证了对本算法能力的乐观设想。
分享到:
相关推荐
zlib 源码分析 对Huffman tree, lz77基础进行了深入讲解 对zlib的实现思路有深度的分析
zlib算法的使用,压缩多个文件,从压缩文件中解码,代码是公司做项目的时候的。
ZLIB数据压缩算法源码ZLIB数据压缩算法源码ZLIB数据压缩算法源码ZLIB数据压缩算法源码
zlib 压缩算法示例zlib 压缩算法示例zlib 压缩算法示例
C# 调用Zlib库实现文件的压缩,可以把常见类型的文件压缩成 zlib 格式的文件,主要实现了一个函数 public void ZipFile(string fileToZip, string zipedFile, int compressionLevel, int blockSize); 用户...
在linux环境下通过zlib库压缩文件夹/目录成.zip文件的c++程序。测试ok、不乱码,如果想自己操作一边,请看我写的readme文档(包含说明和操作步骤),可以快速实现压缩。
zlib-通用的zlib解压缩算法,开源Source,用c写的
zlib是一套通用的解压缩开源库,提供了内存(in-memory)压缩和解压函数,能检测解压出来的数据完整性,由Jean-loup Gailly与Mark Adler所开发;zlib初始版本于1995年5月1日发表。zlib支持gzip文件(.gz格式)的读写...
C++利用Zlib库实现zip文件压缩及解压 支持递归压缩.可配合自动更新功能实现zip压缩包进得软件更新
zlib压缩算法.zip
zlib库解压缩
Gzip Zlib PNG 压缩算法,包含了png压缩的方式和格式,libpng等应用,主要是deflate算法
c/c++,zlib库,压缩文件库
基于Zlib压缩率的测试,包含压缩比,压缩时间,cpu占用率,压缩耗时
zlibwapi.rar zlib压缩算法库文件
zlib库的使用,可以压缩和解压文件夹。 压缩: CreateDirFromZip("test\\example2", "test\\example.zip"); 解压: CreateZipFromDir("test\\example", "test\\example.zip");
通常用zlib库只能对tar.gz文件进行解压缩。本源码解决了在内存中直接对gzip内容进行解压缩,从而对我们感兴趣的内容进行修改。 压缩函数和解压缩函数放在gzip.c文件里,头文件是gzip.h,其他则为zlib库文件。 在...
ZLIB 解压缩代码移植到STM上
zlib压缩算法相关规范文档:rfc1950-zlib.pdf、rfc1951-deflate、rfc1952-gzip。
STM32移植 MINI LZO2.09压缩算法 编译通过 可以直接烧录运行 使用STM32F103VET6