python - 如何匹配实际上是随机的字符串？

Question

我正在编写的 Python 应用程序需要从源代码中提取标识符和文本字符串。它找到的一小部分是(看似)随机字符串。我想过滤掉它们，但到目前为止还无法创建一个正则表达式来做到这一点。不可能只按长度过滤，因为有一些很长的标识符是有效的。这是一个随机取的例子，与相同长度的有效标识符相比:

UGxhemEgZGUgaWZXNaWdhZGyOiBDSUWRVNUQVYtSVBOIFVuaWQ
NSApplicationDidChangeScreenParametersNotification

有没有办法编写一个正则表达式或其他检测系统来检测这样的垃圾序列？我开始怀疑如果不针对大量单词词典测试字符串就无法完成，我认为这很容易出错并且需要大量计算。但是，也许更聪明的人知道检测或匹配这样的随机序列的方法？

这个问题的理想解决方案是一个函数，它可以将字符串作为输入，并报告它是否“可能”是随机的。它可能会产生误报(误报一些随机字符串不是随机的)，最好是低概率，但它不能报告误报(有些东西是随机的，但不是随机的)。以防万一，字符串的长度似乎在 25 到 80 个字符之间。

EDIT #1 2017-02-08:进一步思考，我想到一种可能的方法可能是匹配行中最少数量的唯一字符的正则表达式。例如，第二个字符必须与第一个不同，第三个与前两个不同，第四个与前三个不同，等等。足够长的版本可能会捕捉到很多随机序列。然而，查看不同的正则表达式运算符，我没有看到(因为缺少更好的词)“负向后引用”或“匹配其他而不是你刚刚匹配的东西”的版本。如果有人知道这方面的变体，也许我可以让它发挥作用。

编辑 #1 2017-02-10:我担心我在上面编写两个示例字符串的方式可能会被误解为单个字符串。上面的例子是两个相同长度的独立字符串——如果不清楚，我深表歉意。这里还有一些例子；每行都是一个单独的标识符。这也是故意显示不同的长度。

shouldBeAbleToCountLiveNeighboursOfACellOnDiagonalsAndStraightLines
eXNZWzIGbHRpbWVkaWEgYWkIGFuaWhdGlvbiBkaXNcmlidXRlZCNCpUgRGlzdHJpYnV
dWxLXRvbGVyYWIHJlYWwtdGltZSBzeXNZWzLgKlSBEaXNcmlidXRlZCBBcmNoaXRlYR
dGhIExvIHNYmltbMgYSBsYSBwWdpbmEgeSBsbyBhbnVuYlhbWzIGVuIGVsIHByhpbWg
aGUgYuZmVyZWjZSBwcmjZWVkaWncygDQoNClNYmpcNpbNCkluIGyZGVyIHRvIHN
YQKUGFyYTogZXNYFyQGluYWlcCteAKQMIExaXMgQSgUGluZWRhDQpDQzogQuYVw
thehasSizeMatcherShouldMatchACollectionWithExpectedSize
QycmVvIGRlIERpcVtaWhYnDsgZGUgYWNaXZpZGFkZXMgZGUgbGEg
NSAppleEventManagerWillProcessFirstEventNotification
SNMTransformGizmoRotationControllerPerformTransform
RndkOiBEaWZcnDsgZGUgYudmjYXRvcmlhIFNVTUJVCBlbiBSRUJ

不管它值多少钱，我都装上了 pastebin a list of the 1000 longest identifiers由我的应用程序从大约 900 个 GitHub 存储库的半随机选择中提取。它包含真实标识符和随机字符串。

Answer 1

