Science Fair Project Encyclopedia
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 algorithms that locates elements of a finite set of patterns (the "dictionary") within an input text.
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
- Alfred V. Aho and Margaret J. Corasick. Efficient string matching: An aid to bibliographic search. Communications of the ACM 18(6):333–340, June 1975. Further details and full text at the ACM Digital Library site
Last updated: 07-29-2005 20:55:24
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details