logo资料库

LZW压缩算法的改进及其参数优化分析.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.28M 资料格式：pdf 举报 版权申诉
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
资料共6页，全文预览结束
    2 2 2 2 2 3 2 第 17卷第 3期 2005年 6月 Journa l of Chongq ing Un iversity of Posts and Telecomm un ica tion s 重 庆 邮 电 学 院 学报 Vol. 17　No. 3 Jun. 2005 文章编号 : 1004 5694 (2005) 03 0351 05　　 L ZW 压缩算法的改进及其参数优化分析 王泉 , 齐春 , 罗新民 , 梁嵩 (西安交通大学 电子与信息工程学院信息与通信工程系 ,陕西 西安 710049) 摘 　要 :采用数据压缩技术可以有效地提高数据的传输率 。针对 LZW 字典压缩算法 ,提出了新的改进方案 。主要 根据待压缩文件新进输入字符的相关性进行 LRU 表项淘汰及对阈值判断操作进行了改进 ,并对改进算法中出现 的 3个参数进行了单参数优化分析 。最后对改进算法和原有 2种算法的最终压缩比进行了比较 ,实验结果表明 , 改进算法的压缩比优于原有 2种算法 。 关键词 : LZW 算法 ; LRU淘汰原则 ;阈值判断 ;最终压缩比 中图分类号 : TP301. 6　　文献标识码 : A 0　引 　言 数据压缩技术是一种减少数据间冗余度并且增 加数据密度的技术 [ 1 ] , LZW 算法是在 1984年由 T A W elch对 LZ编码中的 LZ78算法修改而成的一种实 用的算法 [ 2 ] 。从理论角度分析 LZW 算法 ,当信息源 长度趋于无穷时 ,数据间的冗余度可以趋向于零 ,因 此 ,我们认为这种压缩算法是渐进最优的 。但是由 于该算法总是给出不同的代码字分配固定长度的整 数 ,并且不考虑信息源的概率分布 ,因此存在着相应 的不足 ,留下了改进该算法的空间 [ 3 ] 。文献 [ 4 ]、文 献 [ 5 ]分别从不同的角度对 LZW 算法进行了改进 , 但是文献 [ 4 ]提出的 LRU淘汰原则在进行淘汰操作 时并没有真实的反映出串表填满后输入字符概率分 布的情况 ,对 LRU淘汰原则中引入的删除表项数这 一参数的取值也没有进行具体的分析 ;文献 [ 5 ]提 出的通过引入阈值判断对 LZW 算法的改进 ,在初始 阈值的选取及阈值判断的具体操作上都存在着不 足 。除此 ,在实际编程实现 LZW 算法时还存在着给 串表中代码字的对应字符串预留内存的问题 。针对 上述 LZW 算法的不足之处 ,提出了新的基于相关 LRU淘汰原则和改进阈值判断操作的 LZW 改进算 法 ,并对改进算法中出现的 3个参数进行了详尽的 单参数优化分析 。 1　L ZW 压缩算法 LZW 压缩算法的基本思想是建立一个编码表 (转换表 ) ,W elch称之为串表 ,将输入字符串映射成 定长的码字输出 ,通常码长设置为 12 bit。LZW 串 表具有“前缀性 ”:假设任何一个字符串 P和某一个 字符 S组成一个字符串 PS,若 PS在串表中 ,则 S为 P的扩展 , P为 S的前缀 。字符串表是动态生成的 , 编码前先将其初始化使其包含所有的单字符串 。在 压缩过程中 ,串表中不断产生压缩信息的新字符串 , 存储新字符串时也保存新字符串 PS的前缀 P相对 应的码字 。在解压缩过程中 ,解码器可根据编码字 恢复出同样的字符串表 ,解出编码数据流 [ 6 ] 。 2　L ZW 改进算法 针对引言所提到的原有 LZW 算法的不足 ,对 LZW 压缩算法进行以下几点改进 。 (1) 针对原算法给不同的代码字分配固定长度 整数的情况 ,改进的算法采用给不同的代码字分配 变长长度整数的方法 。以标准码长为 12 bit的 LZW 压缩算法为例 ,该算法编码表可以容纳 4 096个码 字 。整个编码表分成 5个部分 ,其中 1～256, 257～ 512, 513～1 024, 1 025～2 048, 2 049～4 096分别为 第 1,第 2,第 3,第 4,第 5部分 ,每一部分输出的代 码字长度分别为 8 bit, 9 bit, 10 bit, 11 bit, 12 bit。在 算法中设置 257为变长标示 ,每出现一次代码字长 度的变化便输出一个变长标示 ,以提示解码程序代 码字长度的变化 。串表的图例如图 1所示 。 (2) 针对原算法不考虑信息源概率分布的不 足 ,采用改进的阈值判断操作的方法 。当串表填满 之后 ,不要立即删除表 ,而是输入一定长度的比特数 据流用现有的串表对其进行压缩 ,然后判断这个被 压缩的比特数据流的压缩率 (压缩率的计算公式 为 :数据流的总比特数 /压缩后的数据流比特数 ) , 收稿日期 : 2004 作者简介 :王泉 (1979 04 16　　修订日期 : 2005 01 08 ) ,男 ,硕士研究生 ,主要研究方向为无线局域网 ,移动通信 , E mail: wang. quan1@ zte. com. cn;齐 春 ,博士 ,教授 ,主要研究方向为信号处理 、图像处理与模式识别 。
    ·253· 　　　　　　　　　　　　重 庆 邮 电 学 院 学 报 (自然科学版 ) 　　　　　　　2005年第 3期 图 1　12 bit码长的 LZW 编码表 Fig. 1 Encode table of 12 bit length LZW codes 如果所得到的压缩率大于所指定的阈值 ,则继续先 前的操作 ,再次进行压缩 、判断 ;如果所得到的压缩 率小于所指定的阈值 ,则进行删除串表操作 。阈值 判断操作在原有数据的基础之上对新数据进行操 作 ,在一定程度上考虑到信息源概率分布的情况 ,从 而提高了 LZW 压缩算法的压缩率 ,并且提高了算法 的执行效率 。此处使用的阈值判断方法与文献 [ 5 ] 中使用的阈值判断方法的不同之处在于 :文献 [ 5 ] 在进行阈值判断时 ,初始的阈值选为固定值 1,然后 进行阈值判断 ,在当前压缩率小于先前的阈值时进 行删除表项的操作 ;在当前的压缩率大于先前的阈 值时 ,首先把当前压缩率的值做为新的阈值 ,然后再 继续进行阈值判断的操作 。而改进算法的阈值判断 操作 ,在程序的起始就预先指定一个大于 1的值做 为阈值 ,并且在程序的执行中阈值的取值不发生改 变 。这样操作可以有效地解决文献 [ 5 ]所提出的初 始阈值过低 、阈值逐步增加 、周期过长所导致的短文 件最终压缩效果差的诸多问题 ;同时能够避免阈值 更替的操作 ,提高中等长度文件的压缩效率 ;并且能 够避免对于中 、长文件由于突发数据流与原有串表 相关性过强 ,造成的阈值突增 ,由此导致删除表项操 作 、更新表操作过于频繁 ,造成压缩效率降低的问 题 。 (3)针对原算法不考虑信息源概率分布的不 足 ,在串表填满之后采用相关 LRU 淘汰原则 。首先 在串表中设置清表标志 ,当串表填满后 ,在进行阈值 判断时 ,对每一个代码字的使用情况进行计数 。进 行计数时不同于文献 [ 4 ]采用的 LRU淘汰原则 ——— 只对所使用的代码字计数 ,而是采用相关 LRU 淘汰 原则 ,即在进行字符串的匹配时 ,不仅要对最终匹配 字符串的代码字进行计数 ,还要对在匹配过程中出 现的不是最终匹配字符串的每个过程字符串的代码 字进行计数 。当进行阈值判断所得到的压缩率小于 指定的阈值时 ,发出清表标志 ,这时根据串表中每一 个代码字计数值的大小进行排序 ,对串表进行相应 的重构 ,然后删除排序最后的若干项 。这样做不仅 可以克服文献 [ 4 ]采用的 LRU淘汰原则没有真实的 反映出串表填满后输入字符概率分布情况的不足 , 在一定程度上考虑了新输入数据的概率分布 ,同时 还克服了 LFU 淘汰原则需要过多的考虑先期数据 并且进行反复的比较 、计算的不足 ,提高了算法的运 行速度 。采用相关 LRU淘汰原则 ,可以获得相对于 文献 [ 4 ]更高的最终压缩比和较高的执行效率 。 (4) 在 LZW 压缩算法中 ,为了节省每一个代码 字对应字符串的预留内存 ,同时为了解决当所对应的 字符串过长所造成的精度问题 ,可以采用以代码字加 上单个字符的 ASC II码值来表示匹配字符串的方法。 以标准码长为 12 bit、单个字符串 ASC II码值为 0～ 255的 LZW 压缩算法为例 ,在压缩时 ,对于所有的单 个字符串其匹配字符串的表示值为其 ASC II码值 ,对 于多字符串 (2个字符或者更多 )的匹配字符串的表 示值为最后一个字符的 ASC II码值 ,再加上剩余字符 串所对应的代码字乘以 1 000后的值。在解压缩时 , 根据代码字找到其相应的匹配字符串的表示形式 ,除 以 1 000,如果得到的商 (整数部分 )大于 256,则继续 寻找商所对应匹配字符串的表示形式 ;如果所得到的 商不大于 256,则把商减 1输出其数值所对应的字符。 最终按照先进后出的原则输出字符。LZW 改进压缩 算法的匹配字符串表示方法 (以 12 bit码长的串表为 例 )分为单字符和多字符串 ,而单字符串的匹配字符 串即为匹配字符串 ASC II码值 ,多字符的匹配字符串 = 1 000 ×前缀的 Index +扩展单个字符的 ASC II码 值。这样的代码字表示方法不仅有效地解决了多字 符串 ASC II码值表示的精度问题 ,避免了由于精度问 题所导致的编、译码错误的发生 ;同时也解决了压缩、 解压缩过程中给代码字所对应的匹配字符串预留内 存的问题 ,节省了程序所占用的内存空间 ;还避免了 程序中复杂的表项链查找与清除的操作 ,提高了算法 的执行效率。 3　L ZW 改进算法的参数优化及分析 LZW 改进算法中出现了 3 个参数 ———输入字 符个数 、阈值 、删除表项数 ,对于短文件的压缩 ,由于 文件在串表还没有填充完便已经压缩完毕 ,所以这 3个参数对最终压缩比并不产生影响 。对于中 、长 文件的压缩 ,这 3个参数的选取会在一定程度上影 响到文件的最终压缩比 。下面对上述 3个参数的取 值进行分析 ,以求得其在何种取值下 ,能够得到较优 的最终压缩比 。下文所提到的通过对实验数据进行 3次样条以得到拟和曲线的方法 ,采用非扭结 ( not knot)条件 。具体的拟和条件为 :任意 2个数据点 a 之间的曲线用一个 3次多项数逼近 ,每个三次多项 式的一阶和二阶导数在断点处相等 ,近似多项式通 过这些断点的斜率和曲率连续 ;对于第 1个和最后 1个三次多项式由于其在第 1个和最后 1个断点之 外没有伴随多项式 ,因此要求第 1个和第 2 个三次 多项式的三阶导数相等 ,最后 1个和倒数第 2个三
    王泉 ,等 : LZW 压缩算法的改进及其参数优化分析 ·353· 次多项式的三阶导数也相等 。 3. 1　输入字符个数的取值分析 在进行 LZW 压缩时 ,当串表填满后就要进行阈 值判断 ,这就涉及到输入字符个数的问题 ,输入字符 的数量不能太小 ,如果太小就会造成程序执行效率 的下降 ;输入的字符数量不能太大 ,如果太大则不能 尽快的反应数据的压缩情况从而使得数据文件的最 终压缩比不高 。一般输入字符数的取值范围为 100 ～1 000,为了程序的简洁性 ,一般取值为整数 。 为了获得输入字符个数的最佳参数取值 ,以得 到相应较高的最终压缩比 ,在进行压缩时 ,针对相同 文件 ,先固定阈值和删除表项数这 2个参数 ,对于输 入字符个数的不同取值所得到的最终压缩比进行三 次样条拟和 ,找到其拟和曲线的最大点 ,然后选取最 接近该点所对应的输入字符数的整百数点 ,则该整 百数点为此文件的最优参数点 。A , B 文件在阈值 取为 1. 9,删除表项数为 1 000时变换不同的输入字 符数得到的实验数据见表 1,其拟和曲线如图 2,图 3所示 。 表 1　A , B文件在阈值为 1. 9,删除表项数为 1 000时的最终压缩率的实验结果 Tab. 1 Experiment result of A and B files when threshold is 1. 9 and parameter of deleting table item s is 400 字符数 100 200 300 400 500 600 700 800 700 3. 2744286 4855138 2. 4137806 8002702 3. 2744286 4855138 2. 3995433 5344220 3. 2746054 3128116 2. 3798328 2826601 3. 2754896 3133641 2. 3671675 7389394 3. 2787357 8752005 2. 3519241 7394357 3. 2766103 0378334 2. 3536024 4151453 3. 2760203 8060602 2. 3692079 875346 3. 2784994 8649574 2. 3502225 3403784 3. 2912491 4083131 2. 2917370 3901657 1 000 3. 2863748 0132929 2. 3410095 9806073 数据文件 A文件. txt (22. 2 KB ) B文件. txt (26. 1 KB ) 图 2　A文件在阈值为 1. 9,删除表项数为 图 3　B文件在阈值为 1. 9,删除表项数为 1 000时的输入字符数与最终压缩比的拟和曲线 1 000时的输入字符数与最终压缩比的拟和曲线 Fig. 2 A file’s curve of relation between final comp ression ratio Fig. 3 B file’s curve of the relation between final comp ression and parameter of inputting characters when the parameter ratio and parameter of inputting characters when threshold threshold is 1. 9 and parameter of deleting table item s is 1000 图 2,图 3中 号处标记的点就是最终压缩比取值 最大的点 ,由图 2中的曲线看 ,该点的取值最接近整 百数点 900,所以对于 A 文件. txt在阈值取为 1. 9, 删除表项数为 1 000 时 ,输入字符数为 900 时可以 得到较优的最终压缩比 。同理 ,图 3中的压缩率取 值最大的点最接近 100,所以对于 B文件. txt在阈值 取为 1. 9,删除表项数为 1 000,输入字符个数为 100 时可以得到较优的最终压缩比 。由实验数据可知对 于不同的待压缩数据文件 ,参数输入字符数的优化 取值可能不同 。 (对于图 3,为了能够准确的反映曲 线的走向 ,从而更好的确定输入字符个数参数的优 化取值点 ,在这里又选取了当输入字符个数参数取 值为 50, 75时的两个附加参考点 ,从而更精确的拟 和曲线 。当输入字符个数参数取值为 50, 75时其所 is 1. 9 and parameter of deleting table item s is 1000 得到的最终压缩比分别为 2. 381 203 74 5661 23, 2. 397 645 320 051 98) 。 3. 2　阈值的取值分析 在进行 LZW 压缩时 ,当串表填满后进行阈值判 断时 ,这就涉及到阈值取值的问题 。根据实验结果 分析 ,阈值参数的选取不像输入字符数和删除表项 数 (见 3. 3)这 2个参数 。对于同一个文件 ,阈值参 数的变化对最终压缩率的影响不大 (对 A , B 文件的 实验数据见表 2) ,尤其是中等长度文件 ,这是由于 在一定字符个数输入的情况下当进行阈值判断发现 压缩率小于指定的阈值时 ,便要重新填表 ,文件在还 没有再次填充完串表时便已经被压缩完毕 。对于阈 值参数的选择 ,在实际的压缩过程中可以根据得到 的最终压缩比和程序的执行效率进行折衷的选择 。
    2 ·453· 　　　　　　　　　　　　重 庆 邮 电 学 院 学 报 (自然科学版 ) 　　　　　　　2005年第 3期 表 2　A , B文件在删除表项数为 1000,输入字符数为 300时的实验结果 Table 2 Experiment results of A and B files when parameterof deleting table item s is 1000 and parameter of inputting characters is 300 阈值 1. 3 1. 5 1. 7 1. 9 2. 1 2. 3 数据文件 3. 27460543128116 3. 2977508744586 3. 2977508744586 3. 2977508744586 3. 2977508744586 2. 28714075401651 2. 287140754011651 2. 287140754011651 2. 37983282826601 2. 37867104547825 2. 37745766658904 3. 27460543128116 A文件. txt (22. 2 KB) B文件. txt (26. 1 KB) 3. 3　删除表项数的取值分析 LZW 压缩在串表填满后进行阈值判断时 ,当所 得到的压缩率小于所指定的阈值时 ,就要删除串表 中的若干项 。如果删除的项目过少 ,则会导致程序 执行效率下降 ;如果删除的项目过多则不能很好地 利用原有数据对后续数据进行压缩 ,从而导致程序 执行效率下降 。对于 12比特码长的编码表 ,一般选 取删除表项的个数为 600～1300。 为了获得删除表项数的最佳取值 ,以得到较高 的最终压缩比 ,在进行压缩时针对相同的文件 ,固定 输入字符数及阈值这两个参数 ,对于删除表项数的 不同取值所得到的最终压缩比进行 3次样条拟和 , 找到其拟和曲线的最大点 ,选取与该最大值点对应 的删除表项数最接近的两个整数点 (由于在拟和程 序中对删除表项数 600 ～1 300 的区间进行了细分 有可能拟和曲线上最大值的点所对应的删除表项数 不是整数 ) ,把这 2个参数点带入程序中 ,分别计算 最终压缩比 ,选取最终压缩比取值最大时所对应的 数值为相对最优参数 。A , B 文件在阈值为 2. 0,输 入字符数为 200时 ,选取不同的删除表项数所得到 的实验数据见表 3,其拟和曲线如图 4, 5所示 。 表 3　A, B文件在阈值为 2. 0,输入字符数为 200时的实验结果 Tab. 3 Experiment results of A and B files when threshold is 2. 0 and parameter of inputting characters is 200 数据文件 A文件. txt (22. 2 KB) B文件. txt (26. 1KB) 删除表项数 600 700 800 900 1000 1100 1200 1300 3. 2772004 3945752 2. 2991345 7516971 3. 2780860 4165165 2. 3125013 4829037 3. 2838134 875592 2. 3740089 4715861 3. 2771414 1632447 2. 3565516 5591303 3. 2744286 4855138 2. 3901802 7358775 3. 2776727 0107178 2. 4098736 5676004 3. 2736039 1479562 2. 4267587 2997906 3. 2745465 0158365 2. 3995164 9729149 标示出的点便是最终压缩比 　　图 4拟和曲线中 的最大值点 ,由程序可以得到最接近最大压缩比取 值所对应的删除表项数的两个整数为 792, 793,按 照上文所描述的方法得到其分别对应的最终压缩比 为 3. 277 731 743 344 02和 3. 278 440 416 561 57, 则其相对最优参数 ———删除表项数的取值为 793。 同理 ,图 5中 标示出的最终压缩比取值最大的点 所对应的删除表项数的两个整数为 1 212, 1 213,按 照上文描述的方法得到其分别对应的最终压缩比为 2. 446 391 893 742 30和 2. 427 445 652 173 91,则其 相对最优参数 ———删除表项数的取值为 1 212。从 实验可知 ,删除表项数的相对最优取值点会根据数 据文件的不同而做相对的变化 ,并不是文献 [ 4 ]中 所提到的一个固定值 。 图 4 A文件在阈值为 2. 0,输入字符数为 200时的删除表项数与最终压缩比的拟和曲线 Fig. 4 A file’s curve of relation between final comp r essionratio and parameter of deleting table item s when shold is 2. 0 and parameter of inputting characters is 200
    2 2 2 2 王泉 ,等 : LZW 压缩算法的改进及其参数优化分析 ·553· 2 4　仿真实验结果比较与分析 3种 LZW 算法 ———LZW 基本压缩算法 、基于 LRU淘汰原则的 LZW 压缩算法和本文提出的 LZW 改进压缩算法 ,基于 Matlab的仿真实验数据见表 4 (表 4中括号内的 3个参数分别对应的是阈值 、输入 字符个数 、删除表项数 ) 。 由表 4可知 ,对于任意的待压缩数据文件 ,本文 提出的 LZW 改进压缩算法得到的最终压缩比最大 , 基于 LRU淘汰选择的 LZW 压缩算法得到的最终压 缩比次之 , LZW 基本压缩算法所得到的最终压缩比 最小 ,由此证明了改进算法的正确性及有效性 。 图 5 B文件在阈值为 2. 0,输入字符数为 200时的删除表项数与最终压缩比的拟和曲线 Fig. 5 B file’s curve of relation between final comp ression ratio and parameter of deleting table item s when threshold is 2. 0 and parameter of inputting characters is 200 表 4　3种 LZW 算法实验结果对比表 Tab. 4 Experiment results of three different LZW algorithm s 数据文件 LZW 基本 压缩算法 基于 LRU淘汰原则的 LZW 压缩算法 本文提出的 LZW 改进压缩算法 参数为 (1. 1, 300, 1000) 参数为 (1. 8, 400, 800) 参数为 (2. 1, 300, 1000) 参数为 (1. 8, 400, 800) A文件. txt(22. 2 KB ) C文件. txt(24. 3 KB ) 3. 15716417392511 3. 06092617614544 3. 28696845984320 3. 12204594928977 5　结 　论 LZW 压缩算法是一种有效的数据压缩算法 ,可 以在对数据文件完全不了解的情况下对数据文件进 行压缩 。本文针对 LZW 原有算法的不足 ,提出了新 的基于相关 LRU 淘汰原则和改进阈值判断操作的 LZW 改进算法 ,并且对改进算法中出现的 3个参数 进行了单参数的优化分析与选取 ;并通过大量的仿 真实验验证了改进算法的优越性 。 对于改进算法中出现的 3个参数 ,任何一个参 数的变化都会或多或少的影响到最终压缩比的取 值 。通过对单参数的分析可以发现 ,对于中 、长文 件 ,阈值参数的选取在一定程度上对最终压缩比的 影响相对最弱 ,可以根据实际的要求选取一个合适 的阈值 ,对输入字符数及删除表项数这 2个参数分 别取不同的值进行双参数优化分析 ,这需要今后进 一步的研究分析 。 参考文献 : [ 1 ] 　HAYASHJ S, KUBO J I, YAMAZATO T, et al. A new source coding method based on LZW a dop ting the least recently used deletion heuristic [A ]. IEEE Pacific R im Conference On Commu nications[ C ]. Computers and Signal Processing, 1993, 190 193. 3. 29775087445856 3. 20966028014812 3. 27460543128116 3. 09596061561398 [ 2 ] 　黄贤武 ,王加俊 ,李家华. 数字图像处理与压 缩编码技术 [M ]. 成都 : 电子科技大学出版 社 , 2000. 3. 28086403058005 3. 20141320057813 [ 3 ] 　CHO Gyoun yon, CHO Dong ho. A study on the efficient comp ression algorithm of the voice / data integrated multip lexer [ A ]. IEEE International Conference on Communications [ C ]. 1995, 18 22. [ 4 ] 　高长铎. 采用 LRU淘汰原则的 LZW 压缩算法 [ J ]. 青岛大学学报 , 1998, 13 (4) : 25 28. [ 5 ] 　周天晖 ,王光. 改进的 LZW 压缩算法在语音 数据复接 器中 的应 用 [ J ]. 电 力系 统通 信 , 2002, 23 (11) : 12 13. [ 6 ] 　吴宇新 ,余松煜. 对 LZW 算法的改进及其在 图像无损压缩中的应用 [ J ]. 上海交通大学学 报 , 1998, 32 (9) : 10 113. [ 7 ] 　KINSNER W , GREENF IELD R H. The Lempel - Ziv - W elch (LZW ) data comp ression algo rithm for packet radio [ A ]. W ESCANEX ’91 ’ IEEE W estern Canada Conference on Computer, Power and Communications System s in a Rural Environment[ C ]. 1991, 225 229. [ 8 ] 　王平. LZW 无损压缩算法的实现与研究 [ J ]. 计算机工程 , 2002, 28 (7) : 98 99. (责任编辑 :刘勇 ) 　 (下转 371页 )
    2 宋虎 ,等 :构建基于 RTL inux的嵌入式系统研究与开发 ·173· 参考文献 : [ 1 ] 　DAN IEL P, Bovet, MARCO Cesati. 深入理解 L inux内核 [M ]. 陈莉君 ,冯锐 ,牛欣源译. 北 京 :中国电力出版社 , 2001. [ 2 ] 　杨朝军 ,李世畅 ,陶洋. L inux嵌入式系统的优 化 [ J ]. 重庆邮电学院学报 (自然科学版 ) , 2002, 14 (4) : 61 64. [ 3 ] 　 The RTL inux p roject [ EB /OL ]. http: / /www. rtlinx. at. 2004 06 04. [ 4 ] 　邹思轶. 嵌入式 L inux设计与应用 [M ]. 北京 : 清华大学出版社 , 2002. [ 5 ] 　 Iw IP Project home site [ EB /OL ]. http: / /www. sics. se / adam / Im ip, 2004 06 04. [ 6 ] 　 Josep vidal. Imp lementation of POSIX signals timers in RTL inux[ EB /OL ]. http: / / bernia. dis ca. upv. es/ rtportal/ , 2004 04. 06 [ 7 ] 　 ALESSANDRO Rubini, JONATHAN Corbet. L inux设备驱动程序 (第 2 版 ) [M ]. 魏永明 , 骆刚 ,姜君译. 北京 :中国电力出版社 , 2002. (责任编辑 :龙能芬 ) Research and explo ita tion of em bedded system s w ith RTL inux ( Chongqing U n iversity of Posts and Telecomm unications, Chongqing 400065, P. R. China) SONG Hu, L I B ing zhi time L inux (RTL inux) , which is a small, determ inistic, real time system s since L inux doesn’t comp ly with the restrictions that real Abstract:L inux is becom ing an op tion for develop ing embedded system s, but it is not app rop riate for re time system s demand. Real al time features can be achieved with Real time critical tasks and runs L inux as its lowest p riority execution thread. However kernel that handles time RTL inux has also important drawbacks. One of them is that real time tasks cannot make use of L inux in particular, TCP / IP networking. This paper introduces Iw IP, a lightweight TCP / IP stack, services and, which runs RTL inux and can be used by real time time task, or even enables L inux user p rocess. According tasks to communicate directly w ith remote real to such features the authors integrate L inux, Iw IP and RTL inux app rop riately, and get a real time p lat form. Key words: embedded system; RTL inux; time tasks. The Iw IP runs on RTL inux and allow s real Iw IP; device driver (上接 355页 ) M od if ied L ZW a lgor ithm and its param eters optim iza tion WANG Quan, Q I Chun, LUO Xin m in, L IANG Song (D epartm ent of Inform ation and Comm unica tion Eng ineering, S chool of E lectron ic and Inform a tion Engineering, X i’an J iaotong U n iversity, X i’an 710049, P. R. China) the imp roved judgement of threshold is used in the algorithm. Third, Abstract:A modified LZW dictionary comp ression algorithm is p roposed. First, the correlation of the new input characters is considered in transferred data file, and then the correlation LRU elim ination p rincip le comes out. Second, the op tim ization of three single parameters is analyzed. The final comp ression ratios of p roposed algorithm and the other two LZW comp ression algorithm s are compared. The experiment results show that the p roposed algorithm has the better comp ression ratio than the other two LZW comp ression algorithm s. The authors suggest multip le pa rameters op tim ization should be considered in further research. Key words:LZW algorithm; LRU elim ination p rincip le; judgement of threshold; final comp ression ratio
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料