文档介绍：第十章数据压缩算法
2017/11/10
1
计算机算法设计与分析
数据压缩
将信源所发出的信号用较少的数码表示,减少容纳给定数据集合的信号空间。
所谓信号空间亦即被压缩的对象是指:
①物理空间,即数据存储介质的尺寸。
②时间区间,传输消息集合所需要的时间。
③电磁频谱区域,如为传输消息的带宽等。
信号空间的各种形式相互关联。减少存储空间就能提高传输效率和节省带宽的占用。
2017/11/10
2
计算机算法设计与分析
可逆压缩和不可逆压缩
可逆压缩叫做无失真、无差错编码。压缩后的数据可以精确地恢复为原来的数据。如ZIP、RAR、ARJ、CAB等文件,都是可逆压缩。
不可逆压缩叫做失真编码。压缩后的数据不可能精确地恢复成原始数据。如在计算机中存储的图片、声音、视频等文件。
人的感觉器官本身对于图片、声音、视频中的某些信息的丢失,是难以察觉的。
不可逆压缩技术的标准有:JPEG、MPEG-1、MPEG-2、MPEG-4等,均达到了很高的压缩比。
2017/11/10
3
计算机算法设计与分析
ASCII码压缩算法
数采用不同的基数来表示,长度不同。一般来说,基数较大,长度较短。
例如,十进制的1234是四位,需要四个字节存储,用16进制数表示为三位,4D2,只需要两个字节。
如果采用100为基数,即每两位十进制数用一个字节存放,就可以压缩50%。
例如,十进制的1234表示为百进制数,即12 34,只需要两个字节。
但是数字00~99只需要7个比特,每个字节还有一个比特闲置,因此还可以压缩。
把第八个数的依次放到前7个字节的最高位上。%。
2017/11/10
4
计算机算法设计与分析
ASCII码压缩算法
1、将原数据的每两位数字作为一组,其值在00~99之间;然后将它们转化为16进制,即00~99分别对应于00H~63H。
2、从第一个16进制数开始,
3、每8个16进制数为一组,将第8个数字拆成7个比特,把它们依次放到前面7个16进制数的最高位上。
4、重复第3步,直至完成全部数据为止。
2017/11/10
5
计算机算法设计与分析
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个字节。
2017/11/10
6
计算机算法设计与分析
哈夫曼编码
哈夫曼()于1952年提出一种编码方法,它完全依据字符出现的概率来构造平均长度最短的编码,也称之为最佳编码。
哈夫曼树为在权为wl,w2,…,wn的n个叶子所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为哈夫曼树。
哈夫曼编码中各字符编码的长度不同,它的基本理论基于下列定理:在变长编码中,若各码字长度严格按照所对应的符号出现概率的大小逆序排列,则其平均长度最小。
为了避免产生歧义,编码时必须使得任一字符的编码都不是另外任意字符编码的前缀,这种编码称为前缀编码。
2017/11/10
7
计算机算法设计与分析
哈夫曼编码的算法
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的序列,即该字符的哈夫曼编码。
2017/11/10
8
计算机算法设计与分析
字典法
基本思想是:构造一个字典,将信息中反复出现的字符串,登记为较短的字符串,解码时对这种字符串,通过查字典,转换为原字符串。
该算法的原理很简单,但要真正实现却很困难,因为它存在几个长期困扰着研究者的难点:
1、如何找到这些重复出现的字符串?