霍夫曼编码霍夫曼编码-复旦大学.PPT

* * * * * * * * * * * * * * * * * * * * * 例子 码字(Code word) 前缀(Prefix) 1 　 … … 193 A 194 B … … 255 　 … … 1305 abcdefxyF01234 … … * LZW编码 LZW编码器就是通过管理这个词典完成输入与输出之间的转换。 LZW编码器的输入是字符流(Char stream)，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流 (Code stream)，码字代表单个字符或多个字符组成的字符串(String)。LZ78输出是码字+字符 C B A B B C B A A 193… * 贪婪分析算法 LZW采用greedy parsing algorithm 每一次分析都要串行地检查来自字符流(Charstream)的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀(Prefix)。 用已知的前缀(Prefix)加上下一个输入字符C也就是当前字符(Current character)作为该前缀的扩展字符，形成新的扩展字符串。 判断新的串是否在词典中 是：继续输入C 否：加入词典，分配码字 * 具体执行步骤 开始时词典包含所有可能的根(Root)，当前前缀P是空的； 当前字符(C) ：=字符流中的下一个字符； 判断缀-符串P+C是否在词典中 如果“是”：P ：= P+C // (用C扩展P) ； 如果“否” ① 把代表当前前缀P的码字输出到码字流; ② 把缀-符串P+C添加到词典; ③ 令P ：= C //(现在的P仅包含一个字符C); * 4. 判断字符流中是否还有字符需要编码 (1) 如果“是”，就返回到步骤2； (2) 如果“否” ① 把代表当前前缀P的码字输出到码字流; ② 结束。 注意：每个输出的码字对应于词典中的一个词条，因为只有当出现新的字符串的时候才输出码字。 * 位置 1 2 3 4 5 6 7 8 9 字符 A B B A B A B A C 步骤 位置 词典 当前字符C 当前前缀P 输出 　 　 (1) A － － 　 　 　 (2) B － － 　 　 　 (3) C － － 　 1 1 (4) A B A B A AB, B (1) 2 2 (5) B B B BB, B (2) 3 3 (6) B A A BA, A (2) 4 4 (7) A B A B A AB ABA, A (4) 5 6 (8) A B A C B A C AB ABA ABAC, C (7) 6 -- -- -- (3) * LZW的特点 1) 对于一段短语，它只输出一个数字，即字典中的序号。（这个数字的位数决定了字典的最大容量，当它的位数取得太大时，比如 24 位以上，对于短匹配占多数的情况，压缩率可能很低。取得太小时，比如 8 位，字典的容量受到限制。所以同样需要取舍。）2) 对于一个短语，比如 abcd ，当它在待压缩文件中第一次出现时，ab 被加入字典，第二次出现时，abc 被加入字典，第三次出现时，abcd 才会被加入字典，对于一些长匹配，它必须高频率地出现，并且字典有较大的容量，才会被最终完整地加入字典。相应地，lz77 只要匹配在“字典区域”中存在，马上就可以直接使用。3) 一个长匹配被加入字典的过程，是从两个字节开始，逐次增长一个字节，确定了字典的最大容量，也就间接确定了匹配的可能的最大长度。 * LZW与LZ77 相对于 lz77 用两个数字来表示一个短语，lzw 只用一个数字来表示一个短语，因此，“字典序号”的位数可以取得多一点（二进制数多一位，意味着数值大一倍），也就是说最长匹配可以比 lz77 更长，当某些超长匹配高频率地出现，直到被完整地加入字典后，lzw将开始弥补初期的低效，逐渐显出自己的优势。 在多数情况下，lz77 拥有更高的压缩率，而在待压缩文件中占绝大多数的是些超长匹配，并且相同的超长匹配高频率地反复出现时，lzw 更具优势，GIF 就是采用了 lzw 算法来压缩背景单一、图形简单的图片。zip 是用来压缩通用文件的，这就是它采用对大多数文件有更高压缩率的 lz77 算法的原因。 第2章 数据无损压缩 参考文献和站点 David Salomon, Data Compress