首先，谢谢您，您的问题让我很感兴趣，而且我正在寻找一些有趣的培训。下面我已经实现了我在你的帖子评论中提到的想法，以及@swbandit 的想法。也可以通过修改 is_rnd 函数在代码中添加任何其他策略。我已经从此处找到的短字典 (https://gist.github.com/jbergantine/2390284) 生成了有意识的字符串(当然这本字典很小，可能不具有代表性，但我将其用于测试目的)。这些字符串在代码中被称为 strok。之后生成相同长度的随机字符串(strrnd)。我只使用小写字符并假设字符串中没有空格。

如果字符串是随机的，函数 is_rnd1 和 is_rnd2 返回 True。函数 is_rnd1 检查最常见的英文字符“e”(12.7%) 和最罕见的“z”(0.074%) 的出现频率。然而，在函数中，频率的边界被显着扩展了。函数 is_rnd2 只是检查四个连续辅音的出现，正如@swbandit 所建议的那样。

在代码的测试部分，上述函数针对不同长度的字符串进行测试，字符串的长度根据构成strok 的单词数来衡量。函数 is_rnd 被调用了两次。首先是 strok，然后是随机字符串。求和定义字符串随机与否的错误。

所以这是代码:

nouns = ['here is a list from gist.github.com/jbergantine/2390284']
allch = "abcdefghijklmnopqrstuvwxyz"

import numpy as np
import matplotlib.pyplot as plt
import random, string
import collections
import re

alb = 'etaoinshrdlcumwfgypbvkjxqz'

def frqlist(s):
    dic = collections.Counter(s)
    arr = np.zeros(len(alb))
    for key in dic:
        idx = alb.index(key)
        arr[idx] = float(dic[key])/float(len(s))
    return arr

def generate_strs(nw=1):
    strok = ''.join([nouns[random.randrange(0, len(nouns))] 
                     for i in range(nw)])
    rand_str = lambda n: ''.join([random.choice(string.lowercase) 
                         for i in xrange(n)])
    strrnd = rand_str(len(strok))
    return strok, strrnd

def is_rnd1(s):
    fq = frqlist(s)
    return not (fq[0] > 0.07 and fq[-1] < 0.01)

def is_rnd2(s):
    return re.search(r'[^aeiou]{4}', s)

maxwords = 12
nprobe = 1000

is_rnd = is_rnd1
nwa = []
err = []
print "Words\t% of errors"
for nw in range(1, maxwords):
    errok = 0
    errrnd = 0
    for i in range(0, nprobe):
        strok, strrnd = generate_strs(nw)
        if is_rnd(strok):
            errok += 1./nprobe
        if not is_rnd(strrnd):
            errrnd += 1./nprobe
    print nw, "\t", (errok*100. + errrnd*100.)/2.
    nwa.append(nw)
    err.append((errok*100. + errrnd*100.)/2.)

plt.plot(nwa, err)
plt.show()

下面是一些结果

For function is_rnd1
Words   % of errors
1   28.2
2   20.45
3   17.15
4   13.15
5   13.7
6   10.65
7   9.25
8   7.35
9   6.5

For function is_rnd2 (4 consecutive consonants)
Words   % of errors
1   23.15
2   13.0
3   13.55
4   17.75
5   22.2
6   24.35
7   27.7
8   30.6
9   33.25

For function is_rnd2 (6 consecutive consonants)
Words   % of errors
1   39.45
2   20.8
3   11.9
4   6.5
5   4.05
6   3.05
7   2.5
8   1.6
9   2.0

对我来说，结果很有趣。

更新:

我尝试过机器学习。我使用了一个有 26 个入口和 1 个导出的神经元。在入口处提供字符串中字符的频率。如果字符串是随机的，则输出为 1，否则为 0。神经元由以下类描述:

class Neuron(object):
    def __init__(self, nin, wt=0.):
        self.nin = nin
        self.w = np.full(nin, wt, dtype=np.float32)
        self.out = 0.
        self.learnspd = 0.01

    def result(self, ins):
        self.out = np.sum(self.w * ins)
        self.out = 1. if self.out > 0.1 else 0.
        return self.out

    def correctw(self, ins, err):
        self.w = self.w + err*self.learnspd*ins

在定义了神经元neuron = Neuron(len(alb))之后，实现了它的学习过程:

def learning(neuron, nset, maxwords):
    for i in xrange(nset):
        nw = np.random.randint(1, maxwords+1)
        strok, strrnd = generate_strs(nw)
        fq = frqlist(strok)
        neurres = neuron.result(fq)
        errok = 0.0 - neurres
        neuron.correctw(fq, errok)
        fq = frqlist(strrnd)
        neurres = neuron.result(fq)
        errrnd = 1.0 - neurres
        neuron.correctw(fq, errrnd)

让我们学习learning(neuron, nset, maxwords)。

最后，神经元就可以使用了:

def is_rnd_neuron(s, neuron):
    fq = frqlist(s)
    return bool(neuron.result(fq))

使用与上述相同的测试程序，我获得了以下结果:

nset = 100
Words   % of errors
1   50.0
2   50.0
3   50.0
4   50.0
5   50.0
6   50.0
7   50.0
8   50.0
9   50.0
nset = 500
Words   % of errors
1   20.4
2   13.25
3   9.5
4   5.55
5   5.95
6   3.9
7   3.35
8   2.55
9   2.4
nset = 1000
Words   % of errors
1   16.95
2   9.35
3   4.55
4   2.4
5   1.7
6   0.65
7   0.4
8   0.15
9   0.1
nset = 5000
Words   % of errors
1   16.6
2   7.25
3   3.8
4   1.8
5   1.1
6   0.5
7   0.1
8   0.1
9   0.05

它的实现如此简单，结果如此出色，给我留下了深刻的印象。