ZIP算法原理

zip的算法原理

无损数据压缩是一件奇妙的事情，想一想，一串任意的数据能够根据一定的规则转换成只有原来1/2 - 1/5 长度的数据，并且能够按照相应的规则还原到原来的样子，听起来真是很酷。

原理部分：

有两种形式的重复存在于计算机数据中，zip 就是对这两种重复进行了压缩。

一种是短语形式的重复，即三个字节以上的重复，对于这种重复，zip用两个数字：1.重复位置距当前压缩位置的距离；2.重复的长度，来表示这个重复，假设这两个数字各占一个字节，于是数据便得到了压缩，这很容易理解。

一个字节有0 - 255 共256 种可能的取值，三个字节有256 * 256 * 256 共一千六百多万种可能的情况，更长的短语取值的可能情况以指数方式增长，出现重复的概率似乎极低，实则不然，各种类型的数据都有出现重复的倾向，一篇论文中，为数不多的术语倾向于重复出现；一篇小说，人名和地名会重复出现；一张上下渐变的背景图片，水平方向上的像素会重复出现；程序的源文件中，语法关键字会重复出现（我们写程序时，多少次前后copy、paste？），以几十K 为单位的非压缩格式的数据中，倾向于大量出现短语式的重复。经过上面提到的方式进行压缩后，短语式重复的倾向被完全破坏，所以在压缩的结果上进行第二次短语式压缩一般是没有效果的。

第二种重复为单字节的重复，一个字节只有256种可能的取值，所以这种重复是必然的。其中，某些字节出现次数可能较多，另一些则较少，在统计上有分布不均匀的倾向，这是容易理解的，比如一个ASCII 文本文件中，某些符号可能很少用到，而字母和数字则使用较多，各字母的使用频率也是不一样的，据说字母 e 的使用概率最高；许多图片呈现深色调或浅色调，深色（或浅色）的像素使用较多（这里顺便提一下：png 图片格式是一种无损压缩，其核心算法就是zip 算法，它和zip 格式的文件的主要区别在于：作为一种图片格式，它在文件头处存放了图片的大小、使用的颜色数等信息）；上面提到的短语式压缩的结果也有这种倾向：重复倾向于出现在离当前压缩位置较近的地方，重复长度倾向于比较短（20字节以内）。这样，就有了压缩的可能：给256 种字节取值重新编码，使出现较多的字节使用较短的编码，出现较少的字节使用较长的编码，这样一来，变短的字节相对于变长的字节更多，文件的总长度就会减少，并且，字节使用比例越不均匀，压缩比例就越大。

在进一步讨论编码的要求以及办法前，先提一下：编码式压缩必须在短语式压缩之后进行，因为编码式压缩后，原先八位二进制值的字节就被破坏了，这样文件中短语式重复的倾向也会被破坏（除非先进行解码）。另外，短语式压缩后的结果：那些剩下的未被匹配的单、双字节和得到匹配的距离、长度值仍然具有取值分布不均匀性，因此，两种压缩方式的顺序不能变。

在编码式压缩后，以连续的八位作为一个字节，原先未压缩文件中所具有的字节取值不均匀的倾向被彻底破坏，成为随机性取值，根据统计学知识，随机性取值具有均匀性的倾向（比如抛硬币试验，抛一千次，正反面朝上的次数都接近于500 次）。因此，编码式压缩后的结果无法再进行编码式压缩。

短语式压缩和编码式压缩是目前计算机科学界研究出的仅有的两种无损压缩方法，它们都无法重复进行，所以，压缩文件无法再次压缩（实际上，能反复进行的压缩算法是不可想象的，

因为最终会压缩到0 字节）。

短语式重复的倾向和字节取值分布不均匀的倾向是可以压缩的基础，两种压缩的顺序不能互换的原因也说了，下面我们来看编码式压缩的要求及方法：

压缩文件无法再次压缩是因为：

1. 短语式压缩去掉了三个字节以上的重复，压缩后的结果中包含的是未匹配的单双字节，和匹配距离、长度的组合。这个结果当然仍然可能包含三个字节以上的重复，但是概率极低。因为三个字节有256 * 256 * 256 共一千六百多万种可能的情况。

所以只要把原始文件中“自然存在”的短语式重复倾向压掉就可以了，一千六百万分之一的概率再去压缩没有必要。

编码式压缩利用各个单字节使用频率不一样的倾向，使定长编码变为不定长编码，给使用频率高的字节更短的编码，使用频率低的字节更长的编码，起到压缩的效果。如果把编码式压缩的“结果”按照8位作为1字节，重新统计各字节的使用频率，应该是大致相等的。因为新的字节使用频率是随机的。相等的频率再去变换字节长短是没有意义的，因为变短的字节没有比变长的字节更多。

所以压掉了原始文件中“自然存在”的单字节使用频率不均匀的倾向后，随机的使用频率再去压缩也失去了意义。

首先，为了使用不定长的编码表示单个字符，编码必须符合“前缀编码”的要求，即较短的编码决不能是较长编码的前缀，反过来说就是，任何一个字符的编码，都不是由另一个字符的编码加上若干位0 或 1 组成，否则解压缩程序将无法解码

看一下前缀编码的一个最简单的例子：

符号编码

A 0

B 10

C 110

D 1110

E 11110

有了上面的码表，你一定可以轻松地从下面这串二进制流中分辨出真正的信息内容了：

1110010101110110111100010 – DABBDCEAAB

要构造符合这一要求的二进制编码体系，二叉树是最理想的选择。考察下面这棵二叉树：

要编码的字符总是出现在树叶上，假定从根向树叶行走的过程中，左转为0，右转为1，则一个字符的编码就是从根走到该字符所在树叶的路径。正因为字符只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径，符合要求的前缀编码也就构造成功了：

a - 00

b - 010

c - 011

d - 10

e – 11

接下来来看编码式压缩的过程：

为了简化问题，假定一个文件中只出现了a，b，c，d ，e四种字符，它们的出现次数分别是

a : 6次

b : 15次

c : 2次

d : 9次

e : 1次

如果用定长的编码方式为这四种字符编码： a : 000 b : 001 c : 010 d : 011 e : 100

那么整个文件的长度是3*6 + 3*15 + 3*2 + 3*9 + 3*1 = 99

用二叉树表示这四种编码(其中叶子节点上的数字是其使用次数，非叶子节点上的数字是其左右孩子使用次数之和):

（如果某个节点只有一个子节点，可以去掉这个子节点。）

现在的编码是：a : 000 b : 001 c : 010 d : 011 e : 1 仍然符合“前缀编码”的要求。

第一步：如果发现下层节点的数字大于上层节点的数字，就交换它们的位置，并重新计算非叶子节点的值。

先交换11和1，由于11个字节缩短了一位，1个字节增长了一位，总文件缩短了10位。

再交换15和1、6和2，最终得到这样的树：

这时所有上层节点的数值都大于下层节点的数值，似乎无法再进一步压缩了。但是我们把每一层的最小的两个节点结合起来，常会发现仍有压缩余地。

第二步：把每一层的最小的两个节点结合起来，重新计算相关节点的值。

在上面的树中，第一、二、四三层都只有一或二个节点，无法重新组合，但第三层上有四个节点，我们把最小的3和6结合起来，并重新计算相关节点的值，成为下面这棵树。

然后，再重复做第一步。

这时第二层的9小于第三层的15，于是可以互换，有9个字节增长了一位，15个字节缩短了一位，文件总长度又缩短了6位。然后重新计算相关节点的值。

这时发现所有的上层节点都大于下层节点，每一层上最小的两个节点被并在了一起，也不可能再产生比同层其他节点更小的父节点了。

这时整个文件的长度是3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63

这时可以看出编码式压缩的一个基本前提：各节点之间的值要相差比较悬殊，以使某两个节点的和小于同层或下层的另一个节点，这样，交换节点才有利益。

所以归根结底，原始文件中的字节使用频率必须相差较大，否则将没有两个节点的频率之和小于同层或下层其他节点的频率，也就无法压缩。反之，相差得越悬殊，两个节点的频率之和比同层或下层节点的频率小得越多，交换节点之后的利益也越大。

在这个例子中，经过上面两步不断重复，得到了最优的二叉树，但不能保证在所有情况下，都能通过这两步的重复得到最优二叉树，下面来看另一个例子：

这个例子中，所有上层节点都大于等于下层节点，每一层最小的两个节点结合在了一起，但仍然可以进一步优化：

通过最低一层的第４第５个节点对换，第３层的８大于第２层的７。

到这里，我们得出这样一个结论：一棵最优二叉编码树（所有上层节点都无法和下层节点交换），必须符合这样两个条件：

１．所有上层节点都大于等于下层节点。

２．某节点，设其较大的子节点为ｍ，较小的子节点为ｎ，ｍ下的任一层的所有节点都应大于等于ｎ下的该层的所有节点。

当符合这两个条件时，任一层都无法产生更小的节点去和下层节点交换，也无法产生更大的节点去和上层节点交换。

上面的两个例子是比较简单的，实际的文件中，一个字节有256种可能的取值，所以二叉树的叶子节点多达256个，需要不断的调整树形，最终的树形可能非常复杂，有一种非常精巧的算法可以快速地建起一棵最优二叉树，这种算法由 D.Huffman（戴·霍夫曼）提出，下面我们先来介绍霍夫曼算法的步骤，然后再来证明通过这么简单的步骤得出的树形确实是一棵最优二叉树。

