Access Restriction

Author Aho, Alfred V. ♦ Corasick, Margaret J.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Bibliographic search ♦ String pattern matching ♦ Text-editing ♦ Information retrieval ♦ Keywords and phrases ♦ Computational complexity ♦ Finite state machines
Abstract This paper describes a simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text. The algorithm consists of constructing a finite state pattern matching machine from the keywords and then using the pattern matching machine to process the text string in a single pass. Construction of the pattern matching machine takes time proportional to the sum of the lengths of the keywords. The number of state transitions made by the pattern matching machine in processing the text string is independent of the number of keywords. The algorithm has been used to improve the speed of a library bibliographic search program by a factor of 5 to 10.
Description Affiliation: Bell Labs, Murray Hill, NJ (Aho, Alfred V.; Corasick, Margaret J.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 18
Issue Number 6
Page Count 8
Starting Page 333
Ending Page 340

Open content in new tab

   Open content in new tab
Source: ACM Digital Library