压缩算法试图找到重复的子序列,以较短的表示形式替换它们。

让我们用25字节长的字符串 Blah blah blah blah blah! (200位)来自 An Explanation of the Deflate Algorithm 例如。

幼稚方法

一种幼稚的方法是用相同长度的代码字对每个字符进行编码。我们有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%)。

哈夫曼码方法

这个 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!"

现在我们 废话废话! 可编码为:

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%)

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

检查 this 维基页面…

无损压缩算法通常利用统计冗余来更简洁地表示发送者的数据,而不会产生错误。无损压缩是可能的,因为大多数现实数据都有统计冗余。例如,在英语文本中,字母“e”比字母“z”更常见,字母“q”后跟字母“z”的概率非常小。

另一种压缩,称为有损数据压缩或感知编码,如果某些保真度损失是可以接受的,则是可能的。一般来说,有损数据压缩将以人们如何感知相关数据的研究为指导。例如,人眼对亮度的细微变化比对颜色的变化更敏感。jpeg图像压缩部分通过“舍入”一些不太重要的信息来工作。有损数据压缩提供了一种获得给定压缩量的最佳保真度的方法。在某些情况下,需要透明(不明显)压缩;在其他情况下,为了尽可能减少数据量,牺牲了保真度。

无损耗压缩方案是可逆的,因此可以重建原始数据,而有损压缩方案接受一些数据损失,以实现更高的压缩。

然而,无损数据压缩算法总是无法压缩某些文件;实际上,任何压缩算法都必然无法压缩任何不包含可识别模式的数据。因此,试图压缩已经压缩的数据通常会导致扩展(由于符号较少,文本文件在压缩后通常可以压缩得更多),以及试图压缩除最普通加密数据以外的所有数据。

在实践中,有损数据压缩也将达到再次压缩不起作用的程度,尽管极端有损算法(例如总是删除文件的最后一个字节)总是将文件压缩到文件为空的程度。

无损压缩与有损压缩的示例如下:

25.888888888

此字符串可以压缩为:

25.[9]8

被解释为“二十五点九个八分”,原始字符串被完美地重新创建,只是以较小的形式书写。在有损系统中,使用

26

相反,原始数据会丢失,这得益于较小的文件大小。

无损压缩算法将每个可能的输入转换为不同的输出,这样更常见的输入转换为更短的输出。这在数学上是不可能的 全部的 可能需要压缩的输入——否则,您将有多个输入a和b压缩到同一个表单,所以当您解压缩它时,是返回到a还是返回到b?在实践中,最有用的信息有一些冗余,并且这种冗余符合某些模式;因此,数据可以有效地被压缩,因为 扩大 当你压缩它们时,自然不会出现。

例如,在jpeg或mp3压缩中使用的有损压缩,其工作原理是通过一些信号来近似输入数据,这些信号可以用比原始数据更少的位来表示。当你减压时,你得不到原始的,但你通常能得到足够接近的东西。

简单来说,常见的压缩形式是 http://en.wikipedia.org/wiki/Dictionary_coder . 这包括用较短的字符串替换较长的重复字符串。

例如,如果您有一个如下所示的文件:

"Monday Night","Baseball","7:00pm"
"Tuesday Night","Baseball","7:00pm"
"Monday Night","Softball","8:00pm"
"Monday Night","Softball","8:00pm"
"Monday Night","Baseball","5:00pm"

它大约有150个字符,但是如果您在哪里做一个简单的替换,如下所示: a=“星期一晚上”,b=“星期二晚上”,c=“棒球”,d=“垒球”,e=“7:00 pm”,f=“8:00 pm”,g=5:00 pm”

然后相同的内容可以编码为:

A,C,E
B,C,E
A,D,F
A,D,F
A,C,G

使用25个字符!如果我们对文件的格式做了更多的假设,一个聪明的观察者也可以看到如何将其进一步简化为15个字符。显然,替换键的开销很大,但通常非常大的文件都有很多这样的替换。这是一种非常有效的压缩大型文件或数据结构的方法,并且仍然允许它们“稍微”具有人类可读性。

罗塞塔密码有一个 entry 关于哈夫曼编码,和前面的一样 blog entry 我的。