Różnica między odległością Jaro-Winklera i Levenshteina? [Zamknięte]

Mam przypadek użycia, w którym muszę przeprowadzić rozmyte dopasowywanie milionów rekordów z wielu plików. Zidentyfikowałem dwa algorytmy do tego: Jaro-Winkler i odległość edycji Levenshteina .

Kiedy zacząłem badać oba, nie byłem w stanie zrozumieć, jaka jest dokładna różnica między nimi. Wygląda na to, że Levenshtein podaje liczbę edycji między dwoma ciągami, a Jaro-Winkler zapewnia znormalizowany wynik od 0,0 do 1,0. Nie rozumiem algorytmu.

Ponieważ muszę użyć dowolnego algorytmu, muszę wiedzieć, jakie są podstawowe różnice między tymi dwoma algorytmami.

Po drugie, chciałbym wiedzieć o różnicy w wydajności między tymi dwoma algorytmami.

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.