lz77算法例题

Ⅰ 呵呵，今天咋不见电脑高手呢

winrar的rar文件和winzip的zip文件压缩算法基本相同

zip 的压缩原理与实现
作者: NCS 时间: 2005-01-05 文档类型: 转载 来自: 蓝色理想
浏览统计: total: 563 year: 563 quarter: 329 month: 141 week: 23 today: 5
第 1 页 zip 的压缩原理与实现
第 2 页 编码式压缩的要求及方法
第 3 页 霍夫曼算法
第 4 页 lz77 算法压缩

无损数据压缩是一件奇妙的事情，想一想，一串任意的数据能够根据一定的规则转换成只有原来 1/2 - 1/5 长度的数据，并且能够按照相应的规则还原到原来的样子，听起来真是很酷。
半年前，苦熬过初学 vc 时那段艰难的学习曲线的我，对 MFC、SDK 开始失望和不满，这些虽然不算易学，但和 DHTML 没有实质上的区别，都是调用微软提供的各种各样的函数，不需要你自己去创建一个窗口，多线程编程时，也不需要你自己去分配 CPU 时间。我也做过驱动，同样，有DDK（微软驱动开发包），当然，也有 DDK 的“参考手册”，连一个最简单的数据结构都不需要你自己做，一切都是函数、函数……
微软的高级程序员编写了函数让我们这些搞应用的去调用，我不想在这里贬低搞应用的人，正是这些应用工程师连接起了科学和社会之间的桥梁，将来可以做销售，做管理，用自己逐渐积累起来的智慧和经验在社会上打拼。

但是，在技术上来说，诚实地说，这并不高深，不是吗？第一流的公司如微软、Sybase、Oracle 等总是面向社会大众的，这样才能有巨大的市场。但是他们往往也是站在社会的最顶层的：操作系统、编译器、数据库都值得一代代的专家去不断研究。这些帝国般的企业之所以伟大，恐怕不是“有经验”、“能吃苦”这些中国特色的概念所能涵盖的，艰深的技术体系、现代的管理哲学、强大的市场能力都是缺一不可的吧。我们既然有志于技术，并且正在起步阶段，何必急不可耐地要转去做“管理”，做“青年才俊”，那些所谓的“成功人士”的根底能有几何，这样子浮躁，胸中的规模和格局能有多大？

在我发现vc只是一个用途广泛的编程工具，并不能代表“知识”、“技术”的时候，我有些失落，无所不能的不是我，而是 MFC、SDK、DDK，是微软的工程师，他们做的，正是我想做的，或者说，我也想成为那种层次的人，现在我知道了，他们是专家，但这不会是一个梦，有一天我会做到的，为什么不能说出我的想法呢。那时公司做的系统里有一个压缩模块，领导找了一个 zlib 库，不让我自己做压缩算法，站在公司的立场上，我很理解，真的很理解，自己做算法要多久啊。但那时自己心中隐藏的一份倔强驱使我去寻找压缩原理的资料，我完全没有意识到，我即将打开一扇大门，进入一个神奇的“数据结构”的世界。“计算机艺术”的第一线阳光，居然也照到了我这样一个平凡的人的身上。

上面说到“计算机艺术”，或者进一步细化说“计算机编程艺术”，听起来很深奥，很高雅，但是在将要进入专业的压缩算法的研究时，我要请大家做的第一件事情是：忘掉自己的年龄、学历，忘掉自己的社会身份，忘掉编程语言，忘掉“面向对象”、“三层架构”等一切术语。把自己当作一个小孩，有一双求知的眼睛，对世界充满不倦的、单纯的好奇，唯一的前提是一个正常的具有人类理性思维能力的大脑。
下面就让我们开始一段神奇的压缩算法之旅吧：

