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

数据压缩算法的综述S14050428 许申益摘要：数据压缩技术在数据通讯和数据存储应用中都有十分显著的益处。随着数 据传输技术和计算机网络通讯技术的普及应用，以及在计算机应用中，应用软件 的规模和处理的数据量的急剧增加，特别是多媒体技术在计算机通讯领域中的出 现，使数据压缩技术的研究越来越引起人们的注意。本文综述了在数据压缩算法 上一些已经取得的成果，其中包括算术编码、字典式压缩方法以及Huffman码及 其改进。关键字：数据压缩；数据存储；计算机通讯；多媒体技术L引言数据压缩技术在数据通讯和数据存储应用中都有十分显著的益处。在数据的 存储和表示中往往存在一定的冗余度，一些研究者提出了不同的理论模型和编码 技术降低了数据的冗余度。提出了一种基于统计模型的压缩方法，提出了一种基于字典模型的压缩方法。随着数据传输技术和计算机网络通 讯技术的普及应用，以及在计算机应用中，应用软件的规模和处理的数据量的急 剧增加，特别是多媒体技术在计算机和通讯两个领域中的浮现，使数据压缩技术 的研究越来越引起人们的注意。本文综述了在数据压缩算法上的一些已经取得的 成果。本文主要介绍了香农范诺编码以及哈弗曼算法的基本思想，运用其算法的基 本思想设计了一个文件压缩器，用 语言内置的优先队列、对象序列化等功 能实现了文件压缩器的压缩和解压功能。2数据压缩算法的分类普通可以将数据压缩算法划分为静态的和动态的两类。动态方法又是又叫做 适应性(adaptive)方法，相应的，静态方法又叫做非适应性方法(non-adaptive) o静态方法是压缩数据之前，对要压缩的数据经过预扫描，确定出信源数据的都为叶结点都为非叶结点一个叶结点和一个非叶结点对第一种情况 分配两个类型结点存放其权值而作为哈弗曼树的叶结点再分配一个类型结点存放其合并后的权值作为两个类型结点的父亲而成为哈弗曼树的非叶结点然后把该非叶结点进入队列保存同时插入单链表中相应位置 对第二种情况 分配一个 类型结点从队列中取出队首的两个元素分别作该类型结点的左孩子和右孩子然后合并所得新权值进入单链表和对应结点进入队列保存对第三种情况叶结点按第一种情况来操作非叶结点按第二种情况来操作即可图 就是用该算法思想于上例来构树的整个过程。8 .综述数据压缩技术在数据通讯和数据存储应用中都有十分显著的益处。在数据的 存储和表示中往往存在一定的冗余度，一些研究者提出了不同的理论模型和编码 技术降低了数据的冗余度。随着数据传输技术和计算机网络通讯技术的普及应 用，以及在计算机应用中，应用软件的规模和处理的数据量的急剧增加，特别是 多媒体技术在计算机和通讯两个领域中的浮现，使数据压缩技术的研究越来越引 起人们的注意。本文用 语言实现了该文件压缩器。在实现过程中用优先队 列构建哈弗曼树，用对象序列化保存和加载压缩数据的方法简单易用，有一定的 通用性。本文用例举的算法实现的压缩器解压过程比压缩过程慢，但该算法使用 的压缩方法属于无损压缩。9 .参考文献严蔚敏，吴伟民数据结构北京：清华大学出版社,杨学良张占军分布式多媒体计算机系统教程北京电子工业出版孙家骄 欧阳民陈文科 语言程序设计北京 北京大学出版社计算机算法 设计与分析导论影印版 北京高等教育出版社傅祖芸信息论基础理论与应用北京电子工业出版社刘 峰 袁春风 基于的数学表达式等价性的研究计算机应用研每一个符号在编码后对应的码字(codeword)。这样，信息集对码字集的映像在 数据开始之前就已经固定下来了。面动态方法则是在编码过程中，随着信源信 息的输入，根据输入流的变化，不断动态地修改编码压缩。这样就省去了为统 计信源中的符号概率需要做的第一遍预扫描。也不必向编码端传送编码所用 的数据模式。于是动态的数据压缩方法比静态的方法要优越得多。3 .数据压缩技术的理论基础文件压缩的基本思想是对字符设计长度不等的编码方案，对浮现次数多的字符 用尽可能短的编码表示，这样文件的总长度就会降低，实现文件压缩。比如有字 符串“ ”，个字符需要两个比特编码，假设、的编码分别是、 和，则整个字符串可表示成 ，总长度 个比特。如果、 的编码分别是、 和，则字符串总长度为比特。设计长短 不等的编码方案时，必须满足一个字符的编码不能是另一个字符编码的前缀，以 保证解码成字符的转换过程中不发生歧义，这种编码称为前缀编码。4 .数据压缩算法4.1 Huffman编码及其演变哈弗曼算法提出了一种编码方法，使得文本总长度最短。其基本思想是利用 字符的频率作为权重，以字符作为叶结点构造一颗最优二叉树也称为哈弗曼 树，使得带权路径长度 最小，其中 表示第 个字符结点的权重，表示第 个字符结点的路径长度。哈弗曼算法流程如下：()每一个字符创建一棵二叉树构成一个树集合，其中二叉树的根结点为权重，摆布子树为空。()在树集中选取两颗根结点权值最小的树作为摆布子树构成一颗新的二 叉树，根结点为摆布子树根结点的权重之和。()在树集中删除这两颗树，把新得到的二叉树加入到 中。()重复步骤和，直到 中惟独一棵树为止。例如字符串“"个字符、的频率分别为、。以字符频率为权重构造最优树。利用最优二叉树，、 的编码分别是、 和 。这种以字符频率为权重，构造一颗最优二叉树，使得带权路径长度最小 的前缀编码方案称为哈弗曼编码。哈弗曼算法保证了高频字符用短编码，低频字 符用长编码，到达整体编码长度最短，从而实现文件压缩的目的。哈弗曼编码方法：先按浮现的概率大小排队，把两个最小的概率相加，作为 新的概率和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到 最后变成。每次相加时都将“ ”和“ ”赋予相加的两个概率，读出时由该符 号开始向来走到最后的” ”或者“ ”，将路线上所遇到的“ ”和“ ”按最低 位到最高位的顺序排好，就是该符号的霍夫曼编码。哈弗曼编码在信息论中应用举例Q哈弗曼编码在信息论中应用举例高位低位 用霍夫曼编码所得的平均码长为：z码长x浮现概率上例为：X X 义 X X X X可以算出本例的信源端为,二者已是很接近了。香农范诺编码方法:将符号从最大可能到至少可能排序，将罗列好的信源符号分化为两大组，使 两组的概率和近于相同，并各赋予一个二元码符号“0”和“1”。只要组内有两 个或者两个以上符号，就以同样的方法重复以上分组，以此确定这些符号的连续 编码数字。挨次下去，直至每一组只剩下一个信源符号为止。香农范诺编码算法步骤:()按照符号浮现的概率减少的顺序将待编码的符号排成序列。()将符号分成两组，使这两组符号概率和相等或者几乎相等。()将第一组赋值为，第二组赋值为。(4)对每一组，重复步骤2的操作，直至每一组只剩下一个信源符号为止。5 .文件压缩器的设计与实现文件数据在机器内部以二进制形式存在，机器对二进制比特以字节为单位进 行处理。从机器处理层面上来说，对文件数据的压缩就是对字节码形式的数据进 行压缩。文件压缩器的一个设计思想就是对高频字节码用短编码，低频字节码用 长编码，把文件的字节码变换成哈弗曼码，使文件长度变短(以哈弗曼方法为例)。文件压缩器主要的功能是压缩和解压，分别设计压缩类和解压类实现压缩和 解压功能。还有辅助功能的类，如结点类设计、叶结点类设计，用来构建哈弗曼 树。为了方便压缩后的数据保存及解压，需要设计一个压缩结果类，用来保存压 缩结果和哈弗曼码表，在解压过程中必须用压缩过程的哈弗曼码表才干做逆变 换，把压缩数据还原成原来的数据。5.1 结点类设计类表示哈弗曼树的分支结点，类中成员变量包括结点类型、权重、左 子结点和右子结点等记录结点的基本信息数据。类表述如下：结点叶结点左结点右结点权重结点类型类是类的派生类，表示树的叶子结点，成员变量包括字节码及字节码的哈弗曼编码。类表述如下：字节码哈弗曼码5.2 压缩结果类设计类，用来保存压缩后的数据，保存原文件名供解压之后 用，此外还要保存哈弗曼码表，在解压过程从哈弗曼码转换到字节码，必须使用 压缩过程中的哈弗曼码表。类描述如下：哈弗曼码表压缩数据原文件名在具体实现过程中，采用了语言的对象序列化功能，使得保存压缩文件和加载压缩文件的过程变得简单，简化了实现过程。5.3 压缩类设计类该类完成文件加载、统计字节频率、构建哈弗曼树、生成哈弗 曼码和文件压缩等功能。类描述如下：字节码频率字节码的哈弗曼码表文件数据源文件路径目标文件路径压缩结果哈弗曼树初始化变量压缩函数保存压缩文件目标路径加载源文件统计字符频率构建哈弗曼树生成哈弗曼编码生成压缩文件字符串转换成数值优先队列的比较器，按权重比较结点大小函数 完成哈弗曼的构建，算法采用第 节中算法。具体实现 中哈弗曼树用 语言内置的优先队列 类实现，队列中元素按 权重自动排序，需要提供一个按权重比较大小的比较器，实现代码如下：完成对字节码的哈弗曼,其中字节码是的索类型的表示字节O算法伪代码如下：函数编码，生成字节码映射到哈弗曼码表引。由于 语言类型范围是码用作索引时需要作适当的变换，映射成递归终止条件函数生成压缩数据，把文件的字节码映射成哈弗曼码，算法流程如下：()字节码转换为字符形式哈弗曼码。()字符形式哈弗曼码转化为数字形式。遍历哈弗曼表映射成字节码存在子串生成字节文件6 .树型模式匹配在计算机科学与人工智能的许多领域中，模式匹配是最基本的运算之一 .在早 期的应用研究中，其主要内容集中在两个串之间的“彻底匹配”和“一致匹配”. 在许多更复杂的问题中，具有线性结构的串是不能刻划匹配目标和匹配模式，此时 需要借助更复杂的数据结构-树.在这样的结构中，为了和串中的彻底匹配或者一 致匹配相区别，我们引入“结构相容”匹配的概念.一棵目标子树1）与一个模式Pi ”结构相容”，通常是指I;具有与Pi中非叶子节点部份彻底相同的结构，且Pi中的叶子节点与T,中相应部份（可能是叶子节点，也可能是子树）“相容”.例如，有目标子树Tl:xl+x2,T2:y+y,T3:a+bXc 和模式 Pl:x+y,P2:x+x.目标子树 T1,T2 和 T3 都和模式树 P1结构相容,但惟独T2才干和P2结构相容。上面是关于“结构相容”的普通定义,在不同的应用环境中，“相容”的具体定义具有不同的形式.由上面的定义可知，目标子树1;具有与模式树Pi中非叶子节点部份彻底相同的结构，但在哈弗曼树中,不需要1;具有与Pi中非叶子节点部份完 全相同.因此，为了和上面“结构相容”相区别，我们引入“结构基本相容”的概念.一棵目标子树1）与一个模式Pi ”结构基本相容”，是指b具有与Pi中非叶子节点 部份形状相同（但不要求对应节点的具体内容相同）的结构，且Pi中的叶子节点与 T/中相应部份（可能是叶子节点，也可能是子树）“相容”。所以上例中目标T1,T2和 T3和模式P:xopy（op表示任意符号）结构基本相容。7 .改进的哈弗曼编码算法由以上分析可得若由权值最小的两个结点合并成新结点时其权值大于或 者等于其他任意两个或者多个结点的权时所得到的哈弗曼树的高度最低 哈弗曼编码效果最好另一方面哈弗曼编码的普通作法是分两步先构造哈弗 曼树再进行哈弗曼编码如果在构造哈弗曼树的同时就进行哈弗曼编码就将 大大提高算法效率需要充分利用短编码及存储结构的改进。要降低哈弗曼树的高度就应该充分利用短编码在有不少与合并之后得到 的权值相等时特别如此为此对算法的前期工作做出如下调整首先按所有信源符号浮现的概率由小到大排序得到信源符号的概率序列挨次 罗列。然后选择前面两个最小的进行合并假设合并之后得到的概率和为，通常采用顺 序存储结构来存放这些概率值这会导致大量的元素挪移而降低效率方便元素 的插入和删除操作而改为链式存储。此外哈弗曼编码时无须对所有结点进行编码只对哈弗曼树中非叶子结点 进行编码即可因为叶结点是共享非叶结点的如图所示 只对 和 个结 点编码这样既减少了编码结点的个数又缩短编码的长度而且在存储时对叶结 点和非叶结点区别对待会降低存储空间复杂度相应的结构定义如下所示但是 在合并时可能是非叶结点和非叶结点叶结点之间进行合并用一个队列来保 存这些已被合并而得的非叶结点由合并的顺序保证从队首到队尾的元素的权值 挨次递增如果在进行合并时有非叶结点参预就从队列中取出队首元素即可因 此得到如下算法思想 对当前得到的两个权值最小的结点 来自单链表中 和 它们是否叶结点有以下种情况