Wikipedie

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 informaci 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.[1] „O několik týdnů později“ algoritmus nezávisle objevil Donald Ervin Knuth při výzkumech v teorii automatů.[2][3] Všichni tři algoritmus společně publikovali v roce 1977.[2] 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č.[4][5] Šlo o první algoritmus pro vyhledávání v řetězců pracující v lineárním čase.[6]

Pozadí

editovat

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[0]. 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[999], 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

editovat

Příklad algoritmu vyhledávání

editovat

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: ABCABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

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[3] = ' ' nesouhlasí s W[3] = '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[1]. Algoritmus proto nastaví m = 3 a i = 0. 

             1 2 
m: 01234567890123456789012
S: ABCABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

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

             1 2 
m: 01234567890123456789012
S: ABC ABCDABABCDABCDABDE
W: ABCDABD
i: 0123456

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[6] a S[10] 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 ABCDABABCDABCDABDE
W: ABCDABD
i: 0123456

Toto porovnání na nové pozici okamžitě selže, protože 'C' na pozici W[2] nesouhlasí s mezerou na pozici S[10]. 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 ABCDABABCDABCDABDE
W: ABCDABD
i: 0123456

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 ABCDABCDABDE
W: ABCDABD
i: 0123456

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 ABCDABCDABDE
W: ABCDABD
i: 0123456

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

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

editovat

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[0] = -1, což indikuje, že pokud W[0] 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

editovat

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í“)

editovat

Úč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[0], 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[0] = -1, jak je diskutováno níže.

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

editovat

Uvažujme nejdříve například W = „ABCDABD“. Uvidíme, že následuje přesně stejný vzorek jako v hlavním hledání, a je z podobných důvodů efektivní. Nastavíme T[0] = -1. Pro nalezení T[1], musíme najít vlastní sufix řetězce “A“, který je zároveň předponou vzorku W. Ale neexistují žádné vlastní sufixy “A“, proto nastavíme T[1] = 0. Pro zjištění T[2] vidíme, že podřetězec W[0..1] (“AB“) má vlastní sufix “B“. Ale „B“ není předpona vzorku W. Proto, nastavíme T[2] = 0.

Pokračujeme na T[3], nejdříve zkontrolujeme vlastní sufix délky 1, což jako v předchozí případě selže. Musíme kontrolovat také delší sufixy? Ne, nyní si všimneme, že kontrolu všech sufixů lze zkrátit: řekněme, že jsme objevili vlastní sufix, který je vlastní předpona (vlastní předpona řetězce není rovna samotnému řetězci) a ukončení v W[2] s délkou 2 (maximální možné); pak jeho první znak je také vlastní předponou W, tedy samotnou vlastní předponu, a skončí v W[1], což jsme již určili, nese objeví jako T[2] = 0 a not T[2] = 1. V každé fázi tedy platí pravidlo zkratky, že sufixy dané velikosti m+1 stačí kontrolovat pouze tehdy, když byl v předchozí fázi nalezen platný sufix délky m (tj. T[x] = m) a není třeba kontrolovat m+2, m+3, atd.

Proto se vůbec nemusíme starat o podřetězce délky 2, a protože jako v předchozím případě jediný s délkou 1 selže, takže T[3] = 0.

Přejdeme na následující W[4], 'A'. Stejná logika ukazuje, že nejdelší podřetězec, který potřebujeme uvažovat, má délku 1, a selže jako v předchozím případě, protože „D“ není předponou vzorku W. Ale než nastavíme T[4] = 0, všimneme si,že W[4] = W[0], a také, že použití T[4] implikuje, že odpovídající znak S, S[m+4], se neshoduje a proto S[m+4] ≠ 'A'. Tedy nemá žádný význam při novém startu vyhledávání v S[m+4]; musíme začít o 1 pozici dopředu. To znamená, že můžeme vzorek W posunout o délku shody plus jeden znak, proto T[4] = -1.

