不同于哈弗曼编码针对于每个元素编码，LZW主要针对字符串的编码优化，也就是把出现频率高的字符串压缩成一个字符表示，这也是大名鼎鼎的GIF采用的压缩格式。下面我将从三个角度谈谈我的一些理解，文章主要参考了这位大佬：LZW编解码详解_lzw编码-CSDN博客。
思想简述
LZW主要针对字符串压缩。比如对于字符串ABAB，首先对于每个会出现的字符都有一个默认编码，也就是A-0，B-1，因为LZW的压缩要求解压时不需要压缩编码表，因此是要求不需要编码表重建的，所以第一个A和第二个B不能连在一起压缩，分别编码为0和1；然后因为AB出现过了，记录在字典中，即AB-2，所以后面的AB就直接编码为2，编码后的字符串为012。
可以想象，如果直接把两个AB都变成2，那么压缩后是22，一上来就是一个2，那么无法重建字典了，因为这个2怎么来的无从得知。
如何压缩
压缩的过程相比解压要简单，简单来说就是维护两个字符串，分别是未编码P和当前字符C，这里的P是当前最长的可编码字符串，C就是当前指向的字符，比如xyabcdef，假设此时P起点为的a,终点是d（加粗处），此时C指向的e，假设abcd+e在字典中出现了，那么P更新为P+C也就是abcde，相当于此时还可能继续往下找到更长的编进字典；如果abcd+e没有出现在字典中，那么最长的可编码字符串就是abcd，此时为这个字符串编码，并且在字典中增加一个新的编码对应abcde，同时更新P为e（更新为指针C指向的字符），继续找下面的最长可编码字符串。
这个过程简单来说就是找最长可编码字符串，一直找到无法编码了，为字符串编码，把无法编码的加入字典。
下面是对于ababcababac的编码过程，可以对照，编码后的结果是0132372 ：
如何解码
解码略复杂。可以想想编码的过程，编码的过程实际上就是找到P和C，然后把P编码，把P+C放入字符串，解码就反过来，将当前码值解码，并且把当前码值的解码（P）和下一个码值对应的解码的首字符（C）加入字典。
具体实现还是维护P和C，只不过P代表当前编码对应字符串，C代表下一个位置的编码对应字符串的首字符。
下面是推导的过程，可以参考对照一下：
下面是具体的过程解析：
在解码时，我们面对的实际上是一串数字，就像是0132372这样 ，我们一开始知道的是默认的编码规则，也是就是a-0，b-1，c-2…，假设对于编码后的字符串0132372，编码是把最长可编码字符串P+C编为新的字典元素，P实际就是这里的其中一个元素，比如0,而C就是P的后一个元素，也就是0后面的1串解码后的第一个字符（这个第一个很关键，后面的我都不管，我就要第一个，这是由编码决定的），解码过程就呼之欲出了，P指向一个元素，C是下一个元素，分两种情况讨论（建议先写一遍上面的过程，然后再看）：
-
如果C对应的解码可以直接从字典中找到，比如P对应0，C对应1，此时0解码为a，1解码为b，P=a，C=b(1解码后的第一个字符），把P+C加入字典，也就是ab-2。
-
如果C对应的解码不能直接从字典中找到，就比如到了这里的37部分，p=3解码为ab，C=7，但是字典中还未出现7对应的元素，这时就要想想是什么导致了这种情况？
先看7是怎么来的，在编码时，ca编码为6之后，P更新为a，然后找到P=ab发现ab字典中也有，所以保留，再往后此时C指向a，aba字典中没有，于是给aba编码为7，更新P为a。
不考虑前后的细节，用…代替，这里的P=3=ab，C+y对应的是7对应的解码字符串，目前还不知道 7的编码规则，无法解码。假如 7的编码没有用到P，那么两种情况：一种是7在P之前就编码好了，那么此时7应该在字典中，矛盾；一种是7的编码在C+y+…中编好，这与编码时寻找可编码字符串矛盾，因为还没放入字典就被用了，所以唯一可能性就是7的编码用到了前面的P，而由于7还未解码，因此对应的解码规则也还没被推导出来，而我们关心的放入字典的就是7的首字符，那么其实也就是这里P的首字符a，所以新的规则P+C(P的第一个)=aba-7加入字典，解码7。
最后这段解析比较绕，我自己也绕来绕去感觉有点乱，有不足和错误可以直接指正。
原文地址:https://blog.csdn.net/weixin_60360239/article/details/134758445
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_29306.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
