3 ms·

Also, they could compress the regular expressions for speedup by using a trie data structure and then walking the trie to match common-overlap. This is a Java e

by gleenn 4y ago

Also, they could compress the regular expressions for speedup by using a trie data structure and then walking the trie to match common-overlap. This is a Java example but you could easily port it or even just run it in Java and then export the regex after running with your fixed set of strings and paste into C++: https://github.com/gleenn/regex_compressor https://github.com/gleenn/regex_compressor

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 ago
  Some 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 ago
  This 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 ago
    Do 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 ago
      I 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 ago
        We used my regex compressor and saw a very large speedup on a large production system so anecdotally it was very useful.
dhosek 4y ago
Yeah, my first thought was that this was a job for a trie. You can inspect your input character by character, and you can rule out most strings by the first byte since it must be h, f or w. If your set is small and static, you can hard-code the trie and it will be superfast, but a long as you can fail fast when checking each character (so don’t use the default hasher in Rust), you can check for matches quickly and easily.

by gleenn 4y ago

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 ago
Some 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 ago
This 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 ago
  Do 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 ago
    I 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 ago
      We used my regex compressor and saw a very large speedup on a large production system so anecdotally it was very useful.

dhosek 4y ago

Yeah, my first thought was that this was a job for a trie. You can inspect your input character by character, and you can rule out most strings by the first byte since it must be h, f or w. If your set is small and static, you can hard-code the trie and it will be superfast, but a long as you can fail fast when checking each character (so don’t use the default hasher in Rust), you can check for matches quickly and easily.