Dopasowywanie Ciągów KMP: Nigdy Nie Cofnij Się

Dlaczego naiwne przeszukiwanie marnuje pracę

Wyraźny sposób na znalezienie wzorca o długości m w tekście o długości n polega na próbie każdego możliwego położenia początkowego, porównując znak po znaku, aż do uzyskania pełnego dopasowania lub wystąpienia nieprawidłowości. W typowych tekstach jest to szybkie, ale w przypadku danych przeciwnych lub bardzo powtarzalnych danych pogarsza się znacznie: szukając "AAAAB" w długim ciągu "A", dopasowuje się prawie na każdym początkowym położeniu przed niepowodzeniem na piątym znaku, co daje O(n·m) porównań w najgorszym przypadku.

Wgląd: wzorzec już ci mówił

Algorytm Knuta, Morrisa i Pratta z 1977 roku zauważa, że gdy wystąpi nieporównanie po porównaniu pewnych znaków, te dopasowane znaki stanowią fragment wzorca – wiesz dokładnie, czym są, ponieważ pasowały. Jeśli część tego fragmentu przypadkowo jest również wstępem do wzorca, możesz kontynuować porównywanie od połowy wzorca zamiast od jego pierwszego znaku, i to bez cofania kursora tekstu.

Budowanie funkcji niepowodzenia

To jest wstępnie obliczone raz, na podstawie samego wzoru, przed rozpoczęciem skanowania tekstu. failure[i] to długość najdłużego poprawnego prefiksu wzoru, który również jest prawidłowym sufiksem wzoru[0..i]:

buildFailure(wzor): failure = tablica o długości m, failure[0] = 0 k = 0 // długość aktualnego pasującego prefiksu dla i od 1 do m - 1: podczas gdy k > 0 i wzor[i] != wzor[k]: k = failure[k - 1] // cofamy się do krótszego prefiksu jeśli wzor[i] == wzor[k]: k += 1 failure[i] = k zwróć failure To samo wstępne przetwarzanie kosztuje O(m), używając tej samej techniki "nigdy nie cofaj się do tyłu" na wzorze w porównaniu z nim samym.

buildFailure(pattern):
  failure = array of length m, failure[0] = 0
  k = 0                          // length of current matching prefix
  for i = 1 to m - 1:
    while k > 0 and pattern[i] != pattern[k]:
      k = failure[k - 1]         // fall back to a shorter prefix
    if pattern[i] == pattern[k]:
      k += 1
    failure[i] = k
  return failure

Faza wyszukiwania

Po przygotowaniu funkcji niepowodzenia, skanowanie tekstu wymaga jedynie jednego przemieszczenia w prawo — indeks tekstu nigdy nie maleje, a jedynie indeks wzorca przeskakuje do tyłu przy użyciu wstępnie obliczonej tabeli:

search(text, pattern, failure): j = 0 // indeks do wzorca for i = 0 to n - 1: // indeks do tekstu, nigdy nie maleje while j > 0 and text[i] != pattern[j]: j = failure[j - 1] // przeskocz wzorcem do tyłu, a nie tekstem if text[i] == pattern[j]: j += 1 if j == m: zgłoś dopasowanie kończące się na i j = failure[j - 1] // kontynuuj poszukiwanie nakładających się dopasowań Ponieważ indeks tekstu i zawsze tylko rośnie, każdy znak tekstu jest badany ograniczoną liczbę razy w sumie (amortyzowany argument dla indeksu wzorca daje O(n) pracy całkowitej podczas skanowania), więc cały algorytm — wstępne przetwarzanie plus wyszukiwanie — działa w czasie O(n + m), bez zależności od tego, jak powtarzalny jest żaden z ciągów.

search(text, pattern, failure):
  j = 0                                   // index into pattern
  for i = 0 to n - 1:                     // index into text, never decreases
    while j > 0 and text[i] != pattern[j]:
      j = failure[j - 1]                  // jump the pattern backward, not the text
    if text[i] == pattern[j]:
      j += 1
    if j == m:
      report match ending at i
      j = failure[j - 1]                  // continue looking for overlapping matches

Gdzie jest używane

Narzędzia wyszukiwania tekstu preferują KMP lub jego bliskich krewnych do wyszukiwania w jednym rzędzie bezwzględnych ciągów znaków, ponieważ jej najgorszy przypadek gwarantuje liniową czasowość, w przeciwieństwie do naiwnego skanowania, które sprawdza się średnio, ale jest patologiczne na powtarzalnym wejściu – dokładnie taki typ wejścia może wygenerować wróg lub prawdziwy genom (długie ciągi powtarzających się baz). Narzędzia bioinformatyczne wykorzystują je do lokalizowania krótkich motywów wewnątrz długich sekwencji DNA i białek. Pomysł na jej funkcję awaryjną bezpośrednio uogólnia się w algorytm Aho-Corasick, który buduje pojedynczy automat do wyszukiwania wielu wzorców jednocześnie w jednym przejściu przez tekst.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz KMP String Matching i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.