1. 原理部分：
有两种形式的重复存在于计算机数据中，zip 就是对这两种重复进行了压缩。
一种是短语形式的重复，即三个字节以上的重复，对于这种重复，zip用两个数字：1.重复位置距当前压缩位置的距离；2.重复的长度，来表示这个重复，假设这两个数字各占一个字节，于是数据便得到了压缩，这很容易理解。
一个字节有 0 - 255 共 256 种可能的取值，三个字节有 256 * 256 * 256 共一千六百多万种可能的情况，更长的短语取值的可能情况以指数方式增长，出现重复的概率似乎极低，实则不然，各种类型的数据都有出现重复的倾向，一篇论文中，为数不多的术语倾向于重复出现；一篇小说，人名和地名会重复出现；一张上下渐变的背景图片，水平方向上的像素会重复出现；程序的源文件中，语法关键字会重复出现（我们写程序时，多少次前后、paste？），以几十 K 为单位的非压缩格式的数据中，倾向于大量出现短语式的重复。经过上面提到的方式进行压缩后，短语式重复的倾向被完全破坏，所以在压缩的结果上进行第二次短语式压缩一般是没有效果的。
第二种重复为单字节的重复，一个字节只有256种可能的取值，所以这种重复是必然的。其中，某些字节出现次数可能较多，另一些则较少，在统计上有分布不均匀的倾向，这是容易理解的，比如一个 ASCII 文本文件中，某些符号可能很少用到，而字母和数字则使用较多，各字母的使用频率也是不一样的，据说字母 e 的使用概率最高；许多图片呈现深色调或浅色调，深色（或浅色）的像素使用较多（这里顺便提一下：png 图片格式是一种无损压缩，其核心算法就是 zip 算法，它和 zip 格式的文件的主要区别在于：作为一种图片格式，它在文件头处存放了图片的大小、使用的颜色数等信息）；上面提到的短语式压缩的结果也有这种倾向：重复倾向于出现在离当前压缩位置较近的地方，重复长度倾向于比较短（20字节以内）。这样，就有了压缩的可能：给 256 种字节取值重新编码，使出现较多的字节使用较短的编码，出现较少的字节使用较长的编码，这样一来，变短的字节相对于变长的字节更多，文件的总长度就会减少，并且，字节使用比例越不均匀，压缩比例就越大。
在进一步讨论编码的要求以及办法前，先提一下：编码式压缩必须在短语式压缩之后进行，因为编码式压缩后，原先八位二进制值的字节就被破坏了，这样文件中短语式重复的倾向也会被破坏（除非先进行解码）。另外，短语式压缩后的结果：那些剩下的未被匹配的单、双字节和得到匹配的距离、长度值仍然具有取值分布不均匀性，因此，两种压缩方式的顺序不能变。
在编码式压缩后，以连续的八位作为一个字节，原先未压缩文件中所具有的字节取值不均匀的倾向被彻底破坏，成为随机性取值，根据统计学知识，随机性取值具有均匀性的倾向（比如抛硬币试验，抛一千次，正反面朝上的次数都接近于 500 次）。因此，编码式压缩后的结果无法再进行编码式压缩。
短语式压缩和编码式压缩是目前计算机科学界研究出的仅有的两种无损压缩方法，它们都无法重复进行，所以，压缩文件无法再次压缩（实际上，能反复进行的压缩算法是不可想象的，因为最终会压缩到 0 字节）。
短语式重复的倾向和字节取值分布不均匀的倾向是可以压缩的基础，两种压缩的顺序不能互换的原因也说了，下面我们来看编码式压缩的要求及方法：
首先，为了使用不定长的编码表示单个字符，编码必须符合“前缀编码”的要求，即较短的编码决不能是较长编码的前缀，反过来说就是，任何一个字符的编码，都不是由另一个字符的编码加上若干位 0 或 1 组成，否则解压缩程序将无法解码。
看一下前缀编码的一个最简单的例子：

符号 编码
A 0
B 10
C 110
D 1110
E 11110

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

1110010101110110111100010 - DABBDCEAAB

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

根(root)
0| 1
+-------+--------+
0 |1 0 | 1
+-----+------++----+----+
||| |
a |d e
0|1
+-----+-----+
| |
b c

要编码的字符总是出现在树叶上，假定从根向树叶行走的过程中，左转为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

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

根
|
+---------33---------+
| |
+----32---+ +----1---+
|| | |
+-21-+ +-11-+ +--1--+
| | | | | |
6 15 29 1

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

根
|
+------33------+
||
+-----32----+ 1
| |
+--21--+ +--11--+
|| ||
6 152 9

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

