实际压缩和柯尔莫哥洛夫复杂度的界限

Question

我正在研究使用压缩作为衡量文档与文档语料库关系的一种方法。在使用bzip2时，我发现了一个奇怪的结果; len（compress（corpus））> len（compress（corpus + new_document））。实际的压缩算法应该是这种情况吗？当考察Kolmogorov数据的复杂性时，这在理论上是可行的吗？ （其思想是使用压缩算法来近似数据的复杂度）

Answer 1

是的，实际的压缩算法应该是这种情况，理论上可以使用Kolmogorov complexity。解释原因的最简单方法就是举一个例子。

假设如下：

• 你的文件分隔符为,
• 语料库文件ABC，DEF，ABC，DEF，ABC，DEF，ABC，
• 新的文件是高清
• 您的压缩算法（或kolmogorov描述语言）只允许重复前缀重复计数，后跟|（这是run-length encoding的变体）

然后：

• 压缩（语料库）= “3 | ABC，DEF，1个| ABC”
• 压缩（语料库+ new_document）= “4 | ABC，DEF，”

因此compress(corpus)比compress(corpus+new_document)长。这是有点人为的，但希望解释如何结果理论上可以用简单的方案出现。我并不是说bzip2会发生这种情况，只是展示它在理论上是可行的。

编辑 它已运行长度编码不是图灵完整的，因此不能用于柯尔莫哥洛夫复杂另一个答案被提及。虽然这是真的，但使用图灵语言，您可以使用实现以您选择使用的任何描述语言编码游程长度，结果相同，因此该示例仍然有效。

Answer 2

真实的压缩算法有这样的怪癖，但它们只是提供了一个非常粗略的近似值。

至于在理论上是否可能发生，但差别不大。

我们假设你有两个字符串，x和y，其中x是y的前缀。比方说，例如该

X = “asdfasdfasdfasdfasdfasdfasdfasdfasdf”

Y = “asdfasdfasdfasdfasdfasdfasdfasdfasdf23452345234523452344523452452345234524345234”

让我们进一步假设，d为y的最短描述。 （即在这种情况下，x可以被描述为|“由D描述的数字减46个字符”|，其比D更长，但是仅仅通过小的常数和对数因子（基本上其余指令中的字符数）。

甚至有可能是x的一个短的描述，但我们知道，在最坏情况下，K（X）< = K（Y）+日志（| Y | - | X |）

但是，你必须请记住，理论Kolmogorov复杂性是难以置信的，恒定的差异在这个领域没有任何意义。

（注：上面的RLE例子也不是一个有效RLE不是图灵完整的语言，因此它不能被用来作为Kolmogorov复杂的描述语言。）