Knuthův–Morrisův–Prattův algoritmus

Knuthův–Morrisův–Prattův algoritmus (KMP algoritmus) je v matematické informatice algoritmus pro hledání výskytů vzorku v textu, jehož časová složitost v nejhorším případě je lineární s délkou textu a vyžaduje předzpracování se složitostí lineární s délkou vzorku. Algoritmus využívá pozorování, že při odhalení neshody obsahuje samotný vzorek dostatek informace pro určení, kde by mohla začínat další shoda, díky čemuž je možné omezit opětovnou kontrolu již porovnaných znaků.

Algoritmus formuloval v roce 1970 James H. Morris a téhož roku jej publikoval s Vaughanem Prattem jako technickou zprávu. „O několik týdnů později“ algoritmus nezávisle objevil Donald Ervin Knuth při výzkumech v teorii automatů. Všichni tři algoritmus společně publikovali v roce 1977. V roce 1969 objevil při studiu problému vyhledávání vzorků v řetězci nad binární abecedou podobný algoritmus pro dvourozměrný Turingův stroj Jurij Vladimirovič Matijasevič., přeloženo do angličtiny jako Tento fakt zmiňuje Knuth v erratech své knihy Selected Papers on Design of Algorithms : Šlo o první algoritmus pro vyhledávání v řetězců pracující v lineárním čase.

Pozadí Algoritmus pro vyhledávání vzorku v řetězci má vrátit pozici m v textovém řetězci S[], od kterého je v řetězci slovo (vzorek) W[].

Nejpřímočařejší „naivní“ algoritmus, známý také jako „řešení hrubou silou“, postupně zjišťuje, zda vzorek nezačíná na každé pozici m v S[] tak, že porovná, zda se znak S[m] neshoduje s prvním znakem hledaného vzorku W. Pokud se znaky shodují, algoritmus porovnává postupně další znaky vzorku s indexy i s následujícími znaky v prohledávaném textu, tj. porovnává S[m+i] s W[i]. Pokud je shoda ve všech znacích vzorku W[], je vrácena hodnota m. Pokud index m dosáhne konce textu, pak se vzorek v textu nevyskytuje, a algoritmus vrátí, že „vyhledání selhalo“.

Test obvykle rychle vyloučí shodu. Pokud by v řetězci byla rovnoměrně rozdělená náhodná velká písmena anglické abecedy, pak by pravděpodobnost shody prvního znaku vzorku s m-tým znakem textu byla 1/26. Test by tedy většinou odmítl shodu již porovnáním počátečního písmene. Pravděpodobnost, že se první dvě písmena se budou shodovat, je (1/26)2 = (1/676). Pokud jsou znaky náhodné, očekávaná složitost vyhledávání v textu S[] délky n je řádově n porovnání neboli O(n). Očekávaná výkonnost je velmi dobrá. Pokud S[] má délku 1 milion znaků a W[] má délku 1000 znaků, pak se při vyhledání provede asi 1,04 milionu porovnání znaků.

Tato očekávaná výkonnost však není zaručená. Pokud řetězce nejsou náhodné, pak zkontrolování, zda se vzorek neshoduje s textem od pozice m může vyžadovat mnoho porovnání znaků. Nejhorší případ je, když se oba řetězce shodují ve všech znacích kromě posledního. Pokud by např. řetězec S[] byl tvořen milionem znaků A, a hledaný vzorek W[] by byl tvořen 999 znaky A, za kterými by byl znak B, pak by naivní algoritmus pro každou z milionu počátečních pozic v S[] provedl porovnání 1000 znaků, tedy 1 miliardu porovnání. Pokud délku vzorku W[] označíme k, pak by složitost v nejhorším případě byla O(k⋅n).

KMP algoritmus má i v nejhorším případě mnohem lepší výkonnost než přímočarý algoritmus. KMP stráví krátký čas přípravou tabulky (velikosti řádu W[], O(k)), kterou pak používá pro mnohem efektivnější vyhledávání řetězce v O(n).

Na rozdíl od přímočarého algoritmu využívá KMP informace o předchozí shodě. Když ve výše uvedeném příkladě KMP zjistí, že porovnání selže na 1000. znaku (i = 999), protože S[m+999] ≠ W, zvýší m o 1, ale již bude vědět, že se prvních 998 znaků v nové pozice shoduje. KMP porovnal 999 znaků A před nalezením neshody na 1000. znaku (na pozici 999). Posunutím pozice shody m o jedno místo vypadne první A, a proto KMP ví, že existuje 998 A znaků, které se shodují s W[] a znovu je netestuje; to jest KMP nastaví i na 998. KMP udržuje svoji znalost v předem vytvořené tabulce a v dvou stavových proměnných. Když KMP objeví neshodu, tabulka určuje, o kolik se má zvětšit (proměnná m), a kde se bude pokračovat v testování (proměnná i).