第一步：如果发现下层节点的数字大于上层节点的数字，就交换它们的位置，并重新计算非叶子节点的值。
先交换11和1，由于11个字节缩短了一位，1个字节增长了一位，总文件缩短了10位。

根
|
+----------33---------+
||
+-----22----++----11----+
| || |
+--21--+ 1 2 9
| |
6 15

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

根
|
+----------33---------+
||
+-----18----+ +----15----+
| | | |
+--3--+ 156 9
| |
2 1

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

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

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

根
|
+----------33---------+
| |
+------9-----+ +----24----+
| | | |
+--3--+ 6159
| |
21

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

根
|
+----------33---------+
||
15 +----18----+
||
+------9-----+ 9
| |
+--3--+6
| |
21

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

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

这时可以看出编码式压缩的一个基本前提：各节点之间的值要相差比较悬殊，以使某两个节点的和小于同层或下层的另一个节点，这样，交换节点才有利益。
所以归根结底，原始文件中的字节使用频率必须相差较大，否则将没有两个节点的频率之和小于同层或下层其他节点的频率，也就无法压缩。反之，相差得越悬殊，两个节点的频率之和比同层或下层节点的频率小得越多，交换节点之后的利益也越大。

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

根
｜
＋－－－－－－－－－19－－－－－－－－＋
｜｜
＋－－－－－－12－－－－－－＋7
｜｜
＋－－－5－－－＋＋－－－7－－－＋
｜｜｜｜
＋－2－＋＋－3－＋＋－3－＋＋－4－＋
｜｜｜｜｜｜｜｜
11121222

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

根
｜
＋－－－－－－－－－19－－－－－－－－＋
｜｜
＋－－－－－－12－－－－－－＋7
｜｜
＋－－－4－－－＋＋－－－8－－－＋
｜｜｜｜
＋－2－＋＋－2－＋＋－4－＋＋－4－＋
｜｜｜｜｜｜｜｜
11112222

通过最低一层的第4第5个节点对换，第3层的8大于第2层的7。
到这里，我们得出这样一个结论：一棵最优二叉编码树（所有上层节点都无法和下层节点交换），必须符合这样两个条件：
1．所有上层节点都大于等于下层节点。
2．某节点，设其较大的子节点为m，较小的子节点为n，m下的任一层的所有节点都应大于等于n下的该层的所有节点。

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

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

·从各个节点中找出最小的两个节点，给它们建一个父节点，值为这两个节点之和。
·然后从节点序列中去除这两个节点，加入它们的父节点到序列中。

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

仍以上面的例子来看霍夫曼树的建立过程。
最初的节点序列是这样的：
a(6) b(15) c(2) d(9) e(1)

把最小的c和e结合起来
| (3)
a(6) b(15) d(9)+------+------+
| |
ce

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

根
|
+-----33-----+
||
15 +----18----+
| |
9 +------9-----+
| |
6 +--3--+
| |
21

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

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

6 15291
6 1593
159 9
1518
33

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

对霍夫曼树的建立过程运用逆推法：
当这个过程中的节点序列只有两个节点时（比如前例中的15和18），肯定是一棵最优二叉树，一个编码为0，另一个编码为1，无法再进一步优化。
然后往前步进，节点序列中不断地减少一个节点，增加两个节点，在步进过程中将始终保持是一棵最优二叉树，这是因为：
1.按照霍夫曼树的建立过程，新增的两个节点是当前节点序列中最小的两个，其他的任何两个节点的父节点都大于（或等于）这两个节点的父节点，只要前一步是最优二叉树，其他的任何两个节点的父节点就一定都处在它们的父节点的上层或同层，所以这两个节点一定处在当前二叉树的最低一层。
2.这两个新增的节点是最小的，所以无法和其他上层节点对换。符合我们前面说的最优二叉树的第一个条件。
3.只要前一步是最优二叉树，由于这两个新增的节点是最小的，即使同层有其他节点，也无法和同层其他节点重新结合，产生比它们的父节点更小的上层节点来和同层的其他节点对换。它们的父节点小于其他节点的父节点，它们又小于其他所有节点，只要前一步符合最优二叉树的第二个条件，到这一步仍将符合。

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

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

