4 ms·
Most of those regexes fail after processing the first few characters. I wonder if an optimizing regex-compiler could transform the set of regexes into a single
by aaaaaaaaaaab 4y ago
Most of those regexes fail after processing the first few characters.
I wonder if an optimizing regex-compiler could transform the set of regexes into a single finite state machine that’s more efficient than running individual regex recognizers in parallel. The optimal solution feels NP-hard, but I wonder if one could get sufficient improvements with some heuristic optimizations, like extracting common clauses, etc.
Maybe @burntsushi has some insights about this?
- burntsushi 4y agoTaking a set of regexes and compiling them all into one automaton is exactly what RegexSet is: https://docs.rs/regex/latest/regex/struct.RegexSet.html https://docs.rs/regex/latest/regex/struct.RegexSet.html However, when you're talking about thousands of regexes, that's going to be a very large automaton. Probably impractically large. It's not NP-hard. It's "just" impractical. Using heuristics to whittle down the set of possible regexes to match---likely using literals extracted from each regex---is exactly what you want to do for a problem like this. If all you have are literals, an Aho-Corasick automaton is feasible to build for 90,000 entries. Aho-Corasick, in my experience, doesn't really start to break down until you eclipse 1,000,000 entries.
- Arnt 4y agoEmacs used such a thing ~30 years ago. Common wisdom was that it was great when it worked, but a few carelessly written regexes would shoot the performance. If course there'll be some carelessly written ones in any set of >1k regexes.