실제로 랜덤 한 문자열을 일치시키는 방법은 무엇입니까?

Question

필자가 쓰고있는 파이썬 애플리케이션은 소스 코드에서 식별자와 텍스트 문자열을 추출해야한다. 발견 한 것의 작은 비율은 (겉으로보기에) 임의의 문자열입니다. 나는 그들을 필터링하고 싶습니다만, 지금까지 그것을하기 위해 정규 표현식을 만들 수 없었습니다. 매우 긴 식별자가 유효하기 때문에 길이로만 필터하는 것은 불가능합니다.

UGxhemEgZGUgaWZXNaWdhZGyOiBDSUWRVNUQVYtSVBOIFVuaWQ 
NSApplicationDidChangeScreenParametersNotification 

같이 정크 서열을 검출 유용한 정규식 또는 다른 감지 시스템을 작성하는 방법이된다 다음 예는 동일한 길이의 유효한 식별자에 비해 랜덤 촬영? 나는 많은 단어 사전에 대해 문자열을 테스트하지 않고는 오류를 일으키지 않을뿐만 아니라 계산 집약적 일 수밖에 없다고 생각하기 시작했습니다. 어쩌면이 같은 무작위 순서를 탐지하거나 일치시키는 접근법을 더 똑똑히 알고있는 사람이 있을까요?

이 문제에 대한 이상적인 솔루션은 문자열을 입력으로 사용하고 "아마"무작위 인 경우보고 할 수있는 기능입니다. 거짓 가청을 생성 할 수 있으며 (임의의 문자열을 임의로 잘못보고하지 않음) 바람직하지는 않지만 가능성이 낮습니다. 그러나 가양 성을보고하지 않아야합니다. 문제가되는 경우 문자열의 길이는 25에서 80 자까지입니다.

EDIT # 1 2017-02-08 : 생각해 보면 가능한 접근법은 행의 최소 고유 문자 수와 일치하는 정규 표현식 일 수 있습니다. 예를 들어, 두 번째 문자는 첫 번째 문자와 다른 문자 여야합니다. 앞의 두 문자와 다른 문자가 있어야하고, 이전 문자와 다른 문자가 있어야합니다. 그러나 다른 regexp 연산자를 보면 "부정적인 역 참조"또는 "일치하는 것보다 기타과 일치하는"(더 나은 단어가 부족한 경우) 버전이 표시되지 않습니다. 누군가가 이것에 변이를 알고있는 경우에, 어쩌면 나는 그것을 일하게 할 수있다.

편집 # 1 2017-02-10 : 두 개의 예제 문자열을 작성한 방법이 단일 문자열로 잘못 해석 될 수 있습니다. 위의 예는 동일한 길이의 두 개의 분리 된 문자열 – 그것이 불분명 한 경우 진심으로 사과합니다. 여기에 몇 가지 예가 있습니다. 각 행은 별도의 식별자입니다. 이것은 또한 목적에 따라 길이가 다름을 보여줍니다. 그것은 가치가 무엇이든 들어

shouldBeAbleToCountLiveNeighboursOfACellOnDiagonalsAndStraightLines 
eXNZWzIGbHRpbWVkaWEgYWkIGFuaWhdGlvbiBkaXNcmlidXRlZCNCpUgRGlzdHJpYnV 
dWxLXRvbGVyYWIHJlYWwtdGltZSBzeXNZWzLgKlSBEaXNcmlidXRlZCBBcmNoaXRlYR 
dGhIExvIHNYmltbMgYSBsYSBwWdpbmEgeSBsbyBhbnVuYlhbWzIGVuIGVsIHByhpbWg 
aGUgYuZmVyZWjZSBwcmjZWVkaWncygDQoNClNYmpcNpbNCkluIGyZGVyIHRvIHN 
YQKUGFyYTogZXNYFyQGluYWlcCteAKQMIExaXMgQSgUGluZWRhDQpDQzogQuYVw 
thehasSizeMatcherShouldMatchACollectionWithExpectedSize 
QycmVvIGRlIERpcVtaWhYnDsgZGUgYWNaXZpZGFkZXMgZGUgbGEg 
NSAppleEventManagerWillProcessFirstEventNotification 
SNMTransformGizmoRotationControllerPerformTransform 
RndkOiBEaWZcnDsgZGUgYudmjYXRvcmlhIFNVTUJVCBlbiBSRUJ 

