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
[editovat | editovat zdroj]- 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
[editovat | editovat zdroj]- Obrázky, zvuky či videa k tématu Algoritmus Aho-Corasick na Wikimedia Commons
- Implementace v ActionScript 3, stavba a vykreslení automatu v reálném čase (flash)