前言

在看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压缩算法



算法      LZW压缩算法

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!