Aho-Corasick algorithm
Encyclopedia : A : AH : AHO : Aho-Corasick algorithm
The Aho-Corasick algorithm is a string searching algorithm discovered by Alfred V. Aho and Margaret J. Corasick. It is a kind of dictionary-matching algorithm that locates elements of a finite set of patterns (the "dictionary") within an input text. It matches all patterns "at once", so the complexity of the algorithm is linear in the size of the patterns plus the size of the search string.
Informally, the algorithm constructs a finite automaton first and then applies that automaton to the input text. When the pattern dictionary is known in advance (e.g. a computer virus database), the construction of the automaton can be performed once off-line and the compiled automaton stored for later use.
The Aho-Corasick algorithm forms the basis of the Unix command fgrep.
Sources
- (Access to the full text may be restricted.)
External links
- [Animation of the Aho/Corasick Pattern Matching Automaton]
- [Set Matching and Aho-Corasick Algorithm] by Pekka Kilpeläinen
- [Aho-Corasick string matching in C#] by Tomáš Petříček ([mirror])
- [Aho-Corasick entry] in NIST's [Dictionary of Algorithms and Data Structures]
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.