常用的数据压缩算法有哪些

基本的分为两大类：有损和无损。

有损压缩：主要是一些量化算法，比如a率，u率，lloyds最优量化。

无损压缩：主要是一些编码算法，比如子带编码，差分编码，哈夫曼编码等。

另外时频变换虽然没压缩效果，但是是很好的压缩工具，比如fft，dct等。

最后就是压缩感知稀疏重建等。

只有最常见的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

结束循环

---