摘要： 利用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
中图分类号: