algorithm - 是否有任何不基于模式的数据压缩算法？

Question

大多数数据压缩算法都基于“模式”。但我正在寻找一种不基于“模式”的数据压缩算法

标签： algorithmcomputer-sciencedata-compression

Answer 1

您的问题的答案几乎是“不”。推理很复杂，但我会尝试解释一下：

定义“（无损）数据压缩算法”的最简单方法是将一个字节序列以可逆方式转换为一个新的字节序列的函数，这样新的字节序列通常会比原来的短。

'通常'这个词在那里，因为没有算法可以压缩每个可能的文件。因为压缩必须是可逆的，所以每个不同的输入文件必须映射到不同的输出文件。对于任何给定的长度N，只有这么多长度为N或更少的文件。因此，如果压缩器将任何比N长的输入文件映射到N字节或更短的输出文件，那么它还必须将较短的文件映射到比N长的文件，因为没有足够的可能更短输出以压缩它们。

因此，在最好的情况下，压缩算法是文件的排列。它不能压缩每个文件。它不能压缩“随机”文件，因为排列的输出仍然是随机的。

那么问题是“这些压缩机怎么可能工作？” 他们通过尝试将最可能的输入文件分配给最短的输出文件来工作，这样平均输出将比输入短。就像它有一个按概率顺序排列的所有文件的大列表，它只是与按长度顺序排列的所有文件列表相匹配。

为了做到这一点，压缩器需要有一些模型来确定哪些文件更有可能被使用。基于 LZ 的压缩器基本上假设我们在现实生活中使用的文件往往具有比随机数据更多的重复字符串。因此，与没有重复的文件相比，具有更多重复字符串的输入文件被分配给更短的输出文件。霍夫曼和算术压缩器假设文件往往具有输入符号的倾斜分布。

因此，每个压缩器本质上都有一个概率模型——它期望文件经常匹配的模式。与模式匹配的文件可以很好地压缩，而不匹配的文件则不能。