LZW编码的学习与实现

大家好，现在是2020年5月19日，不知不觉5年过去了，看到最近还有很多人评论我的这篇文章，非常的开心和满足，显然我写这篇文章所做的微小贡献帮助到了一些人。今天我从头到尾再看了一遍我写的东西，还是有一些东西没有描述清楚，比如下面第一个表里里面，dictionary 那一列里面的 xx:5，我就一直没明白什么意思。另外，一些朋友在评论区对256，257是怎么来的感到疑惑，我都会对文章做一次修订，将这些内容描述清楚，谢谢大家。

Preface

看了一天，感觉终于搞明白了一点（代码终于写对了），编码过程大四的时候学过一点点，按部就班的按照步骤来做就行了，解码过程貌似课堂上老师没讲，自己看wiki上的讲解和example搞懂了。

LZW全称Lempel–Ziv–Welch，就是这个三个人搞出来的。

LZW的工作思路，考虑一段数据，abcabcabc，对于这样的一段数据，如果不做任何处理和压缩，假设每个字符用一个字节来表示，直接存储的空间应该是9字节。详细说明下：
下表是我们dictionary，也就是码表，字符与编码的对应。

观察上面的字符串，发现abc是重复的，如果abc能用一个字节来表示的话，那么，只需要3字节存储就足够了。

OK，LZW就是这个尿性，它就是想这么搞。

Encoding

基本思想

编码的基本思想是这样的，首先我们有一个码表或者称为dictionary，里面只定义单个字符和编码，比如0-9a-zA-Z这些，其实ASCII码中的所有全部都放进去都可以。

也就是说通常用十进制数0-255来表示单一字符（single character）。

然后我们开始读取字符串，很显然对于任何常规字符串，每个single character都可以得到一个码字，但是如果我们不做处理的话，那么n个字符encode后，就是n个码字了完全没有压缩。

所以，再边读取的时候，一边开始对dictionary进行扩增，不断的将single character拼接成dictionary中不存在的符号（symbol），扩充dictionary，这样下次再次遇到这样的组合，就可以使用有一个码字表示了。

流程

P -> Previous -> 表示之前的字符 C -> Current -> 表示当前读取的字符 

然后我们考虑字符串abcbcabcabcd

来，按步骤演算一下：

首先我们需要一个dictionary，简单考虑，只考虑a-d，4个英文小写字母吧。这里想表达的意思是，整个宇宙全世界只有a-d 4个英文字母，我们的ascii表中也只有 4 个字母。

经过上面的演算过程，我们的dictionary也扩展为：

代码实现

最后贴下自己实现的代码：

 public static List<Integer> encode(String data) { 
         List<Integer> result = new ArrayList<>(); //初始化dictionary int idleCode = 256; HashMap<String, Integer> dic = new HashMap<>(); for (int i = 0; i < 256; i++) { 
         dic.put((char)i + "", i); } String previous = ""; String pc = ""; for (char c : data.toCharArray()) { 
         pc = previous + c; if (dic.containsKey(pc)) { 
         previous = pc; } else { 
         dic.put(pc, idleCode++); result.add(dic.get(previous)); previous = "" + c; } } //最后一次输出 if (!previous.equals("")) { 
         result.add(dic.get(previous)); } return result; } 

Output

//abcbcabcabcd [97, 98, 99, 257, 256, 99, 260, 100] 

256, 257 是怎么来的？

上面用表格模拟整个过程的时候，是假设全世界只有4个字符，ASCII码表的大小也只有4个字符，但是上面这会程序运行时，我们的世界又是真实世界了，ASCII表示有256个字符的，编码范围从0到255。那么我们新创造的字符用什么来编码呢？当然是从 255 后面开始追加了。

Decoding

主要思想

解码的主要思想是，一个编码序列，我们也是事先知道一个固定的码表，我一边读取码字，一边输出解码后的字符，同时一边扩充码表。这个我也觉得好难用用文字表达清楚，上流程图。

流程

同样的，这里给出一个编码序列

[97, 98, 99, 257, 256, 99, 260, 100] 

首先我们需要一个默认的dictionary。

接下来是演算过程：

代码实现

 public static String decode(List 
        
          arr) { StringBuilder result = new StringBuilder(); int idleCode = 256; HashMap 
         
           dic = new HashMap<>(); for (int i = 0; i < 256; i++) { dic.put(i, (char)i + ""); } String p = ""; String c = ""; for (int code : arr) { if (dic.containsKey(code)) { c = dic.get(code); } else if (code == idleCode) { //这里唯一的情况是 aaaaaaa c = c + c.charAt(0); } else { System.out.println("bad encode"); } if (!p.equals("")) { dic.put(idleCode++, p + c.charAt(0)); } result.append(c); p = c; } return result.toString(); } 
          
        

Summary

References

1. Lempel–Ziv–Welch from Wikipedia.
2. LZW的各种语言的实现
3. ASCII