Fast String Matching for Analytics Pipelines

The difference between a DAWG and the minimized deterministic dictionary automaton is the way they are constructed. Otherwise, the resulting automata should be very similar in size, and of course their running times will be the same. Note that, we build the automata offline.

The main advantage of using general purpose automata becomes clear when we are able to reuse the codebase and the pipelines we built for a dictionary automaton to both build and execute a search automaton. Otherwise, a generalized suffix tree would have done the job at least as well.

In addition, when we have general purpose automata combined with a powerful tool like OpenFST, we can compose the automata with transducers, and the resulting automata will transform the input strings as we are matching them.