霍夫曼算法的步骤是这样的：

·从各个节点中找出最小的两个节点，给它们建一个父节点，值为这两个节点之和。

·然后从节点序列中去除这两个节点，加入它们的父节点到序列中。

重复上面两个步骤，直到节点序列中只剩下唯一一个节点。这时一棵最优二叉树就已经建成了，它的根就是剩下的这个节点。

仍以上面的例子来看霍夫曼树的建立过程。

最初的节点序列是这样的：

a(6) b(15) c(2) d(9) e(1)

把最小的c和e结合起来

不断重复，最终得到的树是这样的：

这时各个字符的编码长度和前面我们说过的方法得到的编码长度是相同的，因而文件的总长度也是相同的：3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63

考察霍夫曼树的建立过程中的每一步的节点序列的变化：

6 1529 1

6159 3

1599

1518

33

下面我们用逆推法来证明对于各种不同的节点序列，用霍夫曼算法建立起来的树总是一棵最优二叉树：

对霍夫曼树的建立过程运用逆推法：

当这个过程中的节点序列只有两个节点时（比如前例中的15和18），肯定是一棵最优二叉树，一个编码为0，另一个编码为1，无法再进一步优化。

然后往前步进，节点序列中不断地减少一个节点，增加两个节点，在步进过程中将始终保持是一棵最优二叉树，这是因为：

1.按照霍夫曼树的建立过程，新增的两个节点是当前节点序列中最小的两个，其他的任何两个节点的父节点都大于（或等于）这两个节点的父节点，只要前一步是最优二叉树，其他的任何两个节点的父节点就一定都处在它们的父节点的上层或同层，所以这两个节点一定处在当前二叉树的最低一层。

2.这两个新增的节点是最小的，所以无法和其他上层节点对换。符合我们前面说的最优二叉树的第一个条件。

3.只要前一步是最优二叉树，由于这两个新增的节点是最小的，即使同层有其他节点，也无法和同层其他节点重新结合，产生比它们的父节点更小的上层节点来和同层的其他节点对换。它们的父节点小于其他节点的父节点，它们又小于其他所有节点，只要前一步符合最优二叉树的第二个条件，到这一步仍将符合。

这样一步步逆推下去，在这个过程中霍夫曼树每一步都始终保持着是一棵最优二叉树。

由于每一步都从节点序列中删除两个节点，新增一个节点，霍夫曼树的建立过程共需(原始节点数- 1) 步，所以霍夫曼算法不失为一种精巧的编码式压缩算法。

附：对于huffman 树，《计算机程序设计艺术》中有完全不同的证明，大意是这样的：１．二叉编码树的内部节点（非叶子节点）数等于外部节点（叶子节点）数减１。

２．二叉编码树的外部节点的加权路径长度（值乘以路径长度）之和，等于所有内部节点值之和。（这两条都可以通过对节点数运用数学归纳法来证明，留给大家做练习。）

３．对huffman 树的建立过程运用逆推，当只有一个内部节点时，肯定是一棵最优二叉树。４．往前步进，新增两个最小的外部节点，它们结合在一起产生一个新的内部节点，当且仅当原先的内部节点集合是极小化的，加入这个新的内部节点后仍是极小化的。（因为最小的两个节点结合在一起，并处于最低层，相对于它们分别和其他同层或上层节点结合在一起，至少不会增加加权路径长度。）

５．随着内部节点数逐个增加，内部节点集合总维持极小化。

实现部分：

如果世界上从没有一个压缩程序，我们看了前面的压缩原理，将有信心一定能作出一个可以压缩大多数格式、内容的数据的程序，当我们着手要做这样一个程序的时候，会发现有很多的难题需要我们去一个个解决，下面将逐个描述这些难题，并详细分析zip 算法是如何解决这些难题的，其中很多问题带有普遍意义，比如查找匹配，比如数组排序等等，这些都是说不尽的话题，让我们深入其中，做一番思考。

我们前面说过，对于短语式重复，我们用“重复距当前位置的距离”和“重复的长度”这两个数字来表示这一段重复，以实现压缩，现在问题来了，一个字节能表示的数字大小为0 －255，然而重复出现的位置和重复的长度都可能超过255，事实上，二进制数的位数确定下来后，所能表示的数字大小的范围是有限的，ｎ位的二进制数能表示的最大值是２的ｎ次方减１，如果位数取得太大，对于大量的短匹配，可能不但起不到压缩作用，反而增大了最终的结果。针对这种情况，有两种不同的算法来解决这个问题，它们是两种不同的思路。一种称为lz77 算法，这是一种很自然的思路：限制这两个数字的大小，以取得折衷的压缩效果。例如距离取15 位，长度取8 位，这样，距离的最大取值为32 k - 1，长度的最大取值为255，这两个数字占23 位，比三个字节少一位，是符合压缩的要求的。让我们在头脑中想象一下lz77 算法压缩进行时的情况，会出现有意思的模型：

在最远匹配位置和当前处理位置之间是可以用来查找匹配的“字典”区域，随着压缩的进行，“字典”区域从待压缩文件的头部不断地向后滑动，直到达到文件的尾部，短语式压缩也就结束了。

不断地从压缩文件中读出匹配位置值和匹配长度值，把已解压部分的匹配内容拷贝到解压文件尾部，遇到压缩文件中那些压缩时未能得到匹配，而是直接保存的单、双字节，解压时只要直接拷贝到文件尾部即可，直到整个压缩文件处理完毕。

lz77算法模型也被称为“滑动字典”模型或“滑动窗口”模型。

另有一种lzw算法对待压缩文件中存在大量简单匹配的情况进行了完全不同的算法设计，它只用一个数字来表示一段短语，下面来描述一下lzw的压缩解压过程，然后来综合比较两者的适用情况。

lzw的压缩过程：

1) 初始化一个指定大小的字典，把256 种字节取值加入字典。

2) 在待压缩文件的当前处理位置寻找在字典中出现的最长匹配，输出该匹配在字典中的序号。

3) 如果字典没有达到最大容量，把该匹配加上它在待压缩文件中的下一个字节加入字典。

4) 把当前处理位置移到该匹配后。

5) 重复2、3、4 直到文件输出完毕。

lzw 的解压过程：

1) 初始化一个指定大小的字典，把256 种字节取值加入字典。

2) 从压缩文件中顺序读出一个字典序号，根据该序号，把字典中相应的数据拷贝到解压文件尾部。

3) 如果字典没有达到最大容量，把前一个匹配内容加上当前匹配的第一个字节加入字典。

4) 重复2、3 两步直到压缩文件处理完毕。

从lzw 的压缩过程，我们可以归纳出它不同于lz77 算法的一些主要特点：

1) 对于一段短语，它只输出一个数字，即字典中的序号。（这个数字的位数决定了字典的最大容量，当它的位数取得太大时，比如24 位以上，对于短匹配占多数的情况，压缩率可能很低。取得太小时，比如8 位，字典的容量受到限制。所以同样需要取舍。）

2) 对于一个短语，比如abcd ，当它在待压缩文件中第一次出现时，ab 被加入字典，第二次出现时，abc 被加入字典，第三次出现时，abcd 才会被加入字典，对于一些长匹配，它必须高频率地出现，并且字典有较大的容量，才会被最终完整地加入字典。相应地，lz77 只要匹配在“字典区域”中存在，马上就可以直接使用。

3) 设lzw 的“字典序号”取n 位，它的最大长度可以达到2 的n 次方；设lz77 的“匹配长度”取n 位，“匹配距离”取d 位，它的最大长度也是 2 的n 次方，但还要多输出d 位（d 至少不小于n），从理论上说lzw 每输出一个匹配只要n 位，不管是长匹配还是短匹配，压缩率要比lz77 高至少一倍，但实际上，lzw 的字典中的匹配长度的增长由于各匹配互相打断，很难达到最大值。而且虽然lz77 每一个匹配都要多输出d 位，但lzw 每一个匹配都要从单字节开始增长起，对于种类繁多的匹配，lzw 居于劣势

可以看出，在多数情况下，lz77 拥有更高的压缩率，而在待压缩文件中占绝大多数的是些简单的匹配时，lzw 更具优势，GIF 就是采用了lzw 算法来压缩背景单一、图形简单的图片。zip 是用来压缩通用文件的，这就是它采用对大多数文件有更高压缩率的lz77 算法的原因。

接下来zip 算法将要解决在“字典区域”中如何高速查找最长匹配的问题。

（注：以下关于技术细节的描述是以gzip 的公开源代码为基础的，如果需要完整的代码，可以在gzip 的官方网站https://www.wendangku.net/doc/f915386594.html,下载。下面提到的每一个问题，都首先介绍最直观简单的解决方法，然后指出这种方法的弊端所在，最后介绍gzip 采用的做法，这样也许能使读者对gzip 看似复杂、不直观的做法的意义有更好的理解。）

