8_数据压缩.ppt

* 字典编码压缩 字典编码（dictionary encoding）。压缩后的信息是字典中单词的索引号。 字典编码的基本思想就是给每个词编号，而不是给每个字母（或汉字）编号。 例如，50000个ASCII字符的文字，每个字符8位，共40万bit 50000*8=40万bit 如果它们由平均6个字母长的单词组成，大约8333个单词 如果给每每个单词一个代号，需要14位， 共8333*14=50000/6*14=11.7万bit * 字典编码压缩 【课堂练习2-45】下面是一首外国诗歌，其中包含了许多重复的字母组合。 The Rain Pitter patter Pitter patter Listen to the rain Pitter patter Pitter patter On the window pane 将此诗歌按照图示方法压缩。 * 现在归纳一下字典编码压缩的思想 在文本中查找字母组合，如果这个字母组合曾经出现过（意味着可以被索引），它将被移除并用指针/索引（就像上面练习中画出的箭头和方格）代替。 在计算机上的实现？ （a）标记重复串起点和长度 所画的指示箭头和需要参照的字符串用当前位置与参照字符串的距离和拷贝字符数来表示。 例如，Pitter patter压缩后的结果为Pitter pa（7，4）。其中，7表示从当前位置倒数7个字符（包括空格），4表示把从该处开始的4个字符复制到当前位置。 long＿(5,4)＿ago 解压后? * 字典编码压缩 还可以如何实现？ 在实际应用中，为了加快速度、提高压缩比， 往往采用的并不是文本自参照方法，而是需要使用一个字典来作为文本中出现的字母或单词的参照。 文本将被编码为一个包含了许多字典索引号的数字串。 同时，字典也是随着编码过程的进展而不断扩充的（称为自适应字典编码）。 初始字典仅包含基本字符和单词， 随着压缩过程的进展，信息中包含的更长的单词会逐渐被加入字典， 而新加入的单词又可用在其后的编码过程中。 （b）以空格为单词分隔的字典条目法 * 字典编码压缩 【例2-14】考虑压缩文本：xyx xyx xyx xyx。 首先要有一个包含3个条目的字典：第一个条目是x，第二个是y，第三个是空格。分别记为（1，x），（2，y）和（3，“ ”）。 第1个单词不在字典中,增加条目，字典变成了（1，x），（2，y），（3，“ ”）和（4，xyx），第1个单词xyx编码为121，空格编码为3，结果1213，后面一个单词xyx已在字典中，编码4... 以此类推，整段文本最终编码为121343434。 解压缩时，仍用原始的3条目字典，首先将起始的1213解码为xyx和一个空格。因为xyx形成了一个单词，就将其添加到字典中作为第4个条目。接着发现后面的索引4是指字典中的第4个条目，于是将其解码为xyx，由此得到12134表示的是xyx xyx。按这种方法，最终将121343434解码为原始文本：xyx xyx xyx xyx。 字典条目法 编码：xxyx xxyx yyxy xxyx yyxy xxy 写出字典和编码结果 * * (c)LZW编码 LZW（Lempel-Ziv-Welsh）压缩——也称LZ压缩； 是另一种字典压缩方法 用于RAR压缩和ZIP压缩格式的文件； 图像文件，如GIF和PNG格式的文件。 * (4)差分编码压缩(differential encoding) 比如图像，像素的灰度是连续的 在一片区域中，相邻像素之间灰度值的差别可能很小 如果只记录第一个像素的灰度，其他像素的灰度都用它与前一个像素灰度差来表示，如： 像素灰度：248,250,251,251,252,255 记录为：248,,2,1,0,1,3 表示原灰度值需要8个比特， 而表示灰度差只需要2个比特，这样就实现了压缩。 差分编码的应用是预测编。 压缩算法的应用 文字：字典压缩、Huffman编码 声音：差分编码、预测差分编码 图像：变换编码、行程编码 视频：差分编码、变换编码、行程编码 * 本节掌握 压缩的必要性、可能性 行程编码 信息熵 Huffman编码 平均编码长度 字典编码 重复串起点和长度的方式 以空格为单词分隔的字典条目法 了解 差分编码、图像编码、音视频编码、jpeg,mpeg gif，jpg,mpg * 作业1——算法编写 1.编写算法，将十进制数转换为二进制形式，小数转换不尽时保留8位小数。 例如，将220.625，转换为 101B 　提示，转换后的二进制保存在数组（列表）中　 2. 编写算法，将二进制数转换为十进制进制形式 　　　　例如，101转换为220.625 　提示，输入的二进制用字符串表示，从高位到低位