PNGPNG 图像格式的压缩算法图像格式的压缩算法便携式网络图形（Portable Network Graphics）简称为 PNG，它是一种无损压缩的位图图形格式，其含有以下几种特性：1、 支持 256 色调色板技术以产生小体积文件2、 支持最高 48 位真彩色图像以及 16 位灰度图像3、 支持阿尔法通道（Alpha Channel，表示图片的透明度和半透明度）的透明/半透明性4、 支持图像亮度的伽马校正（Gamma 校准，用来针对影片或是影像系统里对于光线的辉度 (luminance) 或是三色刺激值 (tristimulus values)所进行非线性的运算或反运算）信息5、 使用了无损压缩的算法6、 使用了循环冗余校验（CRC，用来检测或校验数据传输或者保存后可能出现的错误）防止文件出错一、一、 PNGPNG 格式的文件结构格式的文件结构PNG 定义了两种类型的数据块：一种是 PNG 文件必须包含、读写软件也都必须要支持的关键块（critical chunk） ；另一种叫做辅助块（ancillary chunks） ，PNG 允许软件忽略它不认识的附加块。这种基于数据块的设计，允许 PNG 格式在扩展时仍能保持与旧版本兼容。关键数据块中有关键数据块中有 4 4 个标准数据块：个标准数据块：1、文件头数据块 IHDR(header chunk)：包含有图像基本信息，作为第一个数据块出现并只出现一次。2、调色板数据块 PLTE(palette chunk)：必须放在图像数据块之前。3、图像数据块 IDAT(image data chunk)：存储实际图像数据。PNG 数据允许包含多个连续的图像数据块。4、图像结束数据 IEND(image trailer chunk)：放在文件尾部，表示 PNG 数据流结束二、二、PNGPNG 格式文件的压缩算法格式文件的压缩算法PNG 格式文件采用的是从 LZ77 派生的一个称为 DEFLATE 的非专利无失真式压缩算法，这个算法对图像里的直线进行预测然后存储颜色差值，这使得 PNG 经常能获得比原始图像更大的压缩率。PNG 算法的压缩过程一般有以下几个步骤：1、图像信息由数据过滤器（delta filtering）进行处理，delta filtering 是一个无损的数据过滤算法，它不会改变图像信息的大小，但是会让图像信息具有更高的可压缩性。2、被处理过的数据将会用 Ziv-Lempel（LZ77）算法进行处理，处理后的数据被Huffman 算法压缩，得到最后的 PNG 格式的图像数据，过程可用下图表示。（1 1） LZ77LZ77 压缩算法原理压缩算法原理为了更好地说明 LZ77 算法的原理，首先介绍算法中用到的几个术语： 1.输入数据流(input stream)：要被压缩的字符序列。 2.字符(character)：输入数据流中的基本单元。 3.编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。 4.前向缓冲存储器(Lookahead buffer)：存放从编码位置到输入数据流结束的字符序列的存储器。 5.窗口(window)：指包含 W 个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。 6.指针(pointer)：指向窗口中的匹配串且含长度的指针。LZ77 编码算法的核心是查找从前向缓冲存储器开始的最长的匹配串。编码算法的具体执行步骤如下： 1.把编码位置设置到输入数据流的开始位置。 2.查找窗口中最长的匹配串。 3.以“(Pointer, Length) Characters”的格式输出，其中 Pointer 是指向窗口中匹配串的指针，Length 表示匹配字符的长度，Characters 是前向缓冲存储器中的不匹配的第 1 个字符。 4.如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤 2（2 2） 使用使用 LZ77LZ77 算法进行压缩算法进行压缩如果当前处理开始字节的串在窗口中有匹配串，就先输出一个标志位，表明下面是一个（之间的距离，匹配长度）对，然后输出（之间的距离，匹配长度）对，再从刚才处理完的串之后的下一个字节继续处理。如果当前处理字节开始的串在窗口中没有匹配串，就先输出一个标志位，表明下面是一个没有改动的字节，然后不做改动的输出当前处理字节，再继续处理下一个字节。伪代码如下：压缩一段字节流，src - 源数据区，srclen - 源数据区字节长度，dest - 压缩数据区，返回值 0 压缩数据长度，返回值 = 0 数据无法压缩，返回值 = srclen return 0; do if _SeekPhase(src, srclen, i, return destlen; (3)(3) LZ77LZ77 算法算法解压算法解压算法对于 LZ77 压缩文本的解压很简单。解压算法必须保存解压输出的最后 N 个字符。当碰到编码字符串时，解压算法使用，和，字段将编码替换成实际的正文字符串。三、三、LZ77LZ77 算法优劣以及应用算法优劣以及应用（1 1）LZ77LZ77 算法优劣算法优劣Ziv-Lempel（LZ77） 算法假设需要压缩的数据中连续的序列重复的出现，如果正在处理的序列与历史滑动窗口中的一条或者朵小序列相匹配，则将该序列处理为一个 LZ77 对，LZ77 对包含(距离，长度) 这两个数据，指向最近的一个匹配的序列。如果在一定范围(例如长度在 3258 之间)内无法找到相应的匹配对，则 LZ77 算法会采取一种“贪婪”策略来处理该序列。这种“贪婪”策略在压缩文本或者很多二进制文件时效果很好，然而它在处理过滤后的数据时效果不太理想。过滤后数据主要由很小的随机分布的数据组成，在这种情况下，即使使用“贪婪”策略也不一定能得到很好的效果。（2 2）LZ77LZ77 算法应用算法应用如今除了 PNG 图像格式压缩使用了 LZ77 算法，还有 GZIP(GNU 自由软件的文件压缩程)以及 ZLIB（提供数据压缩用的函式库）均采用了 LZ77 算法进行压缩。