andyherbert/lz1

[本文最初发布于 andyh.org。](http://andyh.org/LZ1.html) Abraham Lempel 和 Jacob Ziv 被认为是数据压缩技术领域的先驱，这是因为他们在 20 世纪 70 年代末共同发表了两篇学术论文，概述了一种无需丢失任何信息即可高效压缩数据的技术。本文将研究他们第一篇论文中描述的算法，该算法通常被称为 LZ1。 LZ1 会寻找重复的数据序列，并通过在与原始信息并列的位置存储指针来记录这些重复的块。随后，这些指针被用于重建数据以恢复其原始结构。其工作方式如下：按顺序从前到后读取字节，当前正在检查的字节的位置被称为“编码点”。编码点处的每个字节都会与之前窗口（称为“window”）中的信息进行比较，该窗口不会匹配整个数据大小，但可能扩展到数千个字节。如果窗口中的一个或多个字节与当前编码点处的序列匹配，则会保存一个指向压缩数据的指针。该指针由两部分组成：一是当前编码点到重复数据的偏移量，二是已匹配的字节数。这个值随后被称为指针的“长度”。记录指针时，还会存储匹配序列后紧跟的字节。如果在窗口中未找到匹配项（在读取文件的第一个元素时总会发生这种情况），则会保存一个空指针以及当前编码点处的字节。因此，无论是否在窗口中找到匹配，我们都会在遍历数据时同时保存一个指针和一个字节。 以以下字符串为例：一系列连续的 ‘A’，随后是一个 ‘B’，最后是一个 ‘C’： ``` AAAAAAAABC ``` 第一个 ‘A’ 被检查，此时窗口中没有任何数据，因此记录一个空指针，并将编码点处的字节（即字母 ‘A’）一并保存。随后编码点移动到下一个字节，即第二个 ‘A’。算法之前已经见过这个字节，即前一个字节，于是它会查看如果继续前进编码点并仍基于当前偏移量（目前为 1）是否还能匹配后续多少字节。这就是算法较为巧妙的地方：它可以匹配超出当前编码点的数据；当前指针位于第一个字节，编码点位于第二个，两个指针同时前进并逐个匹配字节。在这种情况下，完全等效的字节总数为 7，直到遇到 ‘B’。如果此时已读取更多数据，窗口会更大，算法就会对窗口大小的整个数据范围执行相同的匹配操作。因为这是唯一且最长的匹配，所以会写入一个偏移量为 1、长度为 7 的指针，以及指针长度之后编码点处的下一个字节，即字母 ‘B’。接着编码点移动到 ‘B’ 之后，并检查最后一个字节。它在窗口中未见过 ‘C’，因此会保存一个空指针和字母 ‘C’。需要注意的是，在存储最终指针和字节时，避免让编码点超出数据长度。为了说明这种情况，假设数据仅由 8 个连续的 ‘A’ 组成，没有 ‘B’ 或 ‘C’，那么第一个 ‘A’ 会记录为空指针（如前所述），然后记录一个指向第一个 ‘A’、长度为 6 的指针，并在其后附带最后一个 ‘A’。之所以给出长度 6 而不是 7，是因为我们仍需要记录最后一个字节以及指针，如果匹配 7 个字符，编码点就会超出数据长度，因为还需要额外保存一个字节。 解压是一项极其简单的任务：在数据解码期间，编码点和窗口仍保留在内存中。当遇到指针偏移量时，会将指针偏移量处的数据复制到当前编码点，复制次数由指针长度指定，随后将指针所携带的字节插入到当前编码点。因此，对于第一个示例，找到空指针并忽略它，然后读取第一个字节 ‘A’ 并将其插入编码点。第二个指针被读取，可以看出偏移量指向前一个字符，于是将已插入的所有内容复制接下来的七次。这样就得到了七个 ‘A’。指针附带的下一个字符是 ‘B’，将其添加到编码点并前进编码点。最后，发现一个空指针和最后一个字节 ‘C’，忽略指针并将字节添加到编码点。至此，原始数据结构已成功重建。 向压缩数据添加指针既有成本也有收益。如果指针在压缩数据中占用空间过大，就会降低其实用性。因此，窗口大小和字节长度也受到限制。对于后续的代码示例，我选择将指针存储为 16 位字节，其中 12 位表示指针偏移量，4 位表示长度。这会产生一个 4096 字节的窗口和最大 15 字节的指针长度。在尝试了各种尺寸和长度的组合后，这种 16 位指针的尺寸似乎是一个有益的折中方案。对于大多数文本文件，不太可能出现超过 15 字节的重复序列——尽管这更适合包含长重复数据的可执行文件。4096 字节的窗口也有助于找到重复数据，如果小于这个值，会对压缩数据的大小产生负面影响。窗口过大也会增加压缩数据所需的时间，因为最终需要比较更多数据。此外，还需要考虑内存限制，因为压缩和解压缩例程仅在执行操作时存储窗口。 在以下代码中，压缩函数接受以下参数：一个指向待压缩字节序列的指针、未压缩数据的大小，以及一个用于存储输出的内存指针。解压时，只需要指向压缩数据的指针以及用于保存未压缩数据的指针即可。解压函数不需要未压缩数据大小的原因在于：压缩数据写入时，会在开头以 32 位无符号整数形式记录最终的未压缩长度，因此解压函数可以通过比较数据最终大小与编码点当前值来判断何时停止解码。 ``` #include uint32_t lz77_compress (uint8_t *uncompressed_text, uint32_t uncompressed_size, uint8_t *compressed_text) { uint8_t pointer_length, temp_pointer_length; uint16_t pointer_pos, temp_pointer_pos, output_pointer; uint32_t compressed_pointer, output_size, coding_pos, output_lookahead_ref, look_behind, look_ahead; *((uint32_t *) compressed_text) = uncompressed_size; compressed_pointer = output_size = 4; for(coding_pos = 0; coding_pos < uncompressed_size; ++coding_pos) { pointer_pos = 0; pointer_length = 0; for(temp_pointer_pos = 1; (temp_pointer_pos < 4096) && (temp_pointer_pos <= coding_pos); ++temp_pointer_pos) { look_behind = coding_pos - temp_pointer_pos; look_ahead = coding_pos; for(temp_pointer_length = 0; uncompressed_text[look_ahead++] == uncompressed_text[look_behind++]; ++temp_pointer_length) if(temp_pointer_length == 15) break; if(temp_pointer_length > pointer_length) { pointer_pos = temp_pointer_pos; pointer_length = temp_pointer_length; if(pointer_length == 15) break; } } coding_pos += pointer_length; if(pointer_length && (coding_pos == uncompressed_size)) { output_pointer = (pointer_pos << 4) | (pointer_length - 1); output_lookahead_ref = coding_pos - 1; } else { output_pointer = (pointer_pos << 4) | pointer_length; output_lookahead_ref = coding_pos; } *((uint32_t *) (compressed_text + compressed_pointer)) = output_pointer; compressed_pointer += 2; *(compressed_text + compressed_pointer++) = *(uncompressed_text + output_lookahead_ref); output_size += 3; } return output_size; } uint32_t lz77_decompress (uint8_t *compressed_text, uint8_t *uncompressed_text) { uint8_t pointer_length; uint16_t input_pointer, pointer_pos; uint32_t compressed_pointer, coding_pos, pointer_offset, uncompressed_size; uncompressed_size = *((uint32_t *) compressed_text); compressed_pointer = 4; for(coding_pos = 0; coding_pos < uncompressed_size; ++coding_pos) { input_pointer = *((uint32_t *) (compressed_text + compressed_pointer)); compressed_pointer += 2; pointer_pos = input_pointer >> 4; pointer_length = input_pointer & 15; if(pointer_pos) for(pointer_offset = coding_pos - pointer_pos; pointer_length > 0; --pointer_length) uncompressed_text[coding_pos++] = uncompressed_text[pointer_offset++]; *(uncompressed_text + coding_pos) = *(compressed_text + compressed_pointer++); } return coding_pos; } ``` 我还包含了以下用于本地加载和保存文件的例程，以及一个入口函数，用于演示程序如何压缩自身的源文件，输出到文件，然后再解压为原始文件的副本。要使此操作正确运行，所有引用的代码必须保存在名为 'lz.c' 的文件中，尽管从代码阅读中这一点应该显而易见。向压缩函数传递内存时，此代码仅分配 640KB，这应该足以应对大多数情况。显然，处理更大文件时应增加该值。 作为参考，未压缩代码的原始大小为 5111 字节，压缩后为 1834 字节——总共节省了 3277 字节，即原始大小的 64%。 ``` #include #include #include long fsize (FILE *in) { long pos, length; pos = ftell(in); fseek(in, 0L, SEEK_END); length = ftell(in); fseek(in, pos, SEEK_SET); return length; } uint32_t file_lz77_compress (char *filename_in, char *filename_out) { FILE *in, *out; uint8_t *uncompressed_text, *compressed_text; uint32_t uncompressed_size, compressed_size; in = fopen(filename_in, "r"); if(in == NULL) return 0; uncompressed_size = fsize(in); uncompressed_text = malloc(uncompressed_size); if((uncompressed_size != fread(uncompressed_text, 1, uncompressed_size, in))) return 0; fclose(in); compressed_text = malloc(655360); compressed_size = lz77_compress(uncompressed_text, uncompressed_size, compressed_text); out = fopen(filename_out, "w"); if(out == NULL) return 0; if((compressed_size != fwrite(compressed_text, 1, compressed_size, out))) return 0; fclose(out); return compressed_size; } uint32_t file_lz77_decompress (char *filename_in, char *filename_out) { FILE *in, *out; uint32_t compressed_size, uncompressed_size; uint8_t *compressed_text, *uncompressed_text; in = fopen(filename_in, "r"); if(in == NULL) return 0; compressed_size = fsize(in); compressed_text = malloc(compressed_size); if(fread(compressed_text, 1, compressed_size, in) != compressed_size) return 0; fclose(in); uncompressed_size = *((uint32_t *) compressed_text); uncompressed_text = malloc(uncompressed_size); if(lz77_decompress(compressed_text, uncompressed_text) != uncompressed_size) return 0; out = fopen(filename_out, "w"); if(out == NULL) return 0; if(fwrite(uncompressed_text, 1, uncompressed_size, out) != uncompressed_size) return 0; fclose(out); return uncompressed_size; } int main (int argc, char const *argv[]) { FILE *in; in = fopen("./lz.c", "r"); if(in == NULL) return 0; printf("Original size: %ld\n", fsize(in)); fclose(in); printf("Compressed: %u\n", file_lz77_compress("./lz.c", "lz.c.z77")); printf("Decompressed: %u", file_lz77_decompress("./lz.c.z77", "lz-2.c")); return 0; } the_odyssey.txt: 678171 Compressed (1): 680083 Compressed (2): 437965 Compressed (3): 372199 * 54.88% Compressed (4): 399466 Compressed (5): 444541 Compressed (6): 497605 Compressed (7): 561688 Compressed (8): 639040 Compressed (9): 734527 Compressed (10): 854881 Compressed (11): 1004944 Compressed (12): 1200883 Compressed (13): 1457752 Compressed (14): 1831507 Compressed (15): 1993543 lz.c: 5872 Compressed (1): 6112 Compressed (2): 3994 Compressed (3): 2707 Compressed (4): 2044 Compressed (5): 1894 * 32.25% Compressed (6): 2032 Compressed (7): 2485 Compressed (8): 3124 Compressed (9): 3931 Compressed (10): 5362 Compressed (11): 7366 Compressed (12): 10879 Compressed (13): 12904 Compressed (14): 14251 Compressed (15): 14998 mach_kernel: 8194272 Compressed (1): 8566924 Compressed (2): 6171100 Compressed (3): 5012707 Compressed (4): 4768687 * 58.20% Compressed (5): 4912633 Compressed (6): 5261968 Compressed (7): 5804539 Compressed (8): 6590989 Compressed (9): 7682254 Compressed (10): 9311959 Compressed (11): 11194129 Compressed (12): 13686307 Compressed (13): 16359478 Compressed (14): 18106570 Compressed (15): 18874819 ``` [本文最初发布于 andyh.org。](http://andyh.org/LZ1-Postscript.html) 在对 LZ1 算法进行初步测试后，我开始思考在不同类型的文件上使用不同指针长度所带来的收益。我决定首先测试一个大型纯文本文档，因此选择了荷马的《奥德赛》；第二个测试文件是一个较小的程序源代码；最后一个是任意的二进制文件，即位于 OS X 根目录下的 mach_kernel 操作系统内核。以下结果包括原始文件大小（以字节为单位），并以括号注明用于每个测试的指针长度位宽。结果也以字节为单位衡量，并在最佳结果旁标注了星号，星号后的数值表示压缩文件占原始文件的百分比。 ``` The Odyssey: 678171 lz.c: 5872 mach_kernel: 8194272 Compressed (1): 680083 Compressed (1): 6112 Compressed (1): 8566924 Compressed (2): 437965 Compressed (2): 3994 Compressed (2): 6171100 Compressed (3): 372199 * 54.88% Compressed (3): 2707 Compressed (3): 5012707 Compressed (4): 399466 Compressed (4): 2044 Compressed (4): 4768687 * 58.20% Compressed (5): 444541 Compressed (5): 1894 * 32.25 Compressed (5): 4912633 Compressed (6): 497605 Compressed (6): 2032 Compressed (6): 5261968 Compressed (7): 561688 Compressed (7): 2485 Compressed (7): 5804539 Compressed (8): 639040 Compressed (8): 3124 Compressed (8): 6590989 Compressed (9): 734527 Compressed (9): 3931 Compressed (9): 7682254 Compressed (10): 854881 Compressed (10): 5362 Compressed (10): 9311959 Compressed (11): 1004944 Compressed (11): 7366 Compressed (11): 11194129 Compressed (12): 1200883 Compressed (12): 10879 Compressed (12): 13686307 Compressed (13): 1457752 Compressed (13): 12904 Compressed (13): 16359478 Compressed (14): 1831507 Compressed (14): 14251 Compressed (14): 18106570 Compressed (15): 1993543 Compressed (15): 14998 Compressed (15): 18874819 ``` 结果并不意外，收益最大的情况出现在指针位宽为 3 到 5 之间。源代码文件包含大量对函数调用和变量名的重复引用，在三个测试文件中产生了最佳结果。 我更新了压缩和解压函数的代码，现在允许通过额外参数指定指针长度的位宽。指针大小仍保持为 16 位整数，因为更小的尺寸会对程序效率产生负面影响。此外，压缩文件时，指针长度会以 8 位整数的形式紧跟在未压缩文件长度值之后、原始压缩数据之前写入。这样可以动态存储不同文件的指针长度位宽。另一个细微变化是两个例程中，长度为零的指针将不再使用，因此现在零表示 1，1 表示 2，以此类推。这两项修改破坏了与旧例程生成文件的兼容性。 ``` #include #include uint32_t lz77_compress (uint8_t *uncompressed_text, uint32_t uncompressed_size, uint8_t *compressed_text, uint8_t pointer_length_width) { uint16_t pointer_pos, temp_pointer_pos, output_pointer, pointer_length, temp_pointer_length; uint32_t compressed_pointer, output_size, coding_pos, output_lookahead_ref, look_behind, look_ahead; uint16_t pointer_pos_max, pointer_length_max; pointer_pos_max = pow(2, 16 - pointer_length_width); pointer_length_max = pow(2, pointer_length_width); *((uint32_t *) compressed_text) = uncompressed_size; *(compressed_text + 4) = pointer_length_width; compressed_pointer = output_size = 5; for(coding_pos = 0; coding_pos < uncompressed_size; ++coding_pos) { pointer_pos = 0; pointer_length = 0; for(temp_pointer_pos = 1; (temp_pointer_pos < pointer_pos_max) && (temp_pointer_pos <= coding_pos); ++temp_pointer_pos) { look_behind = coding_pos - temp_pointer_pos; look_ahead = coding_pos; for(temp_pointer_length = 0; uncompressed_text[look_ahead++] == uncompressed_text[look_behind++]; ++temp_pointer_length) if(temp_pointer_length == pointer_length_max) break; if(temp_pointer_length > pointer_length) { pointer_pos = temp_pointer_pos; pointer_length = temp_pointer_length; if(pointer_length == pointer_length_max) break; } } coding_pos += pointer_length; if((coding_pos == uncompressed_size) && pointer_length) { output_pointer = (pointer_length == 1) ? 0 : ((pointer_pos << pointer_length_width) | (pointer_length - 2)); output_lookahead_ref = coding_pos - 1; } else { output_pointer = (pointer_pos << pointer_length_width) | (pointer_length ? (pointer_length - 1) : 0); output_lookahead_ref = coding_pos; } *((uint16_t *) (compressed_text + compressed_pointer)) = output_pointer; compressed_pointer += 2; *(compressed_text + compressed_pointer++) = *(uncompressed_text + output_lookahead_ref); output_size += 3; } return output_size; } uint32_t lz77_decompress (uint8_t *compressed_text, uint8_t *uncompressed_text) { uint8_t pointer_length_width; uint16_t input_pointer, pointer_length, pointer_pos, pointer_length_mask; uint32_t compressed_pointer, coding_pos, pointer_offset, uncompressed_size; uncompressed_size = *((uint32_t *) compressed_text); pointer_length_width = *(compressed_text + 4); compressed_pointer = 5; pointer_length_mask = pow(2, pointer_length_width) - 1; for(coding_pos = 0; coding_pos < uncompressed_size; ++coding_pos) { input_pointer = *((uint16_t *) (compressed_text + compressed_pointer)); compressed_pointer += 2; pointer_pos = input_pointer >> pointer_length_width; pointer_length = pointer_pos ? ((input_pointer & pointer_length_mask) + 1) : 0; if(pointer_pos) for(pointer_offset = coding_pos - pointer_pos; pointer_length > 0; --pointer_length) uncompressed_text[coding_pos++] = uncompressed_text[pointer_offset++]; *(uncompressed_text + coding_pos) = *(compressed_text + compressed_pointer++); } return coding_pos; } ```

标签：C程序, LZ1, LZ77, 信息压缩, 偏移量, 压缩实现, 压缩算法, 客户端加密, 指针, 数据压缩, 数据压缩技术, 无损压缩, 滑动窗口, 编码点, 重复序列