第五章字典编码

《第五章字典编码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章字典编码迄今为止，我们大多假设符号是独立的但这对许多常见数据类型来说是不对的如：文本、图像和源代码文件基本思想标识经常出现的符号模式—保存于字典中对这些常出现的模式采用更有效的编码方式—用其在字典中的索引作为码字而对其它部分采用缺省（不太有效）的编码方式以期总的编码效率更高注意这对如文本这样的信源是合理的显然对（接近）随机数据不会有效1例考虑某英文文本信源26字母和6个标点符号单字符，定长码5比特/字符4字符模式，定长码20比特/模式(324=220=1,048,576)假设为非均匀分布字典：256个最常出现的模

2、式，每个用8比特编码对其它模式用20比特编码再增加1比特用于指示是上述两种情况中的哪种2例(2)若用p表示使用字典的概率，则比特率为R=9p+21(1-p)=21-12p压缩<=>21-12p<20=>p>0.084还不太坏在等概率假设下，p=0.00025p越大，性能越好选择最可能出现的模式存于字典中为了达到好的性能，需要知道信源的结构信息有足够的先验信息，静态字典否则，在编码过程中获得信源的知识自适应字典3静态字典静态字典对信源的结构有足够的先验知识时，利用先验知识构造字典对特定应用特别有效只对针对其设计的特

3、定应用和数据有效例：电话号码的区号例：学校的学生信息表地区长途区号北京市010上海市021天津市022重庆市023沈阳市024南京市025……乌鲁木齐市0991喀什市09984自适应字典有许多场合，开始时不知道要编码数据的统计特性，也不一定允许事先知道它们的统计特性。字典编码的思路：根据数据本身包含有重复代码的特性例：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是字典。实用的字典编码算法的核心就是如何动态地形成字典，

4、以及如何选择输出格式以减小冗余。5自适应字典开始JacobZiv/AbrahamLempel1977(LZ77/LZ1),1978(LZ78/LZ2)1984TerryWelch(LZW)LZ77vs.LZ78两种不同的方法有很多变种是很多主流压缩的基础6LZ77基本方法：字典为先前已编码序列的一部分搜索缓冲区为当前字典，通常为几千字节机制：滑动窗口搜索缓冲区(Searchbuffer)、前向（lookahead）缓冲区、搜索指针(searchpointer)目标：在搜索缓冲区中，寻找与搜索指针指向的字符串匹配的最长串

5、，并对其进行编码基本原理：如果某些模式在局部重复出现，能得到更有效的表示7LZ77(2)(o)ffset=searchptr-matchptr=7(l)ength=连续匹配的字符数=4(c)odeword=C(‘r’)编码=<7,4,C(‘r’)>If

6、searchbuff

7、=S,

8、A

9、=A,S+

10、LAbuff

11、=W定长码：log2S+log2W+log2ASearchpointer8LZ77编码举例序列cabracadabrarrarradW=13,S=7

12、cabraca

13、dabrar

14、ra

15、rrad对d，没有匹配的字符串发送<0,0,C(d)>(可以做得更好?)

16、abracad

17、abrarr

18、rarrad

19、abracad

20、abrarr

21、rarrad

22、abracad

23、abrarr

24、rarrad

25、abracad

26、abrarr

27、rarrad发送<7,4,C(r)>9LZ77编码举例(2)

28、cadabrar

29、rarrad

30、

31、cadabrar

32、rarrad

33、

34、cadabrar

35、rarrad

36、发送<3,3,C(r)>可以做得更好?发送<3,5,C(d)>!总结：三种情况没有匹配匹配匹配串超过了搜索缓冲区10LZ77解

37、码举例输入<0,0,C(d)><7,4,C(r)><3,5,C(d)>输出cabraca解码：<0,0,C(d)>增加一个‘d’:c

38、abracad

39、解码：<7,4,C(r)>从第一个‘a’开始，拷贝4个字母，解码C(r)cabrac

40、adabrar

41、解码：<3,5,C(d)>从第一个‘r’开始，拷贝3个字母cabracada

42、brarrar

43、再拷贝2个字母cabracadabr

44、arrarar

45、解码C(d)：cabracadabrarrarard11LZ77编码小结使用固定大小窗口进行词语匹配，而不是在所有已经编码的

46、信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制词典的大小才能保证算法的效率；随着压缩的进程滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。LZ77解码器比编码器简单得多（非对称压缩）维持一个与编码器窗口大小相同的缓冲区，并在缓冲区中找出匹配串，将匹配串