压缩的算法都有哪些？

只有最常见的zip的，估计你都要研究上n久了。。。

文本文件一般有zip,rar,

网页文件有htz

视频文件有rm,avi

语音文件有mp3,

图片文件有png,gif,jpg

这些都是文件压缩的。。。。

------------------------------------

ZIP文件的总体格式

分文件头信息+文件压缩数据

中心目录+中心目录记录结束符

1.分文件头信息:

字节数 描述

4 分文件头信息标志(0x04034b50)

2 解压缩所需版本

2 通用比特标志位(置比特0位=加密置比特1位=使用压

缩方式6,并使用8k变化目录,否则使用4k变化目录置比特2位=使用压

缩方式6,并使用3个ShannonFano树对变化目录输出编码,否则使用2个

ShannonFano树对变化目录输出编码,其它比特位未用)

2 压缩方式(0=不压缩,1=缩小,2=以压缩因素1缩小,3=以

压缩因素2缩小,4=以压缩因素3缩小,5=以压缩因素4缩小,6=自展)

2 文件最后修改时间

2 文件最后修改日期

4 32位校验码

4 压缩文件大小

4 未压缩文件大小

2 文件名长

2 扩展段长

? 文件名(不定长)

? 扩展段(不定长)

2.中心目录结构

文件头信息...中心目录记录结束符

文件头:

字节数 描述

4 中心文件头信息标志(0x02014b50)

2 主机 *** 作系统(高位字节表示主机 *** 作系统,低位字

节表示ZIP压缩软件版本号,其值除以10表示主版本号,其值模10表示

次版本号。0=MS-DOS,OS/2 FAT文件系统,1=Ami ga,2=VMS,3=Unix及

变种,4=VM/CMS,5=AtariST,6=OS/2 HPFS,7=Macintosh,8=Z-System,9

=C P/M,10-255未用)

2 解压缩所需版本

2 通用比特标志

2 压缩方式

2 文件最后修改时间(用标准的MS-DOS时间日 期格式

编码)

2 文件最后修改日期

4 32位校验码(使用David Schwaderer的CRC-32算法产

生)

4 压缩文件大小

4 未压缩文件大小

2 文件名长

2 扩展段长

2 文件注释长(分别为文件名长,扩展段,注释 段,小于

64K)

2 磁盘起始号(本文件在磁盘中的起始号)

2 内部文件属性(最低位若置1,表示为ASC文本,否则为

二进制数据,其它位未用)

4 外部文件属性(依赖于主机 *** 作系统)

4 分文件头相对位移

? 文件名(不定长)

? 扩展段(不定长,用于未来扩展,低版本为0长)

? 文件注释(不定长)

3.中心目录记录结束符

字节数 描述

4 中心目录标记结束符(0x06054b50)

2 磁盘号(其中包括中心目录结束记录)

2 磁盘中心目录起始号

2 磁盘中心目录入口总数

2 中心目录入口总数(ZIP文件中的文件总数)

2 整个中心目录大小

4 关于起始磁盘号的中心目录初始偏移

2 ZIP文件注释长度

? ZIP文件注释(不定长)

加密方法

PKZIP中使用的加密方法由Roger Schlafly提供。ZIP文件在解压

缩前必须先解密。每个加密文件具有一个12字节的加密文件头扩展信

息,存储于数据区的起始位置,加密前先设置一个起始值,然后被三个3

2位的密钥加密。密钥被使用者提供的口令初始化。12个字节加密之

后,由PKZIP的伪随机数产生方法,结合PKZIP中使用CRC-32算法对密钥

进行更新。

具体实施分为三步:

1.用口令对三个32位密钥初始化。

K(0)=305419896,K(1)=591751049,K(2)=878082192

循环 for i=0 to length(password)-1

调用更新密钥函数 update_keys(password(i))

结束循环(循环口令长度次)

其中更新密钥函数为:

update_keys(char):

Key(0)=crc32(key(0),char)

Key(1)=Key(1)+(Key(0)&000000ffH)

Key(1)=Key(1)*134775813+1

Key(2)=crc32(Key(2),Key(1)〉〉24)

end update_keys

CRC32函数中,给定一个4字节的CRC值和一个字符,返回一个由CRC

-32算法更新的CRC。具体为:

crc32(c,b)=crc32tab[(c^b)&0xff]^(c>>8),crc32tab[256]的值

为固定的256个4字节数。

