LZ77 编码压缩与解压的实现
2018年5月24日LZ77 是无损数据压缩算法，主要思想是把已输入的数据流存储起来，作为字典使用。编码器为输入流开设一个滑动窗口，将输入的数据存在窗内，做字典使用，窗口右侧是待编码的数据流缓存器。
下面以自然对数底 e 的部分数字为例，横线表示窗内的数据，括号下方的数据表示待编码的数据流缓存器：
\overline{\ \ \ \ \ \ \ }\overbrace{2.71828}1828459045
用三元标识( (offset, length, symbol) 给数据编码， offset 是窗内从右向左搜索的字符串位数，length 是数据流缓存中在窗内的有相同符号的最大匹配长度，symbol 是窗外已找到匹配的串后面串的首字符。
- 刚开始，窗内空，输入当前位置 2，窗内没有与 2 匹配的串，故 offset、length 均为 0，把 2 编码为 (0, 0, 2)，往后 .718 也与 2 情况类似，被编码为 (0, 0, .)、（0, 0, 7）、(0, 0, 1)、(0, 0, 8)。
经过 1 的编码，现窗内与数据流缓存器情况如下：
\overline{\ \ \ \ 2.718}\overbrace{281828}459045
将数据流缓存器中的 281828 这几个字符与窗内的 2.718 这几个字符匹配，发现只能在窗内(2.718)从右往左数第 5 位处匹配到 2 这一个字符，匹配串长度 length 为 1，且2 后面为 8 这一个字符，故编码为 (5, 1, 8)。并将 28 这两个字符加入到窗口中。
现窗内与数据流缓存器情况如下：
\overline{\ \ \ \ 2.71828}\overbrace{182845}9045
将数据流缓存器中的 182845 这几个字符与窗内的 2.71828 这几个字符匹配，发现能在窗内(2.71828)从右往左数第 4 位处匹配到 1828 这4个字符，匹配串长度 length 为 4，且 1828 后面为 4 这一个字符，故编码为 (4, 4, 4)。并将 18284 这 5 个字符（包含匹配到的4个字符与其后面的第一个未能匹配字符）加入到窗口中。
现窗内与数据流缓存器情况如下：
\overline{\ \ \ \ 2.7182818284}\overbrace{59045}
此时窗内没有与 5、9、0这三个字符相匹配的串，故 offset、length均是 0，得编码依次为 (0, 0, 5)，(0, 0, 9)，(0,0,0)。并将 590 这三个字符加入窗内。
现窗内与数据流缓存器情况如下：
\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;
}
参考：
