前言

在看writeup的时候，题目含有base64和lzw算法，由于不了解lzw算法，遂学习一下。

---

简介

LZW就是通过建立一个字符串表，用较短的代码来表示较长的字符串来实现压缩。

---

加密

从原字符串不断地读入新的字符，并试图将单个字符或字符串编码为记号 (Symbol)。

维护两个变量，一个是P (Previous)，表示手头已有的，还没有被编码的字符串，一个是C (current)，表示当前新读进来的字符。

1. 初始状态，字典里只有所有的默认项，例如0->a，1->b，2->c。此时P和C都是空的。
2. 读入新的字符C，与P合并形成字符串P+C。

3. 在字典里查找P+C，如果:

   1. P+C在字典里，P=P+C。

   2. P+C不在字典里，将P的记号输出；在字典中为P+C建立一个记号映射；更新P=C。

4. 返回步骤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

---

解密

1. 初始状态，字典里只有所有的默认项，例如0->a，1->b，2->c。此时pW和cW都是空的。
2. 读入第一个的符号cW，解码输出。注意第一个cW肯定是能直接解码的，而且一定是单个字符。
3. 赋值pW=cW。
4. 读入下一个符号cW。

5. 在字典里查找cW，如果:

   1. cW在字典里：

      1. 解码cW，即输出 Str(cW)。
      2. 令P=Str(pW)，C=Str(cW)的第一个字符。
      3. 在字典中为P+C添加新的记号映射。

   2. cW不在字典里:

      1. 令P=Str(pW)，C=Str(pW)的第一个字符。
      2. 在字典中为P+C添加新的记号映射，这个新的记号一定就是cW。
      3. 输出P+C。
6. 返回步骤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

LZW压缩算法

---