jedną z możliwych definicji przybliżonego problemu z dopasowaniem łańcuchów jest następująca: podano wzór łańcuch p = p 1 p 2. . . p m {\displaystyle P = p_{1} p_{2}…p_{m}}
I ciąg tekstowy T = T 1 t 2 … t n {\displaystyle T=t_{1}t_{2}\dots t_{n}}
, znajdź podłańcuch T j ’, j = T j '… T J {\displaystyle T_{J’,J}=T_{J’}\Dots T_{J}}
w T, który ze wszystkich podłańcuchów t ma najmniejszą odległość edycji do wzorca P.
podejściem brute-force byłoby obliczenie odległości edycji do p dla wszystkich podłańcuchów t, a następnie wybranie podłańcucha z minimalnym odległość. Algorytm ten miałby jednak czas działania O (n3 m).
lepsze rozwiązanie, które zaproponowali sprzedawcy, opiera się na programowaniu dynamicznym. Używa alternatywnego sformułowania problemu: dla każdej pozycji j w tekście T i każdej pozycji i w wzorze P Oblicz minimalną odległość edycji między pierwszymi znakami wzorca i, P i {\displaystyle P_{i}}
I dowolnym podłańcuchem T j’, j {\displaystyle T_{j’, j}}
t kończącego się na pozycji j.
dla każdej pozycji j w tekście T, oraz dla każdej pozycji i we wzorze P, przejrzyj wszystkie podłańcuchy t kończące się na pozycji j i określ, który z nich ma minimaledytuj odległość do i pierwszych znaków wzorca P. Zapisz tę minimalną odległość jako E (i, j). Po obliczeniu E (i, j) dla wszystkich i I j możemy łatwo znaleźć rozwiązanie pierwotnego problemu: jest to podłańcuch, dla którego E(m, j) jest minimalny (M jest długością wzorca P.)
Obliczanie E(M, j) jest bardzo podobne do obliczania odległości edycji między dwoma łańcuchami. W rzeczywistości możemy użyć algorytmu obliczania odległości Levenshteina dla E (m, j), jedyną różnicą jest to, że musimy zainicjalizować pierwszy wiersz zerami i zapisać ścieżkę obliczeń, to znaczy, czy użyliśmy E(i − 1,j), E(i,j − 1) lub E(i − 1,j − 1) w obliczeniach E (i, j).
w tablicy zawierającej wartości E(x, y) wybieramy wartość minimalną w ostatnim wierszu, niech będzie to E(x2, y2) i podążamy ścieżką obliczeń wstecz, z powrotem do wiersza numer 0. Jeśli pole, do którego dotarliśmy, było E (0, y1), to T … T jest podciÄ … giem T z minimalnym odlegĹ ’ oĹ ” ciÄ … edycji do wzorca P.
obliczenie tablicy E(x, y) zajmuje O(mn) czas przy pomocy algorytmu programowania dynamicznego, podczas gdy faza pracy wstecznej zajmuje O(N + m) czas.
innym niedawnym pomysłem jest połączenie podobieństwa. Gdy dopasowanie bazy danych dotyczy dużej skali danych, Czas O (mn) z algorytmem programowania dynamicznego nie może działać w ograniczonym czasie. Chodzi więc o to, aby zamiast obliczać podobieństwo wszystkich par ciągów, zmniejszyć liczbę par kandydatów. Powszechnie stosowane algorytmy opierają się na weryfikacji filtrów, hashowaniu, Hashowaniu lokalnie wrażliwym (LSH), próbach i innych algorytmach chciwości i aproksymacji. Większość z nich jest zaprojektowana tak, aby pasowała do niektórych frameworków (takich jak Map-Reduce) do obliczeń jednocześnie.