Nyní uvažujme další znak, W[5], kterým je 'B': ačkoli by inspekce nejdelší podřetězec by se vyskytují být 'A', stejně nastavíme T[5] = 0. Vyvozování je podobné, jako v případě proč T[4] = -1. W[5] samotný rozšiřuje předpona shoda begun s W[4], a můžeme předpokládat, že odpovídající znak v S, S[m+5] ≠ 'B'. Proto návrat před W[5] nemá význam, ale S[m+5] může být 'A', tedy T[5] = 0.

Nakonec vidíme, že další znak v aktuálním úseku začínajícím W[4] = 'A' bude 'B', a opravdu to je také W[5]. Stejný argument jako výše navíc ukazuje, že abychom našli úsek pro W[6], nemusíme se dívat před W[4], proto nastavíme T[6] = 2.

Tabulka tedy bude vypadat takto:

i 0 1 2 3 4 5 6 7
W[i] B C D B D
T[i] -1 0 0 0 -1 0 2 0

Jiný příklad:

i 0 1 2 3 4 5 6 7 8 9
W[i] B C B B C
T[i] -1 0 -1 1 -1 0 -1 3 2 0

Další příklad (nepatrně změněný oproti předchozímu):

i 0 1 2 3 4 5 6 7 8 9
W[i] B C B B
T[i] -1 0 -1 1 -1 0 -1 3 -1 3

Ještě složitější příklad:

i 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
W[i] P R T I C I P T E I N P R C H U T E
T[i] -1 0 0 0 0 0 0 -1 0 2 0 0 0 0 0 -1 0 0 3 0 0 0 0 0 0

Popis pseudokódu algoritmu vytváření tabulky

editovat

Příklad v předchozí části demonstruje obecnou techniku pro bezproblémové sestavení tabulky. Princip je stejný jako v celém hledání: většina práce byla již provedena při cestě do aktuální pozice, takže při jejím opuštění stačí udělat velmi málo. Menší komplikací je, že logika, která funguje na konci řetězce, dává na začátku chybné nevlastní podřetězce. Kvůli tomu je nutné provést určitý inicializační kód. 

algoritmus kmp_table:
    vstup:
        pole znaků W (slovo, které má být analyzováno)
    výstup:
        pole celých čísel T (tabulka, která bude plněna hodnotami)

    definuje proměnné:
        celé číslo pos ← 1 (aktuální pozice, kterou počítáme v T)
        celé číslo cnd ← 0 (index dalšího znaku v právě prověřovaném podřetězci ve W počítaný od nuly)

    T[0] ← -1

    while pos < délka(W) do
        if W[pos] = W[cnd] then
            T[pos] ← T[cnd]
        else
            T[pos] ← cnd
            while cnd ≥ 0 a W[pos] ≠ W[cnd] do
                cnd ← T[cnd]
        pos ← pos + 1, cnd ← cnd + 1

    T[pos] ← cnd (potřebné pouze, když se mají hledat všechny výskyty slova)

Efektivita algoritmu vytváření tabulky

editovat

Časová (i prostorová) složitost tabulkového algoritmu je  , kde   je délka vzorku W.

  • Vnější smyčka: pos je inicializováno na 1, podmínka smyčky je pos < k, a pos se zvětšuje o 1 v každém průchodu smyčkou. Celkem se smyčkou projde take  -krát.
  • Vnitřní smyčka: proměnná cnd je inicializována na 0 a zvětšuje se nejvýše o 1 v každém průchodu vnější smyčkou. T[cnd] je vždy menší než cnd, takže cnd se sníží alespoň o 1 při každém průchodu vnitřní smyčkou; podmínka vnitřní smyčky je cnd ≥ 0. To znamená, že se vnitřní smyčkou může projít nejvýše tolikrát, kolikrát vnější smyčkou – pro každé snížení cnd o 1 ve vnitřní smyčce se musí zvětšuje o 1 ve vnější smyčce. Protože se provádí   průchodů vnější smyčkou, vnitřní smyčka nemůže celkem trvat více než   iterace celkem.

