Dopasuj dwa ciągi, ale dopuszczaj pewien stopień błędu

Jak mogę dopasować dwa ciągi, ale jednocześnie pozwolić, aby X znaków było niepoprawnych w dopasowaniu. Liczba błędów powinna być zmienną kontrolowaną.

Chociaż liczba znaków X nie może się zgadzać w ciągu, powinien istnieć limit liczby uruchomionych sekwencji. Biorąc pod uwagę dwa ciągi znaków, mogę pozwolić, aby 5 znaków różniło się, ale nie więcej niż 2 z rzędu.

Szukam zalecanego algorytmu do porównywania tych dwóch ciągów, a może istnieje już znane rozwiązanie tego problemu.

Przybliżonym punktem początkowym wyszukiwania ciągu jest odległość Levenshteina . Ten algorytm zlicza liczbę edycji pojedynczych znaków (wstawianie, usuwanie i podstawianie) w celu zmiany jednego słowa na inne.

Przykładem tego jest kitten->, sittingktórego odległość edycji wynosi trzy

1. k itten -> s itten (zamień „s” na „k”)
2. sitt e n -> sitt i n ( zamień „i” na „e”)
3. sittin -> sittin g (dodaj „g” na końcu)

Istnieją różne warianty tego algorytmu, w szczególności odległość Damerau – Levenshteina, która pozwala na transpozycję dwóch sąsiednich znaków („hte” na „the” ma odległość DL 1 i odległość Levenshteina 2) i dlatego często jest bardziej odpowiednia dla sprawdzanie pisowni. Istnieją inne warianty dla aplikacji, w których luki są ważne (łańcuchy DNA).

Odległość Levenshteina jest dobrze znana i nie jest zbyt trudna do znalezienia (kiedyś miałem okazję znaleźć jej implementację jako funkcję w wyroczni - było to znacznie szybsze niż ściąganie wszystkich danych, a następnie uruchamianie strony kodu zapytania). Rosettacode ma wiele (54) implementacji odległości Levenshteina (zwróć uwagę, że niektóre języki mają to gdzieś jako część biblioteki ciągów - jeśli używasz Javy, spójrz na język apache commons lang ). Wikibooks ma 31 implementacji, a pobieżne spojrzenie na te dwa nie pokazuje tego samego kodu dla tego samego języka.

Działa to w ten sposób, że tworzy macierz, która odpowiada relacji między dwoma łańcuchami:

 .kitten
.0123456
s1123456
i2212345
t3321234
t4432123
i5543223
n6654332
g7765443

.Wiersz i kolumna reprezentują, które mogą dostać się do łańcucha docelowego przez „tylko” wkładając każdą literę z pustym ciągiem. To nie jest idealny przypadek, ale służy on do zaszczepienia algorytmu.

Jeśli wartość jest taka sama jak w miejscu („i” == „i”), wartość jest taka sama jak wartość po przekątnej w lewo. Jeśli dwa punkty są odmienne ('s'! = 'K'), wartość wynosi minimum:

• przekątna w górę iw lewo + 1 (zmiana)
• bezpośrednio powyżej + 1 (wstawka)
• bezpośrednio w lewo + 1 (usunięcie)

Wartość powrotu odległości edycji jest wartością w prawym dolnym rogu matrycy.

Jeśli wykonasz minimum od prawego dolnego rogu do lewego górnego, zobaczysz wykonane zmiany:

 .kitten
.0.   .
s.1   .
i  1  .
t   1 .
t    1.
i.....2
n      2
g......3

Zauważ, że jest to podejście wymagające dużej ilości pamięci. Można zmniejszyć zakres pamięci, nie budując pełnej macierzy - cały algorytm, o który się troszczy, to podzbiór danych i można go zmniejszyć z N*Mprzestrzeni do 2*max(N,M)przestrzeni, po prostu przechowując poprzedni wiersz (i to, co zostało obliczone na podstawie bieżącego rząd). Code Project pokazuje, jak to zrobić (z kodem C # do pobrania).