algorithm - 简单来说，压缩通常是如何实现的？

Question

所以我最近一直在考虑如何实现压缩，到目前为止我假设的是它可能使用一种“字节签名”键的哈希表，其内存位置值是“字节签名” ' 应该在相关压缩项目扩展时被替换。

这与事实相去甚远吗？

压缩通常是如何实现的？无需一页纸的回答，简单来说就可以了。

Answer 1

压缩算法试图找到重复的子序列，用更短的表示来替换它们。

让我们从 An Explanation of the Deflate Algorithm 中获取 25 字节长的字符串 Blah blah blah blah blah blah!(200 位)例如。

朴素的方法

一种天真的方法是用相同长度的代码字对每个字符进行编码。我们有 7 个不同的字符，因此需要长度为 ceil(ld(7)) = 3 的代码。我们的代码字可以看起来像这样:

000 → "B"
001 → "l"
010 → "a"
011 → "h"
100 → " "
101 → "b"
110 → "!"
111 → not used

现在我们可以对字符串进行如下编码:

000 001 010 011 100 101 001 010 011 100 101 001 010 011 100 101 001 010 110
B   l   a   h   _   b   l   a   h   _   b   l   a   h   _   b   l   a   !

这只需要 25·3 位 = 75 位用于编码字加上 7·8 位 = 56 位用于字典，因此 131 位 (65.5%)

或者对于序列:

00 → "lah b"
01 → "B"
10 → "lah!"
11 → not used

编码后的词:

01 00    00    00    00    10
B  lah b lah b lah b lah b lah!

现在我们只需要 6·2 位 = 12 位用于编码字，10·8 位 = 80 位加上 3·8 位 = 24 位用于每个字的长度，因此 116 位 (58.0%)。

哈夫曼编码方法

Huffman code用于编码频率更高的字符/子字符串，代码比频率更低的字符/子字符串更短:

5 × "l", "a", "h"
4 × " ", "b"
1 × "B", "!"

// or for sequences

4 × "lah b"
1 × "B", "lah!"

一个可能的霍夫曼编码是:

0      → "l"
10     → "a"
110    → "h"
1110   → " "
11110  → "b"
111110 → "B"
111111 → "!"

或者对于序列:

0  → "lah b"
10 → "B"
11 → "lah!"

现在我们的 Blah blah blah blah blah blah! 可以编码为:

111110 0 10 110 1110 11110 0 10 110 1110 11110 0 10 110 1110 11110 0 10 110 1110 11110 0 10 110 111111
B      l a  h   _    b     l a  h   _    b     l a  h   _    b     l a  h   _    b     l a  h   !

或者对于序列:

10 0     0     0     0     11
B  lah b lah b lah b lah b lah!

现在第一个代码只需要 78 位或 8 位，而不是像我们的初始字符串那样的 25·8 = 200 位。但是我们仍然需要添加存储我们的字符/序列的字典。对于我们的每个字符示例，我们将需要 7 个额外的字节(7·8 位 = 56 位)，而我们的每个序列示例将再次需要 7 个字节加上每个序列的长度 3 个字节(因此为 59 位)。这将导致:

56 + 78 = 134 bit (67.0%)
59 +  8 =  67 bit (33.5%)

实际数字可能不正确。请随时编辑/更正它。