自己来写压缩算法——LZW
之前用哈夫曼算法，把固定长的字符编码根据其出现次数，编码为不固定长的编码。而这次介绍的算法恰恰相反，该算法是把不等长的字符串，编码为固定长的编码。
LZW
蓝博-立夫-卫曲编码法（Lempel-Ziv-Welch，缩写LZW），是亚伯拉罕·蓝波、杰可布·立夫与泰瑞·卫曲共同提出的一种无损数据压缩演算法。与霍夫曼编码相比，LZW把不同长度的字符串转换为固定长的编码。该方法不需要事先对数据做任何分析，所以可以流式地对文件进行处理。
原理
编码
举个简单的例子，如果有一份数据，内容中的字符只有’abc’三种。那么如何对它进行编码呢？
首先先将单字符建立成一个字符串编码表，分别给予编号。
| string | code |
|--------|------|
| a | 0 |
| b | 1 |
| c | 2 |若数据为aabcaac，进过LZW编码后结果为 [0,0,1,2,3,2,]，过程如下
| No. | cur | prefix | prefix + cur | in str->code | code | add into str->code |
| --- | --- | ------ | ------------ | ------------ | ---- | ------------------ |
| 1 | a | | a | true | | |
| 2 | a | a | aa | false | 0 | aa -> 3 |
| 3 | b | a | ab | false | 0 | ab -> 4 |
| 4 | c | b | bc | false | 1 | bc -> 5 |
| 5 | a | c | ca | false | 2 | ca -> 6 |
| 6 | a | a | aa | true | | |
| 7 | c | aa | aac | false | 3 | aac -> 7 |
| 8 | | c | | | 2 | |整个算法过程如下：
- 从输入流读取一个字符 char
- 若字符串 prefix + 字符 char 在 字符串编码表中，字符串 prefix += 字符 char
- 若字符串 prefix + 字符 char 不在 字符串编码表中：
- 获取 字符串 prefix 的编码 k，写入输出流
- 将 字符串 prefix + 字符 char 以编码 k + 1 存入字符串编码表
- 字符串 prefix = 字符 char
- 重复以上步骤，直到输入流无新数据
- 最后获取 字符串 prefix 的编码 k，写入输出流
解码
| string | code |
|--------|------|
| a | 0 |
| b | 1 |
| c | 2 |一开始的字符串编码都是同一个，那么如何把 [0,0,1,2,3,2,] 解码为 aabcaac ？
解码过程如下：
| No. | code | str | char | prefix | prefix + char | in str->code | add into str->code | result |
| --- | ---- | --- | ---- | ------ | ------------- | ------------ | ------------------ | ------- |
| 1 | 0 | a | a | | a | true | | a |
| 2 | 0 | a | a | a | aa | false | aa -> 3 | aa |
| 3 | 1 | b | b | a | ab | false | ab -> 4 | aab |
| 4 | 2 | c | c | b | bc | false | bc -> 5 | aabc |
| 5-1 | 3 | aa | a | c | ca | false | ca -> 6 | aabcaa |
| 5-2 | | aa | a | a | aa | true | | |
| 7 | 2 | c | c | aa | aac | false | aac -> 7 | aabcaac |整个算法过程如下：
- 从输入流中获取一个编码 k
- 对照 字符串编码表 取得字符串 str
- 从字符串 str 中取得字符 char
- 若字符串 prefix + 字符 char 在 字符串编码表中，字符串 prefix += 字符 char
- 若字符串 prefix + 字符 char 不在 字符串编码表中：
- 将字符串 prefix + 字符 char 存入字符串编码表
- 字符串 prefix = 字符 char
- 重复以上步骤
- 重复以上步骤
- 从字符串 str 中取得字符 char
- 重复以上步骤
实现
核心代码
照着算法步骤，我们很容易地写出以下的代码：
from six import int2byte
# 初始字符串编码表
# str -> code
original_cdict = {b'a': 0, b'b': 1, b'c': 2}
# code -> str
original_kdict = [b'a', b'b', b'c']
def encode(data):
'''
>>> encode(b'aabcaac')
[0, 0, 1, 2, 3, 2]
'''
cdict = original_cdict.copy()
rv = []
prefix = b''
for c in data:
if prefix + int2byte(c) in cdict:
prefix += int2byte(c)
else:
rv.append(cdict[prefix])
cdict[prefix + int2byte(c)] = len(cdict)
prefix = int2byte(c)
rv.append(cdict[prefix])
return rv
def decode(data):
'''
>>> decode([0, 0, 1, 2, 3, 2])
b'aabcaac'
'''
cdict = original_cdict.copy()
kdict = original_kdict.copy()
prefix = b''
rv = b''
for key in data:
cs = kdict[key]
for c in cs:
if prefix + int2byte(c) in cdict:
prefix += int2byte(c)
else:
cdict[prefix + int2byte(c)] = len(cdict)
kdict.append(prefix + int2byte(c))
prefix = int2byte(c)
rv += cs
return rv以上就是LZW压缩算法的核心代码。若是要应用到文件上，还是有挺多步要走的。
文件压缩
要做到压缩、解压缩，如何保存其压缩结果是一个躲避不了的问题。有了之前处理自己来写压缩算法——哈夫曼算法 哈夫曼算法的经验，我们知道要把压缩后的编码列表写入文件过程。先是将其变换成比特流，然后再把比特流写入到文件里。那么一个编码以多少长度写入文件里呢？
如果要压缩一个文件，如果是以一字节一字节地读取处理，那么初始字符串编码表长度至少哋256($2^8$)个，所以一个压缩后的编码的长度大于8比特。
长度为9比特，就能保存$2^9 = 512$个编码；长度为10比特，就能保存$2^{10} = 1024$个编码；长度为16比特，就能保存$2^{16} = 65536$个编码。若是选择长度短的，那么怎么压缩大文件呢；若是选择长度长的，那么目标文件更大呢；总不能选个超级长的长度，最后是能压缩大多数文件了，可哪能叫压缩吗（压缩结果大小反而大过源文件）
动态编码长度
当字符串编码表的长度为1024($2^{10}$)时，在此之前出现的所有编码都小于1024($2^{10}$)，若用长度16来保存编码未免也太浪费空间了。 只有动态地改变保存长度，才能更加有效地利用存储空间，使压缩效果更好。
比如字符串编码表超过为512($2^9$)时，就以长度10来保存；超过1024($2^10$)，就以长度11来保存；如此类推既可以。
但不能让字符串编码表无限增大下去，所以得设置个哨兵值来重置字符串编码表。
处理过程
- 设置重置字符串编码表的哨兵值（解决字符串编码表无节制增长）
- 读文件
- 使用 LZW 算法压缩或者解压文件数据
- 写文件
核心代码加上以上的处理过程，就能写出一个真正实用的压缩程序了！
LZW 支持流式处理数据，读写和处理可以同时进行
扩展
初始的字符串编码表的大小可以不是256个吗？
可以，每次处理的数据大小决定了初始编码表的大小。每 8bits 的处理，初始编码表的大小为256；每 10bits 的处理，初始编码表的大小为1024；每 11bits 的处理，初始编码表的大小为2048；
完整代码
GIST: LZW Encoding and Data Compression. | linw1995
