TOOLS FOR VERY FAST REGULAR EXPRESSION MATCHING

DotStar is an innovative algorithmic solution that compiles user-provided regular expressions into a compact automaton using a sequence of more manageable intermediate representations. The system can search using a single pass without backtracking, and is both space and time efficient. The entire software tool chain supports the extended Posix standard syntax for regex. At the core of DotStar is a large class of regex that DotStar tools can compile into an Aho-Corasick automaton, the de facto standard for keyword scanning, going through a series of intermediate representations that include the Glushkov automaton. The DotStar tool chain comprises five elements, a classification engine/preprocessor, an expander, a compiler, a compactor and a runtime engine. The DotStar preprocessor examines the regex set, recognizing the problematic parts, and the expander fragments them into multiple DotStar expressions. The expander allocates a minimal set of add-on data items and annotates expressions with set and test operations.