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.

PropertyValue
prop-cs:wikiPageUsesTemplate
dbpedia-owl:abstract
  • 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.
dbpedia-owl:wikiPageExternalLink
dbpedia-owl:wikiPageID
  • 270931 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 2015 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 10 (xsd:integer)
dbpedia-owl:wikiPageRevisionID
  • 9919801 (xsd:integer)
dbpedia-owl:wikiPageWikiLink
dbpedia-owl:wikiPageWikiLinkText
  • algoritmus Aho-Corasick
  • Algoritmus Aho-Corasick
dcterms:subject
rdfs:comment
  • 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.
rdfs:label
  • Algoritmus Aho-Corasick
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbpedia-owl:wikiPageRedirects of
is dbpedia-owl:wikiPageWikiLink of
is foaf:primaryTopic of