Hledat:

Invia.cz Last minute Tunisko Dovolená v Chorvatsku Pojeďte do Egypta Bulharsko Last minute Kréta
 

Algoritmus Aho-Corasick

(přesměrováno z Algoritmus Aho-Corasickové, přímý odkaz na 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.

Externí odkazy[editovat | editovat zdroj]

 
Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „https://cs.wikipedia.org/w/index.php?title=Algoritmus_Aho-Corasick&oldid=9919801
Stránka byla naposledy upravena 13. 3. 2013 v 01:54. Editovat celý článek Algoritmus Aho-Corasickové.
Text je dostupný pod licencí Creative Commons Uveďte autora – Zachovejte licenci 3.0 Unported, případně za dalších podmínek. Podrobnosti naleznete na stránce Podmínky užití.
Další služby: Portál | Katalog | Hledej | Zprávy | Počasí | Kurzy | Práce | Slovník | TV | Online hry | Java hry | SMS | Loga a melodie | Chat | Fórum | Kontakt | Set-top-boxy