The Prague Stringology Conference 2005

Ernest Ketcha Ngassam, Derrick G. Kourie and Bruce W. Watson

Reordering Finite Automata States for Fast String Recognition

The spatial and temporal locality of reference on which cache memory relies to minimize cache swaps, is exploited to design a new algorithm for finite automaton string recognition. It is shown that the algorithm, referred to as the state reordering algorithm, outperforms the traditional table-driven algorithm for strings that tend to repeatedly access the same set of states.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF