Finite (nondeterministic) automata are very useful building blocks in the field of string matching. This is particularly true in the case of multiple pattern matching, where the use of factor-based automata can reduce substantially the number of computational steps when the patterns have large common factors. Direct simulation of nondeterministic automata can be performed very efficiently using the bit-parallelism technique, though this is not necessarily true for factor-based automata. In this paper we present an algorithm for the multiple string matching problem, based on the bit-parallel simulation of nondeterministic factor-based automata which satisfy a particular ordering condition. We also show how to enforce such condition by suitably modifying a minimal initial automaton, through equivalence preserving transformations. The resulting automaton turns out to be smaller than the corresponding maximal automata used by existing bit-parallel algorithms, as they do not take any advantage of common factors in patterns.
|Titolo:||A Space Efficient Bit-Parallel Algorithm for the Multiple String Matching Problem|
|Autori interni:||FARO, SIMONE|
|Data di pubblicazione:||2006|
|Rivista:||INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE|
|Appare nelle tipologie:||1.1 Articolo in rivista|