论文部分内容阅读
近年来,计算机数据通信和数据存储业务急剧增加,推动了无失真数据压缩技术的迅速发展。LZW算法以其实现简单、编译码速度快、压缩率较高等特点,得到了广泛应用。本文介绍采用LRU(least recently used)算法动态维护LZW算法的字典,以进一步提高压缩率。一、LZW算法简介LZW算法是自适应字典算法LZ78的第一个改进算法,其初始字典包含输入字母表中的所有单字符。例如,当采用LZW编码器压缩一般的磁盘文件时,则其初始字典包含所有的256个8比特的ASCⅡ码字符。LZW算法读入源数据流的第一个未被压缩过的字符,并在字典中寻找该字符和它的后续字符的最长匹配串。编码器输出对应于该串的码字(在字典内的地址指针),然后将匹配串和第一个未匹配字符相连结而形成
In recent years, the business of computer data communications and data storage has dramatically increased, prompting the rapid development of distortionless data compression technology. LZW algorithm has been widely used because of its simple implementation, fast codec speed and high compression ratio. This article describes a dictionary that uses the least recently used (LRU) algorithm to dynamically maintain the LZW algorithm to further improve the compression ratio. First, LZW algorithm introduction LZW algorithm is adaptive dictionary algorithm LZ78 first improved algorithm, the initial dictionary contains all the characters entered in the alphabet. For example, when using an LZW encoder to compress a generic disk file, its initial dictionary contains all 256 8-bit ASCII characters. The LZW algorithm reads in the first uncompressed character of the source data stream and finds in the dictionary the longest match string for that character and its subsequent characters. The encoder outputs a codeword (address pointer in the dictionary) corresponding to the string and then concatenates the matching string with the first unmatched character