手写一个 LZW 压缩算法

起因

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

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

LZW 基本原理

LZW 压缩需要两件东西,一个是字符集一个是字典。最常见的字符集就是 0x000xff 的 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 对于如何建立字典这件事情是 隐含 在算法中的。对于当前压缩过程,如果前一个字典字和当前的字符的组合没有出现在字典中,那么就插入到字典中。为了理解这个概念,我们先简化一下模型。我们假设基本字符集只有 01 两个字符,然后我们编码这个序列: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 应该是前一个字典字 010 的第一个字符 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 行代码就能实现一个性能上还不错的压缩、解压缩算法我已经比较满意了。