斜率压缩实例

Question

我有兴趣学习压缩算法，特别是它是如何表示在数据流，并认为我将受益于一些额外的例子(例如。短文本串的压缩，或压缩块的解压缩)。我正在继续研究我发现的一些资源：ref1、ref2、ref3，但是这些资源并没有太多的例子来说明实际的压缩是如何作为数据流的。

如果我能得到几个例子，说明一些字符串在压缩前后的样子，以及它们之间的关系的解释，那将是非常棒的。

此外，如果有其他资源，我可以查看，请添加这些。

Answer 1

您可以使用gzip或zlib压缩示例数据，并使用英根来分解和检查所产生的压缩数据。infgen还可以选择查看动态标头中的详细信息。

Answer 2

+1表示英根，但这里有一个稍微详细的答案。

您可以查看使用gzip和任何十六进制编辑器之前和之后的情况。例如，大多数linux发行版都包含xxd。我包括了原始的十六进制输出(没有理解就没那么有趣)和infgen的输出。

• hello hello hello hello (触发静态huffman编码，就像大多数短字符串一样)。

~ $ echo -n "hello hello hello hello" | gzip | xxd
00000000: 1f8b 0800 0000 0000 0003 cb48 cdc9 c957  ...........H...W
00000010: c840 2701 e351 3d8d 1700 0000            .@'..Q=.....

~ $ echo -n "hello hello hello hello" | gzip | ./infgen/a.out -i
! infgen 2.4 output
!
gzip
!
last
fixed
literal 'hello h
match 16 6
end
!
crc
length

• \xff\xfe\xfd\xfc\xfb\xfa\xf9\xf8\xf7\xf6\xf5\xf4\xf3\xf2\xf1 (触发器未压缩模式)

~ $ echo -ne "\xff\xfe\xfd\xfc\xfb\xfa\xf9\xf8\xf7\xf6\xf5\xf4\xf3\xf2\xf1" | gzip | xxd
00000000: 1f8b 0800 0000 0000 0003 010f 00f0 ffff  ................
00000010: fefd fcfb faf9 f8f7 f6f5 f4f3 f2f1 c6d3  ................
00000020: 157e 0f00 0000                           .~....

~ $ echo -ne "\xff\xfe\xfd\xfc\xfb\xfa\xf9\xf8\xf7\xf6\xf5\xf4\xf3\xf2\xf1" | gzip | ./infgen/a.out -i
! infgen 2.4 output
!
gzip
!
last
stored
data 255 254 253 252 251 250 249 248 247 246 245 244 243 242 241
end
!
crc
length

• abaabbbabaababbaababaaaabaaabbbbbaa (触发器动态huffman编码)

~ $ echo -n "abaabbbabaababbaababaaaabaaabbbbbaa" | gzip | xxd
00000000: 1f8b 0800 0000 0000 0003 1dc6 4901 0000  ............I...
00000010: 1040 c0ac a37f 883d 3c20 2a97 9d37 5e1d  .@.....=< *..7^.
00000020: 0c6e 2934 9423 0000 00                   .n)4.#...

~ $ echo -n "abaabbbabaababbaababaaaabaaabbbbbaa" | gzip | ./infgen/a.out -i -d
! infgen 2.4 output
!
gzip
!
last
dynamic
count 260 7 18
code 1 4
code 2 1
code 4 4
code 16 4
code 17 4
code 18 2
zeros 97
lens 1 2
zeros 138
zeros 19
lens 4
repeat 3
lens 2
zeros 3
lens 2 2 2
! litlen 97 1
! litlen 98 2
! litlen 256 4
! litlen 257 4
! litlen 258 4
! litlen 259 4
! dist 0 2
! dist 4 2
! dist 5 2
! dist 6 2
literal 'abaabbba
match 4 7
match 3 9
match 5 6
literal 'aaa
match 5 5
literal 'b
match 4 1
literal 'aa
end
!
crc
length

我发现infgen仍然不够详细，无法完全理解格式。我在这里逐点地、手工地对所有三个示例进行解压缩，并详细介绍了我的博客。

关于概念，除了RFC 1951 (平减)(平减)外，我还推荐Feldspar的概念概述 of Huffman代码和LZ77 in DEFLATE