第十章 数据压缩算法 2021/2/21 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 1 第十章 数据压缩算法
数据压缩 ■将信源所发出的信号用较少的数码表示,减少 容纳给定数据集合的信号空间 所谓信号空间亦即被压缩的对象是指: ■①物理空间,即数据存储介质的尺寸。 ■②时间区间,传输消息集合所需要的时间 ■③电磁频谱区域,如为传输消息的带宽等。 ■信号空间的各种形式相互关联。减少存储空间 就能提高传输效率和节省带宽的占用。 2021/221 计算机算法设计与分析 2
2021/2/21 计算机算法设计与分析 2 数据压缩 ◼ 将信源所发出的信号用较少的数码表示，减少 容纳给定数据集合的信号空间。 ◼ 所谓信号空间亦即被压缩的对象是指： ◼ ①物理空间，即数据存储介质的尺寸。 ◼ ②时间区间，传输消息集合所需要的时间。 ◼ ③电磁频谱区域，如为传输消息的带宽等。 ◼ 信号空间的各种形式相互关联。减少存储空间 就能提高传输效率和节省带宽的占用
可逆压缩和不可逆压缩 ■可逆压缩叫做无失真、无差错编码。压缩后的 数据可以精确地恢复为原来的数据。如ZIP RAR、ARJ、CAB等文件,都是可逆压缩。 ■不可逆压缩叫做失真编码。压缩后的数据不可 能精确地恢复成原始数据。如在计算机中存储 的图片、声音、视频等文件。 ■人的感觉器官本身对于图片、声音、视频中的 某些信息的丢失,是难以察觉的。 ■不可逆压缩技术的标准有:JPEG、MPEG-1 MPEG-2、MPEG-4等,均达到了很高的压缩比。 2021/22 计算机算法设计与分析 3
2021/2/21 计算机算法设计与分析 3 可逆压缩和不可逆压缩 ◼ 可逆压缩叫做无失真、无差错编码。压缩后的 数据可以精确地恢复为原来的数据。如ZIP、 RAR、ARJ、CAB等文件，都是可逆压缩。 ◼ 不可逆压缩叫做失真编码。压缩后的数据不可 能精确地恢复成原始数据。如在计算机中存储 的图片、声音、视频等文件。 ◼ 人的感觉器官本身对于图片、声音、视频中的 某些信息的丢失，是难以察觉的。 ◼ 不可逆压缩技术的标准有：JPEG、MPEG-1、 MPEG-2、MPEG-4等，均达到了很高的压缩比
ASCI码压缩算法 ■数采用不同的基数来表示,长度不同。 般来说,基数较大,长度较短 例娜采厭诎摟是驷轄儒数 钥节衿储,节腚进黻颧裁颈 鯽娃数姬众籌蘧壯进数字 郎迹独,剁懦饗瀜置,此还可以压缩 ■把第八个数的依次放到前7个字节的最高 位上。这样可以压缩62.5%。 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 4 ASCII码压缩算法 ◼ 数采用不同的基数来表示，长度不同。 一般来说，基数较大，长度较短。 例如，十进制的1234是四位，需要四个 字节存储，用16进制数表示为三位， 4D2，只需要两个字节。 ◼ 如果采用100为基数，即每两位十进制数 用一个字节存放，就可以压缩50%。 例如，十进制的1234表示为百进制数， 即12 34，只需要两个字节。 ◼ 但是数字00~99只需要7个比特，每个字 节还有一个比特闲置，因此还可以压缩。 ◼ 把第八个数的依次放到前7个字节的最高 位上。 这样可以压缩62.5%
ASCI码压缩算法 ■1、将原数据的每两位数字作为一组,其 值在00~99之间;然后将它们转化为16进 制,即00~99分别对应于00H-~63H ■2、从第一个16进制数开始, ■3、每8个16进制数为一组,将第8个数字 拆成7个比特,把它们依次放到前面7个 16进制数的最高位上。 ■4、重复第3步,直至完成全部数据为止。 2021/22 计算机算法设计与分析 5
2021/2/21 计算机算法设计与分析 5 ASCII码压缩算法 ◼ 1、将原数据的每两位数字作为一组，其 值在00~99之间；然后将它们转化为16进 制，即00~99分别对应于00H~63H。 ◼ 2、从第一个16进制数开始， ◼ 3、每8个16进制数为一组，将第8个数字 拆成7个比特，把它们依次放到前面7个 16进制数的最高位上。 ◼ 4、重复第3步，直至完成全部数据为止
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算法。它们的思路和字典法颇为相似， 因此，人们将基于这一思路的编码方法称作字 典式编码。字典式编码不但在压缩效果上大大 超过了哈夫曼编码，而且，对于好的实现，其 压缩和解压缩的速度也异常惊人