Selective Memoization for Efficient Backtracking Regular Expression Matching
For regex matching practitioners, this provides a practical trade-off between speed and memory, though incremental over existing memoization approaches.
Backtracking regex matchers can be exponential; selective memoization via Minimum Feedback Node (MFN) scheme ensures linear time with reduced memory, outperforming full memoization.
Backtracking regular expression matchers are widely used due to their expressive power but may exhibit exponential worst-case matching time. Memoization provides a principled method for eliminating redundant computation and ensuring linear matching time, but full memoization is memory-intensive and impractical. We introduce the Minimum Feedback Node (MFN) memoization scheme, a selective memoization strategy based on computing a minimum feedback vertex set of an automaton. We establish relationships with existing memoization schemes and analyze their behaviour under both Thompson and Glushkov automaton constructions.