前言
暑假闲来无事，用几天时间写了一个比较完整的LZW压缩算法实现，所以做点简单的笔记。
这个算法本身是怎么回事就不再赘述了，网上已有的教程铺天盖地，只给出两篇我觉得很赞的。第一篇非常详细地描述了整个算法，包括Example、特殊情况等等，以及实现过程中所需要注意的几乎所有细节，可以看出作者非常热衷于这些压缩、加密算法，有空应该好好读读他的其他文章。但令人奇怪的是，尽管作者已经考虑的这么周到了，但却没有实现gif标准中的CLEAR清空标记，这可是非常基础且必要的东西，不然实现出来的程序根本没法压缩大文件。不过作者给出的C代码还是非常严谨可读的，虽然用了很多奇怪的优化Trick，并且看起来注释远远多于代码量……第二篇则是贴上了两张有点语意不清的流程图，但是好在作者给出了一个非常简洁明了的实现，虽然很简陋，但是用来理解算法核心思想还是非常合适的。
核心思想
其实对于所有压缩算法而言，所要做的事情无非就是减少信息的冗余程度——换句话说，就是把那些占用空间大的信息转换成占用空间小的信息，同时定义一种逆变换，使得可以由后者无损恢复出前者。对于LZW压缩算法而言，本质上是在用String->Int的字典来完成这种转换，而在解压过程中使用一个Int->String的字典来完成逆变换。但是LZW算法巧妙之处在于，它通过一种约定好的操作顺序，可以使得我们不用保存压缩过程中产生的字典：因为在解压过程中，这个字典可以被重新创建出来，我们只需要保存压缩文件即可。
LZW算法的压缩操作是这样定义的：首先我们有一个String用来存储未被压缩输出的字符串，以及一个Char用来存储当前读入的字符。假设在某个时刻我们有非空的String，并且已经读入了一个新的Char，那么如果String + Char这个新字符串存在于字典中，就令String += Char，然后再次读入；否则，就先输出String所对应的压缩编码，再将String + Char加入字典，最后令String = Char。我们知道初始状态时String为空，这样从这个状态往后推几步，我们会发现先前所定义的操作就是在不断地尝试构造新的字典项，保证了字典中的所有String均被直接输出过ASCII数值，然后再次出现时才会以压缩编码来代替——这也就是信息冗余的减小过程，算法使用一个压缩编码来代替了一整段字符。
有了上述基础，我们就可以引入巧妙的解压操作。解压过程中我们定义两个字符串NewString和OldString。其中前者表示当前解压出的字符串，而后者表示上一次解压出来的字符串。在解压的过程中，假设我们预先知道基本可以保证每次读入的压缩编码都存在于字典中（存在一种特殊情况，这里不详细讨论），所以每次的NewString就等于压缩编码在字典中的对应字符串。那么问题就在于，我们是如何做出这个保证的呢？从压缩的流程中我们可以看出，每次被加入字典的只有String + Char，而每次输出的仅仅是String所对应的压缩编码——因而它在解压过程中显然就对应OldString。而那个Char在被输出的时候，按照顺序，一定是作为NewString的第一个字符的，也就是说，在解压过程中应该被加入字典的每个字符串，前一部分是上一次解压出的那个OldString，而后一部分，正好就是NewString[0]！这样，只要我们在解压过程中每次将OldString + NewString[0]加入字典，就“基本”能够保证每次读入的压缩编码都会存在于字典中，剩下需要考虑的就只是一些边界条件的处理了，RTFSC即可彻底理解，在此不予赘述。
实现细节
首先，在输出数据的过程中，显然不能用定长的类型来输出，比如int之类，不然压缩之后说不定占用的空间还会变大。从压缩算法的流程中我们可以看出，字典项的编码是会逐渐增大的，也就是说输出的编码长度可以基本认为也是在不断变长。为了实现输出变长的整数编码，我们有必要实现一套支持按长度来输出整数的IO库。这里我用的实现方式是继承了fstream类，然后添加了一个缓冲区、一个缓冲字节以及几个函数来完成上述功能。但是我做了一件非常逗逼的事情，就是为fstream这样明明带有缓冲区的类又额外添加了一个缓冲区，实乃画蛇添足，毫无意义。不过考虑到实现过程着实麻烦，这部分代码就没有优化掉，算是做了个编码练习吧。
由于需要进行变长编码，因此在输出中需要指明何时应该增加编码长度，这种标志的实现方式详见代码，是一种非常巧妙的方法。另一方面，我们可以看出算法中的字典几乎就是一个天然的红黑树，用STL中的map即可轻松实现。但问题在于map中所记录的项目数量显然不可能无限增长，不然会严重影响性能，因此有必要在字典增长到一定程度的时候清空并重建。gif的标准中定义了一个CLEAR标志，意思是如果读取到这个标记，就清空当前已有的字典并重建。这个标志的实现同样很具有技巧性，在代码中可以充分看出。本人的LZW算法实现在这里，附带一个用Python写的简陋GUI。
最后感慨一下，Windows下用VS进行编程开发实乃神器，不仅原生集成了git系统，可以与Github无缝对接，而且操作界面非常简明易用，支持随意添加、排除文件等等。不得不说，这样将编辑器、编译器、调试器、代码优化、版本控制等等功能紧密结合在一起，并且GUI界面极为稳定可靠的IDE，实在是太有竞争力了。
参考文献
- http://michael.dipperstein.com/lzw/
- http://blog.csdn.net/abcjennifer/article/details/7995426