关于LZW算法的压缩与解压缩
LZW算法是基于字典查找的一种优秀算法，该算法的名称来源于它的三个创始人Lemple-Ziv-Welch。它的压缩比通常在1:1--1:3之间,一些数据重复较多的文件采用此压缩方法的效果会更好。下面将详细阐述LZW算法的压缩与解压缩过程。
1：LZW算法的压缩过程
1.1 准备工作：
在讲述压缩过程之前有必要先弄清楚与它相关的几个名词：
“charstream”：字符流，表示从原始文件中输出的数据流。
“prefix_character”：前缀字符，代表当前字符最直接的前一个字符。
“current_character”：当前字符，顾名思意就是当前接收到的一个字符，它与prefix_character可以组成一个字符串。
“string”：字符串，由前缀字符和当前字符组成。
“code_table”：代码表，存储一个新的字符串的代码编号。
“element”：元素，字符流中的不同的单个数据元素，它的代码是在编码前给它按顺序编制
1.2具体实现：
在了解了上面的一些概念以后，下面正式进入压缩算法步骤：
① 从字符流中获取第一个字符把它的值赋给prefix_character
② 字符流是否结束，没结束就从字符流中再取一个字符赋给current_character，字符结束首先输出prefix_character，然后退出程序。
③ String = prefix_character+current_character是否在code_table当中？
④ 在code_table当中，就把string的代码编号赋给prefix_character,转往②步进行。
⑤ 没在cde_table当中，就把string存储到code_table当中去，输出prefix_charracter，并且把current_character赋给prefix_character，再转往②执行。
1,.3举例分析：
被编码的字符串
|
位置 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
字符 |
A |
B |
B |
A |
B |
A |
B |
A |
C |
此例中：A，B，C是element，9个字符组成了char_stream
|
步骤 |
位置 |
词典（code_table） |
输出 |
|
|
1 |
|
（1） |
A |
|
|
2 |
|
（2） |
B |
|
|
3 |
|
（3） |
C |
|
|
4 |
|
（4） |
AB |
（1） |
|
5 |
|
（5） |
BB |
（2） |
|
6 |
|
（6） |
BA |
（2） |
|
7 |
|
（7） |
ABA |
（4） |
|
8 |
|
（8） |
（7）C |
（7） |
在第4步中，A为前缀，B为当前字符，在第7步当中先得到一个string是AB，但是AB已经在code_table当中了，所以这时以AB作为前缀，后取一个字符A，这时（4）+A在code_table当中没有，所以把这个string放到code_table中去，编号为（7），这时就把（7）作为前缀，继续下面的编码。
2：LZW的解压缩过程
2.1在讲述解压缩的具体实现过程之前，首先把上面压缩字符表对应的解压缩表给出，再对照解压缩表给出解压缩的具体过程。
|
步骤 |
代码 |
词典 |
输出 |
|
|
|
|
（1） |
A |
|
|
|
|
（2） |
B |
|
|
|
|
（3） |
C |
|
|
1 |
（1） |
-- |
-- |
A |
|
2 |
（2） |
（4） |
AB |
B |
|
3 |
（2） |
（5） |
BB |
B |
|
4 |
（4） |
（6） |
BA |
AB |
|
5 |
（7） |
（7） |
ABA |
ABA |
|
6 |
（3） |
（8） |
（7）C |
C |
2.2 LZW解压缩具体步骤：
从上面的解压缩表可以看出以下几条：
当遇到小于3的代码时就直接输出，如A，B，C；
当遇到大于3的代码，并且在code_table当中存在的代码值时就到code_table当中去遍历它存储的字符，并且把它输出。如第4步中的（4）；
当遇到大于3，但是在code_table当中没有存储的就把前缀的第1个字符作为当前字符，把这个当前字符和前缀同时输出，并且把他们存储在code_table当中。如（7），它把AB的第1个字符加在AB之后将其作为一个string输出，并且存储在code_table当中。
具体解压步骤如下：
① 读取第一个字符，输出它，并且把它赋给prefix_character
② 读取下一个字符，是否文件已经结束，没有结束，就把该字符赋给current_character，该字符是否大于N（基本字符element的个数）？
③ 大于N，是否在code_table当中？
④ 没在code_table当中，将prefix_character+prefix_character的第1个字符输出，并且赋给string 存储当code_table当中去，同时把该string赋给prefix_character，转向②执行。
⑤ 在code_table当中，遍历current_character的所有字符，并且输出它，把current_character赋给prefix_character,转向②执行。
⑥ 小于N，输出current_character,并且把cureent_character赋给prefix_character,转向②执行。