附：对于 huffman 树，《计算机程序设计艺术》中有完全不同的证明，大意是这样的：
1．二叉编码树的内部节点（非叶子节点）数等于外部节点（叶子节点）数减1。
2．二叉编码树的外部节点的加权路径长度（值乘以路径长度）之和，等于所有内部节点值之和。（这两条都可以通过对节点数运用数学归纳法来证明，留给大家做练习。）
3．对 huffman 树的建立过程运用逆推，当只有一个内部节点时，肯定是一棵最优二叉树。
4．往前步进，新增两个最小的外部节点，它们结合在一起产生一个新的内部节点，当且仅当原先的内部节点集合是极小化的，加入这个新的内部节点后仍是极小化的。（因为最小的两个节点结合在一起，并处于最低层，相对于它们分别和其他同层或上层节点结合在一起，至少不会增加加权路径长度。）
5．随着内部节点数逐个增加，内部节点集合总维持极小化。

2．实现部分
如果世界上从没有一个压缩程序，我们看了前面的压缩原理，将有信心一定能作出一个可以压缩大多数格式、内容的数据的程序，当我们着手要做这样一个程序的时候，会发现有很多的难题需要我们去一个个解决，下面将逐个描述这些难题，并详细分析 zip 算法是如何解决这些难题的，其中很多问题带有普遍意义，比如查找匹配，比如数组排序等等，这些都是说不尽的话题，让我们深入其中，做一番思考。
我们前面说过，对于短语式重复，我们用“重复距当前位置的距离”和“重复的长度”这两个数字来表示这一段重复，以实现压缩，现在问题来了，一个字节能表示的数字大小为 0 －255，然而重复出现的位置和重复的长度都可能超过 255，事实上，二进制数的位数确定下来后，所能表示的数字大小的范围是有限的，n位的二进制数能表示的最大值是2的n次方减1，如果位数取得太大，对于大量的短匹配，可能不但起不到压缩作用，反而增大了最终的结果。针对这种情况，有两种不同的算法来解决这个问题，它们是两种不同的思路。一种称为 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) 一个长匹配被加入字典的过程，是从两个字节开始，逐次增长一个字节，确定了字典的最大容量，也就间接确定了匹配的可能的最大长度。相对于 lz77 用两个数字来表示一个短语，lzw 只用一个数字来表示一个短语，因此，“字典序号”的位数可以取得多一点（二进制数多一位，意味着数值大一倍），也就是说最长匹配可以比 lz77 更长，当某些超长匹配高频率地出现，直到被完整地加入字典后，lzw将开始弥补初期的低效，逐渐显出自己的优势。
可以看出，在多数情况下，lz77 拥有更高的压缩率，而在待压缩文件中占绝大多数的是些超长匹配，并且相同的超长匹配高频率地反复出现时，lzw 更具优势，GIF 就是采用了 lzw 算法来压缩背景单一、图形简单的图片。zip 是用来压缩通用文件的，这就是它采用对大多数文件有更高压缩率的 lz77 算法的原因。

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

Ⅱ 7Z的压缩算法

7z 已公开了结构编辑功能，所以它可以支持任何一种新的压缩算法。
到目前为止，下列压缩算法已被整合到了 7z 中： 7z压缩格式的算法压缩算法 备注 LZMA 改良与优化后的 LZ77 算法 LZMA2 改良的 LZMA 算法 PPMD 基于 Dmitry Shkarin 的 PPMdH 算法 BCJ 32 位 x86 可执行文件转换程序 BCJ2 32 位 x86 可执行文件转换程序 BZip2 标准 BWT 算法 Deflate 标准 LZ77-based 算法

Ⅲ 哈喽，去年你在知道上求助的lz77算法 java实现，能给我发一份吗非常感谢啊！

DIB设备无关位图文件，这是一种文件格式，

是为了保证用某个应用程序创建的位图图形可以被其它应用程序装载或显示一样。

DIB的与设备无关性主要体现在以下两个方面：DIB的颜色模式与设备无关。
例如，一个256色的DIB即可以在真彩色显示模式下使用，也可以在16色模式下使用。
256色以下(包括256色)的DIB拥有自己的颜色表，像素的颜色独立于系统调色板。
由于DIB不依赖于具体设备，因此可以用来永久性地保存图象。
DIB一般是以*.BMP文件的形式保存在磁盘中的，有时也会保存在*.DIB文件中。

