第三章 词典编码.ppt

多媒体技术 词典编码徐家臻 本章内容 词典编码的基本原理LZ77LZ78LZW 基本思想 对于不同长度的符号串都统一用一种记号 token 来表示 以牛津词典为例子 欲编码 DataCompression 这两个英文字 查词典后发现 Data 出现在第271页的第13个字 Compression 出现在第213页的第8个字 因此 可以用 271 13 213 8 这两个记号来表示 DataCompression 所用的词典共有1354页 每页最多不超过64个字 因此每一个记号可以用11位来表示页数 6位原来表示第几个字 共17位 原本若使用8位的ASCII码需要8x16 128个位元 利用这个方法的压缩比为128 34 3 765倍 词典编码 定长编码问题 如果要压缩二进制文件 词典哪里来 词典就是待压缩文件的一部分JacobZiv AbrahamLempel TerryWelchLZ77 LZ78 LZW LZ77 搜索缓冲区searchingbuffer 词典 前向缓冲区look aheadbuffer 数据 匹配指针 编码位置 滑动窗口slidingwindow LZ77 滑动窗口slidingwindow 前向缓冲区look aheadbuffer 数据 下一步编码 编码位置 搜索缓冲区searchingbuffer 词典 LZ77编码步骤 在滑动窗口中寻找与从前向缓冲区第一个符号开始的最大匹配串以三元组 pos len ch 作为对最大匹配串的描述如果匹配成功pos 由前向缓冲区第一个符号开始 从后向前 从右向左 数的索引值 从0开始计数 len 匹配串长度ch 匹配串之后的第一个符号 的编码 窗口向后滑动匹配串长度 1如果匹配失败pos 0 len 0ch 前向缓冲区第一个符号 的编码 窗口向后滑动1 LZ77编码举例 书P25 LZ77编码举例 假设符号串为 cabraca dabrar rarrad 假设窗口大小13 前向缓冲区大小6从前向缓冲区的第一个符号d开始编码 前3项编码 三元组 是什么 0 0 d 7 4 r 3 5 d LZ77解码举例 cabraca 0 0 d 7 4 r 3 5 d 0 0 d cabraca dc abracad LZ77解码举例 7 4 r abracad abracad abracad a abracad ab abracad abr abracad abra abracad abrarabrac adabrar LZ77解码举例 3 5 d adabrar adabrar adabrar r adabrar ra adabrar rar adabrar rarr adabrar rarra adabrar rarradadabra rrarrad LZ77的一些改进 与Huffman相结合 对三元组进行Huffman编码 0 0 x 情况下的三元组很浪费 用1位标志位表示后面的内容是匹配情况还是不匹配情况 可以省掉前两个0占的位数 LZ77编码方法的简单分析 LZ77为什么可以取得较好的压缩效果 它的假设是什么 在临近的地方可能出现相似的片段如果相似片段总是间隔较远怎么办 LZ78编码 用二元组 i c 编码i 词典索引c 下一个符号步骤 开始时词典为空 i 1 从待编码读入符号从词典中寻找最大匹配片段 如找到 假设对应片段的词典索引为ik 匹配片段为pn 后一个符号cn 输出 ik cn 将片段pncn加入词典第i项如未找到 输出 0 cn 将片段cn加入词典第i项i i 1 继续向后读入符号 LZ78举例 wabba wabba wabba wabba woo woo woo LZW LZ78的改进去掉了编码 i c 中的c LZW编码举例 wabba wabba wabba wabba woo woo woo 1 首先将所有可能出现的单个符号填入词典 LZW编码举例 wabba wabba wabba wabba woo woo woo 2 遇到串的第一符号w 类似LZ78 发现w在词典中 将w和下一个符号a连接起来 作为下一个词条填入词典 同时输出w对应的词典索引5 LZW编码举例 wabba wabba wabba wabba woo woo woo 3 与LZ78不同 从上次匹配字符串的后一个字符a开始处理 将a和下一个符号b连接起来 作为下一个词条填入词典 同时输出a对应的词典索引2 LZW编码举例 wabba wabba wabba wabba woo woo woo 4 按照上述方法继续 输出依次为 5 2 3 3 2 1 LZW编码举例 wabba wabba wabba wabba woo woo woo 5 现在处理到w 注意wa是词典中可以匹配的最大字符串 此时输出wa对应的索引6 同时在词典中添加wa与下一符号b的连接 wab LZW编码举例 wabba wabba wabba wabba woo woo woo 6 列出更多的输出 523321681012911 LZW解码 需要传递词典吗 LZW解码 523321681012911 1 首先将所有可能出现的单个符号填入词典 LZW解码 523321681012911 2 解码首先遇到5 查词典 输出索引5对应的符号w LZW解码 523321681012911 3 解码首先遇到2 查词典 输出索引2对应的符号a 此时 为了模拟编码时创建词典的过程 把a和之前的串w连接起来 加到词典 LZW解码 523321681012911 4 之后依次解码 至6处需要注意 根据我们编码时的规则 解码时先根据6查到wa 然后把片段wa的第一个符号与之前解出一个片段 1对应的 连接 w加入词典 并输出wa LZW解码 523321681012911 5 对8解码 查词典输出为bb 同时把bb的第一个符号b与上一次解码得到的片段wa连接 wab加到词典 以此类推 应用 winzip winrar