Hoe de levenshtein-afstand in python te berekenen

De Levenshtein-afstand tussen twee strings is het minimum aantal wijzigingen van één teken dat nodig is om het ene woord in het andere te transformeren.

Het woord ‘wijzigingen’ omvat vervangingen, invoegingen en verwijderingen.

Stel dat we bijvoorbeeld de volgende twee woorden hebben:

• FEESTEN
• PARK

De Levenshtein-afstand tussen de twee woorden (dwz het aantal wijzigingen dat we moeten aanbrengen om het ene woord in het andere te transformeren) zou 2 zijn:

In de praktijk wordt Levenshtein-afstand in veel verschillende toepassingen gebruikt, waaronder fuzzy string matching, spellingcontrole en natuurlijke taalverwerking.

In deze tutorial wordt uitgelegd hoe u de Levenshtein-afstand tussen strings in Python kunt berekenen met behulp van de Python-Levenshtein-module.

U kunt de volgende syntaxis gebruiken om deze module te installeren:

 pip install python-Levenshtein

Vervolgens kunt u de functie laden om de Levenshtein-afstand te berekenen:

 from Levenshtein import distance as lev

De volgende voorbeelden laten zien hoe u deze functie in de praktijk kunt gebruiken.

Voorbeeld 1: Levenshtein-afstand tussen twee snaren

De volgende code laat zien hoe je de Levenshtein-afstand tussen de twee strings “party” en “park” berekent:

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

2

De Levenshtein-afstand blijkt 2 te zijn.

Voorbeeld 2: Levenshtein-afstand tussen twee tafels

De volgende code laat zien hoe je de Levenshtein-afstand berekent tussen elke paarsgewijze combinatie van strings in twee verschillende arrays:

 #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

De manier om het resultaat te interpreteren is als volgt:

• De Levenshtein-afstand tussen “Mavs” en “Rockets” is 6 .
• De Levenshtein-afstand tussen de “Spurs” en de “Pacers” is 4 .
• De Levenshtein-afstand tussen de “Lakers” en de “Warriors” is 5 .
• De Levenshtein-afstand tussen “Cavs” en “Celtics” is 5 .

Aanvullende bronnen

Hoe Hamming-afstand in Python te berekenen
Hoe de Euclidische afstand in Python te berekenen
Hoe Mahalanobis-afstand in Python te berekenen