|
#2
东海一鱼2010-08-15 11:32
|
LZW压缩方法把文本的字符串映射为数字编码。首先，为该文本文件中所有可能出现的字母分别分配一个代码。例如，要压缩的文本文件为：aaabbbbbbaabaaba
字符串由a和b组成，为a分配代码0，为b分配代码1。字符串和编码的映射关系存储在字典中，每个字典的入口有两个域：key和code，由code表示的字符串存在域key中。
code 0 1 2 3 4 5 6 7
key a b aa aab bb bbb bbba aaba
若初始字典如上所示，LZW压缩器不断地在输入文件中寻找在字典中出现的最长的前缀p，并输出相应的代码。若输入文件中下一个字符为c，咋为pc分配下一个代码，并插入字典，这种策略成为LZW规则。
用LZW方法来压缩上例字符串，文件中第一个在字典中出现的最长前缀为a(#1)，输出编码0。然后为字符串aa分配代码2，并插入到字典中……
所以，上例中字符串的编码为021453
疑惑：#1处说“文件中第一个在字典中出现的最长前缀为a”，我怎么觉得应该是aa，因为aa比a要长呀。
看了半天，对这个压缩方法也不明白......