随机字符串检测

Question

我需要在不执行频率分析的情况下检查字符串是否相当随机，因为这太耗时了。已经有这样的算法了吗？我是用java构建的，但是一个算法的通用描述也是非常有用的。

澄清:对于肉眼来说，下面的文本不知何故是随机的……Dsfsddsfdsfsddsf....或者甚至po340-3gk30g3gkf;glkp。

我不想确切地知道它有多随机。我只是想检测，就像人类一样，如果字符串看起来是随机的，而不是测量它的实际随机性。

Answer 1

我需要在不执行频率分析的情况下检查字符串是否相当随机，因为这太耗时了。

简单的频率分析基本上是我能想象到的最快的事情。您只需遍历字符串中的字符(一次)并跟踪计数。

我无法想象你能找到比这更快的“随机性测试”。

另外，我不能说你的问题很清楚。从技术上讲，任何字符串都是随机的。如果你在寻找“看起来”随机的东西，我想你需要寻找所有类型的模式，这对你来说肯定太耗时了。

在你看来，这是随机的吗：

String str = "                      o         _        _            _        "
           + "           _o        /\_      _ \\o     (_)\__/o     (_)       "
           + "         _< \_      _>(_)    (_)/<_       \_| \      _|/' \/   "
           + "        (_)>(_)    (_)           (_)      (_)       (_)'  _\o_ ";

它对我来说看起来不是很随机，但我很难定义什么是随机的。

Answer 2

压缩后测量字符串的长度。 gzip就可以了。

所有压缩器都通过在输入中寻找冗余来工作。子字符串的重复是一种冗余形式，它对应于对非随机性的常见直观和数学理解。gzip和它的同类特别寻找重复的子字符串，并用更短的“指针”替换第二次和随后出现的子字符串回到原始字符串。

压缩字符串的长度给出了它的Kolmogorov complexity的上限，这在某种意义上是它的“绝对随机性”，但不能直接测量。

尽管gzip和其他通用压缩器通常会产生一个头，因此短字符串看起来可能会变长(即通常不是length(a short string) < length(compress(a short string))的情况)，但一般来说，length(compress(a short repetitive string)) < length(compress(a short non-repetitive string))仍然是正确的，希望这就是您所需要的。

Answer 3

您可以分析生成字符串的算法，也可以进行频率分析。但我认为没有办法确定一个字符串是否相当随机。

'13530168=dwninwebvp‘是随机的吗？