Lekce 5 - Vyhledávání řetězce v textu

V minulé lekci, Interpolační vyhledávání, jsme si ukázali algoritmus na interpolační vyhledávání, který efektivně vyhledává prvky v rovnoměrně setříděném poli.

Tento článek je zároveň drobným úvodem do textových algoritmů, které za posledních několik desítek let mnohonásobně nabily na významu. Dnes se seznámíme s tzv. algoritmem KMP - Knuthův-Morrisův-Prattův algoritmus.

KMP algoritmus

Určitě jste se dostali do situace, kdy jste měli najít něco v neuspořádané hromadě. Nic není srovnané, hledaná věc může být v hromadě jednou, nebo třeba 50x... Podobný problém může být, pokud chceme najít v textu určité slovo či podřetězec. Budeme třeba chtít najít všechny výskyty slova kokos v mezinárodní dohodě dvou států o dovážení potravin. Úloha se podobá velmi známému přísloví o hledání jehly v kupce sena. Nejdříve si však formálně řekněme, jak úloha zní.

Formální zápis problému

Na vstupu dostaneme seno s a jehlu j. Seno i jehla jsou textové řetězce a chceme najít všechny indexy (neboli pozice) od kterých začíná jehla j v seně s, tedy všechny počáteční pozice hledaného slova v textu.

Brute-force řešení problému

Řekněme, že máme n znaků v řetězci. Velikost jehly je j. Můžeme vzít for-cyklus ve for-cyklu a zkoušet 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 se podívat na časovou složitost. Algoritmus pro každé i z n pojede j-krát. Časová složitost je tedy O(n*j). Dá se to dělat lépe? Kdy tento algoritmus provádí zbytečnou práci navíc?

Efektivnější přístup

Představme si, že hledáme v textu ten kokos. Mějme seno nejkokokokosovatější. Můžeme si uvědomit, že když přečteme ko, pak hledáme už jen výraz kos. Pokud přečteme koko, stačí nám už jen s. Co se ale stane v momentě, kdy přečteme další k? Nemusíme přeci zahazovat celý řetězec. Sice máme teď přečtené slovo kokok, ale můžeme vypustit první dva znaky a budeme mít přečtené opět kok. Dále přečteme o a pokud přečteme zase k, postup se opakuje. Pokud však přečteme s, máme hledaný kokos. Uvědomíme si, že se nyní nevracíme a ze vstupního sena čteme vždy další a další znak. Každý znak ze sena přečteme jen jednou. Jediné, co procházíme, je jehla, neboť procházíme jehlu od začátku a odsekáváme prefixy, které víme, že už nebudou užitečné. Nakonec můžeme odseknout celou jehlu, pokud po koko přečteme 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 se tedy ve slově vyskytoval pouze jednou. Každý znak ze sena jsme prošli právě jednou. značka | znázorňuje část slova, kterou jsme převzali z doposud přečteného slova.

Algoritmus

Bohužel se zde nevyhneme pojmu automat. Berte to nyní pouze tak, že postavíme jakýsi parser, který sám bude rozhodovat, zda slovo odsekne nebo znak připojí k již nalezenému prefixu hledaného slova. Pokud máte za sebou teorii automatů, tak v KMP algoritmu využíváme konečný stavový automat.

Sestavení automatu

Prvním krokem bude postavit automat pro naši jehlu. Budeme chtít postavit nějakou krabičku, která se bude sama starat o to, kam se jehla posouvá:

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 jako pole. Vstupem pro funkci bude jehla. Chceme postavit funkci ReturnFunction, neboli návratovou funkci, která se rozhodne pro to, kam se posunout pro přečtený znak. Pro první znak nemá návratová funkce smysl. Pokud je jehla větší než 1, pak pro pole v indexu 1 se vracíme do nuly. Toto odpovídá situaci, kdy jsme chtěli přečíst slovo kokos a přečetli jsme znak m. Vracíme se tedy na začátek. Pro další stavy pošleme stav do KMPStep(), kterému "řekneme", co hledáme, ve kterém jsme stavu a jaký symbol jsme přečetli. Poté co sestavíme automat, neboli budeme mít řečeno pro jaká písmena se kam vracíme, označíme si, že jsme automat sestavili. Díky tomu můžeme využívat funkci KMPStep() bez toho, aby se znova stavěl už postavený automat.

Pattern je naše jehla. Máme již nadefinovanou návratovou funkci. Návratová funkce pro znak určí, o kolik se má v přečtené jehle vrátit.

[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 funkcí 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 odpovídá tomu, že pokud písmeno x není v jehle na pozici [stav], neboli na 4. pozici není kupříkladu písmeno s, musíme se tedy vrátit zpět. Odpovídá to našemu znaku k, když jsme přečetli slovo koko. Pokud bychom přečetli s, automat by se nevracel a cyklus while by neproběhl ani jednou. Pokud jsme našli shodu, jehla se posune o pozici doprava zvednutím stavu. AfterBuildingAutomat je proměnná, která nám řekne, jestli jsme už automat sestavili, nebo ne. Tu samou funkci potom budeme používat při hledání řetězce, zatím si toho nevšímejme.

Použití algoritmu

Nyní máme sestavený automat a máme definováno, co se stane, když KMP dostane znak ve funkci KMPStep(). Nyní už nám stačí mít na vstupu seno a jehlu. Všechny potřebné nástroje již 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;
}

Nejdříve si postavíme automat. Zavedeme si dynamické pole indexů. Je-li pole na konci prázdné, jehla v seně nebyla. Potom máme jeden cyklus for, kterým projdeme seno. Jestliže nám funkce KMPStep() vrátí stav, který se rovná délce jehly, víme, že jsme našli vhodné slovo. Snížíme stav (kvůli indexování pole od 0) a přidáme index slova, kde jehla začíná. Poté ještě zavoláme návratovou funkci, protože přečteme-li slovo kuchtík, tak jsme zároveň přečetli i znak k pro slovo kuchtíkuchtíkuchtík a algoritmus bezpečně odhalí všechny výskyty tohoto slova.

Zhodnocení algoritmu

Proč to vlastně všechno děláme? Pomohli jsme si oproti původnímu algoritmu brute-force? Rozhodně. Časová složitost nového algoritmu je O(j + s), kde j je délka jehly a s je délka sena. Hledáme-li nějaké jméno v několikagigovém textovém souboru, rozdíl rychlostí je očividný.

Co ale dělat pokud bychom v textu chtěli najednou najít více slov? Hlavě taková jako potok, popel, potopení, popelník... Pokaždé na celý text pouštět KMP by bylo neefektivní. V dalším článku se tedy podíváme, jak se vyhledá více jehel v jednom seně mnohem efektivněji.

V další lekci, Binární vyhledávací strom (BST), si popíšeme algoritmus vyhledávací struktury binárního vyhledávacího stromu (BST) s obrázky a teorií.