KMP algoritmus

Příklad algoritmu vyhledávání Pro ilustraci detailů algoritmu, uvažujme (poměrně umělý) běh algoritmu, kde W = „ABCDABD“ a S = „ABC ABCDAB ABCDABCDABDE“. V libovolném okamžiku je stav algoritmu určen dvěma celými čísly:

m je pozice v S, od které začíná potenciální výskyt W, i je index aktuálně porovnávaného znaku v W.

Algoritmus v každém kroku porovná S[m+i] s W[i] a pokud jsou si rovné, zvětší i o 1. Na začátku algoritmu může být následující stav:

1 2 m: 01234567890123456789012 S: W: i:

Algoritmus porovnává další znaky z W s „odpovídajícími“ znaky řetězce S, a zvětšuje i o 1, pokud se shodují. Ale ve čtvrtém kroku S = ' ' nesouhlasí s W = 'D'. Protože jsme znaky na pozici 1 a 2 v S již kontrolovali, víme, že 'A' zde není. Proto není nutné hledat opět od S. Algoritmus proto nastaví m = 3 a i = 0.

1 2 m: 01234567890123456789012 S: ABC W: i:

Toto porovnání selže na prvním znaku, proto algoritmus nastaví m = 4 a i = 0

1 2 m: 01234567890123456789012 S: ABC W: i:

V tomto případě se i zvětšuje o 1 díky téměř úplné shodě “ABCDAB“ až do i = 6, kde se W a S liší. Protože však těsně před koncem aktuální částečné shody byl podřetězec “AB“, který by mohl být začátkem nové shody, algoritmus to musí vzít v úvahu. Protože tyto znaky jsou stejné jako dva znaky před aktuální pozicí, nemusí být znovu kontrolovány; algoritmus nastaví m = 8 (začátek počáteční předpony) a i = 2 (signalizační první dva znaky se shodují) a pokračuje v porovnávání. Algoritmus tedy nejen vynechává dříve porovnané znaky textu S (“AB“), ale také dříve porovnané znaky vzorku W (předpona “AB“).

1 2 m: 01234567890123456789012 S: ABC ABCD W: i:

Toto porovnání na nové pozici okamžitě selže, protože 'C' na pozici W nesouhlasí s mezerou na pozici S. Tato neshoda jako v prvním testu způsobí, že se algoritmus vrátí na začátek vzorku W a začíná vyhledávat od neshodující se pozice textu S: m = 10, přičemž vynuluje i = 0.

1 2 m: 01234567890123456789012 S: ABC ABCDAB W: i:

Porovnání pro m=10 okamžitě selže, takže algoritmus pokračuje dalším testem s m = 11 a i = 0.

1 2 m: 01234567890123456789012 S: ABC ABCDAB W: i:

Algoritmus opět najde shodu “ABCDAB“, ale další znak, 'C', se neshoduje s posledním znakem 'D' vzorku W. Stejně jako minule algoritmus nastaví m = 15, kde začíná dvouznakový řetězec “AB“, nastaví i = 2, a pokračuje v porovnávání od aktuální pozice.

1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCD W: i:

Tentokrát je nalezena úplná shoda, a prvním znakem shody je S.

Popis pseudokódu pro algoritmus vyhledávání

Výše uvedený příklad obsahuje všechny prvky algoritmu. Budeme předpokládat, že máme tabulku T „částečných shod“ popsanou níže, která indikuje, kde se má hledat začátek nové shody, když je nalezena neshoda. Položky tabulky T jsou zkonstruovány tak, že pokud máme shodu začínající v S[m], která selže při porovnávání S[m + i] s W[i], pak další možné shoda bude začínat v S na indexu m + i - T[i] (to znamená, že T[i] je velikost „návratu“, který musíme provést po neshodě). To má dva důsledky: za prvé, T = -1, což indikuje, že pokud W je neshoda, nemůžeme se vrátit zpět, ale musíme jednoduše kontrolovat další znak; a za druhé, přestože další možná shoda bude začínat na indexu m + i - T[i] jako ve výše uvedeném příkladu, není třeba kontrolovat znaky z T[i] po that, ale stačí pokračovat ve vyhledávání od W[T[i]]. KMP algoritmus lze zapsat následujícím pseudokódem: algoritmus kmp_search: vstup: pole znaků S (prohledávaný text) pole znaků W (hledaný vzorek) výstup: pole celých čísel P (seznam pozic v S, na kterých začíná výskyt W) celé číslo, nP (počet výskytů W v S)

definice proměnných: celé číslo j ← 0 (pozice současného znaku v S) celé číslo k ← 0 (pozice současného znaku v W) pole celých čísel, T (tabulka naplněná jinde)