最直观的搜索方式是顺序搜索：以待压缩部分的第一个字节与窗口中的每一个字节依次比较，当找到一个相等的字节时，再比较后续的字节…… 遍历了窗口后得出最长匹配。gzip 用的是被称作“哈希表”的方法来实现较高效的搜索。“哈希（hash）”是分散的意思，把待搜索的数据按照字节值分散到一个个“桶”中，搜索时再根据字节值到相应的“桶”中去寻找。短语式压缩的最短匹配为 3 个字节，gzip 以3 个字节的值作为哈希表的索引，但 3 个字节共有2 的24 次方种取值，需要16M 个桶，桶里存放的是窗口中的位置值，窗口的大小为32K，所以每个桶至少要有大于两个字节的空间，哈希表将大于32M，作为90 年代开发的程序，这个要求是太大了，而且随着窗口的移动，哈希表里的数据会不断过时，维护这

么大的表，会降低程序的效率，gzip 定义哈希表为2 的15 次方（32K）个桶，并设计了一个哈希函数把16M 种取值对应到32K 个桶中，不同的值被对应到相同的桶中是不可避免的，哈希函数的任务是 1.使各种取值尽可能均匀地分布到各个桶中，避免许多不同的值集中到某些桶中，而另一些是空桶，使搜索的效率降低。2.函数的计算尽可能地简单，因为每次“插入”和“搜寻”哈希表都要执行哈希函数，哈希函数的复杂度直接影响程序的执行效率，容易想到的哈希函数是取 3 个字节的左边（或右边）15 位二进制值，但这样只要左边（或右边）2 个字节相同，就会被放到同一个桶中，而 2 个字节相同的概率是比较高的，不符合“平均分布”的要求。gzip 采用的算法是：A(4,5) + A(6,7,8) ^ B(1,2,3) + B(4,5) + B(6,7,8) ^ C(1,2,3) + C(4,5,6,7,8) （说明：A 指3 个字节中的第1 个字节，B 指第2 个字节，C 指第3 个字节，A(4,5) 指第一个字节的第4,5 位二进制码，“^”是二进制位的异或操作，“+”是“连接”而不是“加”，“^”优先于“+”）这样使 3 个字节都尽量“参与”到最后的结果中来，而且每个结果值h 都等于((前1个h << 5) ^ c)取右15 位，计算也还简单。

哈希表的具体实现也值得探讨,因为无法预先知道每一个“桶”会存放多少个元素，所以最简单的，会想到用链表来实现：哈希表里存放着每个桶的第一个元素，每个元素除了存放着自身的值，还存放着一个指针，指向同一个桶中的下一个元素，可以顺着指针链来遍历该桶中的每一个元素，插入元素时，先用哈希函数算出该放到第几个桶中，再把它挂到相应链表的最后。这个方案的缺点是频繁地申请和释放内存会降低运行速度；内存指针的存放占据了额外的内存开销。有更少内存开销和更快速的方法来实现哈希表，并且不需要频繁的内存申请和释放：gzip 在内存中申请了两个数组，一个叫head[]，一个叫pre[]，大小都为32K，根据当前位置strstart 开始的 3 个字节，用哈希函数计算出在head[] 中的位置ins_h，然后把head[ins_h] 中的值记入pre[strstart]，再把当前位置strstart 记入head[ins_h]。随着压缩的进行，head[]里记载着最近的可能的匹配的位置（如果有匹配的话，head[ins_h]不为0），pre[]中的所有位置与原始数据的位置相对应，但每一个位置保存的值是前一个最近的可能的匹配的位置。（“可能的匹配”是指哈希函数计算出的ins_h 相同。）顺着pre[] 中的指示找下去，直到遇到0，可以得到所有匹配在原始数据中的位置，0 表示不再有更远的匹配。

接下来很自然地要观察gzip 具体是如何判断哈希表中数据的过时，如何清理哈希表的，因为pre[] 里只能存放32K 个元素，所以这项工作是必须要做的。

gzip 从原始文件中读出两个窗口大小的内容（共64K 字节）到一块内存中，这块内存也是一个数组，称作Window[]；申请head[]、pre[] 并清零；strstart 置为0。然后gzip 边搜索边插入，搜索时通过计算ins_h，检查head[] 中是否有匹配，如果有匹配，判断strstart 减head[] 中的位置是否大于 1 个窗口的大小，如果大于 1 个窗口的大小，就不到pre[] 中去搜索了，因为pre[] 中保存的位置更远了，如果不大于，就顺着pre[] 的指示到Window[] 中逐个匹配位置开始，逐个字节与当前位置的数据比较，以找出最长匹配，pre[] 中的位置也要判断是否超出一个窗口，如遇到超出一个窗口的位置或者0 就不再找下去，找不到匹配就输出当前位置的单个字节到另外的内存（输出方法在后文中会介绍），并把strstart 插入哈希表，strstart 递增，如果找到了匹配，就输出匹配位置和匹配长度这两个数字到另外的内存中，并把strstart 开始的，直到strstart + 匹配长度为止的所有位置都插入哈希表，strstart += 匹配长度。插入哈希表的方法为：

可以看出，pre[] 是循环利用的，所有的位置都在一个窗口以内，但每一个位置保存的值不一定是一个窗口以内的。在搜索时，head[] 和pre[] 中的位置值对应到pre[] 时也要% 32K。当Window[] 中的原始数据将要处理完毕时，要把Window[] 中后一窗的数据复制到

前一窗，再读取32K 字节的数据到后一窗，strstart -= 32K，遍历head[]，值小于等于32K 的，置为0，大于32K 的，-= 32K；pre[] 同head[] 一样处理。然后同前面一样处理新一窗的数据。

分析：现在可以看到，虽然3 个字节有16M 种取值，但实际上一个窗口只有32K 个取值需要插入哈希表，由于短语式重复的存在，实际只有< 32K 种取值插入哈希表的32K 个“桶”中，而且哈希函数又符合“平均分布”的要求，所以哈希表中实际存在的“冲突”一般不会多，对搜索效率的影响不大。可以预计，在“一般情况”下，每个“桶”中存放的数据，正是我们要找的。哈希表在各种搜索算法中，实现相对的比较简单，容易理解，“平均搜索速度”最快，哈希函数的设计是搜索速度的关键，只要符合“平均分布”和“计算简单”，就常常能成为诸种搜索算法中的首选，所以哈希表是最流行的一种搜索算法。但在某些特殊情况下，它也有缺点，比如：1.当键码k 不存在时，要求找出小于k 的最大键码或大于k 的最小键码，哈希表无法有效率地满足这种要求。2.哈希表的“平均搜索速度”是建立在概率论的基础上的，因为事先不能预知待搜索的数据集合，我们只能“信赖”搜索速度的“平均值”，而不能“保证”搜索速度的“上限”。在同人类性命攸关的应用中（如医疗或宇航领域），将是不合适的。这些情况及其他一些特殊情况下，我们必须求助其他“平均速度”较低，但能满足相应的特殊要求的算法。（见《计算机程序设计艺术》第3卷排序与查找）。幸而“在窗口中搜索匹配字节串”不属于特殊情况。

时间与压缩率的平衡：

gzip 定义了几种可供选择的level，越低的level 压缩时间越快但压缩率越低，越高的level 压缩时间越慢但压缩率越高。

不同的level 对下面四个变量有不同的取值：

nice_length：前面说过，搜索匹配时，顺着pre[] 的指示到Window[] 中逐个匹配位置开始，找出最长匹配，但在这过程中，如果遇到一个匹配的长度达到或超过nice_length，就不再试图寻找更长的匹配。最低的level 定义nice_length 为8，最高的level 定义nice_length 为258（即一个字节能表示的最大短语匹配长度3 + 255）。

max_chain：这个值规定了顺着pre[] 的指示往前回溯的最大次数。最低的level 定义max_chain 为4，最高的level 定义max_chain 为4096。当max_chain 和nice_length 有冲突时，以先达到的为准。

max_lazy：这里有一个懒惰匹配（lazy match）的概念，在输出当前位置（strstart）的匹配之前，gzip 会去找下一个位置（strstart + 1）的匹配，如果下一个匹配的长度比当前匹配的长度更长，gzip 就放弃当前匹配，只输出当前位置处的首个字节，然后再查找strstart + 2 处的匹配，这样的方式一直往后找，如果后一个匹配比前一个匹配更长，就只输出前一个匹配的首字节，直到遇到前一个匹配长于后一个匹配，才输出前一个匹配。

gzip 作者的思路是，如果后一个匹配比前一个匹配更长，就牺牲前一个匹配的首字节来换取后面的大于等于1的额外的匹配长度。

max_lazy 规定了，如果匹配的长度达到或超过了这个值，就直接输出，不再管后一个匹配是否更长。最低的4级level 不做懒惰匹配，第5级level 定义max_lazy 为4，最高的level 定义max_lazy 为258。

good_length：这个值也和懒惰匹配有关，如果前一个匹配长度达到或超过good_length，那在寻找当前的懒惰匹配时，回溯的最大次数减小到max_chain 的1/4，以减少当前的懒惰匹配花费的时间。第5级level 定义good_length 为4（这一级等于忽略了good_length），最高的level 定义good_length 为32。

分析：懒惰匹配有必要吗？可以改进吗？

gzip 的作者是无损压缩方面的专家，但是世界上没有绝对的权威，吾爱吾师，更爱真理。我觉得gzip 的作者对懒惰匹配的考虑确实不够周详。只要是进行了认真客观的分析，谁都有权利提出自己的观点。

