Jak obliczyć odległość levenshteina w pythonie

Odległość Levenshteina między dwoma ciągami znaków to minimalna liczba zmian pojedynczych znaków wymaganych do przekształcenia jednego słowa w drugie.

Słowo „modyfikacje” obejmuje podstawienia, insercje i skreślenia.

Załóżmy na przykład, że mamy następujące dwa słowa:

• IMPREZOWAĆ
• PARK

Odległość Levenshteina między dwoma słowami (tj. liczba zmian, które musimy wprowadzić, aby przekształcić jedno słowo w drugie) wyniosłaby 2 :

W praktyce odległość Levenshteina jest wykorzystywana w wielu różnych zastosowaniach, w tym w dopasowywaniu ciągów rozmytych, sprawdzaniu pisowni i przetwarzaniu języka naturalnego.

W tym samouczku wyjaśniono, jak obliczyć odległość Levenshteina między ciągami znaków w Pythonie za pomocą modułu Pythona-Levenshteina.

Aby zainstalować ten moduł, możesz użyć następującej składni:

 pip install python-Levenshtein

Następnie możesz załadować funkcję obliczającą odległość Levenshteina:

 from Levenshtein import distance as lev

Poniższe przykłady pokazują, jak w praktyce wykorzystać tę funkcję.

Przykład 1: Odległość Levenshteina pomiędzy dwiema strunami

Poniższy kod pokazuje, jak obliczyć odległość Levenshteina między dwoma ciągami „impreza” i „park”:

 #calculate Levenshtein distance
lev(' party ', ' park ')

2

Okazuje się, że odległość Levenshteina wynosi 2 .

Przykład 2: Odległość Levenshteina między dwoma stołami

Poniższy kod pokazuje, jak obliczyć odległość Levenshteina pomiędzy każdą kombinacją parami ciągów w dwóch różnych tablicach:

 #define arrays
a = ['Mavs', 'Spurs', 'Lakers', 'Cavs']
b <- ['Rockets', 'Pacers', 'Warriors', 'Celtics']

#calculate Levenshtein distance between two arrays
for i,k in zip (a,b):
  print (lev(i, k))

6
4
5
5

Sposób interpretacji wyniku jest następujący:

• Odległość Levenshteina pomiędzy „Mavami” i „Rakietami” wynosi 6 .
• Odległość Levenshteina pomiędzy „Spurs” i „Pacers” wynosi 4 .
• Odległość Levenshteina pomiędzy „Lakerami” a „Wojownikami” wynosi 5 .
• Odległość Levenshteina pomiędzy „Cavs” i „Celtics” wynosi 5 .

Dodatkowe zasoby

Jak obliczyć odległość Hamminga w Pythonie
Jak obliczyć odległość euklidesową w Pythonie
Jak obliczyć odległość Mahalanobisa w Pythonie