运行在不同输出设备下的应用程序可以通过DIB来交换图象。

Ⅳ LZ77和LZW编码是同一个东西吗

不是，但它们有关系。
Ziv和Lempel于1977年发表的算法被后人称为LZ77算法。
1978年，二人又发表了续篇，被命名为LZ78的压缩算法。
1984年，Welch这个人研究了LZ78算法的变种，因为是W在Z和L两人之后研究出来的，因此叫LZW算法。

LZW申请了专利，但专利在2003年过期了。
现在的几乎所有压缩算法，都是从LZ77发展而来的。
而所谓LZ77编码和LZW编码，就是利用各自的压缩算法，对原字符序列压缩后产生的新的编码。

Ⅳ 求7z算法的原理,详细

7z算法的原理：

简单地说也就是把文件中的重复数据用更简洁的方法表示，例如一个文件中有1000个字母A，那么这将占用1KB的数据空间，如果用压缩算法就可以用1000A来表示，那么它只需要5个字节的数据空间，压缩比达到了200倍。

7z 是一种主流高效的压缩格式，它拥有极高的压缩比。在计算机科学中，7z是一种可以使用多种压缩算法进行数据压缩的档案格式。该格式最初被7-Zip实现并采用，但是这种档案格式是公有的，并且7-Zip软件本身亦在GNU宽通用公共许可证 (GNU LGPL)协议下开放源代码。目前LZMA软件开发工具包的最新版本为V9.34。7z格式的MIME类型为application/x-7z-compressed。

Ⅵ 压缩算法进行字符串压缩

Deflater 是同时使用了LZ77算法与哈夫曼编码的一个无损数据压缩算法。

我们可以使用 java 提供的 Deflater 和 Inflater 类对 json 进行压缩和解压缩，下面是工具类

压缩前的字节长度为：1825
压缩后的字节长度为：284
压缩率为63.73%，压缩后体积为原来的36.27%

压缩前的字节长度为：1825
压缩后的字节长度为：307
压缩率为62.04%，压缩后体积为原来的37.95%，也是不错的！

Ⅶ 我们同学之间传文件常常将文件压缩，我不太明白这中的道例，谁能告诉我这个真能提高传输速度吗

计算机处理的信息是以二进制数的形式表示的，因此压缩软件就是把二进制信息中相同的字符串以特殊字符标记来达到压缩的目的。为了有助于理解文件压缩，请您在脑海里想象一幅蓝天白云的图片。对于成千上万单调重复的蓝色像点而言，与其一个一个定义“蓝、蓝、蓝……”长长的一串颜色，还不如告诉电脑：“从这个位置开始存储1117个蓝色像点”来得简洁，而且还能大大节约存储空间。这是一个非常简单的图像压缩的例子。其实，所有的计算机文件归根结底都是以“1”和“0”的形式存储的，和蓝色像点一样，只要通过合理的数学计算公式，文件的体积都能够被大大压缩以达到“数据无损稠密”的效果。总的来说，压缩可以分为有损和无损压缩两种。如果丢失个别的数据不会造成太大的影响，这时忽略它们是个好主意，这就是有损压缩。有损压缩广泛应用于动画、声音和图像文件中，典型的代表就是影碟文件格式MPEG、音乐文件格式MP3和图像文件格式JPG。

压缩原理
很多人都惊异于压缩技术的神奇，一个文件被压缩成一半大小，何以能无损还原呢？

早期使用的压缩技术都基于统计模型，到20世纪80年代初基于字典压缩的新技术才慢慢推广开来。

数据压缩包含了非常多的软件和硬件技术，这些技术各不相同，但是大多数压缩软件都是基于LZ77、LZ88算法并加以修正而成，而LZ77是字典压缩的起源。大家都知道一个文本文件是由一些单词组成，而且必定有重复现象发生，例如我们这里经常出现的“压缩软件”一词，压缩的原理就是在文件的头部做一个类似字典的东西，把“压缩软件”这个词放在“字典”中，并为这个词指定一个占较少字节数的编码，而文章中的“压缩软件” 一词均用此编码代替，以达到压缩的目的。当然压缩软件在实际运作中并非如此简单，还要使用一些看了就头痛的演算方法，在此就不一一细述。也许有人会问，文本文件可用字典技术，那其它文件怎么办呢。这就无须操心了，因为对于压缩软件来说，一个文件中的“数据压缩”一词和“@#￥%^” 是一样的，关键在于冗余码(重复部分)的多少。

