当前位置 博文首页 > XSES_yasuoman的博客:python实现LZW算法
①原理: 提取原始文本文件数据中的不同字符,基于这些字符创建一个编译表,然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符,减少原始数据大小。
②编码过程:
伪代码 Pseudo code:
初
始
化
:
扫
描
所
有
字
符
,
将
所
有
的
单
个
字
符
,
按
字
母
顺
序
初
始
化
,
并
放
入
字
典
中
初始化:扫描所有字符,将所有的单个字符,按字母顺序初始化,并放入字典中
初始化:扫描所有字符,将所有的单个字符,按字母顺序初始化,并放入字典中
读
入
第
一
个
字
符
赋
值
S
1
读入第一个字符赋值S1
读入第一个字符赋值S1
s
t
e
p
:
{
读
入
下
一
个
输
入
字
符
→
S
2
step:\left\{读入下一个输入字符→S2\right.
step:{读入下一个输入字符→S2
i
f
?
S
2
为
空
if \ S_2为空
if?S2?为空
{
扫
尾
:
输
出
S
1
的
i
n
d
e
x
,
结
束
}
\left\{扫尾:输出S1的index,结束\right\}
{扫尾:输出S1的index,结束}
i
f
?
S
1
+
S
2
已
存
在
字
典
中
if\ S_1+S_2已存在字典中
if?S1?+S2?已存在字典中
{
S
1
+
S
2
→
S
1
?
r
e
p
e
a
t
,
s
t
e
p
}
\left\{S_1+S_2→S_1\right. \left.\ repeat,step \right\}
{S1?+S2?→S1??repeat,step}
e
l
s
e
{
输
出
S
1
的
i
n
d
e
x
else\left\{输出S1的index\right.
else{输出S1的index
S
2
→
S
1
S_2→S_1
S2?→S1?
将
S
1
+
S
2
顺
序
添
加
到
字
典
末
尾
将S1+S2顺序添加到字典末尾
将S1+S2顺序添加到字典末尾
r
e
p
e
a
t
,
s
t
e
p
}
\left. repeat,step\right\}
repeat,step}
}
\left.\right\}
}
③解码过程:
根据输出的index,在字典中查找相应的字符按顺序输出,即可解码
# 江南大学 物联网18级——MH
# python pandas库用于展示字典内容,不需要自己使用format进行格式规范了
import pandas as pd
# _flatten用于展平二维列表→一维元组,list(dict.values())得到的是二维列表
from tkinter import _flatten
# LZW解码
def lzw_decoding(list_index_out, dict_syb_idx):
list_index = list(dict_syb_idx.values())
list_index = list(_flatten(list_index))
list_syb = list(dict_syb_idx.keys())
print("\n>>>LZW解码为:")
for index_lp_o in range(0, len(list_index_out)):
for index_lp_i in range(0, len(list_syb)):
if list_index_out[index_lp_o] == list_index[index_lp_i]:
print(list_syb[index_lp_i], end=' ')
# 初始化操作,将单个字符按一定顺序排列,放入字典中
def initialization(str_input):
# 符号列表、存储index和符号的字典、index列表初始化
list_symbol, list_index = [], []
dict_symbol_index = {}
# 遍历输入的字符序列,对于截止当前下标,只出现一次的单个符号,放入字典;出现多次已经在字典中,不必重复
for index_loop in range(0, len(str_input)):
if str_input.count(str_input[index_loop], 0, index_loop + 1) == 1:
list_symbol.append(str_input[index_loop])
list_symbol.sort()
for index_loop in range(0, len(list_symbol)):
dict_symbol_index[list_symbol[index_loop]]