RE#: High Performance Derivative-Based Regex Matching with Intersection, Complement and(…)

on YouTube ↗21m

" summary

RE# is a derivative-based regex engine built on symbolic derivatives that avoids backtracking, adds intersection and complement plus restricted lookarounds, and compiles lazily into a DFA-like graph. The matching algorithm is input-linear in practice and theory, the Rust implementation runs on benchmarks on average 71% faster than the next-fastest Rust engine and beats state-of-the-art on extensions often by orders of magnitude. Artifacts are published and evaluated.

AI-written summary · about

" chapters (20)

1. 0:00RE# introduction
2. 1:04Span semantics for regex
3. 2:28Intersection operator separation
4. 3:34Extracting author names example
5. 6:00Compiling constraints to programs
6. 7:04DFA engine complexity details
7. 8:31Complement via derivatives
8. 9:12Lookarounds approach
9. 9:54Boolean logic simplifications
10. 10:57Leftmost longest semantics
11. 12:43Performance benefits of leftmost
12. 13:45Benchmark results vs engines
13. 14:47Conclusion and takeaways
14. 15:07Q&A
15. 15:30Compile vs runtime performance
16. 16:53Memory usage comparison
17. 17:21PCRE semantics advantages
18. 18:46Complexity with multiple patterns
19. 19:51Avoiding state space explosion
20. 20:12Final remarks