2001 | OriginalPaper | Buchkapitel
Compact DFA Representation for Fast Regular Expression Search
verfasst von : Gonzalo Navarro, Mathieu Raffinot
Erschienen in: Algorithm Engineering
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present a new technique to encode a deterministic finite automaton (DFA). Based on the specific properties of Glushkov’s nondeterministic finite automaton (NFA) construction algorithm, we are able to encode the DFA using (m+ 1)(2m+1 + |Σ|) bits, where m is the number of characters (excluding operator symbols) in the regular expression and Σ is the alphabet. This compares favorably against the worst case of (m + 1)2m+1|Σ| bits needed by a classical DFA representation and m(22m+1 + |Σ|) bits needed by the Wu and Manber approach implemented in Agrep.Our approach is practical and simple to implement, and it permits searching regular expressions of moderate size (which include most cases of interest) faster than with any previously existing algorithm, as we show experimentally.