Algoritmus Aho-Corasick

Algoritmus Aho-Corasick je vyhledávací algoritmus vynalezený Alfredem Ahem a Margaret J. Corasickovou. Je to druh slovníkového vyhledávacího algoritmu, který ve vstupním textu hledá prvky konečné množiny řetězců. Vyhledává všechny prvky množiny najednou, jeho asymptotická složitost je proto lineární k délce všech vyhledávaných prvků plus délce vstupního textu plus délce výstupu. Jelikož algoritmus najde všechny výskyty, celkový počet výskytů pro celou množinu může být až kvadratický (například v případě, kdy vyhledávané řetězce jsou a, aa, aaa, aaaa a vstupní text je aaaa).

Neformálně řečeno, algoritmus konstruuje trie se zpětnými odkazy pro každý vrchol (například abc) na nejdelší vlastní sufix (pokud existuje, tak bc, jinak pokud existuje c, jinak do kořene). Obsahuje také odkazy z každého vrcholu na prvek slovníku obsahující odpovídající nejdelší sufix. Tudíž všechny výsledky mohou být vypsány procházením výsledného spojového seznamu. Algoritmus pak pracuje tak, že postupně zpracovává vstupní řetězec a pohybuje se po nejdelší odpovídající cestě stromu. Pokud algoritmus načte znak, který neodpovídá žádné další možné cestě, přejde po zpětném odkazu na nejdelší odpovídající sufix a pokračuje tam (případně opět přejde zpět).

Pokud je množina vyhledávaných řetězců známa předem (např. databáze počítačových virů), je možné zkonstruovat automat předem a ten pak uložit.

Literatura

  • MAREŠ, Martin; VALLA, Tomáš. Průvodce labyrintem algoritmů. 2. vyd. [s.l.]: CZ.NIC, z.s.p.o., 2022. 542 s. Dostupné online. ISBN 978-80-88168-63-8. Kapitola 13. 

Externí odkazy