Znajdowanie jak podobne są dwa ciągi

Szukam algorytmu, który pobiera 2 ciągi i da mi "współczynnik podobieństwa".

Zasadniczo, będę miał Dane wejściowe, które mogą być błędnie napisane, mają litery transponowane, itp, i muszę znaleźć najbliższy mecz(y) na liście możliwych wartości, które mam.

To nie jest do wyszukiwania w bazie danych. Będę miał w pamięci listę 500 lub tak ciągów do dopasowania, wszystkie poniżej 30 znaków, więc może być stosunkowo wolny.

Wiem, że to istnieje, widziałem wcześniej, ale nie pamiętam jego nazwy.

Edit: dzięki za wskazanie Levenshteina i Hamminga. Który mam wdrożyć? Zasadniczo mierzą różne rzeczy, z których oba mogą być używane do tego, co chcę, ale nie jestem pewien, który z nich jest bardziej odpowiedni.

Czytałem o algorytmach, Hamming wydaje się oczywiście szybszy. Ponieważ żaden z nich nie wykryje dwóch transponowanych znaków(tj. Jordan i Jodran), co moim zdaniem będzie częstym błędem, który będzie dokładniejsze do tego, czego chcę? Czy ktoś może mi powiedzieć coś o kompromisach?

Author: Nick Fortescue, 2009-02-23
Source

4 answers

Ok, więc standardowe algorytmy to:

1) Odległość Hamminga Tylko dobre dla strun tej samej długości, ale bardzo wydajne. Zasadniczo po prostu liczy liczbę różnych znaków. Nieprzydatne do rozmytego przeszukiwania tekstu w języku naturalnym.

2) odległość Levensteina . Odległość Levensteina mierzy odległość pod względem liczby "operacji" wymaganych do przekształcenia jednego ciągu w drugi. Operacje te obejmują wstawianie, usuwanie i zastępstwo. Standardowym podejściem do obliczania odległości Levensteina jest zastosowanie programowania dynamicznego.

3) uogólniony levenstein / (odległość Damerau–Levenshtein) Odległość ta uwzględnia również transpozycje znaków w słowie i jest prawdopodobnie najbardziej odpowiednią odległością edycji dla rozmytego dopasowywania ręcznie wprowadzanego tekstu. Algorytm obliczania odległości jest nieco bardziej zaangażowany niż odległość Levensteina (wykrywanie transpozycji nie jest łatwe). Najbardziej typowe implementacje są modyfikacją algorytmu bitap (podobnie jak grep).

Ogólnie rzecz biorąc, prawdopodobnie chciałbyś rozważyć implementację trzeciej opcji zaimplementowanej w jakimś wyszukiwaniu najbliższych sąsiadów w oparciu o drzewo k-d

 34
Author: Il-Bhima,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-02-23 13:16:34
  • Odległość Levensteina
  • Odległość Hamminga
  • soundex
  • metafona
 3
Author: vartec,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-02-23 12:25:49

Odległość Damerau-Levenshteina {[2] } jest podobna do odległości Levenshteina, ale zawiera również transpozycję dwuznakową. strona Wikipedii (podlinkowana) zawiera pseudokod, który powinien być dość trywialny do wdrożenia.

 3
Author: Autoplectic,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-02-23 12:55:57
 2
Author: tehvan,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-02-23 12:23:00