Ve vnější a vnitřní smyčce se provede celkem nejvýše   iterací. To odpovídá časové složitosti   v Landauově notaci.

Efektivita KMP algoritmu

editovat

Protože první část algoritmu má složitost O(k) a druhá O(n), složitost celého algoritmu je O(n + k).

Tyto složitosti nezávisí na tom, kolik opakujících se vzorků je v W nebo S.

Varianty

editovat

Verzi KMP pracující v reálném čase lze implementovat pomocí zvláštní tabulky funkce selhání pro každý znak abecedy. Pokud se neshoda objeví ve znaku   v textu, zkontroluje se tabulka funkce selhání pro znak   pro index   ve vzorku, kde se objevila neshoda. V tabulce je délku nejdelšího podřetězce ukončení v   vyhovující předpona vzorku, s přidanou podmínkou, že znak po předponě je  . S tímto omezením nemusí být v dalším fázi znak   v textu znovu kontrolován, a proto se mezi zpracováním každého indexu textu provede pouze konstantní počet operací,[zdroj?] což vyhovuje omezením při práci v reálném čase.

Boothův algoritmus používá upravenou verzi KMP funkce pro předzpracování pro vyhledávání lexikograficky minimálního řetězce rotací. Funkce selhání se počítá postupně při rotaci řetězce.

Odkazy

editovat

Reference

editovat

V tomto článku byl použit překlad textu z článku Knuth–Morris–Pratt algorithm na anglické Wikipedii.

  1. ↑ MORRIS, J.H., jr.; PRATT, V., 1970. A linear pattern-matching algorithm. Berkeley, Kalifornie: University of California, Berkeley, Computation Center. 
  2. ↑ a b KNUTH, Donald; MORRIS, James H.; PRATT, Vaughan, 1977. Fast pattern matching in strings. SIAM Journal on Computing. Roč. 6, čís. 2, s. 323–350. DOI 10.1137/0206024. 
  3. ↑ KNUTH, Donald E., 1973. The Dangers of Computer-Science Theory. Studies in Logic and the Foundations of Mathematics. Roč. 74, s. 189–195. ISBN 9780444104915. DOI 10.1016/S0049-237X(09)70357-X. 
  4. ↑ МАТИЯСЕВИЧ, Юрий, 1971. О распознавании в реальное время отношения вхождения. Записки научных семинаров Ленинградского отделения Математического института им. В.А.Стеклова. Roč. 20, s. 104–114. Dostupné online. (rusky) , přeloženo do angličtiny jako MATIYASEVICH, Yuri, 1973. Real-time recognition of the inclusion relation. Journal of Soviet Mathematics. Roč. 1, s. 64–70. Dostupné online. DOI 10.1007/BF01117471. S2CID 121919479. (anglicky) 
  5. ↑ Tento fakt zmiňuje Knuth v erratech své knihy Selected Papers on Design of Algorithms :
    „ V roce 2012 jsem zjistil, že Yuri Matiyasevich již v roce 1969 předvídal algoritmy pro vyhledávání v vzorů a předzpracování vzorů v lineárním čase, které jsou uvedeny v tomto článku, pro speciální případ binární abecedy. Představil je jako konstrukci pro Turingův stroj s dvourozměrným pracovním prostorem. “
  6. ↑ AMIR, Amihood; LANDAU, Gad M.; LEWENSTEIN, Moshe; SOKOL, Dina, 2007. Dynamic text and static pattern matching. ACM Trans. Algorithms. Roč. 3, čís. 2, s. 19. DOI 10.1145/1240233.1240242. S2CID 8409826. 

Literatura

editovat

Externí odkazy

editovat
Citováno z „https://cs.wikipedia.org/w/index.php?title=Knuthův–Morrisův–Prattův_algoritmus&oldid=24076955“