Aho-Corasick-algoritmi

KMP- ja BMH-algoritmit soveltuvat vain yhden hahmon etsimiseen kerrallaan. Kuitenkin yleensä on annettu useampia hakusanoja, jotka kaikki täytyy löytää yhdellä tekstin läpikäynnillä. Aho-Corasick-algorimi on KMP-algoritmin yleistys, joka mahdollistaa useamman kuin yhden hahmon etsimisen tekstistä tehokkaasti. Olkoon annettu hahmojoukko $\mathbf{P} = \{P_1, P_2, ...,P_k\}$. Merkitään $\mathbf{P}$:n hahmojen yhteenlaskettua pituutta $\vert \mathbf{P} \vert= \sum_{i=1}^{k} m_i$. Aho-Corasick-algoritmissa muodostetaan $\mathbf{P}$:stä kuvassa 2 esitetyn kaltainen äärellinen jononsovitusautomaatti $Q_{\mathbf{P}}$ .

Kuva: AC-automaatti $Q_{\mathbf{P}}$ kun $\mathbf{P} = \{ he, she, his, hers \}$

Muodostettavan äärellisen automaatin siirtymät muodostavat $\mathbf{P}$:stä trie-rakenteen (lisää trie-puista kerrotaan luvussa 5.1). Jokaisella siirtymällä luetaan tekstistä yksi merkki. Mikäli luetulla merkillä ei ole siirtymää, suoritetaan korjaussiirtymä (merkitty kuvassa 2 katkoviivalla).

AC-algoritmin automaatti $Q_{\mathbf{P}}$ toteutetaan kolmen funktion avulla.

1. Varsinaiset siirtymät sisältävä funktio $goto[j,a]$. Tilasta $q_j$ siirrytään merkillä $a$ tilaan $goto[j,a]$.
2. Korjaussiirtymät sisältävä funktio $fail[j]$. Jos $goto[j,a] = \emptyset$ vuorossa olevalla tekstimerkillä $a$, siirrytään tilaan $fail[j]$.
3. Tulostusfunktio $output[j]$, joka sisältää listan automaatin tilassa $j$ tulostettavista hahmoista. (Kuvan 2 tiloissa 2 ja 5 tulostetaan ``he'', tilassa 5 tulostetaan myös ``she'', tilassa 7 ``his'' ja tilassa 8 ``hers''.)

$goto$-, $fail$- ja $output$-funktiot voidaan yleensä toteuttaa taulukkoina. Mikäli aakkoston koko $\vert\Sigma\vert$ on hyvin suuri, ei $goto[j,c]$-funktiota voi enää toteuttaa pelkkänä taulukkona, koska merkillä $c$ indeksoitavan taulukon koko kasvaisi liian suureksi. Tällöin täytyy ottaa käyttöön jokin muu yleisesti käytetty hakutietorakenne (esim. lista, hajautustaulu, järjestetty taulukko, ...).

AC-algoritmin jononsovitusautomaatti suorittaa vähemmän kuin $2n$ tilasiirtymää selatessaan tekstin. Suoritettavien tilasiirtymien määrä ei ole riippuvainen hahmojen lukumäärästä $k$. Algoritmin aikavaatimukseen vaikuttaa tilasiirtymien lisäksi yhden tilasiirtymän suoritukseen tarvittavien operatioiden aikavaatimukset:

1. $goto[q,a]$:n evaluointi $O(\vert\Sigma\vert)$
2. $fail[q]$:n evaluointi $O(1)$
3. testaus $output[q]=\emptyset$
4. Löytyneiden esiintymien käsittely?

Mikäli kaikki funktiot ( $goto, fail, output$) voidaan esittää taulukkoina, AC-algoritmin aikavaatimus on $O(n)$, mikäli löytyneiden esiintymien käsittelyyn tarvittavaa aikaa ei oteta huomioon. Jos $k$ tai $\vert\Sigma\vert$ ovat hyvin suuria, voidaan joutua käyttämään hakutietorakenteita, jolloin haun aikavaatimukseksi käytännössä tulee $O(n \log min(k,\vert\Sigma\vert))$.