=====================
== 端阳的主页 ==
=====================

手搓Lzw压缩算法

压缩算法 JavaScript

手搓LZW压缩算法

0.前言

在写完上一篇《手搓编辑器》后，一直在想手搓系列能写啥，考虑过手搓操作系统、手搓数据库，但发现有点不自量力，根本不是一两篇文章能讲明白的，于是转去寻找有没有一些短小精悍、又带点难度的东西。

在偶然的一天，看了眼前端项目线上构建产物，忽然想到代码压缩时候用的是什么压缩算法呢？发现手搓压缩算法这个选题有点搞头。

那就从经典的LZW压缩算法开始。

1.LZW压缩算法

LZW压缩算法的基本原理：提取源文件中的不同字符，基于这些字符创建一个字典，然后用字典中的字符的索引来替代源文件中的相应字符，从而减少原始数据大小。

看到这里，第一感觉那岂不是得先处理一遍源文件以获得这个所谓的字典。但其实并不是，这也是LZW算法第一个精妙的点，算法运行的时候，会根据已读取字符来逐步构建字典，这样一来，当后面再读取到相同的字符串时，即可以用字典中的索引来代替。这也使得压缩后的结果是自解释的，即字典是不会被写进压缩文件的。

LZW压缩算法是的解压过程其实和压缩过程很像，也是读取压缩文件，构建字典，还原文件。但由于压缩文件不包含字典，所以在解压过程中会遇到一种特殊情况：如果一个索引第一次出现，该如何确定它对应的字符串？ 这个问题的解法是LZW压缩算法中第二个精妙的点，解决方案很简单，但理解这个解法有点绕，需要反复揣摩。此处暂且不表，后面来攻克它。

压缩过程

不引入过多概念，给定一个待压缩字符串ababcababac，用自然语言来描述一下LZW压缩算法的压缩过程。

先尝试理解一下字典是如何构建的。

生成一个初始态字典，为待压缩字符串中所有的单字符添加索引：

const dictionary = {
    a: 0,
    b: 1,
    c: 2,
}
  1. 读取到第1个字符a
    • 发现在字典中，继续；
  2. 读取到第2个字符b
    • 和上一步的字符a构成字符串ab；
    • 发现ab不在字典中，添加映射ab: 3；
  3. 读取到第3个字符a
    • 和上一步的字符b构成字符串ba；
    • 发现ba不在字典中，添加映射ba: 4；
  4. 读取到第4个字符b
    • 和上一步的字符a构成字符串ab；
    • 发现ab在字典中，继续；
  5. 读取到第5个字符c
    • 和上一步的字符串ab构成字符串abc；
    • 发现abc不在字典中，添加映射abc: 5；
  6. 读取到第6个字符a
    • 和上一步的字符c构成字符串ca；
    • 发现ca不在字典中，添加映射ca: 6；
  7. 读取到第7个字符b
    • 和上一步的字符a构成字符串ab；
    • 发现ab在字典中，继续；
  8. 读取到第8个字符a
    • 和上一步的字符串ab构成字符串aba；
    • 发现aba不在字典中，添加映射aba: 7；
  9. 读取到第9个字符b
    • 和上一步的字符a构成字符串ab；
    • 发现ab在字典中，继续；
  10. 读取到第10个字符a
    • 和上一步的字符串ab构成字符串aba；
    • 发现aba在字典中，继续
  11. 读取到第11个字符c
    • 和上一步的字符串aba构成字符串abac
    • 发现abac不在字典中，添加映射abac: 8
  12. 字典构建结束

先来回顾后面的压缩是如何利用前面添加的映射的：

  • 映射ab: 3是在第2步添加的，然后在第4步和第7步中就发现ab已在字典中存在，所以可以进行压缩；
  • 映射aba: 7是在第8步添加的，然后在第10步中就发现aba已在字典中存在，所以可以进行压缩。

再关注下压缩过程中提到“继续”的地方，会发现一个特别之处，那就是“继续”的时候，表明可以尝试在前一个字符串的基础上继续添加一个字符，从而组成更长的字符串。当无法构成更长已知字符串时，则从当前字符重新开始增长，像滑动窗口一样。

再来看一个值得思考的地方，注意到ababac子串，给之间加上空格以示区分ab aba c，并标记为第一段、第二段、第三段。对照压缩过程的第8步，添加映射aba: 7，这里的字符串aba其实是第一段的ab和第二段的第一个字符a组成的。添加到字典后，紧跟着第9步、第10步就继续读取字符b、字符a，组成了字符串aba并发现存在于字典中。

什么样的结构能出现上面描述的场景？一定是一个类似于ab aba的形式，因为两段一定有相同的前缀，并且后一段一定是比前一段多了一个字符，这个字符还必须是前一段的第一个字符。

随便举几个反例，如果是ab abc，得到aba的映射后，下一步无法立即使用，用到的abc的映射是第5步得到的；如果是ab bba，得到abb的映射后，下一步的字符串是bb，也无法立即使用。

后一段一定是比前一段多了一个字符，这个字符还必须是前一段的第一个字符这个结论牢记，这是解压里最难的部分。

