多媒体技术3编码qdu.ppt

赫夫曼编码基本思想 在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 练习 假定用于通信的电文由8个字母A B C D E F G H 组成,各字母在电文中出现的概率为 5% 、25%、4%、7%、9%、12%、30%、8%，试为这8个字母设计赫夫曼编码？ 概率估计 在给定符号集和符号概率的情况下，算术编码可以给出接近最优的编码结果。使用算术编码的压缩算法通常先要对输入符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。 LZW算法 首先建立一个字符串表（词典） ，把每一个第一次出现的字符串放入串表中，并用一个数字来表示 压缩文件只存贮数字，而不存贮串，从而使压缩效率得到较大的提高 不管是在压缩还是解压缩的过程中都能正确的建立这个串表，压缩或解压缩完成后，这个串表又被丢弃 例 如print 字符串，如果在压缩时用266表示，只要再次出现，均用266表示，并将print字符串存入串表中，在解码时遇到数字266，即可从串表中查出266所代表的字符串print，在解压缩时，串表可以根据压缩数据重新生成。 LZW与LZ78算法 LZW算法使用的术语与LZ78相同，仅增加了前缀根(Root)，它是由单个字符串组成的缀-符串(String)。 在编码原理上，LZW与LZ78相比有如下差别： LZW在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)。 由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-character prefix)，因此在词典中有哪些信誉好的足球投注网站的第1个缀-符串有两个字符。 LZW编码算法 步骤1：将词典初始化为包含所有可能的单字符，当前前缀P初始化为空。 一个字符串可以由(A,B)两部分来组成，A是前缀,B是后缀,当A长度为0的时候，代表Root，根。 步骤2：当前字符C=字符流中的下一个字符。 步骤3：判断P＋C是否在词典中 （1）如果“是”，则用C扩展P，即让P=P＋C（新前缀），返回到步骤2。 （2）如果“否”，则 输出与当前前缀P相对应的码字W（编码）； 将P＋C添加到词典中； 令P=C（后缀变前缀），并返回到步骤2 LZW算法的伪代码实现 1 STRING = get input character 2 WHILE there are still input characters DO 3 CHARACTER = get input character 4 IF STRING+CHARACTER is in the string table then 5 STRING = STRING+character 6 ELSE 7 output the code for STRING 8 add STRING+CHARACTER to the string table 9 STRING = CHARACTER 10 END of IF 11 END of WHILE 12 output the code for STRING 小结 理解无损压缩和常用无损压缩算法。 信息论方面的知识给出了数据压缩的理论基础。 熵是一种具有统计特性的平均信息量。 算术编码具有比哈夫曼编码更好的压缩率 几种典型的无损压缩算法在多媒体数据压缩中都有应用。 * 算术编码过程举例 符号 A B C D? 概率 0.1 0.4 0.2 0.3? 初始编码间隔 [0，0.1） [0.1，0.5） [0.5，0.7) [0.7，1) 消息序列的输入为： C A D A C D B * 编码过程 步骤 输入符号 编码间隔 编码判决 1 C [0.5，0.7) 符号的间隔范围[0.5，0.7) 2 A [0.5，0.52) [0.5，0.7)间隔的第一个1/10 3 D [0.514，0.52) [0.5，0.52)间隔的最后3个1/10 4 A [0.514，0.5146) [0.514，0.52)间隔的第一个1/10 5 C [0.5143，0.51442) [0.514，0.5146)间隔的第五个1/10开始，二个1