- 1、本文档共128页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
第五章字典編码
第五章 字典编码
迄今为止,我们大多假设符号是独立的
但这对许多常见数据类型来说是不对的
如:文本、图像和源代码文件
基本思想
标识经常出现的符号模式—保存于字典中
对这些常出现的模式采用更有效的编码方式—用其在字典中的索引作为码字
而对其它部分采用缺省(不太有效)的编码方式
以期总的编码效率更高
注意
这对如文本这样的信源是合理的
显然对(接近)随机数据不会有效
例
考虑某英文文本信源
26 字母和6个标点符号
单字符,定长码
5 比特/字符
4字符模式,定长码
20比特/模式 (324 = 220 = 1,048,576)
假设为非均匀分布
字典:256个最常出现的模式,每个用8比特编码
对其它模式用20比特编码
再增加1比特用于指示是上述两种情况中的哪种
例 (2)
若用p 表示使用字典的概率,则比特率为
R = 9p + 21(1-p) = 21 - 12p
压缩 = 21 - 12p 20
= p 0.084
还不太坏
在等概率假设下,p = 0.00025
p越大,性能越好 ? 选择最可能出现的模式存于字典中
为了达到好的性能,需要知道信源的结构信息
有足够的先验信息,? 静态字典
否则,在编码过程中获得信源的知识 ? 自适应字典
静态字典
静态字典
对信源的结构有足够的先验知识时,利用先验知识构造字典
对特定应用特别有效
只对针对其设计的特定应用和数据有效
例:电话号码的区号
例:学校的学生信息表
地 区
长途区号
北京市
010
上海市
021
天津市
022
重庆市
023
沈阳市
024
南京市
025
…
…
乌鲁木齐市
0991
喀什市
0998
自适应字典
有许多场合,开始时不知道要编码数据的统计特性,也不一定允许事先知道它们的统计特性。
字典编码的思路:根据数据本身包含有重复代码的特性
例:吃葡萄不吐葡萄皮,不吃葡萄倒吐葡萄皮
如果用一些简单的代号代替这些字符串,就可以实现压缩,实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是字典。
实用的字典编码算法的核心就是如何动态地形成字典,以及如何选择输出格式以减小冗余。
自适应字典
开始
Jacob Ziv / Abraham Lempel
1977 (LZ77/LZ1), 1978 (LZ78/LZ2)
1984 Terry Welch (LZW)
LZ77 vs. LZ78
两种不同的方法
有很多变种
是很多主流压缩的基础
LZ77
基本方法:字典为先前已编码序列的一部分
有哪些信誉好的足球投注网站缓冲区为当前字典,通常为几千字节
机制:滑动窗口
有哪些信誉好的足球投注网站缓冲区( Search buffer)、前向(look ahead)缓冲区、有哪些信誉好的足球投注网站指针(search pointer)
目标:在有哪些信誉好的足球投注网站缓冲区中,寻找与有哪些信誉好的足球投注网站指针指向的字符串匹配的最长串,并对其进行编码
基本原理:如果某些模式在局部重复出现,能得到更有效的表示
LZ77 (2)
(o)ffset = search ptr - match ptr = 7
(l)ength = 连续匹配的字符数 = 4
(c)odeword = C(‘r’)
编码
o, l, c = 7, 4, C(‘r’)
If |search buff| = S, |A| = A, S + |LA buff| = W
定长码:?log2S? + ?log2W? + ?log2A?
Search pointer
LZ77 编码举例
序列
cabracadabrarrarrad
W = 13, S = 7
|cabraca|dabrar|rarrad
对d,没有匹配的字符串
发送 0, 0, C(d) (可以做得更好?)
|abracad|abrarr|rarrad
|abracad|abrarr|rarrad
|abracad|abrarr|rarrad
|abracad|abrarr|rarrad
发送 7, 4, C(r)
LZ77 编码举例 (2)
|cadabrar|rarrad|
|cadabrar|rarrad|
|cadabrar|rarrad|
发送 3, 3, C(r)
可以做得更好?
发送 3, 5, C(d)!
总结:三种情况
没有匹配
匹配
匹配串超过了有哪些信誉好的足球投注网站缓冲区
LZ77 解码举例
输入
0, 0, C(d) 7, 4, C(r) 3, 5, C(d)
输出
cabraca
解码:0, 0, C(d)
增加一个 ‘d’: c|abracad|
解码: 7, 4, C(r)
从第一个‘a’开始,拷贝4个字母,解码C(r)
cabrac|adabrar|
解码: 3, 5, C(d)
从第一个‘r’开始,拷贝3个字母
cabracada|brarrar|
再拷贝2个字母
cabracad
您可能关注的文档
- 第五章 統计指数.ppt
- 第五章 統计量及其分布.PPT
- 第五章 網际网路配销策略.ppt
- 第五章 老年團体工作.ppt
- 第五章 線性系统的频域分析法.ppt
- 第五章 總体设计.ppt
- 第五章 芳香烴.ppt
- 第五章 茄果類蔬菜栽培.ppt
- 第五章 菜單、工具栏、状态栏和对话框.ppt
- 第五章 視觉与听觉.ppt
- 10《那一年,面包飘香》教案.docx
- 13 花钟 教学设计-2023-2024学年三年级下册语文统编版.docx
- 2024-2025学年中职学校心理健康教育与霸凌预防的设计.docx
- 2024-2025学年中职生反思与行动的反霸凌教学设计.docx
- 2023-2024学年人教版小学数学一年级上册5.docx
- 4.1.1 线段、射线、直线 教学设计 2024-2025学年北师大版七年级数学上册.docx
- 川教版(2024)三年级上册 2.2在线导航选路线 教案.docx
- Unit 8 Dolls (教学设计)-2024-2025学年译林版(三起)英语四年级上册.docx
- 高一上学期体育与健康人教版 “贪吃蛇”耐久跑 教案.docx
- 第1课时 亿以内数的认识(教学设计)-2024-2025学年四年级上册数学人教版.docx
文档评论(0)