关于数字压缩课程的作业记录，附完整代码

1.1 算法特点 LZW压缩算法是一种无损数据压缩算法。在众多的压缩技术中，LZW算法是一种通用的、性能优良并得到广泛应用的压缩算法，它是一种完全可靠的算法，与其他算法相比，往往具有更高的压缩效率。LZW算法保留了LZ码的自适应功能，压缩比也大致相同，其显著特点是逻辑简单（典型的LZW算法处理1个字符不超过三个时钟周期）、硬件实现廉价、运算速度快，在消息长度为一万字符数量级时可以得到令人满意的压缩效果。 1.2 算法基本原理 LZW压缩算法提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小[1]。看起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始文件数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表.

LZW压缩有三个重要的对象：数据流（CharStream）、编码流（CodeStream）和编译表（String Table）。在编码时，数据流是输入对象（文本文件的据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都须要用借助的对象。

字符（Character）：最基础的数据元素，在文本文件中就是一个字节，在光栅数据中就是一个像素的颜色在指定的颜色列表中的索引值； 字符串（String）：由几个连续的字符组成； 前缀（Prefix）：也是一个字符串，不过通常用在另一个字符的前面，而且它的长度可以为0； 根（Root）：一个长度的字符串； 编码（Code）：一个数字，按照固定长度（编码长度）从编码流中取出，编译表的映射值；图案：一个字符串，按不定长度从数据流中读出，映射到编译表条目[2]。

Step1：将词典初始化为包含所有可能的单字符，当前前缀P初始化为空。 Step2：当前字符C：=字符流中的下一个字符。 Step3：判断P+C是否在词典中，如果“是”，则用C扩展P，即让P：=P+C，返回到step2，如果“否”，则输出与当前前缀P相对应的码字W；将P+C添加到词典中，令P:=C，并返回到step2. Step4：判断字符流中是否还有字符，如果“是”，就返回step2，如果否，就把代表当前前缀P的码字输出到码字流。 LZW压缩算法流程图: LZW算法举例

数据的解码，其实就是数据编码的逆向过程，要从已经编译的数据（编码流）中找出编译表，然后对照编译表还原数据。 ：词典中包含所有的前缀根（即每个字符组成词典） ：译码时先记住先前码字（pW） ：从码字流中读出先前的码字（cW） ：输出当前码字（cW）对应的单词，string（cW） ：string（pW）与string（cW）的第一个字符合在一起，放入词典中。 LZW解码过程流程图

编程环境：VC++ 6.0 计算机配置：Windows 10 实验数据类型： 实验数据1：字符串类型 “ ababcbababaaaaaaa” 实验数据2：一段英文文献 “ Data compression has an undeserved reputation for being difficult to master, hard to implement, and tough to maintain. In fact, the techniques used in the previously mentioned programs are relatively simple, and can be implemented with standard utilities taking only a few lines of code. This article discusses a good all-purpose data compression technique: Lempel-Ziv-Welch, or LZW compression.” 实验数据3：浮点数组

当我们对书上的例子一串由三个字母组成的字符串进行LZW压缩时： 发现和书上得到的结果是一致的，代码的正确性得到保障。 信息熵 H(x) =1.166

代码如下：