다른 길이 문자열 파이썬 목록에서 가장 가까운 문자열을 찾는 방법은 무엇입니까?

Question

중히 여기다:

string = 'pizza'
matchings = ['pizzas', 'potato chips', 'cheesy lime', 'pretzels', 'pork']

목록에서 가장 일치하는 항목을 찾을 수있는 좋은 방법을 찾으려고합니다. 나는 다음과 같이 계산하고 있습니다.

matchings_indices = {matching:sum([s == m for s,sdx in enumerate(string)\
                                 for m, mdx in enumerate(matching) if sdx<=mdx])/len(string) 
                     for matching in matchings}
matchings_indices

결과 :

{'pizzas': 1.0,
 'potato chips': 0.6,
 'cheesy lime': 0.2,
 'pretzels': 0.6,
 'pork': 0.4}

간단하지만 충분합니다! 나는 최대 값을 뽑아 낼 수 있고 그것이 일치가 될 것입니다 (명확성을 위해 하나의 일치하는 값, 계산 된 점수 만 필요합니다). 그러나 매우 유사한 문자열이 목록에 나타날 때 정말 힘들어합니다.

string = 'pizza'
matchings = ['pizzas', 'pizza fries', 'cheesy lime', 'pizzo', 'pizza']

이제 내 출력은 다음과 같습니다.

{'pizzas': 1.0,
 'pizza fries': 1.0,
 'cheesy lime': 0.2,
 'pizzo': 1.0,
 'pizza': 1.0}

물론 여기 피자는 최대 지수를 가져야합니다. 나는 그들을 다음과 같이 정렬하려고 시도했다.

matchings_indices = {matching:sum([s == m for s,sdx in enumerate(sorted(string))\
                                 for moose in matching.split() 
                                 for m, mdx in enumerate(sorted(moose)) if sdx==mdx])/len(string) 
                     for matching in matchings}

그러나이 경우 첫 번째 경우에 대한 출력입니다. (아주 유사한 문자열에 대해서는 여전히 충분합니다.)

{'pizzas': 0.8,
 'potato chips': 0.0,
 'cheesy lime': 0.0,
 'pretzels': 0.0,
 'pork': 0.2}

두 번째로 여기에 :

{'pizzas': 0.8,
 'pizza fries': 1.0,
 'cheesy lime': 0.2,
 'pizzo': 0.6,
 'pizza': 1.0}

더 좋지만 여전히. pizzas더 나은 경기이며 pizza fries더 높은 점수를 받아야합니다.

따라서 상황을 개선하는 데 도움이 될 것입니다!

Answer 1

편집 거리 / 레벤 슈타인 거리를 사용하여 살펴볼 수 있습니다. 로부터 위키 백과 페이지 :

Levenshtein 거리는 두 시퀀스 간의 차이를 측정하기위한 문자열 메트릭입니다. 비공식적으로 두 단어 사이의 Levenshtein 거리는 한 단어를 다른 단어로 변경하는 데 필요한 단일 문자 편집 (삽입, 삭제 또는 대체)의 최소 수입니다.

거리를 계산하는 이 답변 을 찾은 다음이 거리를 1에서 빼서 최대 점수를 최고로 만들 수 있습니다.

# from https://stackoverflow.com/a/32558749/6386471
def levenshteinDistance(s1, s2):
    if len(s1) > len(s2):
        s1, s2 = s2, s1

    distances = range(len(s1) + 1)
    for i2, c2 in enumerate(s2):
        distances_ = [i2+1]
        for i1, c1 in enumerate(s1):
            if c1 == c2:
                distances_.append(distances[i1])
            else:
                distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1])))
        distances = distances_
    return distances[-1]

string = 'pizza'
matchings = ['pizzas', 'pizza fries', 'cheesy lime', 'pizzo', 'pizza']

scores = {}

for m in matchings:
    scores[m] = 1 - levenshteinDistance(string,m)

scores

>>> {'pizzas': 0, 'pizza fries': -5, 'cheesy lime': -10, 'pizzo': 0, 'pizza': 1}

import operator
max(scores.items(), key=operator.itemgetter(1))[0]

>>> 'pizza'