手写一个 LZW 压缩算法

, , ,

起因

之前需要在某个单片机下塞点阵字库，为了能多覆盖一些字，准备在字库上做一点压缩。由于常用字相邻编码通常是按形码编码的，所以形状上有很多相似性，因此应该是比较可以压缩的。读取的时候，把一整块相邻编码解压塞到内存里，在内存里做个 LRU 缓存。由于常用字的编码也比较靠近，所以可以一定程度上在覆盖生僻字的同时，达到比较好的读取性能。

不过单片机上写个压缩算法比较麻烦。单片机本身的性能就很差，压缩算法本身约简单越好。最好实现的压缩算法恐怕就是 LZW 了。由于 LZW 的字典是自解释的，也不需要单独构建霍夫曼树，one-pass 一遍读完就解决。于是就考虑写个 LZW。

LZW 基本原理

LZW 压缩需要两件东西，一个是字符集一个是字典。最常见的字符集就是 0x00 到 0xff 的 256 个字符当作字符集，即我们把所以 8-bit 数据看成一个单独字符。字典是这个字符集的组合。字典构成一个更大的空间，通常教科书上的例子的是 14-bit 的字典空间。也就是 0x0000-0x1fff，其中 0x0000-0x00ff 是基础字符集，0x0100-0x1fff 7935 个编号作为可编码的字典。这对于压缩率是比较好的，不过 14-bit 的读取实在太麻烦了，因为它不是 byte 的整倍数。于是我把可编码的字典空间放达到 2 个 bytes 也就是 0x0100-0xffff 65279 个字符，和字符集一起构成一个 65536 字符的空间。

函数签名

头文件和函数签名非常简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <stdbool.h>

struct dictionary {
    size_t count;
    size_t entries_sizes[65536];
    char* entries[65536];
};

struct dictionary* dictionary_init();
void dictionary_free(struct dictionary* dict);
size_t dictionary_insert(struct dictionary* dict, const char* word, size_t size); // The string would be copied, be sure to free the word.
size_t dictionary_find(struct dictionary* dict, const char* word, size_t size);
void compress(const char* source, size_t size, const char* filepath);
char* decompress(size_t* size, const char* filepath);

维护字典大小、插入字典、根据字符查找在字典的位置、执行压缩和解压缩。

其中字典的创建、释放和插入是基本的 C 语言常识：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct dictionary* dictionary_init() {
    struct dictionary* dict = (struct dictionary*) malloc(sizeof(struct dictionary));
    dict->count = 256;

    for (size_t i = 0; i < 256; i++) {
        dict->entries[i] = (char*) malloc(sizeof(char));
        dict->entries[i][0] = (char) i;
        dict->entries_sizes[i] = 1;
    }

    return dict;
}

void dictionary_free(struct dictionary* dict) {
    for (size_t i = 0; i < dict->count; i++) {
        free(dict->entries[i]);
    }
    free(dict);
}

size_t dictionary_insert(struct dictionary* dict, const char* word, size_t size) {
    char* w = (char*) malloc(sizeof(char) * size);
    size_t idx = dict->count;

    assert(idx < 65536);
    memcpy(w, word, size);

    dict->entries[idx] = w;
    dict->entries_sizes[idx] = size;
    dict->count++;
    return idx;
}

查找的一个比较好的实现方法是使用哈希（unordered_map）。不过由于我在使用 C 语言，没有炫酷的 C++ STL 标准库。考虑到字典最大就 65536 个，而且用 size 大小就能很好做初步的筛选，我还是整个遍历一遍算了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
size_t dictionary_find(struct dictionary* dict, const char* word, size_t size) {
    size_t i;
    for (i = 0; i < dict->count; i++) {
        if (dict->entries_sizes[i] == size) {
            bool found = true;
            for (size_t j = 0; j < size; j++) {
                if (dict->entries[i][j] != word[j]) {
                    found = false;
                    break;
                }
            }
            if (found) { return i; }
        }
    }
    return i;
}

压缩过程

