Efficient Matching of Regular Expressions with Lookaround Assertions
summary
States a formal semantics for lookaround, gives an algorithm that matches regexes with lookaround in O(m·n) time by evaluating assertions bottom-up, and implements a new automaton model called oracle-NFAs that consult precomputed oracle tapes for truth values at each position. Memory is dominated by storing per-assertion tapes (growing with K·n), unidirectional patterns need only a single pass, and experiments report linear time where the optimized implementation is tens to thousands of times faster than PCRE/Java on tested workloads.
AI-written summary · about
chapters (12)
- 0:00Regex with lookaround
- 1:47Lookaround examples
- 4:17Formal semantics for lookaround
- 7:32Regex matching limits
- 9:17Automata challenges
- 9:58Efficient lookaround algorithm
- 12:33Oracle NFA memory
- 13:57Algorithm complexity
- 14:18Optimizing unidirectional regex
- 15:21Performance results
- 16:25Summary and conclusions
- 17:09Q&A on back references
related talks
29mVerified and Efficient Matching of Regular Expressions with Lookaround
51mRegular Expressions in C++, Present and Future
37mAll About Regular Expressions
14mRegex Matching with Counting-Set Automata
22mStatic Analysis for Checking the Disambiguation Robustness of Regular Expressions
24mSolving String Constraints with Regex-Dependent Functions through Transducers wi
18mRegular Expression Matching using Bit Vector Automata
01h 03mCompile-Time Regular Expressions