Vyhľadávania reťazca v texte

Tento článok je zároveň drobným úvodom do textových algoritmov, ktoré za posledných niekoľko desiatok rokov mnohonásobne nabili na význame. Dnes sa zoznámime s tzv. Algoritmom KMP - K nuthův- M orrisův- P rattův algoritmus.

KMP algoritmus

Určite ste sa dostali do situácie, kedy ste mali nájsť niečo v neusporiadané zhromaždení. Nič nie je zrovnané, hľadaná vec môže byť v hromade raz, alebo trebárs 50x ... Podobný problém môže byť, ak chceme nájsť v texte určité slovo či podreťazec. Budeme treba chcieť nájsť všetky výskyty slova kokos v medzinárodnej dohode dvoch štátov o dovážanie potravín. Úloha sa podobá veľmi známemu príslovie o hľadanie ihly v kope sena. Najskôr si však formálne povedzme, ako úloha znie.

Formálny zápis problému

Na vstupe dostaneme s ené s a j ehlu j. Seno aj ihla sú textové reťazce a chceme nájsť všetky indexy (čiže pozícia) od ktorých začína ihla j v sene s, teda všetky počiatočné pozície hľadaného slova v texte.

Brute-force riešenie problému

Povedzme, že máme n znakov v reťazci. Veľkosť ihly je j. Môžeme vziať for-cyklus vo for-cykle a skúšať jednotlivé podobnosti:

List<int> mnozinaIndexu = new List<int>();

for (int i = 0; i < n - j; i++) {
    for (int k = 0; k < j; k++) {
        if (seno[i + k] != jehla[i]) {
          break;
        }
        if (k == j - 1) {
            mnozinaIndexu.add(i);
        }
    }
}

Môžeme sa pozrieť na časovú zložitosť. Algoritmus pre každé i z n pôjde j -krát. Časová zložitosť je teda O (n * j). Dá sa to robiť lepšie? Kedy tento algoritmus vykonáva zbytočnú prácu naviac?

Efektívnejší prístup

Predstavme si, že hľadáme v texte ten kokos. Majme seno nejkokokokosovatější. Môžeme si uvedomiť, že keď prečítame ko, potom hľadáme už len výraz kos. Ak prečítame koko, stačí nám už len s. Čo sa ale stane v momente, keď prečítame ďalšie k ? Nemusíme predsa zahadzovať celý reťazec. Síce máme teraz prečítané slovo kokok, ale môžeme vypustiť prvé dva znaky a budeme mať prečítané opäť kok. Ďalej prečítame o a ak prečítame zase k, postup sa opakuje. Ak však prečítame s, máme hľadaný kokos. Uvedomíme si, že sa teraz nevraciame a zo vstupného sena čítame vždy ďalšie a ďalšie znak. Každý znak zo sena prečítame len raz. Jediné, čo prechádzame, je ihla, pretože prechádzame ihlu od začiatku a odsekávame prefixy, ktoré vieme, že už nebudú užitočné. Nakoniec môžeme odseknúť celú ihlu, ak po koko prečítame l:

seno: nejkokokokosovatější
jehla: kokos

n e j k o k o k o k o s o v a t ě j š í
k k k k o k o k
          k o k|o k
              k o k|o s
                        k k k k k k k k

Slovo kokos sa teda v slove vyskytoval iba raz. Každý znak zo sena sme prešli práve raz. značka | znázorňuje časť slova, ktorú sme prevzali z doposiaľ prečítaného slova.

Algoritmus

Bohužiaľ sa tu nevyhneme pojmu automat. Berte to teraz len tak, že postavíme akýsi parser, ktorý sám bude rozhodovať, či slovo odsekne alebo znak pripojí k už nájdenému prefixu hľadaného slova. Ak máte za sebou teóriu automatov, tak v KMP algoritme využívame konečný stavový automat.

Zostavenie automatu

Prvým krokom bude postaviť automat pre našu ihlu. Budeme chcieť postaviť nejakú krabičku, ktorá sa bude sama starať o to, kam sa ihla posúva:

static int[] BuildAutomat(string jehla)
       {
           ReturnFunction = new int[jehla.Length];
           ReturnFunction[0] = -1;
           if (jehla.Length > 1) ReturnFunction[1] = 0;
           int stav = 0;

           for (int i = 2; i < jehla.Length; i++)
           {
               stav = KMPStep(jehla, stav, jehla[i - 1]);
               ReturnFunction[i] = stav;
           }
           AfterBuildingAutomat = true;
           return ReturnFunction;
       }

