3 ms·
The NFA -> DFA subset construction will identify and squeeze out the overlaps. Compressing regexes, I suspect, is a pointless excercise, except as a preprocess
by kazinator 4y ago
The NFA -> DFA subset construction will identify and squeeze out the overlaps.
Compressing regexes, I suspect, is a pointless excercise, except as a preprocessing pass before a pseudo-regex engine that does backtracking (e.g. Perl).
- kazinator 4y agoSome of these backtracking regex engines have problem semantics like if both a|abc can match a string, the left match will win, so only "a" gets matched. If you put some compressing pass before that, you have to be careful not to mess that up. Basically "abc" can be deleted in this example. then you compress.
- burntsushi 4y agoThis applies to non-backtracking non-DFAs too: https://github.com/rust-lang/regex/issues/787#issuecomment-1255190748 https://github.com/rust-lang/regex/issues/787#issuecomment-1... The GitHub issue comment is perhaps a bit high context. I wrote this reddit comment the other day that is lower context and probably more accessible: https://old.reddit.com/r/rust/comments/zsntov/pomsky_08_released_a_powerful_and_modern_regular/j18yr06/ https://old.reddit.com/r/rust/comments/zsntov/pomsky_08_rele... High level problem: general purpose regex engines that use finite state machines basically never build DFAs. Some of them will build lazy DFAs, but sometimes the lazy DFA can't or shouldn't be used. So you're stuck with an NFA simulation or bounded backtracking. And in those cases, getting rid of the alternation clog can be hugely beneficial (by orders of magnitude).
- gleenn 4y agoDo you know is Java's built-in regex engine builds a DFA? This is all news to me. I built that optimizer because we were doing something pretty naive at work I suppose: we were doing the string concatenation joining with | for a relatively large set of strings and got a notably large speedup so I'm going to assume Java doesn't. It was a very fun project none-the-less :)
- burntsushi 4y agoI don't know much about Java's regex engine, but my understanding is that it's a backtracker. Indeed, such an optimization can make the regex go from intractably slow to quite fast.
- gleenn 4y agoWe used my regex compressor and saw a very large speedup on a large production system so anecdotally it was very useful.