随机字符串检测

Question

我需要在不执行频率分析的情况下检查字符串是否相当随机,因为它太耗时.那里有这样的算法吗？我用java构建它,但算法的一般描述也非常有用.

澄清:对于人眼来说,以下文字在某种程度上是随机的...... dsfsddsfdsfsddsfs ....甚至是po340-3gk30g3gkf; glkp.

我不想确切知道它是多么随机.我只是想要检测,就像人类的方式一样,如果一个字符串随机看,而不测量它的实际随机性.

Answer 1

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

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

我无法想象你能找到比这更快的"随机性测试".

此外,我不能说你的问题很清楚.从技术上讲,任何字符串都是随机的.如果你看起来像是"看起来"随机,我想你需要寻找各种各样的模式,这对你来说肯定太费时间了.

你认为这是随机的吗？

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

它对我来说看起来并不随机,但我很难定义看起来随机的内容.

Answer 2

压缩后测量弦的长度. gzip会做.

所有压缩机都通过查找输入中的冗余来工作.重复子串是一种冗余形式,对应于对非随机性的常见直观和数学理解. gzip及其同类产品专门寻找重复的子串,并将较短的"指针"替换为原始的第二次和后续次数.

压缩字符串的长度为您提供了Kolmogorov复杂度的上限,这在某种意义上是"绝对随机性",但无法直接测量.

虽然gzip和其他通用压缩器通常会产生一个标题,所以短字符串可能看起来实际上长度增长(即通常情况并非如此length(a short string) < length(compress(a short string))),但一般情况下仍然如此,length(compress(a short repetitive string)) < length(compress(a short non-repetitive string))希望你所需要的只是.