Comment trouver la correspondance la plus proche d'une chaîne à partir d'une liste de chaînes de différentes longueurs python?

Question

Considérer:

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

J'essaie de trouver un bon moyen de trouver le meilleur match dans la liste. que je calcule avec:

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

Ce qui se traduit par:

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

Simple mais assez bon! Je peux retirer la valeur maximale et ce sera le match (je n'ai besoin que d'une valeur correspondante, des scores calculés pour plus de clarté). Mais cela a vraiment du mal lorsque des chaînes très similaires apparaissent dans la liste:

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

Maintenant, ma sortie devient:

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

Bien sûr, ici, la pizza doit avoir un indice maximum. J'ai aussi essayé de les trier comme:

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}

Mais dans ce cas, c'est la sortie pour le premier cas: (Toujours assez bon pour des chaînes très différentes)

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

et ici pour la seconde:

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

Ce qui est mieux mais quand même. pizzasest un meilleur match que pizza frieset devrait être noté plus haut.

Donc, toute aide pour améliorer la situation sera formidable!

Answer 1

Vous pouvez jeter un oeil à l'utilisation de la distance d'édition / distance levenshtein. Depuis la page Wikipédia :

la distance de Levenshtein est une métrique de chaîne pour mesurer la différence entre deux séquences. De manière informelle, la distance de Levenshtein entre deux mots est le nombre minimum de modifications d'un seul caractère (insertions, suppressions ou substitutions) nécessaires pour changer un mot dans l'autre.

J'ai trouvé cette réponse qui calcule la distance, puis vous pouvez soustraire cette distance de 1 pour que votre score maximum soit le meilleur:

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