Optimizing Regular Expression Matching Using Advanced Finite Automata Techniques

Abstract

Regular expression matching is an essential function for text manipulation, network security protocols, bioinformatics, log analysis, or tools used by programming languages. Naive matching algorithms are easy to implement but can be slow when dealing with large texts, complex patterns, or patterns designed to defeat the matching software.While regular expressions are a concise and expressive way of describing patterns, naive algorithms can become very slow when applied to long texts, patterns of considerable complexity, or patterns that are designed to circumvent the matching software. This paper reviews in detail the optimization of regular expression matching using advanced techniques in finite automata such as nondeterministic finite automata simulation, construction and minimization of deterministic finite automata, hybrid automata, lazy compilation, and parallel processing. The paper summarizes the basic algorithms available and points out important compromises to be made between compilation time, memory usage, matching speed, and the ability to handle sophisticated expression capabilities. A repeatable approach to comparing automata-based matching engines is proposed for both synthetic and application-specific loadsets. This analysis suggests that there is no single representation which works best for all workloads, and that high-performance systems should choose or mix representations adaptively, depending on the complexity of the expression, characteristics of the input, memory limitation, and required latency.