File AhoCorasick.h

↰ Parent directory (ADS/string)

The search of many patterns at once, beyond the book: the automaton of Aho and Corasick of a set of patterns :math:` P_0 , ldots , P_{k-1} ` of M bytes in all finds all their occurrences in a text T of n bytes in one scan, :math:` O( n + mathit{occ} ) ` time.

Definition (ADS/string/AhoCorasick.h)

Detailed Description

The states are the nodes of the trie of the patterns, a state being the string u spelt from the root to it. The failure of u is the state of the longest proper suffix of u that is in the trie, computed in breadth first order from :math:` mathit{fail}( u c ) = delta( mathit{fail}( u ) , c ) `; with it the automaton is made deterministic, :math:`[

delta( u , c ) = left{ begin{array}{ll}

u c & mbox{if } u c mbox{ is in the trie} \ delta( mathit{fail}( u ) , c ) & mbox{otherwise, } u ne

varepsilon \

varepsilon & mbox{otherwise,}

end{array} right.

` a table of 256 transitions per state, so that a byte of T costs one lookup, after a preparation of :math:` O( 256 M ) ` time and space. After reading :math:` T[ 0 .. j ] ` the state is the longest suffix of it that is a prefix of some pattern (the invariant of the automaton), and the patterns that end at j are those of the state and of the chain of its output links, each the nearest proper suffix of a state that is a whole pattern, so that each occurrence costs O( 1 ).

add() gives each pattern its number, in the order of the calls (equal patterns get one number each); build() prepares the automaton, which findAll() and count() then use: findAll() gives the pairs ( start , number ) of the occurrences, by increasing end, and the longer pattern first for one end. The empty pattern is not allowed.

The contracts [see File Contract.h]: a pattern is not empty, and no search comes before build(); findAll() gives, for each pattern, the occurrences of naiveMatching() [see File StringMatching.h] (an audit). The functions are defined in AhoCorasick.tpp.

    1. Aho, M. J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM 18(6), 333-340, 1975, doi:10.1145/360825.360855

  1. Gusfield, Algorithms on Strings, Trees and Sequences, Cambridge University Press, 1997, section 3.4, doi:10.1017/CBO9780511574931

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes