A compact representation of nondeterministic (suffix) automata for the bit-parallel approach

作者：Cantone Domenico; Faro Simone; Giaquinta Emanuele^*

来源：Information and Computation, 2012, 213: 3-12.

DOI：10.1016/j.ic.2011.03.006

We present a novel technique, suitable for bit-parallelism, for representing both the nondeterministic automaton and the nondeterministic suffix automaton of a given string in a more compact way. Our approach is based on a particular factorization of strings which on the average allows to pack in a machine word of w bits automata state configurations for strings of length greater than w. We adapted the Shift-And and BNDM algorithms using our encoding and compared them with the original algorithms. Experimental results show that the new variants are generally faster for long patterns.

• 出版日期2012-4