Kaksoistaulukkoisen Aho–Corasick-automaatin optimoinnit

Abstract

Aho–Corasick-algoritmi ratkaisee usean hahmon samanaikaisen etsinnän ongelman rakentamalla äärellisen automaatin, joka tunnistaa kaikki hahmojen esiintymät yhdellä tekstin läpikäynnillä. Kaksoistaulukkoesitys on tiivis ja välimuistiystävällinen vaihtoehto automaatin tilasiirtymien tallentamiseen. Esitykselle on ehdotettu lukuisia toteutustapoja, mutta käytännön suorituskyvyssä on edelleen useita haasteita. Ensinnäkin konstruointivaihe nojaa tyypillisesti väliaikaiseen trie-rakenteeseen, mikä aiheuttaa suuren väliaikaisen muistihuipun ja hidastaa konstruointia suurilla hahmojoukoilla. Toiseksi tilojen sijoittelu kaksoistaulukkoon edellyttää vapaan paikan etsintää, jonka kustannus kasvaa taulukon täyttyessä. Kolmanneksi sovitusvaiheessa merkittävä osa tilasiirtymistä on olemattomia, ja kukin niistä aiheuttaa turhan muistiviittauksen, joka kuormittaa välimuistia edistämättä hakua.

Tässä tutkielmassa kehitetään kolme toisiaan täydentävää optimointia kaksoistaulukkoiselle Aho–Corasick-automaatille. Ensimmäinen on välimuistioptimoitu suora konstruointimenetelmä, joka poistaa väliaikaisen trie-rakenteen osittamalla hahmot ja johtamalla tilasiirtymät suoraan ositetusta syötteestä kaksoistaulukkoon, mikä pienentää muistihuippua ja nopeuttaa konstruointia. Toinen tehostaa vapaan paikan etsintää bittitason rinnakkaisuudella, mikä mahdollistaa useiden ehdokaspaikkojen samanaikaisen testaamisen yhdellä laskutoimituksella. Kolmas lisää kuhunkin tilaan kevyen suodattimen, joka ohittaa olemattomat tilasiirtymät ja parantaa siten sovitusvaiheen välimuistikäyttäytymistä. Optimoinnit säilyttävät alkuperäisen algoritmin oikeellisuuden ja asymptoottisen aikavaativuuden.

Kokeellisessa arvioinnissa suora konstruointi osoittautuu jopa 5,9 kertaa nopeammaksi kuin trie-pohjainen menetelmä, ja samalla muistihuippu pienenee jopa 69 %. Bittirinnakkainen hakustrategia tuottaa 2,5–3,5-kertaisen nopeutuksen vapaan paikan etsinnässä. Siirtymäsuodatin karsii 23–46 % olemattomista tilasiirtymistä, vähentää välimuistihuteja johdonmukaisesti kaikilla aineistoilla ja nopeuttaa sovitusta jopa 16 % fraasihahmoilla, kun taas sanatasoisilla aineistoilla nopeusvaikutus jää vähäiseksi. Tuloksista voidaan päätellä, että kohdennetuilla rakenteellisilla ja algoritmisilla parannuksilla kaksoistaulukon toteutukseen voidaan merkittävästi tehostaa Aho–Corasick-automaatin käytännön suorituskykyä niin konstruointi- kuin sovitusvaiheessakin.