第四章 数据压缩技术(补充).ppt

信息管理系 第五讲 数据压缩技术 压缩技术分类 压缩技术的应用 压缩技术起源 信息论 D.A.Huffman 接近极限——熵 以色列人 LZW算法 通用数据压缩 多媒体数据压缩 技术准备：什么是熵 技术准备：模型 技术准备：编码 二叉树可以实现前缀编码规则 技术准备：压缩=模型+编码 Shannon-Fano编码 Shannon-Fano编码步骤: Shannon-Fano编码步骤 Shannon-Fano编码步骤 Shannon-Fano编码步骤 Huffman编码 整数位编码与信息熵 Huffman编码的模型选择 算术编码 算术编码 算术编码 算术编码 算术编码 算术编码 自适应模型的阶 阶概念 阶概念 阶概念 字典压缩 字典压缩 字典压缩 字典压缩 LZ77算法 LZ77 算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。 LZ77算法 LZ77算法 LZ77算法 Golomb编码 γ编码 LZ77算法的其他问题 LZSS算法 LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题，但这个解决方案包含有冗余信息。冗余信息表现在两个方面，一是空指针，二是编码器可能输出额外的字符，这种字符是指可能包含在下一个匹配串中的字符。 LZSS算法的思想是如果匹配串的长度比指针本身的长度长就输出指针（匹配串长度大于等于MIN_LENGTH），否则就输出真实字符。另外要输出额外的标志位区分是指针还是字符。 LZSS编码的基本流程 1、从当前压缩位置开始，考察未编码的字符，并试图在滑动窗口中找出最长的匹配字符串，如果匹配串长度len大于等于最小匹配串长度（len = MIN_LENGTH），则进行步骤 2，否则进行步骤 3。 2、输出指针二元组 ( off, len)。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为匹配串的长度，然后将窗口向后滑动 len 个字符，继续步骤 1。 3、输出当前字符c，然后将窗口向后滑动 1 个字符，继续步骤 1。 LZSS编码举例 LZSS算法 在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础，许多后来开发的文档压缩程序都使用了LZSS的思想。例如，PKZip, GZip, ARJ, LHArc和ZOO等等，其差别仅仅是指针的长短和窗口的大小等有所不同。 LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。 第二类词典编码 第二类算法的想法是企图从输入的数据中创建一个“短语词典 (dictionary of the phrases)”，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。 LZ78算法 LZ78的编码思想是不断地从字符流中提取新的字符串(String)，通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流(Char stream)，生成码字流(Code stream)，从而达到压缩数据的目的。 LZ78编码器的输出是码字-字符(W,C)对，每次输出一对到码字流中，与码字W相对应的字符串(String)用字符C进行扩展生成新的字符串(String)，然后添加到词典中。 LZ78编码算法 步骤1：在开始时，词典和当前前缀P都是空的； 步骤2：当前字符C：=字符流中的下一个字符； 步骤3：判断P+C是否在词典中 ? (1) 如果“是”：用C扩展P，让P：= P+C ； ? (2) 如果“否”： ????? ①输出与当前前缀P相对应的码字和当前字符C； ????? ②把字符串P+C添加到词典中； ????? ③令P：=空值； ? (3) 判断字符流中是否还有字符需要编码 ????? ①如果“是”：返回到步骤2； ????? ②如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，然后结束编码。 LZ78编码举例 LZW算法 LZW算法的词典 LZW编码算法 步骤1： 开始时的词典包含所有可能的根(Root)，而当前前缀P