2.读取并加密12字节的加密头,再次对密钥进行初始化。

将12个字节的加密头读入缓冲区buffer(0)至buffer(11),循环fo

r i=0 to 11

C=buffer(i)^decrypt_byte()

update_keys(C)

buffer(i)=C

结束循环(循环12次)

其中的decrypt_byte()函数为:

unsigned char decrypt_byte()

local unsigned short temp

temp=Key(2)¦2

decrypt_byte=((temp*(temp^1))>>8)&0xff

end decrypt_byte

该步结束后,缓冲区中最后的二个字节buffer(10)和buffer(11)

将成为加密文件校验码的二个最高位(按低至高顺序存放)。对ZIP加

密文件进行解压缩前,PKUNZIP软件将使用者提供的口令按上述二个步

骤进行处理,得到的结果与校验码的二个高位字节进行比较,只有当提

供了正确的口令时,结果一致,才能进行后续的解压缩过程,否则,PKZI

P报告错误信息,程序自动结束。

3.读取压缩的数据流并以加密密钥对其进行加密。

压缩数据流按下述过程加密:

循环 直至数据流结束

C=数据流的一个字节

temp=C^decrypt_byte()

update_keys(temp)

输出temp

结束循环

到文件压缩大家很容易想到的就是rar,zip等我们常见的压缩格式。然而，还有一种就是大家在学习数据结构最常见到的哈夫曼树的数据结构，以前还不知道他又什么用，其实他最大的用途就是用来做压缩，也是一些rar,zip压缩的祖先，称为哈弗曼压缩（什么你不知道谁是哈弗曼，也不知道哈弗曼压缩，不急等下介绍）。

随着网络与多媒体技术的兴起，人们需要存储和传输的数据越来越多，数据量越来越大，以前带宽有限的传输网络和容量有限的存储介质难以满足用户的需求。

特别是声音、图像和视频等媒体在人们的日常生活和工作中的地位日益突出，这个问题越发显得严重和迫切。如今，数据压缩技术早已是多媒体领域中的关键技术之一。

一、什么是哈弗曼压缩

Huffman(哈夫曼)算法在上世纪五十年代初提出来了，它是一种无损压缩方法，在压缩过程中不会丢失信息熵，而且可以证明Huffman算法在无损压缩算法中是最优的。Huffman原理简单，实现起来也不困难，在现在的主流压缩软件得到了广泛的应用。对应用程序、重要资料等绝对不允许信息丢失的压缩场合，Huffman算法是非常好的选择。

二、怎么实现哈弗曼压缩

哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。

故我们得了解几个概念：

1、二叉树：在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。

2、哈夫曼编码(Huffman Coding)：是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。

三、哈夫曼编码生成步骤：

①扫描要压缩的文件，对字符出现的频率进行计算。

②把字符按出现的频率进行排序，组成一个队列。

③把出现频率最低（权值）的两个字符作为叶子节点，它们的权值之和为根节点组成一棵树。

④把上面叶子节点的两个字符从队列中移除，并把它们组成的根节点加入到队列。

⑤把队列重新进行排序。重复步骤③④⑤直到队列中只有一个节点为止。

⑥把这棵树上的根节点定义为0（可自行定义0或1）左边为0，右边为1。这样就可以得到每个叶子节点的哈夫曼编码了。

既如 (a)、(b)、(c)、(d)几个图，就可以将离散型的数据转化为树型的了。

如果假设树的左边用0表示右边用1表示，则每一个数可以用一个01串表示出来。

则可以得到对应的编码如下：

1-->110

2-->111

3-->10

4-->0

每一个01串，既为每一个数字的哈弗曼编码。

为什么能压缩：

压缩的时候当我们遇到了文本中的1、2、3、4几个字符的时候，我们不用原来的存储，而是转化为用它们的01串来存储不久是能减小了空间占用了吗。（什么01串不是比原来的字符还多了吗？怎么减少？）大家应该知道的，计算机中我们存储一个int型数据的时候一般式占用了2^32-1个01位，因为计算机中所有的数据都是最后转化为二进制位去存储的。所以，想想我们的编码不就是只含有0和1嘛，因此我们就直接将编码按照计算机的存储规则用位的方法写入进去就能实现压缩了。

比如：

1这个数字，用整数写进计算机硬盘去存储，占用了2^32-1个二进制位

而如果用它的哈弗曼编码去存储，只有110三个二进制位。

效果显而易见。

文件压缩原理

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

---