简单来说,压缩是如何实现的？

Question

所以我最近一直在考虑如何实现压缩,到目前为止我假设它可能是使用一种具有内存位置值的'字节签名'键的HashTable,其中'byte signature'应该是在扩展有问题的压缩物品时更换.

这远非事实吗？

压缩通常如何实施？不需要一个值得回答的页面,只需用简单的术语就可以了.

Answer 1

压缩算法试图找到重复的子序列,用较短的表示替换它们.

让我们Blah blah blah blah blah!从一个 Deflate 算法的解释中获取25字节长的字符串(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 bit = 75 bit加上7·8 bit = 56 bit,因此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%).

霍夫曼代码方法

的霍夫曼码被用来以比较不频繁的那些较短码编码更频繁的字符/字符串:

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!可以编码为:

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

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

Answer 2

查看此 Wiki页面...

无损压缩算法通常利用统计冗余,以便更简洁地表示发送方的数据而不会出错.无损压缩是可能的,因为大多数真实数据都具有统计冗余.例如,在英文文本中,字母"e"比字母"z"更常见,字母"q"后跟字母"z"的概率非常小.

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

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

但是,无损数据压缩算法总是无法压缩某些文件; 实际上,任何压缩算法都必然无法压缩任何不包含可辨别模式的数据.因此,尝试压缩已经压缩的数据通常(文本文件通常可以在压缩之后被压缩得更多,因为符号更少)导致扩展,并且尝试压缩除了最简单的加密数据之外的所有数据.

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

无损与有损压缩的示例是以下字符串:

25.888888888

此字符串可以压缩为:

25.[9]8

解释为"二十五点九八",原始字符串完全重新创建,只是以较小的形式书写.在有损系统中,使用

26

相反,由于文件较小,原始数据会丢失.

Answer 3

无损压缩算法将每个可能的输入转换为不同的输出,使得更常见的输入转换为更短的输出.在数学上不可能压缩所有可能的输入 - 否则,你有多个输入A和B压缩到相同的形式,所以当你解压缩它时,你会回到A还是回到B？实际上,大多数有用的信息都有一些冗余,这种冗余适合某些模式; 因此,数据可以有用地进行压缩,因为压缩它们时会扩展的情况不会自然产生.

例如,在JPEG或MP3压缩中使用的有损压缩通过用一些信号近似输入数据来工作,该信号可以用比原始更少的比特表示.当你解压缩它时,你没有得到原始的,但你通常得到足够接近的东西.