2023年11月29日发(作者：)
【案例】压缩算法——LZ算法
⽂章⽬录
1. 案例介绍
今天我们来介绍⼀种⽆损压缩算法 —— LZ 编码，以此来体会压缩解压的魅⼒。
举个例⼦，如果我们要发送 “AAA” 这个字符串，那么我们就要发送 3 个字节的数据来存储这个信息，但是，如果将数据压缩，以数字
+字符的形式，可能只需要使⽤ “3A” 作为发送的信息，也就是只需要使⽤ 2 个字节即可完成发送，收到者会解压该信息，理解为由 3
个后⾯的字符组成的信息流，解压得到 “AAA”。
Lempel Zip（LZ）编码是称为基于字典的编码的那⼀类算法的⼀个例⼦，它是⽤其发明者的名字（Abraham Lempel 和 Jacob
Ziv）命名的。在通信会话的时候它将会产⽣⼀个字符串字典。如果接受和发送双⽅都有这样的字典，那么字符串可以由字典中的索引
代替，以减少通信的数据的传输量。这种算法有不同的版本（LZ77、LZ78等）。
—— 《计算机科学导论 第三版》
2. 准备⼯作
2.1 异常处理
在学习 Python 的时候，我们编写的代码可能会出错，这些错误会被编译器所捕捉到，显⽰给我们看。⽐如：
ZeroDivisionError #
除零错误
SyntaxError #
语法错误
TypeError #
类型错误
NameError #
命名错误
...
以上是系统会⾃动触发判断出的异常，基本上你只要在控制台看到了这些错误，程序就会停⽌运⾏，类似于 Linux 中的 panic() 命令效
果，系统宕机，不过我们的程序只是会停⽌运⾏，不会导致计算机崩溃。
2.1.1 我们⾃⼰怎么主动触发异常呢?
Python 为我们提供了 raise 语句，我们可以在需要的时候，⾃⼰编写 raise 语句来终⽌程序运⾏。
举⼀个例⼦，编写⼀个数值判断程序：
x = 10
if x > 5:
print("x ⼤于 5.")
if x == 10:
raise RuntimeError("x ⾮法.")
if x > 0:
print("x ⼤于 0.")
该程序⾸先给 x 赋值为 10，然后使⽤ 3 个 if 语句，来分别进⾏判断，你猜程序运⾏结果是什么？
x ⼤于 5.
-------------------------------------------------------------------------------
LZW_main.py 130 <module>
raise RuntimeError("x ⾮法.")
RuntimeError:
x ⾮法.
Process finished with exit code 1
类似上述，程序打印了字符串“x ⼤于 5”，raise 了出错信息“x ⾮法”，但是本应该会执⾏的第 3 个 if 并没有执⾏，我们并没有看到打
印的字符串，所以，当 raise 了⼀个错误类型后，会发出⼀个异常，程序会终⽌执⾏。
2.1.2 我们该如何⾃⼰捕获异常呢？
下⾯这个实例来⾃菜鸟教程，⽬的是为了说明我们如何编写代码捕获处理异常：
try:
runoob()
except AssertionError as error:
print(error)
else:
try:
with open('') as file:
read_data = file.read()
except FileNotFoundError as fnf_error:
print(fnf_error)
finally:
print('这句话，⽆论异常是否发⽣都会执⾏。')
使⽤ try-except-else-finally 结构，当然这其中的关键字不是必须的，其中 except ⽤来捕获可能的异常，如果出错就会执⾏ except 下⾯
的代码，如果没有出错就会执⾏ else 下⾯的代码，⽽ finally 中的代码⽆论出错与否都会执⾏。发现了吗？只要我们使⽤异常捕获语句，我
们就能够让程序即使发⽣了异常也能运⾏下去。
2.2 isinstance() 函数
isinstance() 函数来判断⼀个对象是否是⼀个已知的类型，类似 type()。
>>> x = "123"
>>> isinstance(x, str)
True
2.3 ⽣成器
在 Python 中，使⽤了 yield 的函数被称为⽣成器（generator）。
跟普通函数不同的是，⽣成器是⼀个返回迭代器的函数，只能⽤于迭代操作，更简单点理解⽣成器就是⼀个迭代器。
在调⽤⽣成器运⾏的过程中，每次遇到 yield 时函数会暂停并保存当前所有的运⾏信息，返回 yield 的值, 并在下⼀次执⾏ next() ⽅
法时从当前位置继续运⾏。
—— 菜鸟教程
⽣成器函数并不会将所有结果都计算返回，它只会保存某次计算的”环境“，以进⾏下⼀次运算，你使⽤ next() ⽅法，每调⽤⼀次⽣成
器，那么它就会返回⼀个结果，你不停地调⽤，它就会不停地给你返回结果。
举⼀个我们程序中⽤到的⼀个⽣成器的例⼦，该⽣成器会依据给定的初始值（如果没有给定默认为 1），你每调⽤⼀次⽣成器，他就会给你
返回⼀个在之前基础上加 1 的数字⽤作下标。
def get_index_generator(index_start=None):
"""
索引⽣成器
从 index_start 开始, 否则从 1 开始
:return: 下标索引值
"""
i = 1 if index_start is None else index_start # 1.
三元表达式，⽤来标定下标从哪⾥开始，默认为
while True:
yield i
i += 1
g = get_index_generator(0)
for i in range(10):
print(next(g))
g = get_index_generator(-5)
for i in range(10):
print(next(g))
运⾏结果如下：
0
1
2
3
4
5
6
7
8
9
-5 # -5
指定下标从开始
-4
-3
-2
-1
0
1
2
3
4
2.4 ⼀种特殊的数据结构 —— 有序字典
有序字典和通常的字典类型类似，但是与⼀般字典不同，它可以保存元素插⼊的顺序，⽽不是任意顺序迭代。
样例程序：
d = collections.OrderedDict()
d[0] = 0
d[1] = 10
d[2] = 20
d[3] = 30
for k, v in d.items():
print(k, v)
运⾏结果
0 0
1 10
2 20
3 30
3. 算法思想
压缩：以纯英⽂字符串为例，逐个遍历每个字符串，如果当前字典表中还没有该字符，则将该字符加⼊字典中，键为该字符，值为⽣成器返
本算法为 LZ 编码的简单演⽰，仅限于纯英⽂⽂本
该种编码基于字典。
"""
import collections
import pretty_errors
message = "BAABABBBAABBBBAC" # BA2B3B1A4B5C
def showError(ErrorType=None):
"""
出错处理
:param ErrorType: 错误类型
:return:
"""
if ErrorType is TypeError:
raise TypeError("""
1. maybe index_start is not int(get_index_generator()).
2. maybe charter is not pure English words(encoding_msg()).
3. maybe data is not str or pure English words(dataIsAlpha()).
""")
raise RuntimeError("Unexpected error.")
def dataIsAlpha(data=""):
"""
如果 data 不纯英⽂返回 False 否则 raise
:param data:
:return:
"""
if isinstance(data, str) is False:
showError(TypeError)
if data.isalpha() is False:
showError(TypeError)
else:
return True
def get_index_generator(index_start=None):
"""
索引⽣成器
从 index_start 开始, 否则从 1 开始
:return: 下标索引值
"""
if isinstance(index_start, int) is False and index_start is not None:
showError(TypeError)
i = 1 if index_start is None else index_start
while True:
yield i
i += 1
def encoding_msg(msg=""):
"""
:param msg: 预压缩的字符串
:return: 压缩后的字符串
"""
map = collections.OrderedDict() # map['A'] = 1
映射表
INDEX_GENERATOR = get_index_generator() # generator INDEX_GENERATOR
构造给
subWords = '' #
保存中间⼦串
result_str = "" #
保存最终压缩结果
print("待压缩字符流:t{0}, 长度:{1}.".format(msg, len(msg)))
for i in msg:
subWords += i
subWords += i
if subWords not in map.keys():
map[subWords] = next(INDEX_GENERATOR) # map['A'] = 1
映射表
if len(subWords) > 1:
result_str += str(map[subWords[:-1]]) + subWords[-1]
else:
result_str += subWords
subWords = ''
print("dictionary:")
for k, v in map.items():
print("{0}t-->t{1}".format(k, v))
print("压缩结果:t{0}, 长度:{1}".format(result_str, len(result_str)))
return result_str
def decoding_msg(msg=""):
"""
解压缩字符流
:param msg:
:return:
"""
if dataIsAlpha(message):
pass
print("待解压字符流:t{0}, 长度:{1}.".format(msg, len(msg)))
map = collections.OrderedDict() # map[1] = 'A'
映射表
INDEX_GENERATOR = get_index_generator()
subWords = '' #
保存中间⼦串
result_str = "" #
保存最终压缩结果
for i in msg:
subWords += i
if subWords not in map.values() and i.isalpha():
if len(subWords) > 1:
subWords = map[int(subWords[:-1])] + subWords[-1]
map[next(INDEX_GENERATOR)] = subWords
result_str += subWords
else:
map[next(INDEX_GENERATOR)] = subWords
result_str += subWords
subWords = ''
print("解压缩结果:t{0}, 长度{1}".format(result_str, len(result_str)))
if __name__ == "__main__":
if dataIsAlpha(message):
pass
decoding_msg(msg=encoding_msg(msg=message))
5. 运⾏结果
待压缩字符流: BAABABBBAABBBBAC, 长度:16.
dictionary:
B --> 1
A --> 2
AB --> 3
ABB --> 4
BA --> 5
ABBB --> 6
BAC --> 7
压缩结果: BA2B3B1A4B5C, 长度:12
待解压字符流: BA2B3B1A4B5C, 长度:12.
解压缩结果: BAABABBBAABBBBAC, 长度16
Process finished with exit code 0
6. 算法特点
对于数据流中连续重复出现的字节和字串，该压缩技术有很⾼的压缩⽐。
其不仅可以⽤于⽂本程序，还能够⽤于图像数据处理。
发布评论