nP ← 0

while j < délka(S) do if W[k] = S[j] then j ← j + 1 k ← k + 1 if k = délka(W) then (nalezen výskyt; pokud nás zajímá jen první výskyt, lze vrátit m ← j – k) P[nP] ← j – k, nP ← nP + 1 k ← T[k] (T[délka(W)] nemůže být -1) else k ← T[k] if k < 0 then j ← j + 1 k ← k + 1

Efektivita vyhledávacího algoritmu Pokud máme k dispozici tabulku T, vyhledávací část Knuthova–Morrisova–Prattova algoritmu má asymptotickou složitost O(n), kde n je délka prohledávaného textu S a O je Landauova notace. Až na určitou režii na začátku a konci funkce, se všechny výpočty provádějí ve while smyčce. Pro určení počtu průchodů smyčkou je třeba si všimnout, že tabulka T je zkonstruována tak, že pokud shoda, která začala na pozici S[m], selže při porovnávání S[m + i] s W[i], pak další možná shoda musí začínat prvkem S[m + (i - T[i])], tedy že další možná shoda se musí mít vyšší index než m, tedy musí platit T[i] < i.

Z toho plyne, že smyčkou se může projít nejvýše 2n-krát, protože v každém průchodu se provádí jedna ze dvou větví ve smyčce. V první větvi se vždy zvětšuje i o 1 a m se nemění, takže index m + i aktuálně porovnávaného znaku v S se zvýší. Ve druhé větvi se k m přičítá i - T[i], což musí být vždy kladné číslo. Proto se index m začátku aktuální potenciální shody vždy zvětší. Ve druhé větvi se přitom m + i nemění, do m se přičte i - T[i], a hned poté se do T[i] přiřadí nová hodnota i, tedy new_m + new_i = old_m + old_i - T[old_i] + T[old_i] = old_m + old_i. Provádění smyčky skončí, pokud m + i = n; proto každou její větev lze projít nejvýše n-krát, protože v každé větvi se zvětšuje jak m + i nebo m, a m ≤ m + i: pokud m = n, pak určitě m + i ≥ n, takže protože zvětšuje nejvýše o jedničku, museli jsme v určitém okamžiku v minulosti mít m + i = n, a proto bychom tak jako tak skončili.

Smyčka se tedy provede nejvýše 2n-krát, což znamená, že časová složitost algoritmu vyhledávání je O(n).

Zde je jiný způsob, jak se dívat na provádění algoritmu: Řekněme, že začneme porovnávat W a S na pozici i a p. Pokud je W podřetězcem S od pozice p, pak W[0..m] = S[p..p+m]. Při úspěchu, to jest když se vzorek a text na pozici (W[i] = S[p+i]) shodují, zvýšíme i o 1. Při selhání, to jest když vzorek a text na pozici (W[i] ≠ S[p+i]) nesouhlasí, ukazatel na text se nemění, zatímco ukazatel do vzorku se vrátí o určitý počet pozic (i = T[i], kde T je tabulka skoků), a bude se porovnávat W[T[i]] s S[p+i]. Maximální počet návratů i je omezen hodnotou i, čili při libovolném selhání se můžeme vrátit zpátky nejvýše o tolik, o kolik jsme do tohoto selhání postoupili. Z toho je zřejmé, že čas běhu je 2n.

Tabulka „částečných shod“ (také známá jako „funkce selhání“) Účelem tabulky je umožnit, aby algoritmus porovnával každý znak S nejvýše jednou. To je možné díky pozorování, že pokud byl porovnán určitý úsek hlavního řetězce s nějakým počátečním úsekem vzorku, víme přesně, v jakých místech před aktuální pozicí může začít nová potenciální shoda, která by mohla pokračovat před aktuální pozicí. Jinými slovy musíme „předprohledat“ samotný vzorek a sestavit seznam všech možných návratových pozic, které obcházejí maximum beznadějných znaků, aniž bychom přitom obětovali potenciální shody.

Chceme být schopni vyhledat pro každou pozici v W délku nejdelšího možného počátečního úseku W, která vede před tuto pozici (ne však až do ní), jiného, než je úplný úsek začínající v W, který právě selhal při porovnání; to jest jak daleko se musíme vracet při hledání další shody. Tedy T[i] je právě délka nejdelšího možného vlastního počátečního úseku W, který je také úsekem podřetězce končícího na W[i - 1]. Používáme konvenci, že prázdný řetězec má délku 0. Protože neshoda na úplném začátku vzorku je speciálním případem (neexistuje možnost návratu), nastavíme T = -1, jak je diskutováno níže.

Fungující příklad algoritmus pro vytváření tabulky