采用懒惰匹配，需要对原始文件的更多的位置查找匹配，时间肯定增加了许多倍，但压缩率的提高在总体上十分有限。在几种情况下，它反而增长了短语压缩的结果，所以如果一定要用懒惰匹配，也应该改进一下算法，下面是具体的分析。

1. 连续3次以上找到了更长的匹配，就不应该单个输出前面的那些字节，而应该作为匹配输出。

2. 于是，如果连续找到更长的匹配的次数大于第一个匹配的长度，对于第一个匹配，相当于没有做懒惰匹配。

3. 如果小于第一个匹配的长度但大于2，就没有必要作懒惰匹配，因为输出的总是两个匹配。

4. 所以找到一个匹配后，最多只需要向后做2 次懒惰匹配，就可以决定是输出第一个匹配，还是输出1（或2）个首字节加后面的匹配了。

5. 于是，对于一段原始字节串，如果不做懒惰匹配时输出两个匹配（对于每个匹配，距离占15位二进制数，长度占8位二进制数，加起来约占3字节，输出两个匹配约需要6字节），做了懒惰匹配如果有改进的话，将是输出1或2个单字节加上1个匹配（也就是约4或5字节）。这样，懒惰匹配可以使某些短语压缩的结果再缩短1/3到1/6。

6. 再观察这样一个例子：

1232345145678[当前位置]12345678

不用懒惰匹配，约输出6字节，用懒惰匹配，约输出7字节，由于使用了懒惰匹配，把更后面的一个匹配拆成了两个匹配。（如果678 正好能归入再后面的一个匹配，那懒惰匹配可能是有益的。）

7. 综合考虑各种因素（匹配数和未匹配的单双字节在原始文件中所占的比例，后一个匹配长度大于前一个匹配长度的概率，等等），经过改进的懒惰匹配算法，对总的压缩率即使有贡献，也仍是很小的，而且也仍然很有可能会降低压缩率。再考虑到时间的确定的明显的增加与压缩率的不确定的微弱的增益，也许最好的改进是果断地放弃懒惰匹配。

矢量数据主要压缩方法及比较

矢量数据主要压缩方法及比较 张旭 测绘工程 211305020021 摘要：矢量数据主要是指城市大比例尺地形图。此系统中图层主要分为底图层、道路层、单位层，合理的分层便于进行叠加分析、图形的 阐述矢量数据压缩的概念，详细的对常见的矢量空间数据压缩方法了介绍与评价，并对一些改进方法做了介绍，希望通过本文的总结，大家能够更好地了解矢量数据及其压缩方法。 关键词：矢量数据，压缩方法 引言：矢量数据结构中，传统的方法是几何图形及其关系用文件方式组织，而属性数据通常采用关系型表文件记录，两者通过实体标识符连接。由于这一特点使得在某些方面有便利和独到之处，例如在计算长度、面积、形状和图形编辑、几何变换操作中，有很高的效率和精度。

矢量空间数据压缩 GIS中的矢量数据可分为点状图形要素、线状图形要素、面状图形要素。但从压缩的角度来看，矢量数据的压缩主要是线状图形要素的压缩,因为点状图形要素可看成是特殊的线状图形要素，面状图形要素的基础也是线状图形要素，需要由一条或多条线状图形要素围成。因此，线状图形要素的压缩就成为矢量数据压缩中最重要的问题。 矢量数据压缩是从组成曲线的点集合A中抽取一个子集B，用这个子集B在一定的精度范围内尽可能地反映原数据集合A，而这个子集B 的点数应尽可能少。矢量数据压缩与化简的核心是在不扰乱拓扑关系的前提下对原始采样数据进行合理的删减。 对矢量数据进行压缩除了能节约存贮空间，加快网络传输速度之外，其本质的原因在于原始的数据存在一定的冗余。这种数据冗余一方面是数据采样过程中不可避免产生的；另一方面是由于具体应用变化而产生，比如大比例尺的矢量数据用于小比例尺的应用时，就会存在不必要的数据冗余。因此应该根据具体应用来选择合适的矢量数据压缩与化简算法。 2、矢量数据压缩率与压缩误差 压缩率和压缩误差是评价一个矢量数据压缩算法的基本要素。分别以N和n表示矢量数据压缩前后的结点数。矢量数据压缩率为压缩后点的数量与压缩前点的数量之比,即η= (N-n) / N * 100%。 目前，描述压缩误差的方法主要有三种，分别是最大位移距离、位移距离之和以及偏差面积。假设压缩前的曲线为Fs,…,Ft，压缩后的线

几种视频压缩技术概述

几种视频压缩技术概述 （返回） （一）、JPEG——静止图像压缩标准 1、 JPEG 国际标准化组织（ID）和国际电报电话咨询委员会（CCITT）联合成立的专家组织JPEG （Joint Photographic experts group经过五年艰苦细致地工作后，于是1991年3月 提出了ISO CDIO918号建议草案：多灰度静止图像的数字压缩编码（简称JPEG标准）。 这是一个适用于彩色和单多多灰度或连续色调静止数字图像的压缩标准。它包括基于 DPCM（差分脉冲编码调制）、DCT（离散余弦变换）和Huffman编码的有损压缩算法两个 部分。前者不会产生失真，但压缩比很小；后一种算法进行图像压缩住处虽有损失但压 缩比可以很大，压缩20倍左右时，人眼基本上看不出失真。JPEG标准有三个范畴： A、基本顺序过程Baseline sequential processes实现有损图像压缩。重建图像质量达 到人眼难以实现图像质量达到人眼难以观察出损失的要求。采用8*8像素自适应DCT算 法、量化及H uffman型的熵编码器。 B、基于DCT的扩展过程（Extended DCT Based Process）使用累进行工作方式，采用自 适应算术的编码过程。 C、无失真过程（Lossless Process）采用预测编码及Huffman（或算术编码），可保 证重建图像数据与原始图像数据完全相同。 基中的基本顺序过程是JPEG最基本的压缩过程：符合JPEG标准的硬软件编码/解码器都 必须支持和实现这个过程。另两个过程是可选扩展，对一些特定的应用项目有很大实用 价值。 （1）、JPEG算法 基本JPEG算法操作可分成以下三个步骤：通过离散余弦变换（DCT）去除数据冗余；使 用量化表对DCT系数进行量化，量化表是根据人类礼堂系统和压缩图像类型的特点进行 优化的量化系数矩阵；对量化后的DCT系数时行编码使其熵达到最小，熵编码采用 Huffman可变字长编码 （2）、离散余弦变换 JPEG采用8*8子块的二维离散余弦变换算法。在编者按码器的输入端，把原始图像（对

把1G的文件压缩成1M的方法

1G的文件压缩成1M的方法 1.常见文件压缩 首先我们用WinRAR的最高压缩率对常见的文本文件、程序文件和多媒体文件进行压缩，其压缩结果如下(见图1): 压缩后分别还是挺大的 从上图可以看出，多媒体文件压缩比最低，与原文件相差无几，而文本文件和程序文件压缩比要高一些，最高达到3:1，从实际经验来看，我们平时常见的文件压缩比都在10倍以下。 那么，再来看看这个RAR压缩包(见图2)，注意其中的原文件大小和压缩后的包裹大小分别为16777215和18407，这是多大的比例？笔者用计算器算了一下，约等于911:1，接近1000倍的压缩比！这是怎么回事？真的假的？跟我一起继续做下面的试验就明白了。 这个简直是不可思议 2.把大象装进瓶子里 这里笔者从自己的电脑里随便找了个文件“数字图像噪声和去除.htm”，这是笔者在浏览网页时使用另存为功能从网上下载的文章，大小为125KB。 第一步:压缩为ZIP文件。右键单击“数字图像噪声和去除.htm”文件，选择“WinRAR→添加到档案文件”，在压缩选项对话框中选择“档案文件类型”为“ZIP”，“压缩方式”为“最好”(见图3)，单击“确定”开始压缩。可以看到压缩后的“数字图像噪声和去除.zip”文件只有19KB，压缩率还不错，不过仍离我们的目标相去甚远。

第二步:用WinRAR打开“数字图像噪声和去除.zip”，记下“大小”列中显示的原文件大小数值“127594”，打开计算器程序，单击“查看”菜单选择“科学型”，输入数字“127594”，再点击“十六进制”选项将其转换为16进制值，结果是“1F26A”(见图4)。 用科学型计算器认真算一下 第三步:用UltraEdit编辑器打开“数字图像噪声和去除.zip”文件，我们要在文件中找到“1F26A”的数据，不过由于文件中的十六进制数是高低位倒置表示的，所以我们要查找的数据就变成了“6AF201”，单击“搜索”菜单中的“替换”，将文件中的“6AF201”替换为“FFFFFF”(见图5)，共替换两处，文件开头和结尾各一处，替换后保存文件修改。

视频格式和压缩标准大全

