異なる長さの文字列pythonのリストから文字列の最も近い一致を見つける方法は?

Nov 20 2020

考えてみましょう:

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}

シンプルですが十分です!最大値を引き出すことができ、それが一致になります(1つの一致値、明確にするために計算されたスコアのみが必要です)。しかし、非常によく似た文字列がリストに表示されると、本当に苦労します。

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}

そしてここで2番目:

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

どちらが良いですが、それでも。pizzasはより良い一致でpizza friesあり、より高いスコアを付ける必要があります。

したがって、状況を改善するための助けは素晴らしいでしょう!

回答

1 user6386471 Nov 20 2020 at 15:43

編集距離/レーベンシュタイン距離の使用を確認できます。ウィキペディアのページから:

レーベンシュタイン距離は、2つのシーケンス間の差を測定するための文字列メトリックです。非公式には、2つの単語間のレーベンシュタイン距離は、1つの単語を別の単語に変更するために必要な1文字の編集(挿入、削除、または置換)の最小数です。

私は距離を計算するこの答えを見つけました、そしてあなたはあなたの最大スコアを最高にするために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'