7 ms·

Regular Expression Matching Can Be Simple And Fast

22 points by edw519 17y ago

apu 17y ago
Does anyone know why this is not implemented within Python, Perl, etc.? I don't think the article mentioned...
- blasdel 17y ago
  It's because the standard 'Regular Expressions' include highly irregular language features -- Backreferences in particular are a huge bitch. The clean transform in Thomson's algorithm only works for Regular Languages.
  - viraptor 17y ago
    But "they" could include 2 engines in languages that have different versions for compiled and adhoc RE (like python)... Let's say it could work like this: If you use adhoc, you always get the huge version (it probably doesn't matter anyways - it's going to be used once). If you compile, simple version would start constructing the pattern matching graph - as soon as anything not-supported is found, you go back to the big RE. One time cost should not be big if you're already prepared to match many strings (you're using crazy features and compiling that RE explicitely after all - that's going to take long). Optionally a flag could force a specific engine.
    - steveklabnik 17y ago
      As the article mentions, usually PCREs are just 'fast enough.' Not that an anecdote is better than actual data, but I prefer to use regular expressions wherever possible, and I've never had matching time be an issue. It's not as if people are clamoring for better matching times. Supporting two different matching engines so that a fairly trivial speed increase can be had seems silly.
      - blasdel 17y ago
        But it's not a trivial speed increase -- for some cases PCREs are O(2^n) where Thomson's NFA is at worst O(n^2). The Thomson NFA quickly gets to be millions of times faster Thomson's algorithm would let you could use regular expressions for cases where you would otherwise have never tried.
        haberman 17y ago
        > The Thomson NFA quickly gets to be millions of times faster The O(2^n) worst case only comes from highly ambiguous patterns which are better written in other ways. So this isn't really accurate in practice.
        steveklabnik 17y ago
        Yes, a 1u to .1u increase is 10x, but it's still trivial. In most cases, everything else that you're doing is much slower than the match. Yes, in a degenerate case, the PCRE performs abysmally, but seriously, are you ever going to use "a?a?a?aaa"? I'd like to see some numbers on the average, not the absolute worst case.
      - kingkongrevenge 17y ago
        Perl 5.10 and up has a pluggable regex engine interface.
        steveklabnik 17y ago
        Nice, thanks for pointing this out. That's pretty sweet. I haven't paid attention to Perl in a while... Perl is kinda like that cute girl that you dated in high school, then had an amicable breakup with when you went off to college. You're always glad to see that she's doing well, but you're off on new things by now.
- ekiru 17y ago
  It mentions that those languages tend to have added operators(like backreferences) to regular expressions that make matching them NP-complete.
- bartl 17y ago
  The article uses Perl 5.8.7 for its examples. FYI: the implementation of the regular expressions engine changed a lot for Perl 5.10.
- ubernostrum 17y ago
  Because every approach to regex (not "regular expressions", mathematical pedants can come back when they admit that programming has moved on to something different) has advantages and drawbacks. The one presented in this article has advantages in particular highly-contrived situations. The approaches used by popular libraries and languages have advantages in more common real-world situations.
tc 17y ago
Thompson introduced the multiple-state simulation approach in his 1968 paper. In his formulation, the states of the NFA were represented by small machine-code sequences, and the list of possible states was just a sequence of function call instructions. In essence, Thompson compiled the regular expression into clever machine code. Forty years later, computers are much faster and the machine code approach is not as necessary. Interestingly, if you think in Lisp, it's obvious how much more elegant Thompson's approach is (than a C struct-based state machine), and how you would implement it in Thompson's way with closures.
- agazso 17y ago
  In fact Thompson invented JIT compiling with this in 1968.
BlueZeniX 17y ago
The D language library 'Tango' implements this: http://dsource.org/projects/tango/docs/stable/tango.text.Regex.html http://dsource.org/projects/tango/docs/stable/tango.text.Reg...

22 points by edw519 17y ago

apu 17y ago

Does anyone know why this is not implemented within Python, Perl, etc.? I don't think the article mentioned...

blasdel 17y ago
It's because the standard 'Regular Expressions' include highly irregular language features -- Backreferences in particular are a huge bitch. The clean transform in Thomson's algorithm only works for Regular Languages.
- viraptor 17y ago
  But "they" could include 2 engines in languages that have different versions for compiled and adhoc RE (like python)... Let's say it could work like this: If you use adhoc, you always get the huge version (it probably doesn't matter anyways - it's going to be used once). If you compile, simple version would start constructing the pattern matching graph - as soon as anything not-supported is found, you go back to the big RE. One time cost should not be big if you're already prepared to match many strings (you're using crazy features and compiling that RE explicitely after all - that's going to take long). Optionally a flag could force a specific engine.
  - steveklabnik 17y ago
    As the article mentions, usually PCREs are just 'fast enough.' Not that an anecdote is better than actual data, but I prefer to use regular expressions wherever possible, and I've never had matching time be an issue. It's not as if people are clamoring for better matching times. Supporting two different matching engines so that a fairly trivial speed increase can be had seems silly.
    - blasdel 17y ago
      But it's not a trivial speed increase -- for some cases PCREs are O(2^n) where Thomson's NFA is at worst O(n^2). The Thomson NFA quickly gets to be millions of times faster Thomson's algorithm would let you could use regular expressions for cases where you would otherwise have never tried.
      - haberman 17y ago
        > The Thomson NFA quickly gets to be millions of times faster The O(2^n) worst case only comes from highly ambiguous patterns which are better written in other ways. So this isn't really accurate in practice.
      - steveklabnik 17y ago
        Yes, a 1u to .1u increase is 10x, but it's still trivial. In most cases, everything else that you're doing is much slower than the match. Yes, in a degenerate case, the PCRE performs abysmally, but seriously, are you ever going to use "a?a?a?aaa"? I'd like to see some numbers on the average, not the absolute worst case.
    - kingkongrevenge 17y ago
      Perl 5.10 and up has a pluggable regex engine interface.
      - steveklabnik 17y ago
        Nice, thanks for pointing this out. That's pretty sweet. I haven't paid attention to Perl in a while... Perl is kinda like that cute girl that you dated in high school, then had an amicable breakup with when you went off to college. You're always glad to see that she's doing well, but you're off on new things by now.
ekiru 17y ago
It mentions that those languages tend to have added operators(like backreferences) to regular expressions that make matching them NP-complete.
bartl 17y ago
The article uses Perl 5.8.7 for its examples. FYI: the implementation of the regular expressions engine changed a lot for Perl 5.10.
ubernostrum 17y ago
Because every approach to regex (not "regular expressions", mathematical pedants can come back when they admit that programming has moved on to something different) has advantages and drawbacks. The one presented in this article has advantages in particular highly-contrived situations. The approaches used by popular libraries and languages have advantages in more common real-world situations.

tc 17y ago

Thompson introduced the multiple-state simulation approach in his 1968 paper. In his formulation, the states of the NFA were represented by small machine-code sequences, and the list of possible states was just a sequence of function call instructions. In essence, Thompson compiled the regular expression into clever machine code. Forty years later, computers are much faster and the machine code approach is not as necessary. Interestingly, if you think in Lisp, it's obvious how much more elegant Thompson's approach is (than a C struct-based state machine), and how you would implement it in Thompson's way with closures.

agazso 17y ago
In fact Thompson invented JIT compiling with this in 1968.

BlueZeniX 17y ago

The D language library 'Tango' implements this: http://dsource.org/projects/tango/docs/stable/tango.text.Regex.html http://dsource.org/projects/tango/docs/stable/tango.text.Reg...