数据压缩,算法的综述.doc

数据压缩的 许申益 摘要：技术在数据通讯和数据应用中都有十分显著的益处。随着和计算机网络通讯技术的普及应用，以及在计算机应用中，应用软件的规模和处理的数据量的，尤其是多媒体技术在计算机通讯领域中的出现，数据压缩的研究越来越引起人们的注意。综述了在数据压缩算法上一些已经取得的成果，其中包括算术编码字典压缩以及Huffman码及其改进。 关键字：数据压缩；；；1.引言 数据压缩技术在数据通讯和数据应用中都有十分显著的益处。Huffman 提出了一种基于统计模型的压缩方法，Ziv Jacob 提出了一种基于字典模型的压缩方法。随着和计算机网络通讯技术的普及应用，以及在计算机应用中，应用软件的规模和处理的数据量的，尤其是多媒体技术在计算机和通讯两个领域中的出现，数据压缩的研究越来越引起人们的注意。本文了在数据压缩算法上的一些已经取得的成果。 主要香农范诺编码基本思想Java 语言内置的优先队列、对象序列化等功能实现了文件压缩器的压缩和解压功能。 2数据压缩算法的分类 可以将数据压缩算法划分为静态的和动态的两类。动态又是又叫做适应性（adaptive）方法，相应的静态方法非适应性方法（non-adaptive）。 是压缩数据之前，对压缩的数据经过预，确定出信源数据的每个符号在编码后对应的（codeword）。这样信息集映像在数据开始之前就固定下来了面动态则是在编码过程中信源信息的输入，根据输入流的变化，不断动态修改编码压缩。这样就省去了统计中的符号需要做的第一遍预扫描。也不必传送编码所用的数据模式。因而数据压缩比静态的方法要优越得多。3.数据压缩技术的理论ABACADA”，4个字符需要两个比特编码，假设A、B、C、D的编码分别是00、01、10 和11，则整个字符串可表示成00010010001100，总长度14个比特。如果A、B、C、D的编码分别是0、10、110 和111，则字符串总长度为12 比特。设计长短不等的编码方案时，必须满足一个字符的编码不能是另一个字符编码的前缀，以保证解码成字符的转换过程中不发生歧义，这种编码称为前缀编码。 4.数据压缩算法 4.1 Huffman编码及其演变(也称为哈弗曼树)，使得带权路径长度WPL = W1L1 + … + WnLn 最小，其中Wi 表示第 i 个字符结点的权重，Li 表示第 i 个字符结点的路径长度。哈弗曼算法流程如下： （1） 每个字符创建一棵二叉树构成一个树集合F= {T1,T2,…Tn}，其中二叉树 Ti 的根结点为权重wi，左右子树为空。 （2） 在树集 F 中选取两颗根结点权值最小的树作为左右子树构成一颗新的二叉树，根结点为左右子树根结点的权重之和。 （3） 在树集 F 中删除这两颗树，把新得到的二叉树加入到 F 中。 （4） 重复步骤 2 和 3，直到 F 中只有一棵树为止。 例如字符串“ABACADA”4 个字符A、B、C、D 的频率分别为4、1、1、1。以字符频率为权重构造最优树。利用最优二叉树，A、B、C、D 的编码分别是0、10、110 和111。这种以字符频率为权重，构造一颗最优二叉树，使得带权路径长度最小的前缀编码方案称为哈弗曼编码。哈弗曼算法保证了高频字符用短编码，低频字符用长编码，到达整体编码长度最短，从而实现文件压缩的目的。 哈弗曼编码方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的”0”或者“1”，将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码。 低位 高位 用霍夫曼编码所得的平均码长为：Σ(码长×出现概率) 上例为：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit 可以算出本例的信源熵为2.61bit，二者已经是很接近了。 4.2 香农-范诺编码方法： 将符号从最大可能到最少可能排序，将排列好的信源符号分化为两大组，使两组的概率和近于相同，并各赋予一个二元码符号“0”和“1”。只要组内有两个或两个以上符号，就以同样的方法重复以上分组，以此确定这些符号的连续编码数字。依次下去，直至每一组只剩下一个信源符号为止。 香农-范诺编码算法步骤： （1）按照符号出现的概率减少的顺序将待编码的符号排成序列。 （2）将符号分成两组，使这两组符号概率和相等或几乎相等。 （3）将第一组赋值为0，第二组赋值为1。 （4）对每一组，重复步骤2的操作。5.文件压缩器的设计与实现 哈弗曼方法为例 文件压缩器主要的功能是压缩和解压，分别