performance - 测量位序列复杂度的方法

Question

我正在寻找一种简单的方法来估计固定大小的位序列的复杂性（可能最大长度为 10）。例如，我想 0000000 和 111111 根本不是很复杂，但 101010 和 101101 位于频谱的其他位置。

我知道 Kolmogorov 复杂性是无法计算的，但是是否可以简单地为具有二进制字母的固定（和小）长度序列进行编程？或者是否有另一种可能仅近似该度量但更容易计算的度量？

重要的是该措施相当简单，以便我可以向其他人（尽管受过良好教育）解释它。

谢谢。

Answer 1

你需要有一个计算复杂度的程序，并且没有最好的程序。

例如，您可以对字符串进行运行编码，并计算运行次数。

您可以通过 LZW 压缩器（如 ZIP）运行字符串，并报告其压缩到的大小。

您不必只选择一种方法。您的方法可能是尝试五种不同的方法，并报告给您最小量度的一种。

例如，您可以尝试最初反转每隔一个位，然后尝试运行编码。或者尝试反转位 2 和 3，然后位 6 和 7，依此类推。

这些是获得衡量标准的可能方法，但仅此而已。

Kolmogorov 复杂度是最小程序的大小，以位为单位，可以重现字符串，这取决于语言（无论是高级、汇编、机器或图灵机，还是驱动您拥有的特殊程序的代码）为此目的而创建）。

你知道它的存在是因为你知道有上限和下限。任何可以重现该字符串的程序都会为您提供一个上限。您知道空程序不能，因此您的下限为零。所以它介于两者之间，但这并不意味着你可以找到它。

请记住，仅仅谈论一个字符串的复杂性是没有意义的，因为测量工具可以针对该字符串进行优化。你真的需要谈论一组字符串，只是为了让工具保持诚实。