Efficient String Matching: An Aid to Bibliographic Search
📜 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.
✨ Summary
Contribution
The paper introduces what is now commonly called the Aho–Corasick algorithm, a finite-state method for finding all occurrences of multiple keywords in a text in a single scan. It constructs a trie-like goto graph from the keyword set, adds failure transitions that identify the longest usable suffix after a mismatch, and associates output sets with states so that overlapping and nested matches can be reported.
The construction requires time proportional to the total length of the keywords. During matching, the algorithm performs exactly one successful goto transition per input character and fewer than twice as many total state transitions when failure transitions are included. The paper also presents a deterministic finite-automaton variant that precomputes failure behavior and therefore performs one transition per input character, at the cost of additional memory. Output generation remains proportional to the number and size of the matches that must actually be reported.
The motivating application was a Bell Laboratories bibliographic search system. Replacing successive per-keyword matching with the finite-state method reduced measured CPU time from 0.79 to 0.18 hours for a 15-keyword query and from 1.27 to 0.21 hours for a 24-keyword query, consistent with the paper’s reported five- to ten-fold improvement.
Subsequent influence
The paper became the foundational reference for exact multi-pattern string matching. Later research has extended the algorithm through multicore and GPU implementations, including failureless variants for large-scale DNA-sequence matching and other high-volume workloads. (arxiv.org)
The algorithm also remains part of contemporary production-oriented software. The Rust aho-corasick implementation develops the original trie, failure-transition, and automaton ideas into sparse and dense NFA/DFA representations, streaming search, overlapping matches, regex-compatible match semantics, and SIMD-assisted prefilters. (github.com) Independent current implementations continue to reproduce the original algorithms and cite the 1975 paper directly, demonstrating its continuing role as a reference design for multi-pattern search libraries. (github.com)
The bibliographic publication details and abstract are independently consistent with catalog metadata for Communications of the ACM 18(6), published in June 1975. (cir.nii.ac.jp)