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.
algorithms
strings
Reactgular
źródło
źródło
Odpowiedzi:
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
->,sitting
którego odległość edycji wynosi trzyIstnieją 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:
.
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:
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:
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*M
przestrzeni do2*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).źródło