PL 
EnglishDomyślny
Українська🔎 Wyszukiwanie wzorca KMP — funkcja prefiksowa
Knuth-Morris-Pratt przeszukuje tekst w O(n+m): funkcja prefiksowa pozwala przesuwać wzorzec bez ponownego sprawdzania dopasowanych znaków. Zobacz kursor, który nigdy się nie cofa.
O wyszukiwaniu wzorca KMP
Algorytm Knutha-Morrisa-Pratta (KMP) rozwiązuje problem dopasowywania ciągów — znajdowania wszystkich wystąpień wzorca P o długości m wewnątrz tekstu T o długości n — w czasie O(n + m), w porównaniu z naiwnym najgorszym przypadkiem O(mn). Kluczowa obserwacja, opublikowana przez Donalda Knutha, Vaughana Pratta i Jamesa Morrisa w 1977 roku, to funkcja niepowodzeń (zwana też funkcją prefiksową): wstępnie obliczona tabela kodująca, dla każdej pozycji we wzorcu, długość najdłuższego właściwego prefiksu, który jest jednocześnie sufiksem. Gdy wystąpi niezgodność, algorytm używa tej tabeli, by przesunąć wzorzec do przodu bez ponownego badania jakiegokolwiek już przetworzonego znaku tekstu.
Symulacja animuje dwa wskaźniki — jeden nad tekstem i jeden nad wzorcem — podświetlając dopasowane znaki na zielono, a niezgodności na czerwono. Możesz zobaczyć budowanie tabeli funkcji niepowodzeń, obserwować, jak wzorzec przesuwa się do przodu przy niezgodności, oraz porównać łączną liczbę porównań znaków z licznikiem naiwnego przeszukiwania siłowego wyświetlanym obok.
Najczęściej zadawane pytania
Dlaczego KMP jest szybszy niż naiwne dopasowywanie ciągów?
Naiwne wyszukiwanie może wielokrotnie badać te same znaki tekstu: dla tekstu takiego jak „AAAAAAB” ze wzorcem „AAAB” wykonuje O(nm) porównań w najgorszym przypadku. KMP unika tego, nigdy nie cofając wskaźnika tekstu; każdy znak jest badany co najwyżej dwukrotnie (raz przy budowie funkcji niepowodzeń, raz przy wyszukiwaniu), dając solidną gwarancję O(n + m) niezależnie od wejścia.
Czym jest funkcja niepowodzeń (funkcja prefiksowa)?
Dla wzorca P funkcja niepowodzeń π[i] podaje długość najdłuższego właściwego prefiksu P[0..i], który jest też sufiksem P[0..i]. Na przykład dla wzorca „ABAB”, π = [0, 0, 1, 2]. Gdy niezgodność wystąpi na pozycji i we wzorcu, algorytm ustawia i = π[i−1] zamiast resetować do 0, więc wcześniej dopasowane znaki nie są ponownie porównywane.
Jaka jest złożoność czasowa budowy funkcji niepowodzeń?
Konstrukcja tabeli niepowodzeń zajmuje czas O(m) i pamięć O(m), używając dwuwskaźnikowego skanu samego wzorca. W połączeniu z fazą wyszukiwania O(n) łączna złożoność wynosi O(n + m). Dowód wykorzystuje argument amortyzowany: choć pętla wewnętrzna może iterować, zmienna śledząca długość dopasowania może wzrosnąć co najwyżej n razy w całym wyszukiwaniu.
Jak KMP obsługuje nakładające się dopasowania?
Gdy pełne dopasowanie zostanie znalezione na pozycji i w tekście, algorytm ustawia wskaźnik wzorca na π[m−1] zamiast na 0, pozwalając natychmiast szukać kolejnego nakładającego się dopasowania. Na przykład wyszukiwanie „ABA” w „ABABA” poprawnie znajduje dopasowania zarówno na pozycji 0, jak i 2.
Czy KMP jest najszybszym algorytmem dopasowywania ciągów w praktyce?
Nie zawsze. Choć KMP osiąga teoretyczną granicę O(n + m), algorytmy takie jak Boyer-Moore-Horspool często przewyższają go w praktyce, ponieważ mogą pomijać wiele znaków naraz, używając heurystyk złego znaku i dobrego sufiksu, dając poniżej-liniowe zachowanie w typowym przypadku dla zwykłego tekstu angielskiego. KMP jest preferowany, gdy alfabet jest mały (np. zasady DNA A/C/G/T) lub gdy strumieniowe wejście wyklucza zaglądanie naprzód.
Gdzie KMP jest wykorzystywany w rzeczywistym oprogramowaniu?
KMP i jego pochodne są używane w grep, edytorach tekstu, narzędziach bioinformatycznych (dopasowywanie sekwencji DNA), systemach wykrywania włamań sieciowych (dopasowywanie wzorców w ładunkach pakietów) oraz skanowaniu sygnatur antywirusowych. Jądro Linuksa używa wariantu do wyszukiwania ciągów w modułach jądra.
Jaka jest różnica między KMP a algorytmem Aho-Corasick?
KMP wyszukuje pojedynczy wzorzec w czasie liniowym. Aho-Corasick uogólnia to, by jednocześnie wyszukiwać k wzorców w czasie O(n + m₁ + … + mₖ + z) (z = łączna liczba dopasowań), używając automatu skończonego zbudowanego ze wszystkich wzorców. Jest to algorytm stojący za narzędziami takimi jak fgrep i systemami inspekcji treści sieciowej.
Czy KMP może obsługiwać tekst Unicode?
Tak, pod warunkiem że znaki są porównywane poprawnie. KMP działa na sekwencjach tokenów (punktów kodowych lub bajtów), więc działa na dowolnym alfabecie. Przy używaniu tekstu zakodowanego w UTF-8 powszechne jest operowanie na bajtach, ale trzeba uważać w pobliżu granic znaków wielobajtowych, by uniknąć podzielenia punktu kodowego w środku dopasowania.
Czym jest algorytm Z i jak wiąże się z KMP?
Algorytm Z oblicza dla każdej pozycji i w ciągu długość najdłuższego podciągu zaczynającego się w i, który jest też prefiksem ciągu. Rozwiązuje ten sam problem dopasowywania wzorca w czasie O(n + m), ale używa innego podejścia: łączy P + $ + T i oblicza tablicę Z, a następnie znajduje dopasowania tam, gdzie Z[i] ≥ m. Wielu programistów sportowych preferuje tablice Z ze względu na ich koncepcyjną prostotę.
Dlaczego wskaźnik tekstu nigdy nie cofa się w KMP?
To centralny niezmiennik algorytmu. Funkcja niepowodzeń gwarantuje, że gdy niezgodność wystąpi na pozycji i wzorca, cała informacja o już przeskanowanych znakach tekstu jest zakodowana w π[i−1]. Nigdy więc nie ma potrzeby ponownego badania znaku tekstu, który już został dopasowany, co daje liniową granicę czasową.