実際にランダムな文字列の一致方法は？

Question

私が書いているPythonアプリケーションは、ソースコードから識別子とテキスト文字列を抽出する必要があります。それが見つかったものの小さな割合は、（一見）ランダムな文字列です。私はそれらをフィルタリングしたいと思いますが、これまでに正規表現を作成することができませんでした。非常に長い識別子が有効であるため、長さだけでフィルタリングすることはできません。

UGxhemEgZGUgaWZXNaWdhZGyOiBDSUWRVNUQVYtSVBOIFVuaWQ 
NSApplicationDidChangeScreenParametersNotification 

次のようにジャンク配列を検出するだろう正規表現または他の検出システムを記述する方法があります：ここでの例では、同じ長さの有効な識別子に比べて、ランダムに取られていますか？私は、単語の大規模な辞書に対して文字列をテストしなければ、それができないことを疑うようになり始めています。これは、エラーが発生しやすく、計算集約型であると信じています。しかし、誰かがこのようなランダムな配列を検出したりマッチさせるアプローチをもっと賢明に知っているのかもしれません。

この問題の理想的な解決策は、文字列を入力として取り、「おそらく」ランダムであるかどうかを報告する関数です。それは偽陰性を生成する可能性があります（ランダムな文字列をランダムに誤って報告する可能性があります）が、確率は低いことが望ましいですが、偽陽性を報告してはなりません。重要な場合は、ストリングの長さは25文字から80文字の範囲にあるようです。

EDIT＃1 2017-02-08：さらに考えてみると、可能なアプローチは一番下の一意の文字の最小数と一致する正規表現である可能性があります。例えば、2文字目は最初の文字とは異なるものでなければならず、前の3文字とは異なる3文字、前の3文字とは異なる4文字などでなければなりません。しかし、異なる正規表現演算子を見て、私は "否定的な後方参照"または "他のとちょうどマッチしたものとマッチする"のバージョンを見ません。誰かがこれにバリエーションを知っていれば、おそらく私はそれを動作させることができます。

EDIT＃1 2017-02-10：私は上記の2つの例文を書いた方法が単一の文字列として誤解されるかもしれないと心配しています。上記の例は同じ長さの2つの別々の文字列です–それが不明な場合は誠実にお詫び申し上げます。ここにいくつかの例があります。各行は別個の識別子である。これは目的に応じて異なる長さも示しています。それは価値があるものは何でものために

shouldBeAbleToCountLiveNeighboursOfACellOnDiagonalsAndStraightLines 
eXNZWzIGbHRpbWVkaWEgYWkIGFuaWhdGlvbiBkaXNcmlidXRlZCNCpUgRGlzdHJpYnV 
dWxLXRvbGVyYWIHJlYWwtdGltZSBzeXNZWzLgKlSBEaXNcmlidXRlZCBBcmNoaXRlYR 
dGhIExvIHNYmltbMgYSBsYSBwWdpbmEgeSBsbyBhbnVuYlhbWzIGVuIGVsIHByhpbWg 
aGUgYuZmVyZWjZSBwcmjZWVkaWncygDQoNClNYmpcNpbNCkluIGyZGVyIHRvIHN 
YQKUGFyYTogZXNYFyQGluYWlcCteAKQMIExaXMgQSgUGluZWRhDQpDQzogQuYVw 
thehasSizeMatcherShouldMatchACollectionWithExpectedSize 
QycmVvIGRlIERpcVtaWhYnDsgZGUgYWNaXZpZGFkZXMgZGUgbGEg 
NSAppleEventManagerWillProcessFirstEventNotification 
SNMTransformGizmoRotationControllerPerformTransform 
RndkOiBEaWZcnDsgZGUgYudmjYXRvcmlhIFNVTUJVCBlbiBSRUJ 

、私は約900 GitHubのリポジトリのセミランダム選択から自分のアプリケーションによって引っ張らペーストビンa list of the 1000 longest identifiersに置きます。実際の識別子とランダムな文字列の両方を含んでいます。

Answer 1

マルコフチェーンに依存するrrenaud's gibberish detectorをご覧ください。あなたは、あなたのニーズに合うように、与えられたコードを変更する必要があります。しかし、それは助けるかもしれません。

これはおそらく開始するには最適な場所です。

しかし... 私はこの問題を自分自身でまず解決しようとしました。これは最善の答えではないかもしれませんし、大文字で始まる各単語に完全に依存しています（あなたの与えられたテスト入力に基づいて）。しかし、私は良い結果をもたらす結果を得るためにアイデアを持ち歩いて楽しんだが、はるかに長いテキスト（おそらくあなたが見ているだろう）で非常に遅くなるだろう。私は単語の文字列を検索しようとした最初

I Application Did Change Screen Parameters Notification 

：このスクリプトの結果を実行する

import enchant #Spellchecker 
import re 

endict = enchant.Dict("en_US") 

#Test input... 
instr = 'UGxhemEgZGUgaWZXNaWdhZGyOiBDSUWRVNUQVYtSVBOIFVuaWQNSApplicationDidChangeScreenP arametersNotification' 
outstr = '' 

acceptable_short_words = ['a', 'I', 'if', 'is'] #Any one or two letter words you can think of that are OK. 

#Split the words based on capitals. 
words = re.findall('[A-Z][^A-Z]*', instr) 

def isWord(wordin): 
    if(wordin in acceptable_short_words): 
     return True 
    elif(len(wordin) < 3): 
     return False 

    return endict.check(wordin) 

for w in words: 
    if(isWord(w)): 
     outstr += " " + w 

print(outstr.strip()) 

。これは単語内の単語を検出したときに結果が悪かった（例：通知に「Not」、「if」、「cat」、「at」などの単語も含まれています） 私は大文字で分割し、要素を辞書に対して照合する。これはまた、うまくいっていません。一文字の多くが英語の単語であることが証明されています：

ユーモア|英国|非公式：社会階級。 （「Uマナー」）

誰が知っていましたか？

最後に私は知らなかった短い単語を無視することにしました（かなりのことが判明しました）。それを一般的な短い単語に限定しました。 NLTKや同様のツールを使って言葉のペアの周波数を確認することができます。しかし、それは何度もやったことがあります。

Answer 2

まず、ありがとうございました、あなたの質問は私に興味がありました。私は楽しいトレーニングを探していました。私はあなたの記事にコメントで言及したアイデアと@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が提案したように、4つの連続した子音のapperanceをチェックするだけです。

コードのテスト部分では、上記の関数は、strokを構成する単語数で測定される文字列の長さの違いについてテストされます。関数is_rndが2回呼び出されます。最初はstrokで、2番目はランダムな文字列です。文字列をランダムに定義する際のエラーは合計されます。以下の結果は興味深いものでした私にとっては、いくつかの結果

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 

がある

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() 

：

だから、これはコードです。

UPDATE：

私は機械学習を試してみました。私は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)を学びましょう。

Finaly、ニューロンを使用することができます。

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

I上記と同様の試験手順を使用し、以下の結果を得た：

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 

私はそれがいかに簡単に、本当に感動しました実現し、どのように細かい結果を生み出すか。