这两天实验截止过于集中以至于没法连更，因此小破鱼打算一口气全部打通关后出几期专题答案分享

包括数据结构的实验、python与大数据分析实验、众智科学与网络化群体实验、数据科学导论实验。

LZW压缩（LZW compression）是一种由Abraham Lempel、Jacob Ziv和Terry Welch发明的基于表查寻算法把文件压缩成小文件的无损压缩方法。

之前有在网上看到过一些大佬讲述的相关专题：

比如Lempel-Ziv-Welch Compression Algorithm - Tutorial - YouTube和LZW Compression Algorithm Explained | An introduction to data compression - YouTube

然而，问题是：对于使用的课本 《Data Structures, Algorithms, & Applications in C++》的案例并不是能够很好的匹配到，所以便聊一聊吧。

话不多说，直接看算法。

1、LZW压缩规则 :

开始，为该文本文件中所有可能出现的字母，分配一个代码，构成初始字典。LZW压缩器不断地在输入文件的未编码部分 中寻找在字典中出现的最长的前缀p，输出前 缀p相应的代码，若输入文件中的下一个字符 为c，则为pc分配一个代码,并插入字典。

2、LZW压缩实现:

设当前前缀p为空，读取下一个字符c; 循环(当前字符串pc不为空){
    if (当前字符串pc在字典中) 当前前缀p=当前字符串pc;
    else { 
        将当前字符串pc插入到字典中; 输出当前前缀p的编码;
        p=c;
            }
    读取下一个字符c; 
    }
    输出最后一个当前前缀p的编码;                    

例题1(来自课堂惊险提问)：aaabbbbbbaabaaba的lzw编码（十进制）：

 

分析此题：首先该字符串中只有a和b两个字母，因此字典中a为0，b为1.

循环1:第一位字符为a，a在字典中，前缀为a，

循环2:读取第二位a，aa不在字典中，将aa插入字典中的2，输出当前aa的前缀a的编码0，前缀变为a。（0）

循环3:读取第三位a，aa在字典中，前缀变为aa（0）

循环4:读取第四位b，aab不在字典中，补充aab到字典中的3，输出前缀aa的编码2，前缀变为b（02）

循环5:读取第五位b，bb不在字典中，补充bb到字典中的4，输出前缀b的编码1，前缀变为第五位的b（021）

循环6:读取第六位b，bb在字典中，前缀变为bb（021）

循环7:读取第七位b，bbb不在字典中，补充bbb到字典中的5，输出前缀bb的编码4，前缀变为b（0214）

循环8:读取第八位b，bb在字典中，前缀变为bb（0214）

循环9:读取第九位b，bbb在字典中，前缀变为bbb（0214）

循环10:读取第十位a，bbba不在字典中，补充进字典的6，输出bbb编码5，前缀变为a（02145）

循环11:读取第十一位a，aa在字典中，前缀变为aa（02145）

循环12:读取第十二位b，aab在字典中，前缀变为aab（02145）

循环13：读取第十三位a，aaba，补充aaba到7，输出aab编码3，前缀变为a（021453）

循环14:读取第十四位a：aa，前缀变为aa，（021453）

循环15:读取第十五位b：aab在字典中，前缀为aab（021453）

循环16:读取第十六位a，aaba在字典中，末位按照算法默认输出，对应为7，（0214537）

至此循环结束。

可以不妨得出两个结论：

1、第一位一定是一个字母，如果在字典中有，前缀更新编码不变；字典中没有，先加入字典下一位编号，前缀更新编码输出前缀。

2、和第一条一样（其实可以画一个2*n的表格对应一下）

 

 

有了压缩便会有解压缩（LZW）

输入第一个代码q，输出相应的文本(第一个代码一定对应于一个单一的字母)
输入下一个代码p; 
If (p在字典中){
输出代码p对应的文本串text(p); 
将text(q)fc(p)及代码插入到字典中
}
Else{
此时只会是: text(p)=text(q)fc(q)；
即代码串qp对应文本串text(q)text(q)fc(q)】 
输出代码p对应的文本串text(q)fc(q);
将text(q)fc(q)及代码插入到字典中
}
q=p;

也就是说是上一个过程的逆过程。此处的代码指的是刚刚求出的编号，现在是假设只知道a是0，b是1，继续推。

编码在字典，输出对应的字母组，将该编码和它的前缀插入字典；若不在，只能说明编码重复，输出插入和压缩过程类似

例题2

01041627

 

答案：输出abaaabbb

你明白了吗？