Lempel–Ziv–Welch 字符串压缩算法

MIT 的 Information and Entropy 公开课讲的信息论与压缩，讲的非常 nice ！ 唯一美中不足的地方是教授一步一步复现 LZW 算法的时候一开始搞错了。。卡住之后才发现出了 bug 修正过来，囧

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-050j-information-and-entropy-spring-2008/videos-homework-and-readings/unit-2-lecture-1/

LZW 算法的一个 pdf 课件。

http://web.mit.edu/6.02/www/s2012/handouts/3.pdf

简单看了两天笔记之后，总结了下，教材上常见的字符串压缩可以分为 Huffman encoding 和 LZ 系列 - LZ77, LZ78, LZW 等等。

• Huffman Encoding:

  • 建立在字符pattern的 “出现概率” 上，把出现概率大的pattern用更短的 encoding 方式表达出来，这样就可以节省原始字符串的期望长度。

  • Huffman Encoding 的结构是树状的，一种常见的 variable-length code (又称前缀树) 大概长这样：
  • 其中 0 - B; 10 - A; 110 - C，以此类推。

  • Theorem 3.1 Huffman coding produces a code tree whose expected length is optimal, when restricted to symbol-by-symbol coding with symbols drawn in IID fashion from a known symbol probability distribution.

  • 在 symbol 的 pdf 已知的情况下，Huffman Encoding 的期望长度是最优的。问题就出在这个 “symbol pdf 已知” 上，因为实际应用中很多时候得到 symbol 的 pdf 不但昂贵，也不擅于处理不同 message 之间，symbol 出现概率可能出现的大幅度变化。而且这种方法做了一个类似 naive bayes 的假设，就是 symbol 之间是 iid 关系，independent and identically distributed.

因此我们需要一种 adaptive 并且 variable-length 的算法，因此有了 Lempel-Ziv-Welch 算法。

• LZW 算法最有意思的一点是，在 stream of input/output 进行的过程中，双方不需要传递用于encode/decode 的 String table ，decoder 可以"猜"出来应该对应的是什么。 而且如果原始 table 已经满了的话，可以直接重新初始化，继续 streaming.

一段比较简单粗暴的代码，跑了几个 test case 结果无误，压缩效率尚可。LZW 因为 prefix 搜索非常多，可以用 Trie 进行优化。

里面一些细节因为时间有限先不赘述了，复习去。

• 实际应用中 key 的 size 最好小点，至少最好不要比一个 char 大(同时保证字典不会 overflow)，下面的代码用的就是 8-bit byte 做字典 HashMap 与 TrieNode 的 key，有效范围在 0 ~ 255 之间。

public class Solution {
    private static class TrieNode{
        char chr;
        byte dictIndex;
        TrieNode[] children = new TrieNode[26];
        public TrieNode(){}
        public TrieNode(char chr, byte dictIndex){
            this.chr = chr;
            this.dictIndex = dictIndex;
        }
    }

    // returns code of transmit as integer

    private static byte trieTraverse(String str, int[] index,
                                    HashMap<Byte, String> map,
                                    TrieNode trieRoot, byte[] curCode){
        TrieNode curNode = trieRoot;
        StringBuilder sb = new StringBuilder();
        byte dictIndex = (byte) (str.charAt(index[0]) - 'a');

        while(index[0] < str.length()){
            char curChr = str.charAt(index[0]++);
            int intChr = curChr - 'a';
            sb.append(curChr);
            dictIndex = curNode.dictIndex;

            if(curNode.children[intChr] == null){
                TrieNode newNode = new TrieNode(curChr, curCode[0]);
                curNode.children[intChr] = newNode;
                map.put(curCode[0]++, sb.toString());
                index[0]--;
                break;
            } else {
                curNode = curNode.children[intChr];
                dictIndex = curNode.dictIndex;
            }

        }

        return dictIndex;
    }


    private static String encode(String str, HashMap<Byte, String> map,
                                 TrieNode trieRoot, byte[] curCode){
        StringBuilder sb = new StringBuilder();
        int[] index = new int[1];

        while(index[0] < str.length()){
            byte code = trieTraverse(str, index, map, trieRoot, curCode);
            sb.append(code).append(' ');
        }

        return sb.toString();
    }

    private static String decode(String str, HashMap<Byte, String> map){
        StringBuilder sb = new StringBuilder();
        String[] strs = str.split(" ");
        for(String token : strs){
            byte index = (byte) Integer.parseInt(token);
            sb.append(map.get(index));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String[] testcases = new String[]{"abcabcabcabcabcabcabcabcabcabcabcabc",
                "aaaaabbbbbaaaaabbbb",
                "ittyttybitbinbitbitcoin",
                "abracadabrabrabra",
                "aaabbbmtvmtvmtvaaabbb"};
        String input2 = testcases[0];

        HashMap<Byte, String> map = new HashMap<>();
        TrieNode trieRoot = new TrieNode();

        for(int i = 0; i < 26; i++){
            char chr = (char)('a' + i);
            TrieNode node = new TrieNode(chr, (byte)i);
            trieRoot.children[i] = node;
            map.put((byte) i, String.valueOf(chr));
        }

        byte[] curCode = new byte[1];
        curCode[0] = 26;

        String str = encode(input2, map, trieRoot, curCode);
        String output = decode(str, map);

        System.out.println("Input : " + input2);
        System.out.println("Encode: " + str);
        System.out.println("Output: " + output);
        for(int i = 0; i < curCode[0]; i++){
            System.out.println(i + " : " + map.get((byte) i) + " ");
        }
    }
}