Reordering finite automata states for fast string recognition
Ernest Ketcha Ngassam, Derrick G. Kourie, Bruce W. Watson · TU/e Research Portal · 2005
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.