网络摄像机和视频服务器作为网络应用的新型产品，适应网络传输的要求也必然成为产品开发的重要因素，而这其中视频图像的技术又成为关键。在目前中国网络摄像机和视频服务器的产品市场上，各种压缩技术百花齐放，且各有优势，为用户提供了很大的选择空间。 JPEG 、M-JPEG 有相当一部分国内外网络摄像机和视频服务器都是采用JPEG，Motion-JPEG压缩技术，JPEG、M-JPEG采用的是帧内压缩方式，图像清晰、稳定，适于视频编辑，而且可以灵活设置每路的视频清晰度和压缩帧数。另外，因其压缩后的格式可以读取单一画面，因此可以任意剪接，特别适用与安防取证的用途。 Wavelet Transform 小波变换也属于帧内压缩技术，由于这种压缩方式移除了图像的高频成分，仅保留单帧图像信号，特别适用于画面变更频繁的场合，且压缩比也得到了一定的提高，因此也被一些网络摄像机和视频服务器所采用，例如，BOSCH推出的NetCam-4系列数字网络摄像机，深圳缔佳生产的NETCAM系列网络摄像机等。 H.263 H.263是一个较为成熟的标准，它是帧间预测和变换编码的混合算法，压缩比较高，尤其适用低带宽上传输活动视频。采用H.263技术生产的网络型产品，其成本较为适中，软/硬件丰富，适合集中监控数量较多的需求，如深圳大学通信技术研究所开发的SF－10网络摄像机和SF-20视频服务器，深圳新文鼎开发的W750视频服务器和W74GM网络摄像机等采用的都是这一压缩技术。 MPEG-4 MPEG-4的着眼点在于解决低带宽上音视频的传输问题，在164KHZ的带宽上，MPEG-4平均可传5－7帧/秒。采用MPEG-4压缩技术的网络型产品可使用带宽较低的网络，如PSTN，ISDN,ADSL等，大大节省了网络费用。另外，MPEG-4的最高分辨率可达720×576，接近DVD 画面效果，基于图像压缩的模式决定了它对运动物体可以保证有良好的清晰度。MPEG-4所有的这些优点，使它成为当前网络产品生产厂商开发的重要趋势之一。 另外，也有部分厂商采用的是MPEG-1,MPEG-2压缩格式，除此之外，有的厂商还采用多种压缩技术相结合的方式，例如，有些国外推出的网络摄像机，其压缩方式就是MPEG-4,与JPEG 相结合，在可以看到JPEG静止图像的同时，利用MPEG-4高级压缩功能，令到高质量的动态图像也能在低带宽上传输。 纵观以上这些压缩技术，虽然MPEG-4以其良好的图像压缩性能，可支持非常低的宽带上达到视频会议的质量，从而成为未来网络型产品开发的主流方向，但就现在市场的应用情况来看，MPEG-4暂时还没有占到主导地位，究其原因，主要是由于虽然MPEG-4的国际标准已经制定，但MPEG-4的算法是公开的因而厂商各自为政，良莠不齐，对后续的二次开发带来了严重的影响，另外，MPEG－4在图像质量上也有待提高，在复杂的网路环境中，数据流

脉冲压缩技术

脉冲压缩技术 在雷达信号处理中的应用

一．脉冲压缩的产生背景及定义 1.1 脉冲压缩的定义 脉冲压缩即pulse compression，它是指发射宽编码脉冲并对回波进行处理以获得窄脉冲，因此脉冲压缩雷达既保持了窄脉冲的高距离分辨力，又能获得宽脉冲的强检测能力。 1.2脉冲压缩的主要手段 目前的脉冲压缩的手段主要有线性调频、非线性调频与相位编码等。 1)线性调频 是最简单的脉冲压缩信号，容易产生，而且其压缩脉冲形状和信噪比对多普勒频移不敏感，因而得到了广泛的应用，但是，在利用多普勒频率测量目标方位和距离的情况下很少使用； 2)非线性调频 非线性调频具有几个明显的优点，不需要对时间和频率加权，但是系统复杂。为了达到所需的旁瓣电平，需要对每个幅度频谱分别进行调频设计，因而在实际中很少应用； 3)相位编码 相位编码波形不同于调频波形，它将宽脉冲分为许多短的子脉冲。这些子脉冲宽度相等，其相位通过编码后被发射。根据所选编码的类型，包括巴克码、伪随机序列编码以及多项制编码等。 1.3脉冲压缩的产生背景 随着飞行技术的飞速发展，对雷达的作用距离、分辨能力、测量精度和单值性等性能指标提出越来越高的要求。测距精度和距离分辨力对信号形式的要求是一致的，主要取决于信号的频率结构，为了提高测距精度和距离分辨力，要求信号具有大的带宽。而测速精度和速度分辨力则取决于信号的时域结构，为了提高测速精度和速度分辨力，要求信号具有大的时宽。除此之外，为提高雷达系统的发现能力，要求信号具有大的能量。由此可见，为了提高雷达系统的发现能力、测量精度和分辨能力，要求雷达信号具有大的时宽、带宽、能量乘积。但是，在系统的发射和馈电设备峰值功率受限制的情况下，

图像压缩算法论文

算法论文 基于huffman编码的图像压缩技术 姓名：康凯 学院：计算机学院 专业：网络工程1102 学号：201126680208 摘要 随着多媒体技术和通讯技术的不断发展, 多媒体娱乐、信息高速公路等不断对信息数据的存储和传输提出了更高的要求, 也给现有的有限带宽以严峻的考验, 特别是具有庞大数据量的数字图像通信, 更难以传输和存储, 极大地制约了图像通信的发展, 因此图像压缩技术受到了越来越多的关注。图像压缩的目的就是把原来较大的图像用尽量少的字节表示和传输,并且要求复原图像有较好的质量。利用图像压缩, 可以减轻图像存储和传输的负担, 使图像在网络上实现快速传输和实时处理。 本文主要介绍数字图像处理的发展概况，图像压缩处理的原理和特点，对多种压缩编码方法进行描述和比较，详细讨论了Huffman编码的图像压缩处理的原理和应用。 关键词：图像处理,图像压缩,压缩算法,图像编码,霍夫曼编码 Abstract With the developing of multimedia technology and communication technology, multimedia entertainment, information, information highway have kept on data storage and transmission put forward higher requirements, but also to the limited bandwidth available to a severe test, especially with large data amount of digital image communication, more difficult to transport and storage, greatly restricted the development of image communication, image compression techniques are therefore more and more attention. The purpose of image compression is to exhaust the original image less the larger the bytes and transmission, and requires better quality of

PDF文件压缩保存的技巧

我们在上网查阅资料时，作者为了保证文章格式的稳定性，一般都是上传PDF格式文件，供用户浏览。我们下载之后，需要使用或者发送，但是PDF文件过大，在内存限制情况下会导致PDF文件上传失败。如果再重新查找文件，这样很麻烦，还会浪费时间。那么，今天就给大家分享PDF文件压缩的技巧。 1、当我们遇到PDF文件需要转换的时候，就可以使用转换器来完成了。大家需要在百度浏览器中搜索PDF转换器，找到相对应的下载链接，下载安装到电脑中。然后打开软件，进入操作页面。

2、进入操作页面后，点击页面上方的【PDF的操作】选项，接下来就点击左侧【PDF的其他操作】下拉框中的【PDF压缩】按钮， 3、添加文件，在页面底部找到【添加文件】的按钮，点击之后弹出一个对话框，在本地文件夹中选择需要压缩的PDF文件，再点右下角的打开按钮，文件就添加到处理列表中了。

4、添加需要压缩的文件后，要选择文件压缩的清晰度，因为文件压缩过程中是会变小，所以需要选择固定的清晰度，来调整压缩后文件的清晰度。在页面底部找到【压缩等级】选择清晰度在50%就可以了。

5、这一步要设置保存路径，可以选择原文件夹，也可以浏览选择路径。一般情况下，建议设置保存位置是在原文件夹中，这样方便下次查找和使用。 6、设置好保存路径后，就要开始PDF文件压缩的操作了，点击页面底部的【开始转换】按钮，文件压缩过程中不会改变文件的排版和格式。

7、文件压缩速度还是很快的，看到操作进度显示100%的时候，PDF文件就压缩完成了，点击右上角【打开】按钮查看文件，也可以在原文件夹中查看压缩完成的图片，根据个人爱好选择打开方式。 给大家分享的这个工具。不仅可以解决PDF和其他文件之间的转

图像压缩算法性能的测试与分析工具

图像压缩算法性能的测试与分析工具1 蔡正兴，张虹 中国矿业大学计算机科学与技术学院，江苏徐州 (221008) 摘要：本文研究了图像压缩算法性能的评价方法，提出了图像压缩算法性能的测试算法，包括横向比较测试和纵向分解测试，并在此基础上设计并实现了压缩算法性能的测试与分析工具。该工具能够测试和分析压缩算法的性能，并自动生成各种分析图表，为用户提供了方便，具有较大的实用价值。为了提高评价的效率、准确性和全面性，文中提出了测试图像的选择方法和测试结果的分析方法，具有一定的理论意义。 关键词：压缩性能，测试方法，分析方法，图像选择方法 1. 引言 近年来，图像压缩得到快速发展[1]，各种算法层出不穷，比如有损的压缩算法可以在低失真的条件下达到高压缩比[2，3]，而无损的压缩算法则可以保证重建图像的无失真[4]。因此在实际应用中得知各种压缩算法的性能及特点是必要的。在评价图像压缩算法性能时主要考虑压缩比、重建质量、时间复杂度、空间复杂度和实现代价这几个方面[5]，其中较为重要的是压缩比、重建质量和时间复杂度。为了计算这些压缩性能指标，常常使用一些工具软件，比如在图像处理领域广泛使用的MATLAB系列软件，它提供了大量的内置函数[6]，操作方便，功能强大，但它不是评价图像压缩算法性能的专业工具，需要进行二次开发，不能有效的分析和评价压缩性能。其次，利用性能指标来评价压缩方法，尽管方便快捷，但还不能反映图像压缩算法的全部特点。例如，在考虑变换编码系统的失真性质时，一般采用MSE(均方误差)，有时利用MSE计算得到的重建质量很好，但视觉效果却不好，这是因为MSE对图像中的失真显著性不敏感[7]，可见，性能指标仅仅是对压缩算法进行宏观上的评价，无法评价每个过程对压缩性能的影响。再次，在评价压缩性能时，不可避免地要使用测试图像，用户在选择测试图像时带有随机性，不利于全面地评价压缩方法。针对这些不足，本文设计了图像压缩算法性能的测试与分析工具——AutoTA。AutoTA的目标是自动地对图像压缩算法进行测试与分析，并生成各种分析图表，全面的评价图像压缩算法的性能。AutoTA具有广泛的应用前景，科研人员利用AutoTA可横向比较各种压缩算法的性能，也可纵向分析压缩算法的特点；工程技术人员也可以根据AutoTA的测试结果，在实际应用中选择合适的图像压缩算法。 2. 压缩算法性能指标 压缩性能指标是评价压缩算法的重要方面，也是AutoTA分析图像压缩算法性能的重要依据，下面将描述相关的性能指标。 2.1压缩比 压缩比是指压缩过程中输入数据量和输出数据量之比，反映了图像压缩算法的压缩性能，当压缩比小于1时为正压缩，当压缩比大于1时为负压缩。压缩比的计算公式为： 1本课题得到国家自然科学基金项目(编号：60372102)、教育部博士点基金项目(编号：20030290011)、软件新技术国家重点实验室课题(编号：A200309)资助。

各种音频编码方式的对比

各种音频编码方式的对比 内容简介：文章介绍了PCM编码、WMA编码、ADPCM编码、LPC编码、MP3编码、AAC编码、CELP编码等，包括优缺点对比和主要应用领域。 PCM编码(原始数字音频信号流) 类型：Audio 制定者：ITU-T 所需频宽： Kbps 特性：音源信息完整，但冗余度过大 优点：音源信息保存完整,音质好 缺点：信息量大，体积大，冗余度过大 应用领域：voip 版税方式：Free 备注：在计算机应用中，能够达到最高保真水平的就是PCM编码，被广泛用于素材保存及音乐欣赏，CD、DVD以及我们常见的WAV文件中均有应用。因此，PCM约定俗成了无损编码，因为PCM代表了数字音频中最佳的保真水准，并不意味着PCM就能够确保信号绝对保真，PCM也只能做到最大程度的无限接近。要算一个PCM音频流的码率是一件很轻松的事情，采样率值×采样大小值×声道数bps。一个采样率为，采样大小为16bit，双声道的PCM编码的WAV文件，它的数据速率则为×16×2 =。我们常见的Audio CD 就采用了PCM编码，一张光盘的容量只能容纳72分钟的音乐信息。 WMA(Windows Media Audio) 类型：Audio 制定者：微软公司 所需频宽：320～112kbps（压缩10～12倍）

特性：当Bitrate小于128K时，WMA几乎在同级别的所有有损编码格式中表现得最出色，但似乎128k 是WMA一个槛，当Bitrate再往上提升时，不会有太多的音质改变。 优点：当Bitrate小于128K时，WMA最为出色且编码后得到的音频文件很小。 缺点：当Bitrate大于128K时，WMA音质损失过大。WMA标准不开放，由微软掌握。 应用领域：voip 版税方式：按个收取 备注：WMA的全称是Windows Media Audio，它是微软公司推出的与MP3格式齐名的一种新的音频格式。由于WMA在压缩比和音质方面都超过了MP3，更是远胜于RA(Real Audio)，即使在较低的采样频率下也能产生较好的音质，再加上WMA有微软的Windows Media Player做其强大的后盾，所以一经推出就赢得一片喝彩。 ADPCM( 自适应差分PCM) 类型：Audio 制定者：ITU-T 所需频宽：32Kbps 特性：ADPCM(adaptive difference pulse code modulation)综合了APCM的自适应特性和DPCM系统的差分特性，是一种性能比较好的波形编码。 它的核心想法是： ①利用自适应的思想改变量化阶的大小，即使用小的量化阶(step-size)去编码小的差值，使用大的量化阶去编码大的差值； ②使用过去的样本值估算下一个输入样本的预测值，使实际样本值和预测值之间的差值总是最小。 优点：算法复杂度低，压缩比小（CD音质>400kbps），编解码延时最短（相对其它技术） 缺点：声音质量一般 应用领域：voip

JPEG图像压缩算法及其实现

多媒体技术及应用 JPEG图像压缩算法及其实现 罗群书 0411102班 2011211684

一、JEPG压缩算法（标准） (一)JPEG压缩标准 JPEG(Joint Photographic Experts Group)是一个由ISO/IEC JTC1/SC2/WG8和CCITT VIII/NIC于1986年底联合组成的一个专家组，负责制定静态的数字图像数据压缩编码标准。迄今为止，该组织已经指定了3个静止图像编码标准，分别为JPEG、JPEG-LS和JPEG2000。这个专家组于1991年前后指定完毕第一个静止图像压缩标准JPEG标准，并且成为国际上通用的标准。JPEG标准是一个适用范围很广的静态图像数据压缩标准，既可用于灰度图像又可用于彩色图像。 JPEG专家组开发了两种基本的静止图像压缩算法，一种是采用以离散余弦变换(Discrete Cosine Transform, DCT)为基础的有损压缩算法，另一种是采用以预测技术为基础的无损压缩算法。使用无损压缩算法时，其压缩比比较低，但可保证图像不失真。使用有损压缩算法时，其算法实现较为复杂，但其压缩比大，按25：1压缩后还原得到的图像与原始图像相比较，非图像专家难于找出它们之间的区别，因此得到了广泛的应用。 JPEG有4种工作模式，分别为顺序编码，渐近编码，无失真编码和分层编码，他们有各自的应用场合，其中基于顺序编码工作模式的JPEG压缩系统也称为基本系统，该系统采用单遍扫描完成一个图像分量的编码，扫描次序从左到右、从上到下，基本系统要求图像像素的各个色彩分量都是8bit，并可通过量化线性地改变DCT系统的量化结果来调整图像质量和压缩比。下面介绍图像压缩采用基于DCT的顺序模式有损压缩算法，该算法下的JPEG压缩为基本系统。 (二)JPEG压缩基本系统编码器 JPEG压缩是有损压缩，它利用了人的视觉系统的特性，将量化和无损压缩编码相结合来去掉视觉的冗余信息和数据本身的冗余信息。基于基本系统的JPEG压缩编码器框图如图1所示，该编码器是对单个图像分量的处理，对于多个分量的图像，则首先应将图像多分量按照一定顺序和比例组成若干个最小压缩单元（MCU），然后同样按该编码器对每个MCU各个分量进行独立编码处理，最终图像压缩数据将由多个MCU压缩数据组成。 图1 JPEG压缩编码器结构框图

winrar高压缩技巧

1.常见文件压缩 首先我们用WinRAR的最高压缩率对常见的文本文件、程序文件和多媒体文件进行压缩，其压缩结果如下(见图1): 压缩后分别还是挺大的 从上图可以看出，多媒体文件压缩比最低，与原文件相差无几，而文本文件和程序文件压缩比要高一些，最高达到3:1，从实际经验来看，我们平时常见的文件压缩比都在10倍以下。 那么，再来看看这个RAR压缩包(见图2)，注意其中的原文件大小和压缩后的包裹大小分别为16777215和18407，这是多大的比例？笔者用计算器算了一下，约等于911:1，接近1000倍的压缩比！这是怎么回事？真的假的？跟我一起继续做下面的试验就明白了。 这个简直是不可思议 2.把大象装进瓶子里 这里笔者从自己的电脑里随便找了个文件“数字图像噪声和去除.htm”，这是笔者在浏览网页时使用另存为功能从网上下载的文章，大小为125KB。 第一步:压缩为ZIP文件。右键单击“数字图像噪声和去除.htm”文件，选择“WinRAR→添加到档案文件”，在压缩选项对话框中选择“档案文件类型”为“ZIP”，“压缩方式”为“最好”(见图3)，单击“确定”开始压缩。可以看到压缩后的“数字图像噪声和去除.zip”文件只有19KB，压缩率还不错，不过仍离我们的目标相去甚远。

第二步:用WinRAR打开“数字图像噪声和去除.zip”，记下“大小”列中显示的原文件大小数值“127594”，打开计算器程序，单击“查看”菜单选择“科学型”，输入数字“127594”，再点击“十六进制”选项将其转换为16进制值，结果是“1F26A”(见图4)。 用科学型计算器认真算一下 第三步:用UltraEdit编辑器打开“数字图像噪声和去除.zip”文件，我们要在文件中找到“1F26A”的数据，不过由于文件中的十六进制数是高低位倒置表示的，所以我们要查找的数据就变成了“6AF201”，单击“搜索”菜单中的“替换”，将文件中的“6AF201”替换为“FFFFFF”(见图5)，共替换两处，文件开头和结尾各一处，替换后保存文件修改。

