LZW 算法之解压

上一篇 文章中说到了 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...Oxxx...xo是相同的。即O=tmp[0],w = tmp+tmp[0] 如此循环最终就可以得到原始的数据abaaabba

*****
Written by Functor on 18 March 2015
Tags: [ algorithm  LZW  compression  ]