前言
在看writeup的时候,题目含有base64和lzw算法,由于不了解lzw算法,遂学习一下。
简介
LZW就是通过建立一个字符串表,用较短的代码来表示较长的字符串来实现压缩。
加密
从原字符串不断地读入新的字符,并试图将单个字符或字符串编码为记号 (Symbol)。
维护两个变量,一个是P (Previous),表示手头已有的,还没有被编码的字符串,一个是C (current),表示当前新读进来的字符。
- 初始状态,字典里只有所有的默认项,例如0->a,1->b,2->c。此时P和C都是空的。
- 读入新的字符C,与P合并形成字符串P+C。
在字典里查找P+C,如果:
P+C在字典里,P=P+C。
P+C不在字典里,将P的记号输出;在字典中为P+C建立一个记号映射;更新P=C。
返回步骤2重复,直至读完原字符串中所有字符。
以上表示的是编码中间的一般过程,在收尾的时候有一些特殊的处理,即步骤2中,如果到达字符串尾部,没有新的C读入了,则将手头的P对应的记号输出,结束。
编码过程的核心就在于第3步,需要理解P究竟是什么。P是当前维护的,可以被编码为记号的子串。注意P是可以被编码为记号,但还并未输出。新的字符C不断被读入并添加到P的尾部,只要P+C仍然能在字典里找到,就不断增长更新P=P+C,这样就能将一个尽可能长的字串P编码为一个记号,这就是压缩的实现。当新的P+C无法在字典里找到时,我们没有办法,输出已有的P的编码记号,并为新子串P+C建立字典表项。然后新的P从单字符C开始,重新增长,重复上述过程。
用一个例子来说明编码的过程
ababcababac
初始状态字典里有三个默认的映射:
Symbol String
0 a
1 b
2 c
开始编码:
Step P C P+C P+C in Dict ? Action Output
1 - a a Yes 更新P=a -
2 a b ab No 添加3->ab,更新P=b 0
3 b a ba No 添加4->ba,更新P=a 1
4 a b ab Yes 更新P=ab -
5 ab c abc No 添加5->abc,更新P=c 3
6 c a ca No 添加6->ca,更新P=a 2
7 a b ab Yes 更新P=ab -
8 ab a aba No 添加7->aba,更新P=a 3
9 a b ab Yes 更新P=ab -
10 ab a aba Yes 更新P=aba -
11 aba c abac No 添加8->abac,更新P=c 7
12 c - - - - 2
注意编码过程中的第3-4步,第7-8步以及8-10步,子串P发生了增长,直到新的P+C无法在字典中找到,则将当前的P输出,P则更新为单字符C,重新开始增长。
输出的结果为0132372,完整的字典为:
Symbol String
0 a
1 b
2 c
3 ab
4 ba
5 abc
6 ca
7 aba
8 abac
原字符串对应到压缩后的编码的
0 1 3 2 3 7 2
a b ab c ab aba c
解密
- 初始状态,字典里只有所有的默认项,例如0->a,1->b,2->c。此时pW和cW都是空的。
- 读入第一个的符号cW,解码输出。注意第一个cW肯定是能直接解码的,而且一定是单个字符。
- 赋值pW=cW。
- 读入下一个符号cW。
在字典里查找cW,如果:
cW在字典里:
- 解码cW,即输出 Str(cW)。
- 令P=Str(pW),C=Str(cW)的第一个字符。
- 在字典中为P+C添加新的记号映射。
cW不在字典里:
- 令P=Str(pW),C=Str(pW)的第一个字符。
- 在字典中为P+C添加新的记号映射,这个新的记号一定就是cW。
- 输出P+C。
- 返回步骤3重复,直至读完所有记号。
记号
0 1 3 2 3 7 2
解码
a b ab c ab aba c
初始状态字典里有三个默认的映射:
Symbol String
0 a
1 b
2 c
Step pW cW cW in Dict ? Action Output
0 - 0 Yes P=-,C=a,P+C=a a
1 0 1 Yes P=a,C=b,P+C=ab,添加3->ab b
2 1 3 Yes P=b,C=a,P+C=ba,添加4->ba ab
3 3 2 Yes P=ab,C=c,P+C=abc,添加5->abc c
4 2 3 Yes P=c,C=a,P+C=ca,添加6->ca ab
5 3 7 No P=ab,C=a,P+C=aba,添加7->aba aba
6 7 2 Yes P=aba,C=c,P+C=abac,添加8->abac c
总结
默认的映射表通常为255行,也就是ASCII码表的长度,拓展从256开始。
加密:不断读取源数据,直到不在映射表里,输出P并添加一个新的映射
解密:读取记号流,如果在映射表里,就输出并添加一个映射
REF
本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!