1. 原理部分:
有两种形式的重复存在于计算机数据中,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 共一千六百多万种可能的情况,一千六百万分之一的概率导致匹配的距离很长,需要二进制数24位来表示这个匹配距离,再加上匹配长度就超过了三个字节,得不 偿失。所以只能压缩掉原始文件中“自然存在的,并非随机的短语式重复倾向”。
2.编码式压缩利用各个单字节使用频率不一样的倾向,使定长编码变为不定长编码,给使用频率高的字节更短的编码,使用频率低的字节更长的编码,起到压缩的 效果。如果把编码式压缩的“结果”按照8位作为1字节,重新统计各字节的使用频率,应该是大致相等的。因为新的字节使用频率是随机的。相等的频率再去变换 字节长短是没有意义的,因为变短的字节没有比变长的字节更多。
=======================================
短语式重复的倾向和字节取值分布不均匀的倾向是可以压缩的基础,两种压缩的顺序不能互换的原因也说了,下面我们来看编码式压缩的要求及方法:
首先,为了使用不定长的编码表示单个字符,编码必须符合“前缀编码”的要求,即较短的编码决不能是较长编码的前缀,反过来说就是,任何一个字符的编码,都不是由另一个字符的编码加上若干位 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 2 9 1
(如果某个节点只有一个子节点,可以去掉这个子节点。)
根
|
+------33------+
| |
+-----32----+ 1
| |
+--21--+ +--11--+
| | | |
6 15 2 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--+ 15 6 9
| |
2 1
这时所有上层节点的数值都大于下层节点的数值,似乎无法再进一步压缩了。但是我们把每一层的最小的两个节点结合起来,常会发现仍有压缩余地。
第二步:把每一层的最小的两个节点结合起来,重新计算相关节点的值。
在上面的树中,第一、二、四三层都只有一或二个节点,无法重新组合,但第三层上有四个节点,我们把最小的3和6结合起来,并重新计算相关节点的值,成为下面这棵树。
根
|
+----------33---------+
| |
+------9-----+ +----24----+
| | | |
+--3--+ 6 15 9
| |
2 1
然后,再重复做第一步。
这时第二层的9小于第三层的15,于是可以互换,有9个字节增长了一位,15个字节缩短了一位,文件总长度又缩短了6位。然后重新计算相关节点的值。
根
|
+----------33---------+
| |
15 +----18----+
| |
+------9-----+ 9
| |
+--3--+ 6
| |
2 1
这时发现所有的上层节点都大于下层节点,每一层上最小的两个节点被并在了一起,也不可能再产生比同层其他节点更小的父节点了。
这时整个文件的长度是 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63
这时可以看出编码式压缩的一个基本前提:各节点之间的值要相差比较悬殊,以使某两个节点的和小于同层或下层的另一个节点,这样,交换节点才有利益。
所以归根结底,原始文件中的字节使用频率必须相差较大,否则将没有两个节点的频率之和小于同层或下层其他节点的频率,也就无法压缩。反之,相差得越悬殊,两个节点的频率之和比同层或下层节点的频率小得越多,交换节点之后的利益也越大。
在这个例子中,经过上面两步不断重复,得到了最优的二叉树,但不能保证在所有情况下,都能通过这两步的重复得到最优二叉树,下面来看另一个例子:
根
|
+---------19--------+
| |
+------12------+ 7
| |
+---5---+ +---7---+
| | | |
+-2-+ +-3-+ +-3-+ +-4-+
| | | | | | | |
1 1 1 2 1 2 2 2
这个例子中,所有上层节点都大于等于下层节点,每一层最小的两个节点结合在了一起,但仍然可以进一步优化:
根
|
+---------19--------+
| |
+------12------+ 7
| |
+---4---+ +---8---+
| | | |
+-2-+ +-2-+ +-4-+ +-4-+
| | | | | | | |
1 1 1 1 2 2 2 2
通过最低一层的第4第5个节点对换,第3层的8大于第2层的7。
到这里,我们得出这样一个结论:一棵最优二叉编码树(所有上层节点都无法和下层节点交换),必须符合这样两个条件:
1.所有上层节点都大于等于下层节点。
2.某节点,设其较大的子节点为m,较小的子节点为n,m下的任一层的所有节点都应大于等于n下的该层的所有节点。
当符合这两个条件时,任一层都无法产生更小的节点去和下层节点交换,也无法产生更大的节点去和上层节点交换。
上面的两个例子是比较简单的,实际的文件中,一个字节有256种可能的取值,所以二叉树的叶子节点多达256个,需要不断的调整树形,最终的树形可能非常复杂,有一种非常精巧的算法可以快速地建起一棵最优二叉树,这种算法由D.Huffman(戴·霍夫曼)提出,下面我们先来介绍霍夫曼算法的步骤,然后再来证明通过这么简单的步骤得出的树形确实是一棵最优二叉树。
相关推荐
zip_的压缩原理与实现.pdf,作者详细介绍了zip_的压缩原理,通俗易懂,值得转载,学习.
java实现zip压缩功能,java实现zip压缩功能,java实现zip压缩功能,java实现zip压缩功能,java实现zip压缩功能,java实现zip压缩功能,java实现zip压缩功能,java实现zip压缩功能,java实现zip压缩功能,java实现zip...
详细的zip压缩算法讲解 鄙人从网上找的呵呵
本文通俗易懂地介绍了Python中的ZIP解压缩操作,涵盖了解压缩的必要性、基本思路以及利用zipfile模块的具体代码实现,既解析了概念,也配合示例讲解了实践操作,全面而细致地讲解了ZIP解压缩的相关知识。 适合人群: ...
Java Zip算法压缩多个文件的例子,具体的实现原理是:先打开文件并读取,然后利用ZipEntry实例化待压缩的条目列表,将ZIP条目列表写入输出流,从源文件得到文件输入流,写入缓冲数据等。相关代码: ...
C#编译原理 目 录 译者序 前言 第1章 概论 1 1.1 为什么要用编译器 2 1.2 与编译器相关的程序 3 1.3 翻译步骤 5 1.4 编译器中的主要数据结构 8 1.5 编译器结构中的其他问题 10 1.6 自举与移植 12 1.7 TINY样本语言与...
1.版本:matlab2019a,内含运行结果,不会运行可私信 2.领域:【图像压缩】 3.内容:基于Kmean实现图像压缩附matlab代码.zip 4.适合人群:本科,硕士等教研学习使用
今天项目要用到zip的加密解密,在网上搜索了好多这方面的资料,发现要么只是贴了一部分代码,要么这里少个jar包那里少个方法,花了2天时间翻阅各种资料后,自己整理了一下代码,引用了5个jar包,调用就一个方法搞定...
经典压缩算法zip的详细解释。文档详细解释了算法的思想,和实现。适合初学者。
基于python实现JPEG图片压缩源码+实验报告+注释拉满(多媒体技术作业).zip 【资源说明】 该程序实现对JPEG压缩,使用的是python2.7版本,python3有所不同,适当修改即可使用。 程序运行方法 直接在jpeg文件夹中 ...
华中科技大学编译原理实验源码一到四,运行makefile文件即可,不过电脑应该先安装c编译器...实验一:词法语法分析器的设计与实现; 实验二:符号表管和语义检查; 实验三:中间代码生成和优化; 实验四:目标代码生成。
压缩文件中视频和代码齐全,其中包含python基础、pytorch基础等入门课程及代码;还有神经网络、卷积神经网络(CNN)、循环神经网络(LSTM)、生成对抗网络(GAN)、强化学习(RL)等进阶课程及代码。不用再到处找...
同时,还介绍了SDN中最重要的系统一SDN控制器实现架构和原理;随后,介绍了SDN而临的各种挑战和可能的应对措施;最后,介绍了如何从现有网络架构演进到SDN架构 本书为华为3位顶级架构师的心血之作,是学习SDN的必备书籍 ...
qt video,从基础开始,第3部分,一共14部分,使用vs2015的addin作为教学工具,很不错的。
通过学习和使用这个项目,用户可以深入了解 PID 控制器的原理和实现方法,掌握飞行器动力学模型的建立与仿真方法,从而提高在控制系统设计与实现方面的能力。 基于Matlab实现PID控制四旋翼仿真(源码+数据)高分...
下载文件的基本原理 Java中的文件下载是通过输入输出流实现的,将远程...Java中可以使用ZipOutputStream类将多个文件压缩成一个zip包,首先创建ZipOutputStream对象,然后逐个添加需要压缩的文件,最后关闭流即可。