algorithm - 实际压缩和 Kolmogorov 复杂性的界限

Question

我正在研究使用压缩来衡量文档与文档语料库之间的关系。在这样做的过程中，我在使用 bzip2 时发现了一个奇怪的结果； len(compress(corpus)) > len(compress(corpus + new_document))。这应该是实际压缩算法的情况吗？在查看数据的 Kolmogorov 复杂性时，这在理论上是否可行？ (思路是用压缩算法来近似数据的复杂度)

Answer 1

是的，实用的压缩算法应该是这样的，理论上可以用Kolmogorov complexity .解释原因的最简单方法是举个例子。

假设如下:

• 您的文档分隔符是,
• 语料库是文档 abc,def,abc,def,abc,def,abc,
• 新文件是def
• 您的压缩算法(或 kolmogorov 描述语言)只允许重复，方法是在重复计数前加上 |(这是 run-length encoding 的变体)

然后:

• compress(corpus) = "3|abc,def,1|abc"
• compress(corpus+new_document) = "4|abc,def,"

所以 compress(corpus) 比 compress(corpus+new_document) 长。这有点做作，但希望能解释结果在理论上如何用一个简单的方案出现。我并不是说这就是 bzip2 会发生的情况，只是展示它在理论上是如何实现的。

编辑在另一个答案中提到游程编码不是图灵完备的，因此不能用于 Kolmogorov 复杂性。虽然这是事实，但使用图灵语言，您可以实现您选择使用的任何描述语言的游程长度编码，并获得相同的结果，因此该示例仍然有效。