LZ77 编码压缩与解压的实现

2018年5月24日

LZ77 是无损数据压缩算法,主要思想是把已输入的数据流存储起来,作为字典使用。编码器为输入流开设一个滑动窗口,将输入的数据存在窗内,做字典使用,窗口右侧是待编码的数据流缓存器。

下面以自然对数底 $$e$$ 的部分数字为例,横线表示窗内的数据,括号下方的数据表示待编码的数据流缓存器:

$$\overline{\ \ \ \ \ \ \ }\overbrace{2.71828}1828459045$$

用三元标识( (offset, length, symbol) 给数据编码, offset 是窗内从右向左搜索的字符串位数,length 是数据流缓存中在窗内的有相同符号的最大匹配长度,symbol 是窗外已找到匹配的串后面串的首字符。

  1. 刚开始,窗内空,输入当前位置 2,窗内没有与 2 匹配的串,故 offset、length 均为 0,把 2 编码为 (0, 0, 2),往后 .718 也与 2 情况类似,被编码为 (0, 0, .)、(0, 0, 7)、(0, 0, 1)、(0, 0, 8)。

  2. 经过 1 的编码,现窗内与数据流缓存器情况如下:

    $$\overline{\ \ \ \ 2.718}\overbrace{281828}459045$$

    将数据流缓存器中的 281828 这几个字符与窗内的 2.718 这几个字符匹配,发现只能在窗内(2.718)从右往左数第 5 位处匹配到 2 这一个字符,匹配串长度 length 为 1,且2 后面为 8 这一个字符,故编码为 (5, 1, 8)。并将 28 这两个字符加入到窗口中。

  3. 现窗内与数据流缓存器情况如下:

    $$\overline{\ \ \ \ 2.71828}\overbrace{182845}9045$$

    将数据流缓存器中的 182845 这几个字符与窗内的 2.71828 这几个字符匹配,发现能在窗内(2.71828)从右往左数第 4 位处匹配到 1828 这4个字符,匹配串长度 length 为 4,且 1828 后面为 4 这一个字符,故编码为 (4, 4, 4)。并将 18284 这 5 个字符(包含匹配到的4个字符与其后面的第一个未能匹配字符)加入到窗口中。

  4. 现窗内与数据流缓存器情况如下:

    $$\overline{\ \ \ \ 2.7182818284}\overbrace{59045}$$

    此时窗内没有与 5、9、0这三个字符相匹配的串,故 offset、length均是 0,得编码依次为 (0, 0, 5),(0, 0, 9),(0,0,0)。并将 590 这三个字符加入窗内。

  5. 现窗内与数据流缓存器情况如下:

    $$\overline{\ \ \ \ 2.7182818284590}\overbrace{45}$$

    将数据流缓存器中的 45 在窗内从右往左数第4位,有 45 与数据流缓存器中的 45 匹配,故移位 offset 为4,串长 length 为2,后续字符无,得编码为 (4,2,)。此时编码完毕。

对于解码,我们只需要根据编码的特性,如(offset, length, symbol),如果 offset 是0,就直接输出该字符,否则就往前找到 offset 位,输出长度为 length 个字符,并输出 symbol。

由于 LZ77 在匹配过程中,窗口的大小与数据流缓存器的大小会决定编码的快慢与编码的效率,一般滑动窗口的大小可达几千字节,而数据流缓存器只有几十个字节。不同长度得到的编码也不同。
利用更好的数据结构(如树、哈希)来存窗口字符或更高效的字符串匹配算法,可以在一定程度上提高编码效率。

编码伪代码:

while look-ahead buffer is not empty
    go backwards in search buffer to find longest match of the look-ahead buffer
    if match found
        print: (offset from window boundary, length of match, next symbol in lookahead buffer);
        shift window by length+1;
    else
        print: (0, 0, first symbol in look-ahead buffer);
        shift window by 1;
end while

解码伪代码:

for each token (offset, length, symbol)
    if offset = 0 then
        print symbol;
    else
        go reverse in previous output by offset characters and copy character wise for length symbols;
        print symbol;

以下代码只是实现了 LZ77 算法的原理。由于下面的代码设定的字符串有指定的最大值,对需编码的字符串有长度限制,太长会导致溢出。

#include <stdio.h>
#include <string.h>
#define N 10000
#define WINDOW_SIZE 2000
#define LOOK_AHEAD_SIZE 6
int max(int a, int b)
{
    return a > b ? a : b;
}
void encode(char * str)
{
    FILE *fp = fopen("data.out", "w");  // 将编码输出到一个文件中
    int len = strlen(str);
    int i = 0;
    while (i < len) {
        int length = 0, p = 0;
        for (int j = max(0, i - WINDOW_SIZE); j < i; j++) {
            int cnt = 0;
            for (int k = 0; k < LOOK_AHEAD_SIZE && str[j + k] == str[i + k]; k++) {
                cnt++;
            }
            if (length <= cnt) {
                length = cnt;
                p = j;
            }
        }
        if (length != 0) {
            printf("(%d %d %c)\n", i - p, length, str[i + length]);
            fprintf(fp, "(%d %d %c)\n", i - p, length, str[i + length]);  // 将编码输出到一个文件中
            i += length + 1;
        } else {
            printf("(0 0 %c)\n", str[i]);
            fprintf(fp, "(0 0 %c)\n", str[i]); // 将编码输出到一个文件中
            i++;
        }
    }
    fclose(fp);
}
void decode()
{
    FILE *fp = fopen("data.out", "r"); // 从文件中读取编码
    char buf[N], str[N];
    int i = 0;
    while (fgets(buf, N - 1, fp) != NULL) {
        int p, l;
        char ch;
        sscanf(buf, "(%d %d %c)", &p, &l, &ch);
        if (l != 0) {
            int tmp = i;
            for (int k = 0; k < l; k++) {
                str[i++] = str[tmp - p + k];
            }
        }
        str[i++] = ch;
    }
    printf("%s\n", str);
}
int main()
{
    char str[] = "2.71828182845904523536";
    printf("Source string:%s\n", str);
    printf("Encoding:\n");
    encode(str);
    printf("Decoding:\n");
    decode();
    printf("%s [Source string]\n", str);
    return 0;
}

参考:

http://jens.quicknote.de/comp/LZ77-JensMueller.pdf

发表评论

电子邮件地址不会被公开。 必填项已用*标注