在 上一篇 文章中说到了 LZW 的压缩方法。那么面对一个压缩后的序列，我们如果还原出原始的信息呢？由于得到的只有压缩后的序列而没有压缩表，所以在解压的过程中必须要动态的构建它。 伪代码表述如下
1. 初始化dict为只有长度为一元素的字典
2. tmp = ""，w=""
3. 从输入读取一个字符到c
4. 如果c 在字典中出现
w = 字典中c对应的串,输出w
将 tmp+w[0] 加入字典
5. 否则
w = tmp+tmp[0]
将w加入字典并输出w
6. tmp = w
7. 如果还有输入回到3，否则结束
还是用上一次的例子来说明。 压缩后的数据为
0,1,0,4,1,3
先初始化dict
dic={a=0, b=1}
先看第1个元素0,可以知道原始数据一定是
ax...
也就是说原始数据一定以a开头，下一个字符x还不知道，但是ax不在字典中，由于a已经在字典中，dict不变化，但是在压缩的时候ax已经被添加到字典中
再看第2个元素1,,可以知道原始数据一定是
abx...
这时候就知道刚才加入字典的是ab,现在把它加到dict中
dic={a=0, b=1, ab=2}
在压缩的时候bx已经被加入dict，但是现在还不知道x是多少，先跳过
再看第3个元素1,,可以知道原始数据一定是
abax...
这时候就知道刚才加入字典的是ba,现在把它加到dict中
dic={a=0, b=1, ab=2, ba=3}
在压缩的时候ax已经被加入dict，但是现在还不知道x是多少，先跳过
再看第4个元素4,问题来了,现在dict中最大只有3，可是输入却是4。出现这个情况，说明这次输出的可见原始串就是刚才加入dict的ax,也就是说x=a，所以dict变为
dic={a=0, b=1, ab=2, ba=3, aa=4}
原始串为abaaa...
这也就是伪代码中w = tmp+tmp[0]的原因.
下面再解释一下这个情况
[xxx...x(O]OOO...O)H
假设xxx...x代表一个已经在dict中的串，遇到o后输出了它(tmp)的编号a，同时xxx...xo编号为b,现而下一个又输出了b,说明OOOO...O与xxx...xo是相同的。即O=tmp[0],w = tmp+tmp[0]
如此循环最终就可以得到原始的数据abaaabba