ON IMPLEMENTATION AND PERFORMANCE OF TABLE-DRIVEN DFA-BASED STRING PROCESSORS
Ernest Ketcha Ngassam, Derrick G. Kourie, Bruce W. Watson · International Journal of Foundations of Computer Science · 2008
Table-driven (TD) DFA-based string processing algorithms are examined from a number of vantage points. Firstly, various strategies for implementing such algorithms in a cache-efficient manner are identified. The denotational semantics of such algorithms is encapsulated in a function whose various arguments are associated with each implementation strategy. This formal view of the implementation strategies suggests twelve different algorithms, each blending together the implementation strategies in a particular way. The performance of these algorithms is examined in against a set of artificially generated data. Results indicate a number of cases where the new algorithms outperform the traditional TD algorithm.