压缩代码

function lzwCompress(uncompressed) {
    const dictionary = new Map();
    let dictSize = 256;
    // 生成初始态字典
    for (let i = 0; i < 256; i++) {
        dictionary.set(String.fromCharCode(i), i);
    }
    // 待压缩字符串处理成字符流
    const data = (uncompressed + "").split("");
    const result = [];
    // 想象一个滑动窗口
    let w = "";
    // 遍历字符流
    for (let c of data) {
        // 滑动窗口延伸，不断寻找更长的字符串
        const wc = w + c;
        if (dictionary.has(wc)) {
            w = wc;
        } else {
            result.push(dictionary.get(w));
            // 找不到的时候，向字典中添加新的映射
            dictionary.set(wc, dictSize++);
            // 滑动窗口收缩
            w = String(c);
        }
    }
    // 处理最后一个字符
    if (w !== "") {
        result.push(dictionary.get(w));
    }
    return result;
}

算法代码相比于上面的过程分析，多了个输出压缩结果的步骤。这也很好理解，还用ab aba c来举例子，第一段的ab在字典中，但此时还不能输出ab对应的映射值3，因为不确定后面是否还能组成更长的字符串。只有当第一段的ab加上字符a组成字符串aba的时候，才可以确定目前为止字典中没有比ab更长的字符串映射存在，才可以把ab对应的映射3添加到压缩结果中。

所以正好在else分支中干了三件事，第一，添加前一段的映射值到压缩结果中；第二，添加新的映射；第三，收缩滑动窗口，重新开始增长。

解压过程

给定同样的初始态字典：

const dictionary = {
    0: 'a',
    1: 'b',
    2: 'c',
}

由于键是连续增长的数字，所以可以用数组来代替，初始态字典表示为：

const dictionary = ['a', 'b', 'c']

给定压缩结果：0 1 3 2 3 7 2。

读取到第1个记号0，一定在字典中，输出a；

  1. 读取到第2个记号1
    • 发现在字典中，输出b，添加映射3: ab；
  2. 读取到第3个记号3
    • 发现在字典中，输出ab，添加映射4: ba；
  3. 读取到第4个记号2
    • 发现在字典中，输出c，添加映射5: abc；
  4. 读取到第5个记号3
    • 发现在字典中，输出ab，添加映射6: ca；
  5. 读取到第6个记号7
    • 发现不在字典中，输出aba，添加映射7: aba；
  6. 读取到第7个记号2
    • 发现在字典中，输出c，添加映射8: abac

解压过程也很好理解，对着压缩过程反过来想。比如解压的第三步，如何得到5: abc的映射的？从压缩过程第5步可以知道，字符串abc是由上一步的字符串ab和当前的字符c组成。那解压时候也类似，上一步的结果，加上当前的结果，构成了一个新的值，并写入字典。

有一点要注意，加上当前结果的时候，加的是当前结果的第一个字符。举例来看，压缩过程第3步读取字符a并和上一步的字符b构成字符串ba，添加映射ba: 4，同时输出压缩结果3。所以在解压过程的第2步读到记号3，对应到字符串ab，此时要取第一个字符a和上一步的字符b组成字符串ba并写入4: ba。

到第5步之前，还都好理解，按照上面说的规则一步一步解压即可。但第5步中，既输出了aba，又添加了映射7: aba，这和之前的步骤完全不同，为什么会出现这种情况？就是因为记号7不在字典中，所以一定是在压缩的时候，上一步刚写入aba: 7的映射，下一步立即就用上了。回想压缩过程中是怎么处理这种情况的，那个重要的结论：后一段一定是比前一段多了一个字符，这个字符还必须是前一段的第一个字符就派上用场了，直接按照这个结论写代码就好了。

解压代码

对照着解压过程，直接翻译代码。

function lzwDecompress(compressed) {
    // 使用数组来创建字典
    const dictionary = [];
    let dictSize = 256;
    // 生成初始态字典
    for (let i = 0; i < 256; i++) {
        dictionary[i] = String.fromCharCode(i);
    }
    let w = String.fromCharCode(compressed[0]);
    const result = [w];

    for (let i = 1; i < compressed.length; i++) {
        let k = compressed[i];
        let entry;
        if (dictionary[k]) {
            // 常规情况，记号在字典中
            entry = dictionary[k];
        } else {
            // 处理字典中找不到记号的情况
            // 根据结论：“后一段一定是比前一段多了一个字符，这个字符还必须是前一段的第一个字符”来处理
            entry = w + w.charAt(0);
        }
        result.push(entry);
        // 添加新的映射
        dictionary[dictSize++] = w + entry.charAt(0);
        w = entry;
    }
    return result.join("");
}

2.总结

至此，LZW压缩算法的压缩和解压过程都已经分析完了，但给到的代码只能作为研究和了解算法思想来使用，距离完整应用还有很大的差距。例如，在压缩和解压初始化时，都只生成了256大小的字典，如果超出256要怎么处理，这些都是必须要考虑的。但相信理解了LZW压缩算法的核心后，剩下的都不是太大的问题。

参考文献

https://segmentfault.com/a/1190000011425787