LZW 之所以不需要单独维护字典是因为 LZW 对于如何建立字典这件事情是 隐含 在算法中的。对于当前压缩过程，如果前一个字典字和当前的字符的组合没有出现在字典中，那么就插入到字典中。为了理解这个概念，我们先简化一下模型。我们假设基本字符集只有 0 和 1 两个字符，然后我们编码这个序列：01001101

前一个字典字 当前字符 构成的组合 是否出现在字典中？ 输出
- 0 0 出现（基本字符 0 -> 0） -
0 1 01 没有（插入字典 2 -> 01） 0
1 0 10 没有（插入字典 3 -> 10） 1
0 0 00 没有（插入字典 4 -> 00） 0
0 1 01 出现（2 -> 01） -
01 1 011 没有（插入字典 5 -> 011） 2
1 1 11 没有（插入字典 6 -> 11） 1
1 0 10 出现（3 -> 10） -
10 1 101 没有（插入字典 7 -> 101） 3
1 - 1 1

于是我们把 01001101 编码成了 0102131，这个序列的压缩率是非常糟糕的，因为 01 可以用一个 bit 表示，01001101 只有 1 byte，但压缩后的 0102131 至少需要 2 个 bit 来表示一个字符，虽然整体数量减少到了 7 个字符，但是实际上需要 14-bit（1.75 bytes）才能存储。但随着字符变长，字典覆盖会越来越好，压缩率也会越来越低。

我在实际实现的时候还标注了一个元信息，就是用第一个 size_t 来标注源文件的大小，以便于之后解压的时候申请内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void compress(const char* source, size_t size, const char* filepath) {
    FILE* destination = fopen(filepath, "wb+");
    struct dictionary* dict = dictionary_init();

    // First size_t indicates the file size
    fwrite(&size, sizeof(size_t), 1, destination);

    char* p = NULL;
    size_t p_size = 0;
    char c;

    for (size_t i = 0; i < size; i++) {
        char* ppc = (char*) malloc(p_size + 1); // p + c

        c = source[i];
        memcpy(ppc, p, p_size);
        ppc[p_size] = c;
        size_t idx = dictionary_find(dict, ppc, p_size+1);
        if (idx < dict->count) {
            // Found
            if (p != NULL) { free(p); }
            p_size = p_size + 1;
            p = malloc(sizeof(char) * p_size);
            memcpy(p, ppc, p_size);
        } else {
            // Not found
            assert(p != NULL);
            unsigned short p_res = dictionary_find(dict, p, p_size);
            fwrite(&p_res, sizeof(unsigned short), 1, destination);
            free(p); p = NULL;
            dictionary_insert(dict, ppc, p_size + 1);
            p = (char*) malloc(sizeof(char));
            p[0] = c;
            p_size = 1;
            if (i == size - 1) {
                unsigned short c_res = dictionary_find(dict, p, 1);
                fwrite(&c_res, sizeof(unsigned short), 1, destination);
            }
        }

        free(ppc);
    }

    if (p != NULL) {
        free(p);
    }

    dictionary_free(dict);
    fclose(destination);
}

解压过程

LZW 的压缩是比较简单的，但是解压却是有点 tricky 的。如果我们顺着压缩的思路来解压，我们会认为，顺着我们解压的过程，我们会慢慢构建出我们需要的字典。我们考虑下面一个序列 10101 的压缩过程：

前一个字典字 当前字符 构成的组合 是否出现在字典中？ 输出
- 1 1 出现（基本字符 1 -> 1） -
1 0 10 没有（插入字典 3 -> 10） 1
0 1 01 没有（插入字典 4 -> 01） 0
1 0 10 出现（3 -> 10） -
10 1 101 没有（插入字典 5 -> 101） 3
1 - 1 1

输出的结果是 1031。如果我们解压的话过程如下：

前一个字典字 当前字符 构成的组合 是否出现在字典中？ 输出
- 1 1 出现（基本字符 1 -> 1） 1
1 0 10 没有（插入字典 3 -> 10） 0
0 3 (10) 010 没有（4 -> 010） 10

