在 上一篇 文章中说到了 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