, 나는 약 900 GitHub의 저장소의 반 임의 선택에서 내 응용 프로그램에 의해 끌려 페이스트 빈 a list of the 1000 longest identifiers 입었다. 실제 식별자와 임의 문자열을 모두 포함합니다.

Answer 1

Markov Chains에 의존하는 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'등의 단어가 포함되어 있음) 그래서 대문자로 나누기로하고 요소에 대한 사전. 한 글자의 많은 단어가 영어로 된 단어로 판명됨에 따라 이것도 잘 작동하지 않습니다. :

어 - 형용사 (영국식 또는 비공식적 인) 사회 계급. ("유행")

누가 알았습니까?

그래서 마침내 내가 알지 못하는 짧은 단어를 무시하기로 결정했다. 그리고 그 단어를 일반적인 짧은 단어로 제한했다. NLTK 또는 유사한 도구를 사용하여 횡설수설 탐지기와 비슷한 방법으로 단어 쌍 주파수를 더 확인하고 확인할 수 있습니다. 그러나 오히려 그렇게 많이하지는 않았을 것입니다.

Answer 2

우선, 고맙습니다. 질문에 관심이 많았습니다. 재미있는 훈련을 찾고있었습니다. 아래에서는 @ swbandit에 대한 아이디어뿐만 아니라 게시물에 대한 의견에서 언급 한 아이디어를 구현했습니다. 또한 is_rnd 기능을 수정하여 코드에 다른 전술을 추가 할 수도 있습니다. 여기에있는 짧은 사전 (https://gist.github.com/jbergantine/2390284)에서 의식 문자열을 생성했습니다 (물론이 사전은 작기 때문에 대표적인 것은 아니지만 테스트 목적으로 사용했습니다). 이 문자열은 코드에서 strok으로 표시됩니다. 그 후 동일한 길이의 임의 문자열 (strrnd)이 생성되었습니다. 소문자 만 사용하고 문자열에 공백이 없다고 가정합니다.

함수 is_rnd1 및 is_rnd2 문자열이 임의 인 경우 을 반환합니다. 기능 is_rnd1은 가장 빈번한 영어 문자 'e'(12.7 %)와 가장 드문 'z'(0.074 %)의 빈도를 확인합니다. 그러나 함수에서 주파수의 경계가 크게 확장됩니다. 기능 is_rnd2은 @swbandit에서 제안한대로 4 개의 연속적인 자음의 apperance를 확인합니다.

코드의 테스트 부분에서 위에서 설명한 함수는 strok을 구성하는 단어의 수로 측정 된 문자열의 길이가 다른지 테스트됩니다. 기능 is_rnd이 두 번 호출됩니다. 처음에는 strok이고 두 번째는 임의의 문자열입니다. 임의의 문자열을 정의 할 때의 오류가 합산됩니다. 아래 결과는 흥미 있었다 나를 위해 어떤 결과

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

:

그래서이 코드입니다.

업데이트 :

나는 기계 학습을 시도했습니다. 나는 26 개의 입구와 1 개의 뉴런을 사용했다. 출입구에는 문자열의 문자 빈도가 제공됩니다.캐릭터 라인이 random 인 경우는 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) 알아 보자.

마침내는 신경 세포를 사용할 수 있습니다

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 

나는 그것이 얼마나 쉽게 정말 감동했다 : 나는 다음과 같은 결과를 얻었다 위

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

설명과 동일한 시험 절차를 사용하여 실현하고 얼마나 훌륭한 결과를 만들어 내는지.