基于字典的编码，介绍lzw等压缩算法_基于字典的压缩资源-CSDN文库

共3个文件

ppt：2个

pdf：1个

5星 · 超过95%的资源需积分: 11 27 浏览量 2010-03-23 23:10:36 上传评论 1 收藏 1.3MB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

package

字典编码.rar （3个子文件）

folder

字典编码

第五章字典编码.pdf 1.67MB

4.5 基于字典的编码.ppt 297KB

第五章字典编码.ppt 1.56MB

1

第五章字典编码

 迄今为止，我们大多假设符号是独立的

 但这对许多常见数据类型来说是不对的

 如：文本、图像和源代码文件

 基本思想

 标识经常出现的符号模式—保存于字典中

 对这些常出现的模式采用更有效的编码方式—用其在字典中的索

引作为码字

 而对其它部分采用缺省（不太有效）的编码方式

 以期总的编码效率更高

 注意

 这对如文本这样的信源是合理的

 显然对（接近）随机数据不会有效

2

例

 考虑某英文文本信源

 26 字母和6个标点符号

 单字符，定长码

 5 比特/字符

 4字符模式，定长码

 20比特/模式 (32

4

= 2

20

= 1,048,576)

 假设为非均匀分布

 字典：256个最常出现的模式，每个用8比特编码

 对其它模式用20比特编码

 再增加1比特用于指示是上述两种情况中的哪种

3

例 (2)

 若用p 表示使用字典的概率，则比特率为

R = 9p + 21(1-p) = 21 - 12p

 压缩 <=> 21 - 12p < 20

=> p > 0.084

 还不太坏

 在等概率假设下，p = 0.00025

 p越大，性能越好  选择最可能出现的模式存于字典中

 为了达到好的性能，需要知道信源的结构信息

 有足够的先验信息， 静态字典

 否则，在编码过程中获得信源的知识  自适应字典

4

静态字典

 静态字典

 对信源的结构有足够的先验知识时，利用先验知识构

造字典

 对特定应用特别有效

 只对针对其设计的特定应用和数据有效

 例：电话号码的区号

 例：学校的学生信息表

地区长途区号

北京市

010

上海市

021

天津市

022

重庆市

023

沈阳市

024

南京市

025

… …

乌鲁木齐市

0991

喀什市

0998

5

自适应字典

 有许多场合，开始时不知道要编码数据的统计特性，也不一

定允许事先知道它们的统计特性。

 字典编码的思路：根据数据本身包含有重复代码的特性

 例：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮

 如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上

就是利用了信源符号之间的相关性。字符串与代号的对应表就是字

典。

 实用的字典编码算法的核心就是如何动态地形成字典，以及如何选

择输出格式以减小冗余

。

内容反馈

xueyumicheng

2014-02-26

不错，很好的字典编码算法

a252744386

粉丝: 5
资源: 6

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip