参考：https://blog.csdn.net/hdkks/article/details/116005301
参考：https://segmentfault.com/a/1190000011425787
一、实验目的
掌握词典编码的基本原理，用C/C++/Python等语言编程实现LZW解码器并分析编解码算法。
选择十种不同格式类型的文件，使用LZW编码器进行压缩得到输出的压缩比特流文件。对各种不同格式的文件进行压缩效率的分析。
二、实验内容
（1）实验思路
1．LZW编码原理和实现算法
LZW的编码思想是不断地从字符流中提取新的字符串，通俗地理解为新“词条”，然后用“代号”也就是码字表示这个“词条”。这样一来，对字符流的编码就变成了用码字去替换字符流，生成码字流，从而达到压缩数据的目的。
LZW编码是围绕称为词典的转换表来完成的。LZW编码器通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流。
LZW编码算法的步骤如下：
步骤1 将词典初始化为包含所有可能的单字符，当前前缀P初始化为空。
步骤2 当前字符 C = 字 符 流 中 的 下 一 个 字 符 C=字符流中的下一个字符 C=字符流中的下一个字符。
步骤3 判断 P ＋ C P＋C P＋C是否在词典中
（1）如果“是”，则用 C C C扩展 P P P，即让 P = P ＋ C P=P＋C P=P＋C，返回到步骤2。
（2）如果“否”，则输出与当前前缀 P P P相对应的码字 W W W；将 P ＋ C P＋C P＋C添加到词典中；令 P = C P=C P=C，并返回到步骤2
2．LZW解码原理和实现算法
LZW解码算法开始时，译码词典和编码词典相同，包含所有可能的前缀根。
具体解码算法如下：
步骤1 在开始译码时词典包含所有可能的前缀根。3
步骤2 令CW：=码字流中的第一个码字。
步骤3 输出当前缀-符串string.CW到码字流。
步骤4 先前码字PW：=当前码字CW。
步骤5 当前码字CW：=码字流的下一个码字。
步骤6 判断当前缀-符串string.CW 是否在词典中。
（1）如果”是”，则把当前缀-符串string.CW输出到字符流。
当前前缀P=先前缀-符串string.PW。
当前字符C=当前前缀-符串string.CW的第一个字符。
把缀-符串P+C添加到词典。
（2）如果”否”，则当前前缀P：=先前缀-符串string.PW。
当前字符C：=当前缀-符串string.CW的第一个字符。
输出缀-符串P+C到字符流,然后把它添加到词典中。
步骤7 判断码字流中是否还有码字要译。
（1）如果”是”，就返回步骤4。
（2）如果”否”，结束。
（2）代码补全
补充解码部分代码如下：
————————————————
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。