【算法设计与分析】数据压缩算法.pptVIP

计算机算法设计与分析 第十章数据压缩算法 数据压缩 将信源所发出的信号用较少的数码表示，减少容纳给定数据集合的信号空间。 所谓信号空间亦即被压缩的对象是指： ①物理空间，即数据存储介质的尺寸。 ②时间区间，传输消息集合所需要的时间。 ③电磁频谱区域，如为传输消息的带宽等。 信号空间的各种形式相互关联。减少存储空间就能提高传输效率和节省带宽的占用。 可逆压缩和不可逆压缩 可逆压缩叫做无失真、无差错编码。压缩后的数据可以精确地恢复为原来的数据。如ZIP、RAR、ARJ、CAB等文件，都是可逆压缩。 不可逆压缩叫做失真编码。压缩后的数据不可能精确地恢复成原始数据。如在计算机中存储的图片、声音、视频等文件。 人的感觉器官本身对于图片、声音、视频中的某些信息的丢失，是难以察觉的。 不可逆压缩技术的标准有：JPEG、MPEG-1、MPEG-2、MPEG-4等，均达到了很高的压缩比。 ASCII码压缩算法 数采用不同的基数来表示，长度不同。一般来说，基数较大，长度较短。 ASCII码压缩算法 1、将原数据的每两位数字作为一组，其值在00~99之间；然后将它们转化为16进制，即00~99分别对应于00H~63H。 2、从第一个16进制数开始， 3、每8个16进制数为一组，将第8个数字拆成7个比特，把它们依次放到前面7个16进制数的最高位上。 4、重复第3步，直至完成全部数据为止。 ASCII码压缩算法举例 原数据：1 2 3 4 5 6 7 8 9 1 9 2 9 3 9 4 哈夫曼编码 哈夫曼（D.A.Huffman）于1952年提出一种编码方法，它完全依据字符出现的概率来构造平均长度最短的编码，也称之为最佳编码。 哈夫曼编码的算法 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、怎样选用较短的字符串？如何区分原始信息中就已经存在的用于代替的字符串？ LZ算法 1977 年，Jacob Ziv 和 Abraham Lempel发表了论文《顺序数据压缩的一个通用算法》。1978 年，他们发表了该论文的续篇《通过可变比率编码的独立序列的压缩》。 这两篇论文提出的两个压缩技术被称为 LZ77 和 LZ78算法。它们的思路和字典法颇为相似，因此，人们将基于这一思路的编码方法称作字典式编码。字典式编码不但在压缩效果上大大超过了哈夫曼编码，而且，对于好的实现，其压缩和解压缩的速度也异常惊人。 LZ77算法 LZ77 算法又称为“滑动窗口压缩” ，如下图： LZ77 算法的基本流程 重复进行以下处理，直至所有数据处理完毕： 1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串， 2、如果找到，输出三元符号组(off, len, c)，其中off为窗口中匹配字符串相对窗口边界的偏移，len为可匹配的长度，c为下一个字符；将窗口向后滑动len + 1个字符。 3、如果未找到，输出三元符号组(0, 0, c)，其中c为下一个字符；将窗口向后滑动 1个字符。 LZ77 算法的实例 假设窗口的大小为 10 个字符，我们刚编码过的 10 个字符是：abcdbbccaa，即将编码的字符为：abaeaaabaee。 LZ77 算法的实例 现在将窗口向后滑动3(2+1)个字符，窗口中的内容为：dbbccaaaba，剩余字符为eaaabaee，下一个字符 e 在窗口中没有匹配，我们输出三元组：(0, 0, e)。 LZ77 算法的实例 又将窗口向后滑动 1 个字符，其中内容变为：bbccaaabae。这时发现，要编码的 aaabae 在窗口中存在(off = 4, len = 6)，其后的字符为 e，可以输出：(4, 6, e)。 LZ77 算法的实例 最后又将窗口向后滑动 7 个字符。这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。 LZ77 算法的解压缩 LZ