压缩常识
按压缩方式分:有所谓的“透明压缩”和“打包压缩”。

“透明压缩”一般针对.exe和.com文件，直接压缩。成功的话，文件体积变小，功能不变，运行速度还可能更快。但是，这种压缩方法的对象面很窄。如果压缩失败，还会造成文件不可用。所以，这一类程序总是强烈要求用户在压缩前将文件备份。

“打包压缩”就是现在常提到的压缩软件使用的压缩法。它把一个或多个文件压缩成一个文件——压缩包。要使用压缩后的文件，必须先解压将文件复原。它的特点是风险小，适用于减小不常用的文件所占空间和传输数据。当然，按照压缩算法，我们还可以将压缩分成很多种。

一般我们在谈到压缩时，会提到许多相关术语，下面我们就提出一些常见的术语进行解释。

压缩格式:压缩文件时使用的压缩编码方法不同，压缩生成的文件结构就不同，这种压缩文件结构就称压缩格式。

压缩比率:文件压缩后占用的磁盘空间与原文件的比率称压缩比率。在常用的压缩格式中，RAR格式压缩比率较高，ZIP格式较低。但ZIP格式的文件操作速度较快。

解压:将压缩文件还原为本来的文件格式，也称释放、扩展。

压缩包:一般将通用压缩格式的文件称为压缩包，如ZIP格式压缩文件。这种文件可以在压缩工具的管理下对包中压缩的文件进行管理，如查看、删除、添加等。

打包:将文件压缩成通用压缩格式的压缩包文件称为打包，也指将文件压缩添加到压缩包。

多卷压缩:将压缩的文件包分成几个压缩文件称为多卷压缩，一般是为了将压缩文件储存在多个软磁盘上或方便网上传输。

自解压文件:将文件压缩生成可执行的文件，然后在没有压缩工具的帮助下，通过执行压缩的文件，就可将自己的源文件解压还原出来。

压缩文件格式
目前流行着多种压缩文件格式，下面我们就来看看到底有哪些吧！

ZIP:目前最流行的压缩文件格式(在Internet上，ZIP文件已经取得了绝对胜利。在日常操作中，除专门的压缩软件之外，许多文件管理程序，如Windows Commander等也都支持ZIP格式)。我们可利用WinZip对ZIP文件进行解压、释放等操作，还可以用它来处理ARJ、ARC、CAB、LZH等多种不同格式的压缩文件，从而大大地方便了用户的操作。

RAR:是一种高效快速的文件压缩格式，但不被大多数文件压缩程序支持，WinRAR是在Windows下处理RAR格式文件的最好工具。

ARJ:由DOS下曾经红极一时的压缩软件ARJ压缩而成的文件格式，它具有功能强大、压缩率高等优点。到了现在的Windows时代，它已经没有了往日的辉煌。

CAB:是Windows 98新增的一种特殊压缩文件格式，主要用于对有关软件安装盘中的文件进行压缩，其特点是压缩率非常高(可能是目前最高的)，但一经压缩就不能再进行任何增加、删除、替换等修改，也就是说它的压缩包具有“只读”属性。我们也可使用WinZip对CAB压缩包进行操作。

??_:软件安装盘所采用的一种压缩文件方式，如*.ex_、*.dl_、*.d3_等，它们一般由系统直接解压并完成安装工作，无须用户操心。当然，我们也可使用DOS的EXPAND命令对*.??_文件进行释放操作。

UU/UUE:汉字编码方式，它们原本是Unix系统中使用的一种编码方式，后来被改写到DOS中，我们在传送中文邮件时只须事先使用该方式进行编码，此后就能顺利通过只能处理7位编码的邮件服务器，从而解决了汉字的传输问题。

ACE:一种新式的压缩程序，压缩比很高。