Automat si reprezentujeme ako pole. Vstupom pre funkciu bude ihla. Chceme postaviť funkciu ReturnFunction, čiže návratovú funkciu, ktorá sa rozhodne pre to, kam sa posunúť pre prečítaný znak. Pre prvý znak nemá návratová funkcie zmysel. Ak je ihla väčšia ako 1, potom pre pole v indexe 1 sa vraciame do nuly. Toto zodpovedá situácii, kedy sme chceli prečítať slovo kokos a prečítali sme znak m. Vraciame sa teda na začiatok. Pre ďalšie stavy pošleme stav do KMPStep(), ktorému "povieme", čo hľadáme, v ktorom sme stave a aký symbol sme prečítali. Potom čo zostavíme automat, čiže budeme mať povedané pre aká písmená sa kam vraciame, označíme si, že sme automat zostavili. Vďaka tomu môžeme využívať funkciu KMPStep() bez toho, aby sa znova staval už postavený automat.

Pattern je naša ihla. Máme už nadefinovanú návratovú funkciu. Návratová funkcie pre znak určí, o koľko sa má v prečítané ihle vrátiť.

[k o k o s]  - jehla
[k o k ]     - přečteno
pokud nyní přečtu 'o', je to v pořádku a návratová funkce není třeba.
[k o k o]
pokud nyní přečtu 'k', tak jehla[4] != k, musím použít zpětnou funkci. Ta dostane 'k' a vrátí mě na pozici 3.
[k o k]
pokud nyní přečtu 'o', je to v pořádku a návratová funkce není třeba.
[k o k o]
pokud nyní přečtu 's' nebo 'a', tak mě návratová funkce pošle na začátek. Samozřejmě si pro 's' zaznamenám index, neboť jsem našel jehlu v kupce sena.

Jeden krok automatu

Jeden krok reprezentujeme funkcií KMPStep:

static int KMPStep(string jehla, int stav, char x)
{
    while ( (jehla[stav] != x) && (stav!= 0) )
    {
        stav = ReturnFunction[stav];
        if (AfterBuildingAutomat)
        {
            break;
        }
    }
    if (jehla[stav] == x)

    {
        stav++;
    }

    return stav;
}

Tento kód zodpovedá tomu, že ak písmeno x nie je v ihle na pozícii [stav], čiže na 4. pozícii nie je napríklad písmeno s, musíme sa teda vrátiť späť. Zodpovedá to nášmu znaku k, keď sme prečítali slovo koko. Ak by sme prečítali s, automat by sa nevracal a cyklus while by neprebehol ani raz. Ak sme našli zhodu, ihla sa posunie o pozíciu doprava zdvihnutím stave. AfterBuildingAutomat je premenná, ktorá nám povie, či sme už automat zostavili, alebo nie. Tú istú funkciu potom budeme používať pri hľadaní reťazca, zatiaľ si to nevšímajme.

Použitia algoritmu

Teraz máme zostavený automat a máme definované, čo sa stane, keď KMP dostane znak vo funkcii KMPStep(). Teraz už nám stačí mať na vstupe seno a ihlu. Všetky potrebné nástroje už máme:

public static List<int> SearchKMP(string seno, string jehla)
{
    BuildAutomat(jehla);
    int stav = 0;
    List<int> indexes = new List<int>();

    for (int i = 0; i < seno.Length; i++)
    {
        stav = KMPStep(jehla, stav, seno[i]);
        if (stav == jehla.Length)
        {
            state--;
            indexes.Add(i - jehla.Length + 1);
            stav = ReturnFunction[stav];
        }

    }
    return indexes;
}

Najskôr si postavíme automat. Zavedieme si dynamické pole indexov. Ak je pole na konci prázdne, ihla v sene nebola. Potom máme jeden cyklus for, ktorým prejdeme seno. Ak nám funkcia KMPStep() vráti stav, ktorý sa rovná dĺžke ihly, vieme, že sme našli vhodné slovo. Znížime stav (kvôli indexovanie pole od 0) a pridáme index slová, kde ihla začína. Potom ešte zavoláme návratovú funkciu, pretože prečítame Ak slovo kuchtík, tak sme zároveň prečítali aj znak k pre slovo kuchtíkuchtíkuchtík a algoritmus bezpečne odhalí všetky výskyty tohto slova.

Zhodnotenie algoritmu

Prečo to vlastne všetko robíme? Pomohli sme si oproti pôvodnému algoritmu brute-force? Rozhodne. Časová zložitosť nového algoritmu je O (j + s), kde j je dĺžka ihly a s je dĺžka sena. Hľadáme ak nejaké meno v několikagigovém textovom súbore, rozdiel rýchlostí je očividný.

Čo ale robiť ak by sme v texte chceli naraz nájsť viac slov? Hlave taká ako potok, popol, potopenie, popolník ... Zakaždým na celý text púšťať KMP by bolo neefektívne. V ďalšom článku sa teda pozrieme, ako sa vyhľadá viac ihiel v jednom sene oveľa efektívnejšie.