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

Question

Mam przypadek użycia, w którym muszę wykonać dopasowanie rozmyte milionów rekordów z wielu plików. Zidentyfikowaliśmy dwa algorytmy: Jaro-Winkler i Edycja dystansu Levenshtein.

Kiedy zacząłem badać obie, nie byłem w stanie zrozumieć, jaka jest dokładna różnica między tymi dwoma. Wygląda na to, że Levenshtein podaje liczbę zmian między dwoma strunami, a Jaro-Winkler daje wynik dopasowania od 0,0 do 1,0. Nie rozumiem algorytmu. Ponieważ muszę użyć dowolnego algorytmu, muszę znać dokładne różnice w odniesieniu do wydajności algorytmu.

Answer 1

Levenshtein zlicza liczbę zmian (wstawień, usunięć lub substytucji) potrzebnych do przekonwertowania jednego ciągu znaków na inny. Damerau-Levenshtein jest zmodyfikowaną wersją, która również uważa transpozycje za pojedyncze edycje. Chociaż wyjściowy jest liczbą całkowitą od edycji, może być znormalizowany w celu uzyskania wartości podobieństwa wzorem

1 - (edit distance/length of the larger of the two strings) 

Algorytm Jaro jest miarą cech wspólnych, jest nie więcej niż połowa długości dłuższego sznur w odległości, z uwzględnieniem transpozycji. Winkler zmodyfikował ten algorytm, aby potwierdzić, że różnice w pobliżu początku ciągu są bardziej znaczące niż różnice pod koniec łańcucha. Jaro i Jaro-Winkler nadają się do porównywania mniejszych ciągów, takich jak słowa i nazwy.

Decyzja, który z nich należy używać, to nie tylko kwestia wydajności. Ważne jest, aby wybrać metodę dopasowaną do charakteru porównywanych ciągów. Ogólnie rzecz biorąc, oba algorytmy, o których wspomniałeś, mogą być drogie, ponieważ każdy ciąg musi być porównywany z każdym innym łańcuchem, 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 obliczanie fonetycznego kodowania dla każdego ciągu, a następnie proste grupowanie ciągów dzielących identyczne kodowania.

Istnieje wiele szczegółowych informacji na temat tych algorytmów i innych algorytmów dopasowywania ciągów rozmytych w Internecie. Ten daje start:

A Comparison of Personal Name Matching: Techniques and Practical Issues

Według tego papieru, szybkość czterech Jaro i Levenshteina algorytmów mam wymienić od najszybszego do najwolniejszego:

• Jaro
• Jaro-Winkler
• Levenshteina
• Damerau-Levenshteina

z najwolniejszymi od 2 do 3 razy dłuższymi od najszybszych. Oczywiście czasy te 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.