下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、文章来源 毕业论文网 关于lzw算法的改进研究文章来源 毕业论文网 【摘要】 在分析lzw算法的基础上,对lzw算法的缺陷进行了探讨。并对lzw算法进行了改进,大幅度减少了编码的长度,降低了匹配长度取值变化的影响,完全兼容lzw算法,在平均压缩率方面有较大的提高,而且对改进的算法进行了分析论证。 【关键词】 数据压缩 lzw算法 缓冲区 lzw算法的实质是无损压缩技术1-3,lzw算法通过对输入流进行分析,自适应地生成一个包含输入流中不重复子串的串表,
2、将每一子串映射为一独立的码字输出。这样,它就充分利用了相邻输入之间的相关性,可以取得超过信源一阶熵的编码效率。然而,受缓存容量、计算复杂度和计算速度等因素的限制,串表的长度受到一定限制,且一般信源所具有的局部平稳性随缓存容量加大,编码效率提高不大。即:它自身固有一定的缺陷与不足,难以满足人们的需要,对它进行改进一直成为人们的研究目标之一4-6。为了解决这一问题,本文对lzw算法进行了改进,命名为lzwc编码算法。它兼有lzw算法的优点,还具有自身的优越性。首先对lzw算法进行一些必要的介绍和分析。 1. lz
3、w算法 lzw算法1由韦尔奇(t.a.welch)于1984年通过对lz算法的改进。开发出的一种更优算法。它是一种基于字典的编码方法。并且它是lz系列码中应用最广,变形最多的一种算法。lzw压缩有3个重要的对象:数据流、编码流和编译表。在编码时,数据流是输入对象,编码流就是输出对象;在解码时,编码流则是输入对象,数据流是输出对象;而编译表是在编码和解码时都需要借助的对象。 1.1lzw算法的编码原理
4、 lzw算法的编码原理为:对消息序列xn=x1x2x3…xn从左到右进行阅读,并以此进行lzw编码: (1)对x1显然是第一次出现,它的前面也没有字符,那么他的编号是1,它的码元为(1,0, x1)。 (2)对于x2它可能有两种情况发生,即x1=x2或x1≠x2。对此,有 &
5、nbsp; 如果x1=x2,那么对于x2不作编码,而对x3的编码位点取2,连接位点则为1,这表示对x3作第二次编码,它与第一次编码的x1相连接。 如果x1≠x2,那么x2的编码位点取为2,连接位点则为0,这表示对x2作第二次编码,它的前面没有出现过相同的字符。 (3)依照上述步骤递推,如果对向量xn=x1x2x3…xn,n<m,我们已经得到
6、它的编码:c=(i,li, xji),i=1,2, …, k . 对上式的c满足的条件:对每一个i有且只有一对(i,li),使li<i<ji成立。那么c构成一lzw树。由树的构造可知,对每个点i,它的枝li是唯一的。因此,树c的全部枝为li,i=0,1,…,k 确定,而且每个li与xn中的子向量xαi对应。 (4)如向量xn中的编码c及相应的树确定,那么我们就可
7、读xn+1,xn+2,…, xn+k,并对它们继续进行编码,如果有一个ik使xαi=(xn+1,xn+2,…, xn+k)成立,而且对任何ik都有:xαi≠( xn+1,xn+2,…, xn+k,xn+k+1)成立。那么: 不对字符xn+1,xn+2,…, xn+k进行编码。 对xn+k+1作它的编码为(k+1,i, xn+k+1)。 &n
8、bsp; 以此类推,就可以完成对xn的编码c。 2.2 lzw算法的原理 lzw算法通过编码表来组织输人字符串,并把它们转换成一定长度的编码。lzw算法有一个重要的特性称作前缀性,即如果一个字符串在编码表上,那它的前缀串也在编码表上。例如:a、b为两个不同的字符串,ab组成一新的字符串,a为b的前缀串,如果b在编码表中,则一定在编码表中。 &
9、nbsp; lzw通过编码表识别源输人字符序列,通过向编码表中增加新的字符串,从而识别更多、更长的字符序列。但由于前缀性的约束,这种识别一般每次只在原来的基础上增加一个字符,依次进行。同时,由于编码算法没有很强的分析功能,使它不知道哪些字符序列将来出现的概率较大,所以它具有一定的盲目性。例如,有一个长度为n的字符序列,lzw编码表要完全识别它,则至少需要该序列部分或全部重复出现n次。但是,当一个较长的字符串重复出现两次,我们就能够容易识别它,而且这样的字符串再次出现的概率是非常大的。基于这样一种认识,本文在lzw算法的基础上,构造了一
10、种新的编码算法,我们把新算法称为lzwc编码算法,一般情况下它对数据的压缩率比lzw算法有大幅度提高。新算法在最差的情况下可退化成标准的lzw算法。下面对lzwc算法的原理进行详细的介绍。 2 lzwc算法 lzwc算法的基本原理是针对源输人数据中不同特点的数据序列,采用不同的编码器分别编码。数据序列的分类则是根据它的特点,通过对原始数据序列的分析来完成。 &nbs
11、p; lzwc算法共有两个编码器,它们是: (1) 重复编码器(repeatcorder),简称rc。 (2) lzw编码器。 rc对输入流中重复的数据进行编码,剩下的数据由则由lzw编码器进行编码。rc编码器和lzw编码器的编码通过lzw编码器的编码表统一起来。 2.1 lzwc算法的编码及原理 lzwc的算法过程如下: 对消息序列xn=x1x2x3…xn从左到右进行阅读,并以此进行lzwc编码:
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 七夕节微信的文案大全
- 绍兴市柯桥区部分机关事业单位编外和国企考试试卷及答案
- 瓶子问题教学设计
- 《秋天的雨》教学设计
- 三八妇女节商场策划书4篇
- 范文新学期学习计划模板6篇
- 新学期计划集合5篇资料
- 父母感恩演讲稿范文汇编8篇
- 房地产逼定及车位销售-副本-副本
- 镍钴冶炼厂生产设备故障排除与预防考核试卷
- 小儿疝气的课件
- 技能认证叉车司机高级考试(习题卷3)
- 《中国古代音乐史》课件
- 教育部研究生、本科、高职学科分类及专业目录
- (浙江专版)2023-2024学年五年级上册期中模拟测评卷一
- 酒窖土方开挖施工方案范本
- 全国优质课一等奖教师信息化教学设计和说课大赛高中物理高一《力的合成与分解》赛课课件
- 钬激光碎石术后护理查房
- 肾性贫血络病的中医辨治
- 彩钢棚车棚施工方案
- 中国古代文学史PPT完整PPT完整全套教学课件
评论
0/150
提交评论