lzw压缩算法

update@2011-11-10

只是自己对LZW的理解的小结，不是讲解

---

LZW压缩过程
1. 初始化字典(根据具体情况)
2. 顺序读字符，把读的字符作为当前串的后缀(读第一个字符的时候直接作为前缀，因为它是单个字符)
3. 处理当前串

• 如果当前串已经在字典中(已经被编码)，则把当前串的编码赋给当前串的前缀(转2)
• 如果当前串不在字典中则把当前串编码，并放入字典中，然后输出当前串的前缀并把后缀作为前缀(转2)

CODE:

1. STRING = get input character
2. WHILE there are still input characters DO
3.     CHARACTER = get input character
4.     IF STRING+CHARACTER is in the string table then
5.         STRING = STRING+character
6.     ELSE
7.         output the code for STRING
8.         add STRING+CHARACTER to the string table
9.         STRING = CHARACTER
10.     END of IF
11. END of WHILE
12. output the code for STRING

LZW解压过程
1. 初始化字典(和压缩过程保持一致)
2. 顺序从压缩后的文件中读取编码后的值(如果是定长，每次读取固定位数的bit位；如果是变长，根据当前的编码长度读取一定位数的bit位)
3. 处理读到的编码值

• 如果读到的编码值在字典中就直接输出对应的字符串，并把编码值所对应的 字符串的第一个字符作为当前串的后缀
• 如果读到的编码值不在字典中，我们总有方法找到它的第一个字符，比如 256 = （A,256）,那么码值256的第一个字符肯定是A了，所以同样把第一个字符作为当前串的后缀

4.将当前串编码并放入字典
5.对于当前串的编码值

•  如果读到的编码值和当前串的编码值相等就输出当前串，并将读到的编码值作为前缀(转2)

CODE:

1. Read OLD_CODE
2. output OLD_CODE
3. WHILE there are still input characters DO
4.     Read NEW_CODE
5.     STRING = get translation of NEW_CODE
6.     output STRING
7.     CHARACTER = first character in STRING
8.     add OLD_CODE + CHARACTER to the translation table
9.     OLD_CODE = NEW_CODE
10. END of WHILE

特点
1. 动态生成字典(可以用静态或者混用) ，字典信息已经包含在压缩后的数据流中 解压的时候可以重新构造出这个字典
2. 编码长度根据具体情况确定, 可以采用定长或者变长 (关于变长：刚开始压缩的时候编码值较小，用较少的位数就可以表示，随着编码值越来越大，需要增加编码长度来表示更大的编码值)


影响LZW性能的几个因素
1) 需要压缩的内容的冗余程度，重复的串的长度比较长，重复的次数比较多 压缩比更高
2) 字典的数据结构、查找算法(hash表,trie树等)