ASCI码压缩算法举例 ■原数据:1234567891929394 ■最后原数据压缩编码的结果为7个16进制的数 据:8C22B8 CE DB DO5D ■存储空间由原来的16个字节变成了7个字节 8C 22 B8 CE 100011001001000101011100‖100110 DB DC SD 110110111101110001011101 2021/22 计算机算法设计与分析 6
2021/2/21 计算机算法设计与分析 6 ASCII码压缩算法举例 ◼ 原数据：1 2 3 4 5 6 7 8 9 1 9 2 9 3 9 4 ◼ 按百进制分组： 12 34 56 78 91 92 93 94 ◼ 转换为16进制： 0C 22 38 4E 5B 5C 5D 5E ◼ 每8个数为一组，将第8个，即5E = 01011110的 7个比特分别填到前7个数的最高位。 00001100 0C 00100010 22 00111000 38 01001110 4E 01011011 5B 01011100 5C 01011101 5D 1 8C 0 1 B8 1 CE 1 DB 1 DC 0 ◼ 最后原数据压缩编码的结果为7个16进制的数 据：8C 22 B8 CE DB DC 5D ◼ 存储空间由原来的16个字节变成了7个字节
哈夫曼编码 去曼帖mm以需4性 度线均魔的甲 本鸡客将猜的樱间,均砖 的基 列定理:在变长编码中,若各码 字长度严格按照所对应的符号出现概率的大小 逆序排列,则其平均长度最小 ■为了避免产生歧义,编码时必须使得任一字符 的编码都不是另外任意字符编码的前缀,这种 编码称为前缀编码。 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 7 哈夫曼编码 ◼ 哈夫曼（D.A.Huffman）于1952年提出一 种编码方法，它完全依据字符出现的概 率来构造平均长度最短的编码，也称之 为最佳编码。 ◼ 哈夫曼树为在权为wl，w2，…，wn的n个叶子 所构成的所有二叉树中，带权路径长度最小(即 代价最小)的二叉树称为哈夫曼树。 ◼ 哈夫曼编码中各字符编码的长度不同，它的基 本理论基于下列定理：在变长编码中，若各码 字长度严格按照所对应的符号出现概率的大小 逆序排列，则其平均长度最小。 ◼ 为了避免产生歧义，编码时必须使得任一字符 的编码都不是另外任意字符编码的前缀，这种 编码称为前缀编码
哈夫曼编码的算法 1.将n个频率为{p1,p2,…,pn}的字符表示为n个 结点,将每个结点看成二叉树T频率p为其 权值w,组成集合F={T,T2 ns ■2.在F中选取两棵权值最小的树作为左、右子 树构造一棵新二叉树,令新二叉树的的权值为 其左、右子树的权值之和 3.在F中删除这两棵树,并加入新的二叉树。 4.重复2和3,直到F中只有一棵树为止 5.约定左、右分支分别为0和1。从根到叶子的 路径的0和1的序列,即该字符的哈夫曼编码 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 8 哈夫曼编码的算法 ◼ 1. 将n个频率为{p1 , p2 , …, pn}的字符表示为n个 结点，将每个结点看成二叉树Ti，频率pi为其 权值wi，组成集合F = {T1 , T2 , …, Tn}。 ◼ 2. 在F中选取两棵权值最小的树作为左、右子 树构造一棵新二叉树，令新二叉树的的权值为 其左、右子树的权值之和。 ◼ 3. 在F中删除这两棵树，并加入新的二叉树。 ◼ 4. 重复2和3，直到F中只有一棵树为止。 ◼ 5. 约定左、右分支分别为0和1。从根到叶子的 路径的0和1的序列，即该字符的哈夫曼编码
字典法 ■基本思想是:构造一个字典,将信息中反复出 现的字符串,登记为较短的字符串,解码时对 这种字符串,通过查字典,转换为原字符串。 ■该算法的原理很简单,但要真正实现却很困难, 因为它存在几个长期困扰着研究者的难点: ■1、如何找到这些重复出现的字符串? ■2、如何找到尽量长的字符串被替代,? ■3、怎样选用较短的字符串?如何区分原始信 息中就已经存在的用于代替的字符串? 2021/22 计算机算法设计与分析 9
2021/2/21 计算机算法设计与分析 9 字典法 ◼ 基本思想是：构造一个字典，将信息中反复出 现的字符串，登记为较短的字符串，解码时对 这种字符串，通过查字典，转换为原字符串。 ◼ 该算法的原理很简单，但要真正实现却很困难， 因为它存在几个长期困扰着研究者的难点： ◼ 1、如何找到这些重复出现的字符串？ ◼ 2、如何找到尽量长的字符串被替代，？ ◼ 3、怎样选用较短的字符串？如何区分原始信 息中就已经存在的用于代替的字符串？
LZ算法 1977年, Jacob ziv和 Abraham Lempel发表了 论文《顺序数据压缩的一个通用算法》。1978 年,他们发表了该论文的续篇《通过可变比率 编码的独立序列的压缩》 ■这两篇论文提出的两个压缩技术被称为LZ77 和LZ78算法。它们的思路和字典法颇为相似, 因此,人们将基于这一思路的编码方法称作字 典式编码。字典式编码不但在压缩效果上大大 超过了哈夫曼编码,而且,对于好的实现,其 压缩和解压缩的速度也异常惊人 2021/221 计算机算法设计与分析 10
2021/2/21 计算机算法设计与分析 10 LZ算法 ◼ 1977 年，Jacob Ziv 和 Abraham Lempel发表了 论文《顺序数据压缩的一个通用算法》。1978 年，他们发表了该论文的续篇《通过可变比率 编码的独立序列的压缩》。 ◼ 这两篇论文提出的两个压缩技术被称为 LZ77 和 LZ78算法。它们的思路和字典法颇为相似， 因此，人们将基于这一思路的编码方法称作字 典式编码。字典式编码不但在压缩效果上大大 超过了哈夫曼编码，而且，对于好的实现，其 压缩和解压缩的速度也异常惊人