LZW压缩算法——简明原理与实现
LZW和哈夫曼编码一样,是无损压缩中的一种。该算法通过建立字典,实现字符重用与编码。本文首先讲下LZW的编解码原理,然后给出LZW的实现code。
*********************原理*********************
编码:
编码0-255用来存储Ascii码为[0,255]的字符,放在字典里。编码从256开始,将出现过的字符计入字典核心思想:利用字符的可重用性,每当往结果输出一个编码,就将一个新的string存入dictionary算法流程:
举例:
解码:
编码的逆过程,若编码是string到int的映射,我们可以将解码过程描述为int到string的映射。
LZW算法的解码无需在编码过程中存储字典(这样太浪费空间了)解码初始化依旧用256个Ascii码,后面每读入一个编码(int),检查其在dictionary中的映射,并不断将新的映射加入字典算法流程:
解码的例子建议读者用下面的代码直接调试吧~
*********************实现*********************
我用C++实现的,Compress和Decompress两个函数分别实现编解码
Reference:
1. http://www.stringology.org/DataCompression/lzw-e/index_en.html
2. http://www.dspguide.com/ch27/5.htm
3. http://marknelson.us/1989/10/01/lzw-data-compression/
4. http://www.ccs.neu.edu/home/jnl22/oldsite/cshonor/jeff.html
关于Compression更多的学习资料将继续更新,敬请关注本博客和新浪微博Sophia_qing。