作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 开发研究与工程应用 • 上一篇    下一篇

无损压缩算法LZW前缀编码优化及应用

鄢海舟 1,胥布工 1,石东江 2,郑伟德 3   

  1. (1.华南理工大学 自动化科学与工程学院,广州 510641; 2.华能国际电力股份有限公司湖南分公司,长沙 410002;3.华能湖南岳阳发电有限责任公司,湖南 岳阳 414002)
  • 收稿日期:2016-06-14 出版日期:2017-03-15 发布日期:2017-03-15
  • 作者简介:鄢海舟(1993—),男,硕士研究生,主研方向为电力数据去噪与压缩;胥布工(通信作者),教授、博士;石东江、郑伟德,高级工程师。
  • 基金资助:
    国家自然科学基金-广东联合基金重点项目(U1401253)。

Prefix Encoding Optimization and Application of Lossless Compression Algorithm LZW

YAN Haizhou  1,XU Bugong  1,SHI Dongjiang  2,ZHENG Weide  3   

  1. (1.School of Automation Science and Engineering,South China University of Technology,Guangzhou 510641,China; 2.Hunan Branch,Huaneng Power International Co.,Inc.,Changsha 410002,China;3.Huaneng Hunan Yueyang Power Generation Co.,Ltd.,Yueyang,Hunan 414002,China)
  • Received:2016-06-14 Online:2017-03-15 Published:2017-03-15

摘要: 利用LZW算法进行数据压缩,当字典长度为l时,前缀在区间[0,l-1]中,因而只能通过「lbl bit对前缀进行编码,使区间[l,2「lbl-1]内的数据不能被充分利用,造成冗余现象。针对该问题,提出一种前缀映射编码的改进压缩算法。对满足条件的前缀不直接编码输出,而是将其映射到区间[l,2「lbl-1],此时编码位数并未减少但却隐含一个标志位信息,标志下一个前缀编码用更少的比特位来编码。与原LZW算法相比,改进算法不增加计算量和存储空间,并且通用性好。英文文本数据压缩仿真和残差数据压缩应用结果均验证了该算法的有效性。

关键词: LZW算法, 前缀映射, 编码, 无损压缩, 标志位, 去冗余

Abstract: LZW algorithm can not make full use of the length of dictionary for prefix encoding when compressing data and has redundancy.When considering the length of the dictionary is l,the prefix can be located within [0,l-1] only,and the LZW algorithm uses 「lbl bit to encode the prefix.Therefore,the data of the interval [l,2「lbl-1] is not fully used.Aiming at this problem,this paper proposes an improved compression algorithm of prefix mapping encoding.It does not encode and output the prefix which meets the condition,but maps it to the interval [l,2「lbl-1].In this case,the number of prefix encoding is not decreased but implies the information that the next prefix will be encoded with less bits.Compared with LZW agorithm,the improved algorithm has advantages that it does not increase the amount of calculation and memory space,and can be used more generally in data compression.The effectiveness of the improved algorithm is verified when tested with English text data in simulation experiments and applied into residual data compression.

Key words: LZW algorithm, prefix mapping, encoding, lossless compression, flags, redundancy elimination

中图分类号: