Levenshtein liczy liczbę zmian (wstawienia, usunięcia lub podstawienia) potrzebnych do konwersji jednego ciągu na drugi. Damerau-Levenshtein to zmodyfikowana wersja, która również traktuje transpozycje jako pojedyncze edycje. Chociaż wynikiem jest całkowita liczba zmian, można ją znormalizować, aby uzyskać wartość podobieństwa według wzoru
1 - (edit distance / length of the larger of the two strings)
Algorytm Jaro jest miarą wspólnych znaków, stanowiąc nie więcej niż połowę długości dłuższego ciągu w odległości, z uwzględnieniem transpozycji. Winkler zmodyfikował ten algorytm, aby wspierać ideę, że różnice w pobliżu początku ciągu są bardziej znaczące niż różnice w pobliżu końca łańcucha. Jaro i Jaro-Winkler nadają się do porównywania mniejszych ciągów, takich jak słowa i nazwy.
Decyzja, którego użyć, to nie tylko kwestia wydajności. Ważne jest, aby wybrać metodę dostosowaną do charakteru porównywanych strun. Ogólnie rzecz biorąc, oba wspomniane algorytmy mogą być drogie, ponieważ każdy ciąg musi być porównany z każdym innym ciągiem, a przy milionach ciągów w zestawie danych jest to ogromna liczba porównań. Jest to o wiele droższe niż coś takiego, jak obliczenie kodowania fonetycznego dla każdego ciągu, a następnie po prostu grupowanie ciągów o identycznym kodowaniu.
W Internecie jest mnóstwo szczegółowych informacji na temat tych algorytmów i innych algorytmów dopasowywania rozmytych ciągów znaków. Ten da ci początek:
Porównanie dopasowywania nazwisk: techniki i zagadnienia praktyczne
Zgodnie z tym artykułem, prędkość czterech algorytmów Jaro i Levenshteina, o których wspomniałem, jest od najszybszej do najwolniejszej:
- Jaro
- Jaro-Winkler
- Levenshtein
- Damerau-Levenshtein
najwolniejszy trwa od 2 do 3 razy dłużej niż najszybszy. Oczywiście te czasy zależą od długości łańcuchów i implementacji, i istnieją sposoby optymalizacji tych algorytmów, które mogły nie zostać użyte.