Maybaygiare.org

Blog Network

Przybliżone dopasowanie łańcuchów

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}}

P = p_1p_2...p_m

I ciąg tekstowy T = T 1 t 2 … t n {\displaystyle T=t_{1}t_{2}\dots t_{n}}

T = t_1t_2\dots t_n

, znajdź podłańcuch T j ’, j = T j '… T J {\displaystyle T_{J’,J}=T_{J’}\Dots T_{J}}

t_{J',J} = t_{j'}\dots 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}}

p_{i}

I dowolnym podłańcuchem T j’, j {\displaystyle T_{j’, j}}

T_{J', 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.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.