另外，MP3、MPEG、JPG等音频、视频、图像格式的文件也都采用了压缩技术，从理论上来说它们也应该算压缩文件，不过它们所采用的压缩方式并不相同，这里简单地介绍一下:

JPEG:JPEG 全名为 Joint Photographic Experts Group，它是一个在国际标准组织(ISO)下从事静态影像压缩标准制定的委员会。它制定出了第一套国标静态影像压缩标准:ISO 10918-1 就是我们俗称的JPEG了。由于JPEG优良的品质，使得它在短短的几年内就获得极大的成功，目前网站上80%的影像都是采用JPEG的压缩标准。

JPEG 2000:正式名称为“ISO 15444”，同样是由JPEG 组织负责制定。JPEG 2000与传统 JPEG 最大的不同，在于它放弃了JPEG所采用的以离散余弦转换为主的区块编码方式，而改以小波转换为主的多解析编码方式。其压缩率比 JPEG高约30%左右，同时支持有损和无损压缩，无损压缩对保存一些重要图片十分有用。

MP3:这个大家应该都认识它了，MP3全称是MPEG 1 Layer 3，是一种高性能的声音压缩编码方案，它可以做出超小“体积”的音乐文件，大小只是原始音频数据的1/10到1/12。但人耳听起来，效果却没有太大差异。它一出世就几乎占领了电脑音乐领域，由于MP3的出现，过去在因特网上半小时才能下载完的一首歌曲，现在以MP3格式仅需短短的几分钟就可以“搞定”。

MPEG:MPEG是Moving Pictures Experts Group(动态图像专家组)的缩写。
现在使用的有4个版本:MPEG-1、MPEG-2、MPEG-3、MPEG-4。

Ⅷ zip 的压缩原理与实现

文件压缩原理

我们使用计算机所做的事情大多都是对文件进行处理。每个文件都会占用一定的磁盘空间，我们希望一些文件，尤其是暂时不用但又比较重要不能删除的文件（如备份文件，有点像鸡肋呀），尽可能少的占用磁盘空间。但是，许多文件的存储格式是比较松散的，这样就浪费了一些宝贵的计算机存储资源。这时，我们可以借助压缩工具解决这个问题，通过对原来的文件进行压缩处理，使之用更少的磁盘空间保存起来，当需要使用时再进行解压缩操作，这样就大大节省了磁盘空间。当你要拷贝许多小文件时，通过压缩处理可以提高执行效率。如果小文件很多，操作系统要执行频繁的文件定位操作，需要花费很多的时间。如果先把这些小文件压缩，变成一个压缩文件后，再拷贝时就很方便了。由于计算机处理的信息是以二进制数的形式表示的，因此压缩软件就是把二进制信息中相同的字符串以特殊字符标记来达到压缩的目的。为了有助于理解文件压缩，请您在脑海里想象一幅蓝天白云的图片。对于成千上万单调重复的蓝色像点而言，与其一个一个定义“蓝、蓝、蓝……”长长的一串颜色，还不如告诉电脑：“从这个位置开始存储1117个蓝色像点”来得简洁，而且还能大大节约存储空间。这是一个非常简单的图像压缩的例子。其实，所有的计算机文件归根结底都是以“1”和“0”的形式存储的，和蓝色像点一样，只要通过合理的数学计算公式，文件的体积都能够被大大压缩以达到“数据无损稠密”的效果。总的来说，压缩可以分为有损和无损压缩两种。如果丢失个别的数据不会造成太大的影响，这时忽略它们是个好主意，这就是有损压缩。有损压缩广泛应用于动画、声音和图像文件中，典型的代表就是影碟文件格式mpeg、音乐文件格式mp3和图像文件格式jpg。但是更多情况下压缩数据必须准确无误，人们便设计出了无损压缩格式，比如常见的zip、rar等。压缩软件（compression software）自然就是利用压缩原理压缩数据的工具，压缩后所生成的文件称为压缩包（archive），体积只有原来的几分之一甚至更小。当然，压缩包已经是另一种文件格式了，如果你想使用其中的数据，首先得用压缩软件把数据还原，这个过程称作解压缩。常见的压缩软件有winzip、winrar等