LZW (Lempel–Ziv–Welch) 压缩是一种基于表的无损压缩。在压缩时,会将反复出现的部分放入表格进行编号,而最终输出的结果就是编号的序列。在解压的时候通过查表就可以还原出原始的数据。
通常基于表的压缩方法需要将表格附在压缩的数据上以便解压,然而 LZW 采用了一种巧妙的方法,不需记录表格信息,而是在解压的时候,一遍解压一边进行表的构造,完成整个算法。 压缩的核心伪代码表示如下
1. 初始化字典dict,只包含长度为1的元素
2. w = "", k = “”
3. 从输出中读取一个字母到 k, w = w + k
4. 如果w出现在字典中,跳转到 3
5. 否则,输出 dict[ w[:-1] ]
6. 将 w 加入到字典中
7. w = k
8. 跳转到 3
也就是说,在压缩的时候我们先构造出一个基础的表,然后贪心的从输入里面读取信息直到它不出现在表中。那么这个没出现过字符串w的去掉最后一个字母子串一定出现过,我们把它的编号输出,然后将w加入到字典中。 比如说要压缩这样一个字符串
abaaabba
首先初始化dict
dict={a=0, b=1}
然后从头开始扫描这个字符串
第一次读到最长的 w 后(下面 []
中表示的是当前的 w)
[ab]aaabba
所以输出0
即dict[a]
,同时dict变为
dict={a=0, b=1, ab=2}
第二次读到最长的 w 后
a[ba]aabba
所以输出1
即dict[b]
,同时dict变为
dict={a=0 ,b=1, ab=2. ba=3}
第三次读到最长的w后
ab[aa]abba
所以输出0
即dict[a]
,同时dict变为
dict={a=0, b=1, ab=2. ba=3, aa=4}
第四次读到最长的w后
aba[aab]ba
所以输出4
即dict[aa]
,同时dict变为
dict={a=0, b=1, ab=2, ba=3, aa=4, aab=5}
第五次读到最长的w后
abaaa[bb]a
所以输出1
即dict[b]
,同时dict变为
dict={a=0, b=1, ab=2, ba=3, aa=4, aab=5, bb=6}
第六次读到最长的w后
abaaab[ba]
所以输出3
即dict[ba]
,因为已经结束且ba出现过,所以dict不变
dict={a=0, b=1, ab=2, ba=3, aa=4, aab=5, bb=6}
最终的输出为0,1,0,4,1,3
关于解压的算法,可以看这里