Tietojenkäsittely Ja Tietokannat
Valloita merkkijonohaku Aho-Corasick-algoritmilla
Merkkijonojen manipulointi ja kuvioiden löytäminen niistä ovat perustietoja tietojenkäsittelyssä ja tyypillinen tehtävä kaikille ohjelmoijille.
Tehokkailla merkkijonoalgoritmeilla on tärkeä rooli monissa tietojenkäsittelyprosesseissa. Ne tekevät usein tällaisista prosesseista riittävän toteutettavissa käytännön käyttöön.
Tässä artikkelissa opit yhdestä tehokkaimmista algoritmeista kuvioiden löytämiseksi suuresta määrästä tekstiä: Aho-Corasick-algoritmista. Tämä algoritmi käyttää a trie-tietorakenne (lausutaan 'yritä') hakumallien seuraamiseksi ja käyttää yksinkertaista tapaa löytää kaikki tietyn kuviosarjan esiintymät mistä tahansa tekstikuplasta.
Aikaisempi ApeeScape Engineering -blogin artikkeli osoitti merkkijonohakualgoritmin samalle ongelmalle. Tässä artikkelissa käytetty lähestymistapa tarjoaa paremman laskennallisen monimutkaisuuden.
Knuth-Morris-Pratt (KMP) -algoritmi
Ymmärtääksemme kuinka voimme tehokkaasti etsiä useita kuvioita tekstistä, meidän on ensin puututtava helpompaan ongelmaan: yhden mallin löytäminen annetusta tekstistä.
Oletetaan, että meillä on suuri pituinen teksti N ja kuvio (jonka haluamme löytää tekstistä), jonka pituus on M . Jos haluamme etsiä tämän mallin yksittäisen esiintymän tai kaikki esiintymät, voimme saavuttaa laskennallisen monimutkaisuuden O (N + M) käyttämällä KMP-algoritmia.
Etuliite-toiminto
KMP-algoritmi toimii laskemalla etsimäsi mallin etuliitetoiminto. Etuliite-toiminto laskee etukäteen vaihtoehtoisen sijainnin jokaiselle kuvion etuliitteelle.
Määritetään hakumallimme merkkijonoksi, merkitty S Kullekin alimerkkijonolle S [0..i], missä i> = 1, löydetään tämän merkkijonon suurin etuliite, joka on myös tämän merkkijonon loppuliite. Merkitään tämän etuliitteen pituus P [i]
'Abracadabra' -kuvion etuliitefunktio tuottaisi seuraavat taustapaikat:
Hakemisto (i) | 0 | yksi | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Merkki | että | b | r | että | c | että | d | että | b | r | että |
Etuliitteen pituus (P[i]) | 0 | 0 | 0 | yksi | 0 | yksi | 0 | yksi | 2 | 3 | 4 |
Etuliitetoiminto tunnistaa mielenkiintoisen piirteen kuviosta.
Otetaan esimerkkinä tietty mallin etuliite: 'abrakadabi'. Tämän etuliitteen etuliitefunktion arvo on kaksi. Tämä osoittaa, että tälle etuliitteelle “abracadab” on olemassa kahden pituinen pääte, joka täsmää täsmälleen kahden pituisen etuliitteen kanssa (ts. Kuvio alkaa ”ab” ja etuliite loppuu “ab”). Tämä on myös tämän etuliitteen pisin ottelu.
Toteutus
Tässä on C # -funktio, jota voidaan käyttää minkä tahansa merkkijonon etuliitetoiminnon laskemiseen:
public int[] CalcPrefixFunction(String s) { int[] result = new int[s.Length]; // matriz con valores de función de prefijo result[0] = 0; // la función de prefijo siempre es cero para el primer símbolo (su caso degenerado) int k = 0; // valor actual de la función de prefijo para (int i = 1; i 0 && s[i] != s[k]) k = result[k - 1]; if (s[k] == s[i]) k++; // hemos encontrado el prefijo más largo - caso 1 result[i] = k; // almacenar este resultado en la matriz } resultado de devolución; } Suoritettaessa tätä toimintoa hieman pidemmällä kaavalla 'abcdabcabcdabcdab' tuottaa tämän:
Hakemisto (i) | 0 | yksi | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | yksitoista | 12 | 13 | 14 | viisitoista | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Merkki | että | b | c | d | että | b | c | että | b | c | d | että | b | c | d | että | b |
Etuliitteen toiminto (P[i]) | 0 | 0 | 0 | 0 | yksi | 2 | 3 | yksi | 2 | 3 | 4 | 5 | 6 | 7 | 4 | 5 | 6 |
Laskennallinen monimutkaisuus
Vaikka sisäkkäisiä silmukoita on kaksi, etuliitetoiminnon monimutkaisuus on yksinkertaisesti O (M) , missä M on kuvion pituus S .
Tämä voidaan helposti selittää tarkastelemalla silmukoiden toimintaa.
Kaikki ulomman silmukan iteraatiot i: n läpi Ne voidaan jakaa kolmeen tapaukseen:
-
Lisää
kyhdessä. Silmukka suorittaa yhden iteraation. -
Ei muuta
knollan arvoa. Silmukka suorittaa yhden iteraation. -
Se ei muuta tai vähennä
k: n positiivista arvoa.
Kaksi ensimmäistä tapausta voidaan suorittaa enintään M ajat.
Kolmannessa tapauksessa määritellään P (s, i) = k1 ja P (s, i + 1) = k2, k2 <= k1. Jokaista näistä tapauksista on edeltävä tapahtumia k1 - k2 ensimmäisestä tapauksesta. Laskujen määrä ei ylitä k1 - k2 + 1. Ja yhteensä meillä ei ole enempää kuin 2 * M iteraatiot.
Toisen esimerkin selitys
Katsotaanpa toista esimerkkikuviota 'abcdabcabcdabcdab'. Näin etuliitefunktio käsittelee sen askel askeleelta:
-
Tyhjälle alaosalle ja alaosan 'a' pituudelle yksi etuliitetoiminnon arvo asetetaan nollaksi. (
k = 0) -
Katso alaotsikkoa 'ab'. Nykyinen arvo
kon nolla ja merkki 'b' ei ole sama kuin merkki 'a'. Tässä meillä on toinen tapaus edellisestä osasta. Arvokpysyy nolla ja etuliitteen 'ab' etuliitetoiminnon arvo on myös nolla. -
Se on sama alaotsikoille 'abc' ja 'abcd'. Ei ole etuliitteitä, jotka olisivat myös näiden alaosien loppuliitteitä. Niiden arvo pysyy nolla.
-
Tarkastellaan nyt mielenkiintoista tapausta, alaotsikkoa 'abcda'. Nykyinen arvo
kse on edelleen nolla, mutta alimerkkimme viimeinen merkki vastaa sen ensimmäistä merkkiä. Tämä laukaisee ehdons [k] == s [i], jossak == 0jai == 4. Taulukon indeksi on nolla jakon enimmäispituisen etuliitteen seuraavan merkin hakemisto. Tämä tarkoittaa, että olemme löytäneet alimerkkimme enimmäispituuden etuliitteen, joka on myös pääte. Meillä on ensimmäinen tapaus, jossa uusi arvokon yksi, ja siksi etuliitefunktion arvo P ('abcda') Se on yksi. -
Sama tapaus esiintyy myös kahdella seuraavalla alaosalla, P ('abcdab') = 2 Y P ('abcdabc') = 3 . Täällä etsimme malliamme tekstistä vertaamalla merkkijonoja merkkikohtaisesti. Oletetaan, että kuvion seitsemän ensimmäistä merkkiä vastaavat noin seitsemää peräkkäistä käsiteltyä tekstiä, mutta kahdeksas merkki ei täsmää. Mitä pitäisi tapahtua seuraavaksi? Jos kyseessä on naiivi merkkijono-ottelu, meidän pitäisi palauttaa seitsemän merkkiä ja aloittaa vertailuprosessi uudelleen kuvion ensimmäisestä merkistä. Etuliitetoiminnon arvolla (tässä P ('abcdabc') = 3 ) tiedämme, että kolmen merkin jälkiliitteemme vastaa jo kolmea merkkiä tekstiä. Ja jos tekstin seuraava merkki on 'd', kuvion ja tekstialustan vastaavan alimerkinnän pituus kasvaa neljään ('abcd'). Päinvastoin, P ('abc') = 0 ja aloitamme vertailuprosessin mallin ensimmäisestä merkistä. Mutta tärkeä asia on, että emme palaa takaisin tekstinkäsittelyn aikana.
-
Seuraava alimerkkijono on 'abcdabca'. Yllä olevassa alaosassa etuliitefunktio oli yhtä suuri kuin kolme. Tämä tarkoittaa, että
k = 3on suurempi kuin nolla, ja samalla meillä on ristiriita etuliitteen seuraavan merkin (s [k] = s [3] = 'd') ja pääteosan seuraavan merkin (s [i] = s [7] ='a') välillä. Tämä tarkoittaa, että aktivoimmes [k]! =S [i]-ehdon ja että etuliite 'abcd' ei voi olla merkkijonomme loppuliite. Meidän pitäisi pienentääk-arvoa ja ota vertailu mahdollisuuksien mukaan yllä olevalla etuliitteellä. Kuten aiemmin kuvasimme, taulukon indeksi on nolla jakon seuraavan merkin hakemisto, jonka tarkistamme etuliitteestä. Tällä hetkellä vastaavan etuliitteen viimeinen hakemisto onk - 1. Otetaan etuliitteen funktion arvo parhaillaan vastaavalle etuliitteellek = resultado [k - 1]. Meidän tapauksessamme (kolmas tapaus) suurimman etuliitteen pituus pienennetään nollaan ja sitten seuraavalla rivillä se kasvaa yhdeksi, koska 'a' on suurin etuliite, joka on myös alimerkkimme loppuliite. -
(Täällä jatkamme laskentaprosessiamme, kunnes löydämme mielenkiintoisemman tapauksen.)
-
Alamme käsitellä seuraavaa alaosaa: 'abcdabcabcdabcd'. Nykyinen arvo
kon seitsemän. Kuten yllä olevan 'abcdabca': n kohdalla, olemme osuneet ei-vastaavuuteen: Koska merkki 'a' (seitsemäs merkki) ei ole sama kuin merkki 'd', alaotsikko 'abcdabca' ei voi olla merkkijonomme loppuliite. Nyt saamme jo lasketun arvon etuliitteen funktiosta 'abcdabc' (kolme) ja nyt meillä on osuma: etuliite 'abcd' on myös merkkijonomme loppuliite. Sen suurin etuliite ja etuliitetoiminnon arvo alimerkkijonollemme ovat neljä, koska se on nykyinen arvok -
Jatkamme tätä prosessia mallin loppuun asti.
Lyhyesti sanottuna: molemmat syklit vievät enintään 3 M iteraatiota, mikä osoittaa, että monimutkaisuus on O (M). Muistin käyttö on myös O (M).
KMP-algoritmin toteutus
public int KMP(String text, String s) { int[] p = CalcPrefixFunction(s); // Calcular la función de prefijo para una cadena de patrón // La idea es la misma que en la función de prefijo descrita anteriormente, pero ahora // estamos comparando prefijos de texto y patrón. // El valor del prefijo de longitud máxima de la cadena del patrón que se encontró // en el texto: int maxPrefixLength = 0; for (int i = 0; i 0 && text[i] != s[maxPrefixLength]) maxPrefixLength = p[maxPrefixLength - 1]; // Si ocurrió una coincidencia, aumenta la longitud de la longitud máxima // prefijo. if (s[maxPrefixLength] == text[i]) maxPrefixLength++; // Si la longitud del prefijo tiene la misma longitud que la cadena del patrón, // significa que hemos encontrado una subcadena coincidente en el texto. if (maxPrefixLength == s.Length) { // Podemos devolver este valor o realizar esta operación. int idx = i - s.Length + 1; // Obtenga el prefijo de longitud máxima anterior y continúe la búsqueda. maxPrefixLength = p[maxPrefixLength - 1]; } } return -1; } Yllä oleva algoritmi toistuu tekstin läpi, merkki kerrallaan, ja yrittää kasvattaa sekä mallin että tekstissä olevien peräkkäisten merkkien enimmäistunnusta. Epäonnistumisen yhteydessä emme palaa edelliseen sijaintiin tekstissä. Tiedämme mallin löydetyn alimerkkijonon suurimman etuliitteen; tämä etuliite on myös löydetyn alimerkin loppuliite, ja voimme vain jatkaa hakua.
Tämän funktion monimutkaisuus on sama kuin etuliitetoiminnolla, mikä tekee kokonaislaskennan monimutkaiseksi O (N + M) kanssa O (M) muisti.
Trivia: the
String.IndexOf ()jaString.Contains ().NET-kehyksessä heillä on saman monimutkainen algoritmi hupun alla.
Aho-Corasick-algoritmi
Nyt haluamme tehdä saman useille kuvioille.
Oletetaan, että on olemassa malleja M pituuksia L1 , L2 , ..., Lm . Meidän on löydettävä kaikki sanakirjan kuviot vastaavat tekstistä, jonka pituus on pitkä N .
Triviaali ratkaisu olisi ottaa mikä tahansa algoritmi ensimmäisestä osasta ja suorittaa se ** M ** kertaa. Meillä on monimutkaisuus O (N + L1 + N + L2 +… + N + Lm) , tarkoittaen (M * N + L) .
Jokainen tarpeeksi vakava testi tappaa tämän algoritmin.
Sanakirjan, jossa on 1000 yleisintä englanninkielistä sanaa, käyttäminen malleina ja sen käyttäminen Tolstoi “Sodan ja rauhan” englanninkielisen version etsimiseen vie jonkin aikaa. Kirjassa on yli kolme miljoonaa merkkiä.
Jos otamme 10000 yleisintä sanaa englanniksi, algoritmi toimii noin 10 kertaa hitaammin. Ilmeisesti tätä suuremmilla panoksilla myös toteutusaika kasvaa.
Tässä Aho-Corasick-algoritmi toimii taikuuksillaan.
Aho-Corasick-algoritmin monimutkaisuus on O (N + L + Z) , missä KANSSA on otteluiden määrä. Tämän algoritmin keksi Alfred V.Aho Y Margaret J.Corasick vuonna 1975.
Toteutus
Tarvitsemme trie: n ja lisäämme algoritmiin idean, joka on samanlainen kuin edellä kuvatut etuliitetoiminnot. Laskemme etuliitteen funktion arvot koko sanakirjalle.
Jokainen treen kärki tallentaa seuraavat tiedot:
public class Vertex { public Vertex() { Children = new Hashtable(); Leaf = false; Parent = -1; SuffixLink = -1; WordID = -1; EndWordLink= -1; } // Enlaces a los vértices secundarios en el trie: // Clave: Un solo caracter // Valor: El ID del vértice public Hashtable Children; // Indica que una palabra del diccionario termina en este vértice public bool Leaf; // Enlace al vértice padre public int Parent; // Char que nos mueve desde el vértice padre al vértice actual public char ParentChar; // Enlace de sufijo del vértice actual (el equivalente de P [i] del algoritmo KMP) public int SuffixLink; // Enlace al vértice de hoja de la palabra de longitud máxima que podemos hacer con el prefijo actual public int EndWordLink; // Si el vértice es la hoja, guardamos el ID de la palabra public int WordID; } Toissijaisia linkkejä on useita tapoja. Algoritmin monimutkaisuus on O (N + L + Z) matriisin tapauksessa, mutta tällä on ylimääräinen muistivaatimus O (L * q) , missä q on aakkosen pituus, koska tämä on suurin solmujen lasten määrä.
Jos käytämme jotain rakennetta O (log (q)) pääsy sen elementteihin, meillä on ylimääräinen muistivaatimus O (L) , mutta koko algoritmin monimutkaisuus on O ((N + L) * log (q) + Z) .
Hash-taulukon tapauksessa meillä on O (L) lisämuistia, ja koko algoritmin monimutkaisuus tulee olemaan O (N + L + Z) .
Tämä opetusohjelma käyttää hash-taulukkoa, koska se toimii myös erilaisten merkistöjen, esimerkiksi kiinalaisten merkkien kanssa.
Meillä on jo kärjen rakenne. Seuraavaksi määritämme luettelon pisteistä ja aloitamme treen juurisolmun.
public class Aho { List Trie; List WordsLength; int size = 0; int root = 0; public Aho() { Trie = new List(); WordsLength = new List(); Init(); } private void Init() { Trie.Add(new Vertex()) size++; } } Sitten lisätään kaikki kuviot trieen. Tätä varten tarvitsemme menetelmän sanojen lisäämiseksi trieen:
public void AddString(String s, int wordID) { int curVertex = root; for (int i = 0; i Tässä vaiheessa kaikki kuviosanat ovat tietorakenteessa. Tämä vaatii lisämuistia O (L) .
Seuraavaksi meidän on laskettava kaikki pääte- ja sanakirjolinkit.
Jotta se olisi selkeä ja helppo ymmärtää, aion käydä läpi trie juuristamme lehtiin ja tehdä laskelmia, jotka ovat samanlaisia kuin teimme KMP-algoritmille, mutta toisin kuin KMP-algoritmi, jossa löydämme myös etuliitteen enimmäispituuden, joka oli myös saman alimerkkijänteen loppuosa, nyt löydämme nykyisen alimerkkijonon enimmäispituuden jälkiliitteen, joka on myös jonkin treen kuvion etuliite. Tämän toiminnon arvo ei ole löydetyn jälkiliitteen pituus; on linkki nykyisen alimerkkijonon maksimiliitteen viimeiseen merkkiin. Tätä tarkoitan kärkipisteen linkkiliitteellä.
Käsittelen pisteet tason mukaan. Tätä varten käytän algoritmia etsi leveyden mukaan (BFS) :
Ja alla on tämän crossoverin toteutus:
public void PrepareAho() { Queue vertexQueue = new Queue(); vertexQueue.Enqueue(root); while (vertexQueue.Count > 0) { int curVertex = vertexQueue.Dequeue(); CalcSuffLink(curVertex); foreach (char key in Trie[curVertex].Children.Keys) { vertexQueue.Enqueue((int)Trie[curVertex].Children[key]); } } } Ja alla on menetelmä CalcSuffLink laskea jokaisen kärjen loppuliite (eli etuliitteen funktion arvo jokaiselle trie: n alaosalle):
public void CalcSuffLink(int vertex) { // Processing root (empty string) if (vertex == root) { Trie[vertex].SuffixLink = root; Trie[vertex].EndWordLink = root; return; } // Procesamiento de hijos de la raíz (subcadenas de un caracter) if (Trie[vertex].Parent == root) { Trie[vertex].SuffixLink = root; if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; return; } // Los casos anteriores son casos degenerados en cuanto al cálculo de la función del prefijo; // el valor siempre es 0 y los enlaces al vértice raíz. // Para calcular el sufijo link para el vértice actual, necesitamos el sufijo // enlace para el padre del vértice y el personaje que nos movió a la // vértice actual. int curBetterVertex = Trie[Trie[vertex].Parent].SuffixLink; char chVertex = Trie[vertex].ParentChar; // Desde este vértice y su subcadena comenzaremos a buscar el máximo // prefijo para el vértice actual y su subcadena. while (true) { // Si hay una ventaja con el carácter necesario, actualizamos nuestro enlace de sufijo // y abandonar el ciclo if (Trie[curBetterVertex].Children.ContainsKey(chVertex)) { Trie[vertex].SuffixLink = (int)Trie[curBetterVertex].Children[chVertex]; break; } // De lo contrario, estamos saltando por enlaces de sufijo hasta que lleguemos a la raíz // (equivalente a k == 0 en el cálculo de la función de prefijo) o encontramos un // mejor prefijo para la subserie actual. if (curBetterVertex == root) { Trie[vertex].SuffixLink = root; break; } curBetterVertex = Trie[curBetterVertex].SuffixLink; // Go back by sufflink } // Cuando completamos el cálculo del enlace de sufijo para el actual // vertex, debemos actualizar el enlace al final de la palabra de longitud máxima // que se puede producir a partir de la subcadena actual. if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; } Tämän menetelmän monimutkaisuus on ** O (L) **; lapsikokoelman toteutuksesta riippuen monimutkaisuus voi olla ** O (L * log (q)) **.
Kompleksitesti on samanlainen kuin KMP-algoritmin kompleksisuuden etuliitteen funktiotesti.
Katsotaanpa seuraava kuva. Tämä on sanan trie-näyttö {abba, cab, baba, caab, ac, abac, bac} kaikki lasketut tietosi:
Trie-reunukset ovat tummansinisiä, loppulinkit ovat vaaleansinisiä ja sanakirjan jälkiliitteet ovat vihreitä. Sanakirjan merkintöjä vastaavat solmut on korostettu sinisellä.
Ja nyt tarvitsemme vain yhden menetelmän lisää: tekstilohkon käsittely, jota aiomme etsiä:
public int ProcessString(String text) { // Estado actual del valor int currentState = root; // Valor de resultado apuntado int result = 0; for (int j = 0; j Ja nyt tämä on käyttövalmis:
Syötteessä meillä on luettelo malleista:
List patterns; Ja etsi tekstiä:
string text; Ja tässä miten liimataan kaikki yhteen:
// Inicia la estructura trie. Como parámetro opcional podemos poner el aproximado // tamaño del trie para asignar memoria solo una vez para todos los nodos. Aho ahoAlg = new Aho(); for (int i = 0; i Ja se on! Nyt tiedät kuinka tämä yksinkertainen mutta tehokas algoritmi toimii!
Aho-Corasick on todella joustava. Hakumallien ei tarvitse olla vain sanoja, mutta voimme käyttää kokonaisia lauseita tai satunnaisia merkkijonoja.
Esitys
Algoritmi testattiin Intel Core i7-4702MQ -laitteella.
Testejä varten otin kaksi sanakirjaa: 1 000 yleisintä sanaa englanniksi ja 10 000 yleisintä sanaa englanniksi.
Jos haluat lisätä kaikki nämä sanat sanakirjaan ja valmistella tietorakenne toimimaan jokaisen sanakirjan kanssa, algoritmi vaati vastaavasti 55 ms ja 135 ms.
Algoritmi käsitteli 3-4 miljoonan merkin pituiset oikeat kirjat 1,0-1,3 sekunnissa, kun taas noin 30 miljoonan merkin kirjaan kului 9,6 sekuntia.
Yhdistä Aho-Corasick-algoritmi
Aho-Corasick-algoritmin rinnalle meneminen ei ole ollenkaan ongelma:
Suuri teksti voidaan jakaa useiksi paloiksi ja useiden säikeiden avulla voidaan käsitellä kutakin osaa. Jokaisella säikeellä on pääsy luotuun Trie-sanakirjaan.
Entä sanat, jotka on jaettu fragmenttien välisellä rajalla? Tämä ongelma voidaan ratkaista helposti.
Päästää N olla suuren tekstin pituus, S on fragmentin koko ja L olla sanakirjan suurimman kuvion pituus.
Nyt voimme käyttää yksinkertaista temppua. Jaamme palat päällekkäin, esimerkiksi ottamalla [S * (i - 1), S * i + L - 1], missä i on palan indeksi. Kun saamme mallivastaavuuden, voimme helposti saada nykyisen ottelun aloitusindeksin ja tarkistaa vain, että tämä indeksi on palojen alueella ilman päällekkäisyyksiä [S * (i - 1), S * i - 1].
Monipuolinen merkkijonohakualgoritmi
Aho-Corasick-algoritmi on tehokas merkkijono yhdistävä algoritmi, joka tarjoaa parhaan monimutkaisuuden mille tahansa syötteelle eikä vaadi paljon lisämuistia.
Algoritmia käytetään usein erilaisissa järjestelmissä, kuten oikeinkirjoituksen tarkistajissa, roskapostisuodattimissa, hakukoneissa, bioinformatiikassa / DNA-sekvenssien haussa jne. Itse asiassa jotkut suositut työkalut, joita voit käyttää päivittäin, käyttävät tätä algoritmia kulissien takana.
Itse KMP-algoritmin etuliitetoiminto on mielenkiintoinen työkalu, joka vähentää yksittäisen kuvion sovittamisen monimutkaisuuteen lineaariseen aikaan. Aho-Corasick-algoritmi noudattaa samanlaista lähestymistapaa ja käyttää trie-tietorakennetta tekemään sama useille kuvioille.
Toivottavasti pidit tämän opetusohjeen Aho-Corasick-algoritmista hyödyllisenä.
