파이썬 목록에서 불연속 문자를 검색하는 방법은 무엇입니까?

Question

텍스트 조각과 일치하는 항목을 목록 (DB)으로 검색하려고합니다. 예를 들어, 텍스트 "악마"가있는 DB가 있습니다. 나는 사용자 입력을 사용하여 DB에서 가능한 모든 일치 항목을 검색하고 자신감을 가지고 답변을 제공하려고합니다. 사용자가 "hello"를 입력하면 가능한 일치 항목이 없습니다. 사용자가 "악마"를 입력하면 가능한 일치는 57 %의 신뢰도 (7 자의 알파벳 중 4 개)와 같은 악마입니다.

그러나 "evxxman"과 같은 입력 텍스트를 일치시키는 방법을 원합니다. evxxman의 7 문자 중 5 문자가 DB의 "evilman"텍스트와 일치합니다. 그러나 파이썬에서의 간단한 검사는 연속적으로 일치하는 텍스트 만 출력하기 때문에 일치하지 않는다고 말할 수 있습니다. 나는 그것이 의미가 있기를 바랍니다.

에 따라 감사

내 코드입니다 : 품질 추정과 일치를 찾는

db = [] 
possible_signs = [] 
db.append("evilman") 

text = raw_input() 

for s in db: 
if text in s: 
    if len(text) >= len(s)/2:        
    possible_signs.append(s) 

    count += 1 
    confidence = (float(len(text))/float(len(s))) * 100 
    print "Confidence:", '%.2f' %(confidence), "<possible match:>", possible_signs[0] 

Answer 1

이 첫 번째 버전은 사용자의 요구 사항을 준수하는 것 같습니다. 문자열을 서로 "슬라이드"시키며 동일한 문자의 수를 계산합니다. 비율은 문자 수를 참조 문자열 길이로 나눈 값입니다. 최대량과 최대량을 추가하십시오. DB의 각 문자열에 대해 호출하십시오.

def commonChars(txt, ref): 
    txtLen = len(txt) 
    refLen = len(ref) 
    r = 0 
    for i in range(refLen + (txtLen - 1)): 
     rStart = abs(min(0, txtLen - i - 1)) 
     tStart = txtLen -i - 1 if i < txtLen else 0 
     l = min(txtLen - tStart, refLen - rStart) 
     c = 0 
     for j in range(l): 
      if txt[tStart + j] == ref[rStart + j]: 
       c += 1 
     r = max(r, c/refLen) 
    return r 

print(commonChars('evxxman', 'evilman')) # 0.7142857142857143 
print(commonChars('evil', 'evilman')) # 0.5714285714285714 
print(commonChars('man', 'evilman')) # 0.42857142857142855 
print(commonChars('batman', 'evilman')) # 0.42857142857142855 
print(commonChars('batman', 'man')) # 1.0 

이 두 번째 버전은 다른 결과에서 언급 한 difflib를 사용하여 동일한 결과를 산출합니다. 일치하는 블록을 계산하고, 길이를 합산하고, 참조 길이에 대한 비율을 계산합니다.

import difflib 

def commonBlocks(txt, ref): 
    matcher = difflib.SequenceMatcher(a=txt, b=ref) 
    matchingBlocks = matcher.get_matching_blocks() 
    matchingCount = sum([b.size for b in matchingBlocks]) 
    return matchingCount/len(ref) 

print(commonBlocks('evxxman', 'evilman')) # 0.7142857142857143 
print(commonBlocks('evxxxxman', 'evilman')) # 0.7142857142857143 

위의 호출에 표시된 것과 같이 동작이 약간 다릅니다. 일치하는 블록 사이의 "구멍"은 무시되며 최종 비율은 변경되지 않습니다.

Answer 2

, difflib.SequenceMatcher.ratio 친구를 보라 -이 기능은 빠른 경기 체커하지 않을 수 있지만 쉽게 사용할 수 있습니다 .

예 귀하의 설명과 예제를 바탕으로 difflib 문서

>>> s = SequenceMatcher(None, "abcd", "bcde") 
>>> s.ratio() 
0.75 
>>> s.quick_ratio() 
0.75 
>>> s.real_quick_ratio() 
1.0 

Answer 3

에서 복사, 당신이 실제로 Levenshtein (or edit) distance 같은 뭔가를 찾고 있다는 것을 나에게 보인다. 그것은 당신이 지정한 점수를 제공하지는 않지만, 실제로 당신이 원하는 점수를 줄 것이라고 생각합니다.

는 distance 예를 효율적으로이를 구현하는 여러 가지 패키지가 있습니다

>>> distance.sorensen("decide", "resize") 
0.5555555555555556 
>>> distance.jaccard("decide", "resize") 
0.7142857142857143 

: 라이브러리가 유사성의 몇 가지 조치를 포함

In [1]: import distance 

In [2]: distance.levenshtein('evilman', 'hello') 
Out[2]: 6L 

In [3]: distance.levenshtein('evilman', 'evil') 
Out[3]: 3L 

In [4]: distance.levenshtein('evilman', 'evxxman') 
Out[4]: 2L 

참고, 예를 들면, 인 Jaccard와 소렌슨은 기본적 당 정규화 된 값을 반환

Answer 4

while 루프를 만들고 키워드 ("evil")와 쿼리 단어 ("evilman")에 대한 두 개의 반복기를 추적합니다. 다음은 몇 가지 의사 코드입니다.

key = "evil" 
query = "evilman" 
key_iterator = 0 
query_iterator = 0 
confidence_score = 0 

while(key_iterator < key.length && query_iterator < query.length) { 
    if (key[key_iterator] == query[query_iterator]) { 
     confidence_score++ 
     key_iterator++ 
    } 
    query_iterator++ 
} 

// If we didnt reach the end of the key 
if (key_iterator != key.length) { 
    confidence_score = 0 
} 
print ("Confidence: " + confidence_score + " out of " + query.length)