几种视频压缩算法对比

视频压缩算法对比 视频2008-05-23 10:10:09 阅读557 评论0 字号：大中小订阅 视频压缩标准及比较原始的数字视频信号的数据量是相当惊人的，例如，NTSC 图像以大约640X480的分辨率，24bist/象素，每秒30帧的质量传输时，则视频数据有640X480x24X30=221Mb/S或28MB/s秒，显然这样庞大的数据流对大多数传输线路来说是无法承受的，而且也是无法存储的。为此人们开始专门研究将这些视频、音频数据流进行压缩。很多压缩编码标准相继推出，主要有JPEG月吐一JPEG‘，幻，_H.261旧.263和MPEG等标准。其中JPEG标准主要是用在静止图像的压缩。M一PJEG是将PJEG改进后用到运动图像上，在压缩比不高时，有较好的复现图像质量，但占用存储空间大;在压缩比高的情况下，复现图像质量差。.H261爪.263标准是专门为用于图像质量要求不高的视频会议和可视电话设计。MpEG(MovnigPictureExPertGorPu即活动图像专家组)。它是由150(国际标准化组织)和正(c国际电工委员会)于1988年联合成立的。专门致力于运动图像及伴音编码标准化工作。它们推出了MPEG编码标准【1卜，1l。到现在为止，专家组己制定了MPEG一1，MPEG一2和MPEG一4三种标准，由于其标准化、较大的压缩比及较高的画面质量，成为视频压缩系统首选算法。 MPEGI是一种压缩比高但图像质量稍差的技术;而MPEGZ技术主要专注于图像质量，压缩比小，因此需要的存储空间就大;MPEG4技术是时下比较流行的技术，使用这种技术可以节省空间、提高图像质量、节省网络传输带宽等优点。 来自：https://www.wendangku.net/doc/f915386594.html,/blog/static/80720305200842310109120/

五种压缩软件比较

五种压缩软件（WinRAR、7Z、好压、快压和360压缩）之比拼 除了老牌的WinRAR和7Z压缩软件外，新近又出现了多款国产压缩软件，各自都称其为自主知识产权，最高压缩比，现就WinRAR、7Z、好压、快压和360压缩等五款压缩软件的功能进行一次大比拼。 一、压缩功能之比拼 本人用GHO映像文件、rmvb视频文件和JPG图像文件进行了压缩测试。 1、用GHO映像文件829MB测试 软件编号软件压缩格式用时压缩文件大小备注 1 7Z 7z 12分58秒830M 7Z ZIP 2分13秒826M 2 WinRAR rar 15分22秒824M WinRAR ZIP 1分7秒825M 3 快压kz 12分52秒829M 快压ZIP 4 好压7z 好压ZIP 1分20秒825M 5 360压缩7z 360压缩ZIP 1分55秒826M 从上表看出，在压缩GHO映像文件时，号称最高压缩比的7Z和快压居然毫无建树，7Z压缩文件居然比GHO映像文件还大，原因是因为GHO映像文件也是压缩文件的一种。唯有最老牌的ZIP压缩效果最好，速度最快，压缩比最高。 2、用rmvb视频文件175MB测试 软件编号软件压缩格式用时压缩文件大小备注 1 7Z 7z 3分32秒173M 7Z ZIP 4分00秒173M 2 WinRAR rar 3分10秒173M WinRAR ZIP 15秒173M 3 快压kz 21秒173M 快压ZIP 3分57秒173M 4 好压7z 20秒173M 好压ZIP 173M 5 360压缩7z 3分23秒173M 360压缩ZIP 30秒175M 从上表看出，5种压缩软件的各种压缩格式对rmvb视频文件的压缩比都很小，因为rmvb视频文件是用可变码率编码的一种高压缩视频编码算法，可压缩的空间很小，用压缩软件压缩rmvb视频文件是没有必要的。但仍然是ZIP的压缩速度最快。 3、用JPG图像文件32.2M测试 软件编号软件压缩格式用时压缩文件大小备注 1 7Z 7z 24秒28.6M

脉冲压缩

“雷达原理” 作业报告 西安电子科技大学 2011年11月 摘要简单介绍了脉冲压缩技术的原理和类型，并对线性调频脉冲压缩进行了详细的分析推导。 引言 雷达是通过对回波信号进行接收再作一些检测处理来识别复杂回波中的有用信息的。其中，波形设计有着相当重要的作用，它直接影响到雷达发射机形式的选择"信号处理方式"雷达的作用距离及抗干扰"抗截获等很多重要问题。现代雷达中广泛采用了脉冲压缩技术。脉冲压缩雷达常用的信号有线性调频信号和二相编码信号。脉冲压缩雷达具有高的辐射能量和高的距离分辨力，这种雷达具有很强的抗噪声干扰和欺骗干扰的性能。对线性调频信号有效的干扰方式是移频干扰(对二相编码信号较有效的干扰方式是距离拖引干扰。 1脉冲压缩简介 雷达的基本功能是利用目标对电磁波的散射而发现目标，并测定目标的空间位置。雷达分辨力是雷达的主要性能参数之一。所谓雷达分辨力是指在各种目标环境下区分两个或两个以上的邻近目标的能力。一般说来目标距离不同、方位角不同、高度不同以及速度不同等因素都可用来分辨目标，而与信号波形紧密联系的则是距离分辨力和速度(径向)分辨力。

两个目标在同一角度但处在不同距离上，其最小可区分的距离称为距离分辨力，如图1．1所示，雷达的距离分辨力取决于信号带宽。对于给定的雷达系统，可达到的距离分辨力为 B c r 2=δ 式中，c 为光速，B=f ?可为发射波形带宽。 图1．1脉冲压缩雷达原理示意图 雷达的速度分辨力可用速度分辨常数表征，信号在时域上的持续宽度越大，在频域上的分辨能力就越好，即速度分辨力越好。 对于简单的脉冲雷达，B=f ?=1／τ，此处，τ为发射脉冲宽度。因此，对于简单的脉冲雷达系统，将有 τδ2c r = 在普通脉冲雷达中，由于雷达信号的时宽带宽积为一常数(约为1)，因此不能兼顾距离分辨力和速度分辨力两项指标。 雷达对目标进行连续观测的空域叫做雷达的探测范围，也是雷达的重要性能参数，它决定于雷达的最小可测距离和最大作用距离，仰角和方位角的探测范围。而发射功率的大小影响作用距离，功率大则作用距离大。发射功率分脉冲功率和平均功率。雷达在发射脉冲信号期间τ内所输出的功率称脉冲功率，用Pt 表示；平均功率是指一个重复周期Tr 内发射机输出功率的平均值，用Pav 表示。它们的关系为： r av t T P =P τ 脉冲压缩(PC)雷达体制在雷达脉冲峰值受限的情况下，通过发射宽脉冲而获得高的发射

JPEG2000图像压缩算法标准剖析

JPEG2000图像压缩算法标准 摘要：JPEG2000是为适应不断发展的图像压缩应用而出现的新的静止图像压缩标准。本文介绍了JPEG2000图像编码系统的实现过程, 对其中采用的基本算法和关键技术进行了描述，介绍了这一新标准的特点及应用场合，并对其性能进行了分析。 关键词：JPEG2000；图像压缩；基本原理；感兴趣区域 引言 随着多媒体技术的不断运用，图像压缩要求更高的性能和新的特征。为了满足静止图像在特殊领域编码的需求，JPEG2000作为一个新的标准处于不断的发展中。它不仅希望提供优于现行标准的失真率和个人图像压缩性能，而且还可以提供一些现行标准不能有效地实现甚至在很多情况下完全无法实现的功能和特性。这种新的标准更加注重图像的可伸缩表述。所以就可以在任意给定的分辨率级别上来提供一个低质量的图像恢复，或者在要求的分辨率和信噪比的情况下提取图像的部分区域。 1.JPEG2000的基本介绍及优势 相信大家对JPEG这种图像格式都非常熟悉，在我们日常所接触的图像中，绝大多数都是JPEG格式的。JPEG的全称为Joint Photographic Experts Group，它是一个在国际标准组织(ISO)下从事静态图像压缩标准制定的委员会，它制定出了第一套国际静态图像压缩标准：ISO 10918－1，俗称JPEG。由于相对于BMP等格式而言，品质相差无己的JPEG格式能让图像文件“苗条”很多，无论是传送还是保存都非常方便，因此JPEG格式在推出后大受欢迎。随着网络的发展，JPEG的应用更加广泛，目前网站上80％的图像都采用JPEG格式。 但是，随着多媒体应用领域的快速增长，传统JPEG压缩技术已无法满足人们对数字化多媒体图像资料的要求：网上JPEG图像只能一行一行地下载，直到全部下载完毕，才可以看到整个图像，如果只对图像的局部感兴趣也只能将整个图片载下来再处理；JPEG格式的图像文件体积仍然嫌大；JPEG格式属于有损压缩，当被压缩的图像上有大片近似颜色时，会出现马赛克现象；同样由于有损压缩的原因，许多对图像质量要求较高的应用JPEG无法胜任。 JPEG2000是为21世纪准备的压缩标准，它采用改进的压缩技术来提供更高的解像度，其伸缩能力可以为一个文件提供从无损到有损的多种画质和解像选择。JPEG2000被认为是互联网和无线接入应用的理想影像编码解决方案。 “高压缩、低比特速率”是JPEG2000的目标。在压缩率相同的情况下，JPEG2000的信噪比将比JPEG提高30%左右。JPEG2000拥有5种层次的编码形式：彩色静态画面采用的JPEG 编码、2值图像采用的JBIG、低压缩率图像采用JPEGLS等，成为应对各种图像的通用编码方式。在编码算法上，JPEG2000采用离散小波变换（DWT）和bit plain算术编码（MQ coder）。此外，JPEG2000还能根据用户的线路速度以及利用方式(是在个人电脑上观看还是在PDA上观看)，以不同的分辨率及压缩率发送图像。 JPEG2000的制定始于1997年3月，但因为无法很快确定算法，因此耽误了不少时间，直到2000年 3 月，规定基本编码系统的最终协议草案才出台。目前JPEG2000已由ISO和

