【Python标准库】LZ77编码的基本原理和lzma模块

lz77编码

Python标准库总共提供了三种压缩算法，分别是zlib, bz2以及lzma，并且位这三个模块提供了高度相似的API，考虑到zlib中已经对很多定义做了详尽的解读，本文主要介绍一下lzma算法，然后对常用的函数做一个示例。

lzma是Lempel-Ziv-Markov chain-Algorithm的缩写，在2001年被用在著名的7-Zip中，是在Deflate和LZ77算法上的改良和优化，本文主要介绍一下LZ77算法。

LZ77是Lempel和Ziv在1977年开发的编码方式，核心思想是利用数据的重复结构信息，从而弥补了霍夫曼编码需要了解先验频率的不足。

主要思路是用一个滑窗对数据进行筛选，其编码流程分为3步：

1. 从当前压缩位置开始，用一个滑窗在已编码数据中查找与为编码数据据匹配的最长字符串，如果找到则跳到2，否则跳到3。
2. 输出三元符号组(off, L, c)，其中off位匹配字符串相对窗口边界的偏移，L为匹配长度，c为下一个字符。然后将窗口向后滑动L+1个字符，继续步骤1。
3. 输出单值c，c为当前字符，然后将窗口向后滑动一个字符，继续步骤1。

以AABCBBABCD为例，下面是LZ77的编码流程

1. A是第一个字母，再它出现之前，没有任何可供参考的编码数据，所以A就是A。
2. 第二个A就不一样了，由于有了第一个A做参照，所以可以记作(1,1,B)，前面的1表示此时滑窗移动1，第二个1表示长度为1，B表示该字母之后是B。至此，已经编码的区域为AAB，记作A(1,1,B)。
3. 当前未编码的区域有CBBABC，C无参照，所以直接记下来；B在AAB中有出现过，所以记作(3,1,B)，2表示窗口向右滑动3位可匹配到B，1表示匹配长度，B表示第二个B。此时已编码字符串为AABCBB，记作A(1,1,B)C(2,1,B)。
4. 此时为编码区域有ABC，正好和AABC中的ABC匹配，记作(2,3,D)。

lzma模块调用

稍微讲解一下原理之后，可以先调用一下lzma模块中最关键的两个函数compress和decompress。

import lzma
import sys
ori = 'ifyoumissthetrainimonyouwillknowthatiamgone'*10
bOri = ori.encode()
sys.getsizeof(bOri) # 463
c = lzma.compress(bOri)
sys.getsizeof(c)    # 145

未采取压缩时，占内存463；压缩之后剩下145。

除了压缩和解压缩函数之外，lzma还提供了直接与文件交互的open，其封装为

lzma.open(filename, mode='rb', encoding=None, errors=None, newline=None)

lzma模块提供了方便的文件交互函数open，有了这个就可以直接将数据另存为压缩文件了

>>> with lzma.open('test.txt.xz', 'w') as f:
...   f.write(ori.encode())
...
430

而且这个压缩文件可以直接用解压软件打开

既然能读，那自然能写

>>> with lzma.open('test.txt.xz', 'r') as f:
...    print(f.read())
...
b'ifyoumissthetrainimonyouwillknowthatiamgoneifyoumissthetrainimonyouwillknowthatiamgoneifyoumissthetrainimonyouwillknowthatiamgoneifyoumissthetrainimonyouwillknowthatiamgoneifyoumissthetrainimonyouwillknowthatiamgoneifyoumissthetrainimonyouwillknowthatiamgoneifyoumissthetrainimonyouwillknowthatiamgoneifyoumissthetrainimonyouwillknowthatiamgoneifyoumissthetrainimonyouwillknowthatiamgoneifyoumissthetrainimonyouwillknowthatiamgone'