显然我们把第四个字典的字符值插入错了，应该是 01 而我们却组合出了 010。这会进一步导致之后的解压出错。而且我们很容易思考到一个问题，在压缩过程中我们组合的都是前一个字典字和一个 单一字符，这里我们让 0 和 10 相加，后者显然不是单一字符。进一步思考我们会发现，在压缩过程中如果一个字典被创建，那么这个步骤的前一个插入字典的尾部，必然是这个匹配到的前缀，也就是这个字典值的第一个字符。所以这里的 4 应该是前一个字典字 0 和 10 的第一个字符 1 的组合，也就是 01。

于是我们以此正确构建我们的解压代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
char* decompress(size_t* size, const char* filepath) {
    FILE* source = fopen(filepath, "rb");
    struct dictionary* dict = dictionary_init();

    // First size_t indicates the file size
    fread(size, sizeof(size_t), 1, source);

    char* result = malloc(sizeof(char) * (*size));
    size_t counter = 0;

    if (size == 0) {
        dictionary_free(dict);
        return result;
    }

    unsigned short p_index;
    unsigned short c_index;
    char* c_word;
    size_t c_word_size;
    char* p_word = NULL;
    size_t p_word_size = 0;

    fread(&p_index, sizeof(unsigned short), 1, source);
    p_word = dict->entries[p_index];
    p_word_size = dict->entries_sizes[p_index];
    memcpy(result+counter, p_word, p_word_size);
    counter += p_word_size;


    while (counter < *size) {
        fread(&c_index, sizeof(unsigned short), 1, source);
        if (c_index < dict->count) {
            // Found
            c_word = dict->entries[c_index];
            c_word_size = dict->entries_sizes[c_index];
            memcpy(result+counter, c_word, c_word_size);
            counter += c_word_size;
            char* ppc = malloc(sizeof(char) * (p_word_size + 1));
            memcpy(ppc, p_word, p_word_size);
            memcpy(ppc+p_word_size, c_word, 1);
            dictionary_insert(dict, ppc, p_word_size + 1);
            free(ppc);
        } else {
            char* ppc = malloc(sizeof(char) * (p_word_size + 1));
            memcpy(ppc, p_word, p_word_size);
            memcpy(ppc+p_word_size, p_word, 1);
            c_index = dictionary_insert(dict, ppc, p_word_size + 1);
            memcpy(result+counter, ppc, p_word_size + 1);
            c_word = dict->entries[c_index];
            c_word_size = p_word_size + 1;
            counter += p_word_size + 1;
            free(ppc);
        }
        p_word = c_word;
        p_word_size = c_word_size;
    }

    dictionary_free(dict);
    fclose(source);

    return result;
}

实验

我尝试用马丁路德金的《I have a dream》作为例子实验了一下这个实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main() {
    const char path[] = "/tmp/compressed.lzw";
    char test[] = "I am happy to ...";
    compress(test, sizeof(test), path);

    size_t s = 0;

    FILE* f = fopen(path, "rb");
    fseek(f, 0, SEEK_END); // seek to end of file
    size_t file_size = ftell(f);
    fclose(f);

    char* res = decompress(&s, path);

    assert(sizeof(test) == s);
    assert(strcmp(test, res) == 0);

    printf("         Raw Text: %s\n", test);
    printf("Decompressed Text: %s\n", res);
    printf(" Compression Rate: %d%%\n",  (unsigned int)(file_size * 1.0 / sizeof(test) * 100));
    return 0;
}

最后的输出如下：

1
2
3
4
/Users/delton/CLionProjects/playgound/cmake-build-debug/playgound
         Raw Text: I am happy to ...
Decompressed Text: I am happy to ...
 Compression Rate: 73%

整体压缩率有 73%，对比了一下 zip 42% 的压缩率，实在是望尘莫及。

如果我们把文本重复 5 遍，压缩率能提升到 49%。不过这条件下，zip 能提高到 9% 的压缩率。果然还是不能和 DEFLATE 这种 LZW + 霍夫曼树这样的怪物比啊。不过简简单单 200 行代码就能实现一个性能上还不错的压缩、解压缩算法我已经比较满意了。