国外域名抢注网站,wordpress 爱奇艺插件下载失败,WordPress数据库和网站文件,做和别人一样的网站不同于哈弗曼编码针对于每个元素编码#xff0c;LZW主要针对字符串的编码优化#xff0c;也就是把出现频率高的字符串压缩成一个字符表示#xff0c;这也是大名鼎鼎的GIF采用的压缩格式。下面我将从三个角度谈谈我的一些理解#xff0c;文章主要参考了这位大佬#xff1a;… 不同于哈弗曼编码针对于每个元素编码LZW主要针对字符串的编码优化也就是把出现频率高的字符串压缩成一个字符表示这也是大名鼎鼎的GIF采用的压缩格式。下面我将从三个角度谈谈我的一些理解文章主要参考了这位大佬LZW编解码详解_lzw编码-CSDN博客。
思想简述 LZW主要针对字符串压缩。比如对于字符串ABAB首先对于每个会出现的字符都有一个默认编码也就是A-0B-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假设abcde在字典中出现了那么P更新为PC也就是abcde相当于此时还可能继续往下找到更长的编进字典如果abcde没有出现在字典中那么最长的可编码字符串就是abcd此时为这个字符串编码并且在字典中增加一个新的编码对应abcde同时更新P为e更新为指针C指向的字符继续找下面的最长可编码字符串。 这个过程简单来说就是找最长可编码字符串一直找到无法编码了为字符串编码把无法编码的加入字典。
算法步骤如下 初始状态字典里只有所有的默认项例如0-a1-b2-c。此时P和C都是空的。 读入新的字符C与P合并形成字符串PC。 在字典里查找PC如果: PC在字典里PPC。 PC不在字典里将P的记号输出在字典中为PC建立一个记号映射更新PC。 返回步骤2重复直至读完原字符串中所有字符。 下面是对于ababcababac的编码过程可以对照编码后的结果是0132372 如何解码 解码略复杂。可以想想编码的过程编码的过程实际上就是找到P和C然后把P编码把PC放入字符串解码就反过来将当前码值解码并且把当前码值的解码P和下一个码值对应的解码的首字符C加入字典。 具体实现还是维护P和C只不过P代表当前编码对应字符串C代表下一个位置的编码对应字符串的首字符。
算法流程如下 初始状态字典里只有所有的默认项例如0-a1-b2-c。此时pW和cW都是空的。 读入第一个的符号cW解码输出。注意第一个cW肯定是能直接解码的而且一定是单个字符。 赋值pWcW。 读入下一个符号cW。 在字典里查找cW如果: a. cW在字典里 (1) 解码cW即输出 Str(cW)。 (2) 令PStr(pW)CStr(cW)的第一个字符。 (3) 在字典中为PC添加新的记号映射。 b. cW不在字典里: (1) 令PStr(pW)CStr(pW)的第一个字符。 (2) 在字典中为PC添加新的记号映射这个新的记号一定就是cW。 (3) 输出PC。 返回步骤3重复直至读完所有记号。 下面是推导的过程可以参考对照一下 下面是具体的过程解析 在解码时我们面对的实际上是一串数字就像是0132372这样 我们一开始知道的是默认的编码规则也是就是a-0b-1c-2...假设对于编码后的字符串0132372编码是把最长可编码字符串PC编为新的字典元素P实际就是这里的其中一个元素比如0,而C就是P的后一个元素也就是0后面的1串解码后的第一个字符这个第一个很关键后面的我都不管我就要第一个这是由编码决定的解码过程就呼之欲出了P指向一个元素C是下一个元素分两种情况讨论建议先写一遍上面的过程然后再看 如果C对应的解码可以直接从字典中找到比如P对应0C对应1此时0解码为a1解码为bPaCb(1解码后的第一个字符把PC加入字典也就是ab-2。 如果C对应的解码不能直接从字典中找到就比如到了这里的37部分p3解码为abC7但是字典中还未出现7对应的元素这时就要想想是什么导致了这种情况 先看7是怎么来的在编码时ca编码为6之后P更新为a然后找到Pab发现ab字典中也有所以保留再往后此时C指向aaba字典中没有于是给aba编码为7更新P为a。 回到解码此时37的P3解码为abC对应77在字典中找不到就说明编码7一定同时用到了3和7的首字符看下图 不考虑前后的细节用...代替这里的P3abCy对应的是7对应的解码字符串目前还不知道 7的编码规则无法解码。假如 7的编码没有用到P那么两种情况一种是7在P之前就编码好了那么此时7应该在字典中矛盾一种是7的编码在Cy...中编好这与编码时寻找可编码字符串矛盾因为还没放入字典就被用了所以唯一可能性就是7的编码用到了前面的P而由于7还未解码因此对应的解码规则也还没被推导出来而我们关心的放入字典的就是7的首字符那么其实也就是这里P的首字符a所以新的规则PC(P的第一个)aba-7加入字典解码7。 最后这段解析比较绕我自己也绕来绕去感觉有点乱有不足和错误可以直接指正。
