The Prague Stringology Conference 2006
Ernest Ketcha Ngassam, Derrick G. Kourie and Bruce W. Watson
On Implementation and Performance of Table-Driven DFA-Based String Processors
| Abstract: |
| 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. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |