Regular expression matching can be simple and fast (2007) • Hacker News Board

Re: Regular expression matching can be simple and fast (2007)

#41

Post by joe_guy » Wed, May 22, 2024, 5:32 PM UTC

jjice wrote: post #2

This and the associated series of regex posts from Russ Cox are probably the best content on practical regular expression engine internals you can get. If you have a cursory understanding of NFAs and DFAs, it's some of the best technical writing I've ever had the pleasure to read. These posts are responsible for my love of regular expressions :)

You may also find this very detailed post interesting https://devblogs.microsoft.com/dotnet/regular-expression-imp...

It's an indepth look at where regex in dotnet was prior to and after version 7.

Re: Regular expression matching can be simple and fast (2007)

#42

Post by JonChesterfield » Thu, May 23, 2024, 2:33 PM UTC

mananaysiempre wrote: post #31

burntsushi wrote: post #27

Earlier quoted context omitted.

As the OP specifically and explicitly says, back-references are definitively NP-complete. The OP even links to a proof[1]. If you found a way to implement them in worst case linear time, then I believe you would have discovered a constructive proof for p=np. Look-around is a different story, but I don't believe you can still guarantee linear time. [1]: https://perl.plover.com/NPC/NPC-3SAT.html

I also wanted to post that link, but now that I’m rereading it I’m starting to doubt that it proves what we want it to prove here. The way it’s presented, the size of the 3-SAT formula corresponds to the size of the expression, not the size of the haystack; and that compiling a regex is exponential in its length is not exactly a surprise—the standard determinization procedure used to compile actually regular (no back…

Sat solvers have been implemented on backtracking regex engines. Sat is NP thus game over for looking for linear time solutions to arbitrary backtracking regex. Sadly.

Re: Regular expression matching can be simple and fast (2007)

#43

Post by mananaysiempre » Thu, May 23, 2024, 5:09 PM UTC

JonChesterfield wrote: post #42

mananaysiempre wrote: post #31

Earlier quoted context omitted.

I also wanted to post that link, but now that I’m rereading it I’m starting to doubt that it proves what we want it to prove here. The way it’s presented, the size of the 3-SAT formula corresponds to the size of the expression, not the size of the haystack; and that compiling a regex is exponential in its length is not exactly a surprise—the standard determinization procedure used to compile actually regular (no back…

Sat solvers have been implemented on backtracking regex engines. Sat is NP thus game over for looking for linear time solutions to arbitrary backtracking regex. Sadly.

> Sat solvers have been implemented on backtracking regex engines.

Again, if the (not-really-)regular expression grows as the SAT problem does, that doesn’t mean game over yet. Your favourite ahead-of-time regex compiler (the good interactive ones are usually incremental, but lex/flex or re2c certainly fit) is also exponential in the size of the regex, because determinization can have exponential-size output. After the (exponentially large) compiled form is produced, though, matching is linear in the size of the haystack no matter what it is.

Burntsushi’s sibling reply links to blog post and thence to a proof-of-concept regular+backreferences expression matcher[1] that works in (quite miserable but still) polynomial time wrt the haystack, with the degree of the polynomial depending on the number of groups that have backreferences to them.

That’s not exactly fantastic, mind you—recall that you can match arbitrary context-free languages in “merely” cubic time. But it’s not exponential.

[1] https://github.com/travisdowns/polyregex

Re: Regular expression matching can be simple and fast (2007)

#44

Post by JonChesterfield » Thu, May 23, 2024, 7:20 PM UTC

mananaysiempre wrote: post #43

JonChesterfield wrote: post #42

Earlier quoted context omitted.

Sat solvers have been implemented on backtracking regex engines. Sat is NP thus game over for looking for linear time solutions to arbitrary backtracking regex. Sadly.

> Sat solvers have been implemented on backtracking regex engines. Again, if the (not-really-)regular expression grows as the SAT problem does, that doesn’t mean game over yet. Your favourite ahead-of-time regex compiler (the good interactive ones are usually incremental, but lex/flex or re2c certainly fit) is also exponential in the size of the regex, because determinization can have exponential-size output. After t…

Attempting polynomial with respect to the string being searched for a constant regex is interesting. A finite regex will contain a finite number of back references.

I think a finite number of back references implies a maximum stack use for the backtracking approach. DFA plus finite size stack machine is convertible to a DFA with a smaller stack and onwards to a pure DFA.

That is probably worth trying to implement, thank you for the push.