Wie finde ich die engste Übereinstimmung eines Strings aus einer Liste von Python-Strings unterschiedlicher Länge?

Question

Erwägen:

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

Ich versuche einen guten Weg zu finden, um die beste Übereinstimmung in der Liste zu finden. mit dem ich rechne mit:

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

Was in ... endet:

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

Einfach aber gut genug! Ich kann den Maximalwert herauszupfen und das ist die Übereinstimmung (ich benötige nur einen Übereinstimmungswert, berechnete Punktzahlen zur Klarheit). Aber es hat wirklich Probleme, wenn sehr ähnliche Zeichenfolgen in der Liste erscheinen:

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

Jetzt wird meine Ausgabe:

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

Natürlich sollte Pizza hier einen maximalen Index haben. Ich habe versucht, sie auch zu sortieren wie:

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}

In diesem Fall ist dies jedoch die Ausgabe für den ersten Fall: (Immer noch gut genug für sehr unterschiedliche Zeichenfolgen)

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

und hier zum zweiten:

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

Welches ist besser aber immer noch. pizzasist ein besseres Spiel als pizza friesund sollte höher bewertet werden.

Jede Hilfe zur Verbesserung der Situation wird also großartig sein!

Answer 1

Sie können einen Blick auf die Bearbeitungsentfernung / Levenshtein-Entfernung werfen. Von der Wikipedia-Seite :

Der Levenshtein-Abstand ist eine String-Metrik zum Messen der Differenz zwischen zwei Sequenzen. Informell ist der Levenshtein-Abstand zwischen zwei Wörtern die Mindestanzahl von Einzelzeichenbearbeitungen (Einfügungen, Löschungen oder Ersetzungen), die erforderlich sind, um ein Wort in das andere zu ändern.

Ich habe diese Antwort gefunden , die die Entfernung berechnet, und dann können Sie diese Entfernung von 1 subtrahieren, um Ihre maximale Punktzahl zur besten zu machen:

# 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'