實際壓縮和柯爾莫哥洛夫複雜度的界限

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複雜的描述語言。）