无损压缩算法的比较和分析

Adaptive-Huffman-Coding 自适应霍夫曼编码 压缩比：1.79 分析： 霍夫曼算法需要有关信息源的先验统计知识，而这样的信息通常很难获得，即使能够获得这些统计数字，符号表的传输仍然是一笔相当大的开销。 自适应压缩算法能够解决上述问题，统计数字是随着数据流的到达而动态地收集和更新的。概率再不是基于先验知识而是基于到目前为止实际收到的数据。随着接收到的符号的概率分布的改变，符号将会被赋予新的码字，这在统计数字快速变化的多媒体数据中尤为适用。 Lempel-Ziv-Welch 基于字典的编码 压缩比：1.86 分析： LZW算法利用了一种自适应的，基于字典的压缩技术。和变长编码方式不同，LZW使用定长的码字（本次实验使用12位定长码字）来表示通常会在一起出现的符号/字符的变长的字符串。 LZW编码器和解码器会在接受数据是动态的创建字典，编码器和解码器也会产生相同的字典。 编码器的动作有时会先于解码器发生。因为这是一个顺序过程，所以从某种意义上说，这是可以预见的。

算术编码（arithmetic coding） 压缩比：2 分析： 算术编码是一种更现代化的编码方法，在实际中不赫夫曼编码更有效。 算术编码把整个信息看作一个单元，在实际中，输入数据通常被分割成块以免错误传播。 算术编码将整个要编码的数据映射到一个位于[0,1)的实数区间中。并且输出一个小于1同时大于0的小数来表示全部数据。利用这种方法算术编码可以让压缩率无限的接近数据的熵值，从而获得理论上的最高压缩率。 比较分析： 一般来说，算术编码的性能优于赫夫曼编码，因为前者将整个消息看作一个单元，而后者受到了必须为每一个符号分配整数位的限制。 但是，算术编码要求进行无限精度的实数运算，这在仅能进行有限精度运算的计算机系统是无法进行的。随着研究的深入，有学者提出了一种基于整数运算的算术编码实现算法。在编码和解码的过程还需要不时的调整区间大小，以免精度不足，加大了实现的难度。 在3种无损压缩算法中，LZW算法相对来说，实现最为简单，但其压缩效果要在数据源足够大的时候，才能显现出来。

几种视频压缩标准

几种视频压缩标准简介 3. 基于嵌入式视频服务器的网络化数字视频监控 3.1 什么是网络数字监控 简单的说，网络数字监控就是将传统的模拟视频信号转换为数字信号，通过计算机网络来传输，通过智能化的计算机软件来处理。 系统将传统的视频、音频及控制信号数字化，以IP包的形式在网络上传输，实现了视频/音频的数字化、系统的网络化、应用的多媒体化以及管理的智能化。 3.2 几种视频压缩标准简介 1）MJPEG MJPEG 是指Motion JPEG，即动态JPEG，按照25帧/秒速度使用JPEG 算法压缩视频信号，完成动态视频的压缩。是由JPEG专家组制订的，其图像格式是对每一帧进行压缩，通常可达到6：1的压缩率，但这个比率相对来说仍然不足。就像每一帧都是独立的图像一样。MJPEG图象流的单元就是一帧一帧的JPEG画片。因为每帧都可任意存取，所以MJPEG 常被用于视频编辑系统。动态JPEG能产生高质量、全屏、全运动的视频，但是，它需要依赖附加的硬件。而且，由于MJPEG不是一个标准化的格式，各厂家都有自己版本的MJPEG，双方的文件无法互相识别。 MJPEG的优点是画质还比较清晰，缺点是压缩率低，占用带宽很大。一般单路占用带宽2M左右。 2）H.263 H.263 视频编码标准是专为中高质量运动图像压缩所设计的低码率图像压缩标准。 H.263 采用运动视频编码中常见的编码方法，将编码过程分为帧内编码和帧间编码两个部分。埃帧内用改进的DCT 变换并量化，在帧间采用1/2 象素运动矢量预测补偿技术，使运动补偿更加精确，量化后适用改进的变长编码表（VLC）地量化数据进行熵编码，得到最终的编码系数。 H.263标准压缩率较高，CIF格式全实时模式下单路占用带宽一般在几百左右，具体占用带宽视画面运动量多少而不同。缺点是画质相对差一些，占用带宽随画面运动的复杂度而大幅变化。 3）MPEG-1 VCD标准。

图像压缩算法

《算法设计与分析》课程报告 姓名：文亮 学号：201322220254 学院：信息与软件工程学院 老师：屈老师；王老师

算法实现与应用——《算法设计与分析》课程报告 一． 基本要求 1. 题目: 图像压缩 2. 问题描述 掌握基于DCT 变换的图像压缩的基本原理及其实现步骤；对同一幅原 始图像进行压缩，进一步掌握DCT 和图像压缩。 3. 算法基本思想 图像数据压缩的目的是在满足一定图像质量的条件下，用尽可能少的比特数来表示原始图像，以提高图像传输的效率和减少图像存储的容量，在信息论中称为信源编码。图像压缩是通过删除图像数据中冗余的或者不必要的部分来减小图像数据量的技术，压缩过程就是编码过程，解压缩过程就是解码过程。压缩技术分为无损压缩和有损压缩两大类，前者在解码时可以精确地恢复原图像，没有任何损失；后者在解码时只能近似原图像，不能无失真地恢复原图像。 假设有一个无记忆的信源,它产生的消息为{}N ≤≤i a i 1,其出现的概率是已知的,记为()i a p 。则其信息量定义为: ()()i i a p a log -=I 由此可见一个消息出现的可能性越小，其信息量就越多，其出现对信息的贡献量越大，反之亦然。 信源的平均信息量称为“熵”（entropy ），可以表示为： ()()[]()()∑∑==-=?=H N i i i N i i i a p a p a p I a p 1 1 log 对上式取以2为底的对数时，单位为比特（bits ）： ()()∑=-=H N i i i a p a p 1log 根据香农（Shannon ）无噪声编码定理，对于熵为H 的信号源，对其进行无

极限压缩文件方法

极限压缩文件方法 介绍如何使1G的文件压缩到1M的文件。 1.常见文件压缩 首先我们用WinRAR的最高压缩率对常见的文本文件、程序文件和多媒体文件进行压缩，其压缩结果如下(见图1): 压缩后分别还是挺大的 从上图可以看出，多媒体文件压缩比最低，与原文件相差无几，而文本文件和程序文件压缩比要高一些，最高达到3:1，从实际经验来看，我们平时常见的文件压缩比都在10倍以下。 那么，再来看看这个RAR压缩包(见图2)，注意其中的原文件大小和压缩后的包裹大小分别为16777215和18407，这是多大的比例？笔者用计算器算了一下，约等于911:1，接近1000倍的压缩比！这是怎么回事？真的假的？跟我一起继续做下面的试验就明白了。 这个简直是不可思议 2.把大象装进瓶子里 这里笔者从自己的电脑里随便找了个文件“数字图像噪声和去除.htm”，这是笔者在浏览网页时使用另存为功能从网上下载的文章，大小为125KB。 第一步:压缩为ZIP文件。右键单击“数字图像噪声和去除.htm”文件，选择

“WinRAR→添加到档案文件”，在压缩选项对话框中选择“档案文件类型”为“ZIP”，“压缩方式”为“最好”(见图3)，单击“确定”开始压缩。可以看到压缩后的“数字图像噪声和去除.zip”文件只有19KB，压缩率还不错，不过仍离我们的目标相去甚远。 第二步:用WinRAR打开“数字图像噪声和去除.zip”，记下“大小”列中显示的原文件大小数值“127594”，打开计算器程序，单击“查看”菜单选择“科学型”，输入数字“127594”，再点击“十六进制”选项将其转换为16进制值，结果是“1F26A”(见图4)。 用科学型计算器认真算一下 第三步:用UltraEdit编辑器打开“数字图像噪声和去除.zip”文件，我们要在文件中找到“1F26A”的数据，不过由于文件中的十六进制数是高低位倒置表示的，所