数据压缩,算法的综述

《数据压缩,算法的综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、〔据压缩算法的综述S14050428许申益摘要：数据压缩技术在数据通讯和数据存储应用屮都有十分显著的益处。随着数据传输技术和计算机网络通讯技术的普及应用，以及在计算机应用中，应用软件的规模和处理的数据量的急剧增加，尤其是多媒体技术在计算机通讯领域中的出现，使数据缩技术的研究越来越引起人们的注意。木文综述了在数据压缩算法上一些己经取得的成果，_其屮包拈算术编码、字典式压缩方法以及Huffman码及其改进。关键字：数裾压缩；数据存储；计算机通讯；多媒体技术数据压缩技术在数据通讯和数据存储应用屮都冇十分显

2、著的益处。在数据的存储和表示中常常存在一定的冗余度，一些研究者提出了不同的理论模型和编码技术降低了数据的冗余度。Huffman提出了一种基于统计模型的压缩方法，ZivJacob提出丫一种基于字典模型的压缩方法。随着数据传输技术和计算机网络通讯技术的普及应用，以及在计算机应用中，应用软件的规模和处理的数据量的急剧增加，尤其是多媒体技术在计算机和通讯两个领域屮的出现，使数据压缩技术的研究越來越引起人们的注意。本文综述了在数裾压缩算法上的一些已经取得的成果。木文主要介绍Y香农范诺编码以及哈弗曼算法的基木思

3、想，运用其算法的基本思想设计了一个文件压缩器，用Java语言内置的优先队列、对象序列化等功能实现了文件压缩器的压缩和解压功能。2数据压缩算法的分类一般可以将数据压缩算法划分为静态的和动态的两类。动态方法又是又叫做适E、/:性(adaptive)方法，相成的，静态方法又叫做非适皮性方法(non-adaptive)。静态方法是压缩数据之前，对要压缩的数据经过预扫描，确定出信源数据的每个符号在编码后对应的码字(codeword)。这样，信息集对码字集的映像在数据开始之前就已经固定卜*來了。面动态方法则是在

4、编码过程中，随着信源信息的输入，根据输入流的变化，不断动态地修改编码压缩。这样就省去了为统计信源屮的符号概率需要做的第一遍预扫描。也不必向编码端传送编码所用的数据模式。因而动态的数据压缩方法比静态的方法要优越得多。:据压缩技术的理论基础文件压缩的基本思想是对字符设计K度不等的编码方案，对出现次数多的字符用尽可能短的编码表示，这样文件的总长度就会降低，实现文件压缩。比如冇字符申“ABACADA”，4个字符需要两个比特编码，假设A、B、C、D的编码分别是00、01、10和11,则整个字符串可表示成000

5、10010001100,总长度14个比特。如果八、B、C、D的编码分别是0、10、110和111,则字符串总长度为12比特。设计长短不等的编码方案时，必须满足一个字符的编码不能是另一个字符编码的前缀，以保证解码成字符的转换过程屮不发生歧义，这种编码称为前缀编码。4.数据压缩算法4.1Huffman编码及其演变哈弗曼算法提出了一种编码方法，使得文木总长度最短。其基木思想是利用字符的频率作为权重，以字符作为叶结点构造一颗最优二叉树(也称为哈弗曼树)，使得带权路径长度WPL=W1L1+…+WnLn最小，其

6、屮Wi表示第i个字符结点的权重，Li表示第i个字符结点的路径长度。哈弗曼算法流程如卜、(1)每个字符创建一棵二叉树构成一个树集合F={T1，T2,…Tnh艽中二叉树Ti的根结点为权重wi,左右子树为空。(2)在树集F中选取W颗根结点权值最小的树作为左右子树构成一颗新的二叉树，根结点为左右子树根结点的权重之和。(3)在树集F中删除这两颗树，把新得到的二叉树加入到F中。(4)重复步骤2和3,直到F中只有一棵树为止。例如字符串“ABACADA”4个字符A、B、C、D的频率分别为4、1、1、1。以字符频率为

7、权重构造最优树。利用最优二叉树，A、B、C、D的编码分别是0、10、110和111。这种以字符频率为权重，构造一颗最优二叉树，使得带权路径长度最小的前缀编码方案称为哈弗曼编码。哈弗曼算法保证了高频字符用短编码，低频字符用长编码，到达整体编码长度最短，从而实现文件压缩的口的。哈弗曼编码方法：先按出现的概率大小排队，把W个最小的概率和加，作为新的概率和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最£；变成1。每次相加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的

8、”0”或者“1”，将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码。哈弗曼编码在信息论中应用挙例A估利符％概枣刪《字、A0201020J9It2辱1O.1S00030.170013045010301104吻-0.0101114例对以下位源进行哈夫受編码哈弗曼编码在信息论中应用挙例低位高位用霍夫曼编码所得的平均码长为：2（码长X出现概率）M列为：0.2X2+0.19X2+0.18X3+0.17X3+0.15X3+0.1X4+0.01X4