Jak znaleźć najbliższe dopasowanie ciągu z listy różnych długości ciągów Python?
Rozważać:
string = 'pizza'
matchings = ['pizzas', 'potato chips', 'cheesy lime', 'pretzels', 'pork']
Próbuję znaleźć dobry sposób na znalezienie najlepszego dopasowania na liście. którym obliczam:
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
Co skutkuje w:
{'pizzas': 1.0,
'potato chips': 0.6,
'cheesy lime': 0.2,
'pretzels': 0.6,
'pork': 0.4}
Proste, ale wystarczająco dobre! Mogę wyciągnąć maksymalną wartość i to będzie dopasowanie (potrzebuję tylko jednej pasującej wartości, obliczone wyniki dla jasności). Ale to naprawdę trudne, gdy na liście pojawiają się bardzo podobne struny:
string = 'pizza'
matchings = ['pizzas', 'pizza fries', 'cheesy lime', 'pizzo', 'pizza']
Teraz mój wynik to:
{'pizzas': 1.0,
'pizza fries': 1.0,
'cheesy lime': 0.2,
'pizzo': 1.0,
'pizza': 1.0}
Oczywiście pizza powinna mieć maksymalny indeks. Próbowałem je również posortować jak:
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}
Ale w tym przypadku jest to wynik dla pierwszego przypadku: (Nadal wystarczająco dobre dla bardzo odmiennych ciągów)
{'pizzas': 0.8,
'potato chips': 0.0,
'cheesy lime': 0.0,
'pretzels': 0.0,
'pork': 0.2}
a tu na sekundę:
{'pizzas': 0.8,
'pizza fries': 1.0,
'cheesy lime': 0.2,
'pizzo': 0.6,
'pizza': 1.0}
Co jest lepsze, ale nadal. pizzas
jest lepszym dopasowaniem niż pizza fries
i powinien być wyższy.
Więc każda pomoc w poprawie sytuacji będzie świetna!
Odpowiedzi
Możesz rzucić okiem na użycie odległości edycji / odległości Levenshteina. Ze strony Wikipedii :
odległość Levenshteina jest metryką łańcuchową służącą do pomiaru różnicy między dwoma sekwencjami. Nieformalnie odległość Levenshteina między dwoma słowami to minimalna liczba jednoznakowych edycji (wstawień, skreśleń lub podstawień) wymaganych do zamiany jednego słowa na drugie.
Znalazłem tę odpowiedź, która oblicza odległość, a następnie możesz odjąć tę odległość od 1, aby uzyskać najlepszy wynik:
# 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'