Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Regular expression matching can be simple and fast (2007)

swtch.com

Post reply on HN
Print view View original

31–40 of 44 posts

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

#31

Post by mananaysiempre »

burntsushi wrote: post #27
eyelidlessness wrote: post #26

Earlier quoted context omitted.

FWIW, it seems pretty likely the same multi-NFA algorithm described in the article could be applied to other backtracking scenarios (and therefore to back references and lookaround). Since I’m just speculating, I’ll hazard a guess that it would result in a meaningfully more complex implementation to derive each state machine, and potentially much slower (while still “linear” complexity).

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 backreferences) regexes for linear matching is also exponential. So what we’d actually want to prove is along the lines of NP-completeness even if we allow for an exponential amount of preprocessing on the expression only.

(I’m willing to believe backreference matching is NP-complete, I just think the linked statement is weaker than that.)

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

#32

Post by burntsushi »

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…

Ah I see. Geoff Langdale (creator of Hyperscan) has a post about this. The comments seem relevant: https://branchfree.org/2019/04/04/question-is-matching-fixed...

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

#33

Post by burntsushi »

MattPalmer1086 wrote: post #30
hyperpape wrote: post #23

Earlier quoted context omitted.

In practice, it's apparently often better to avoid these techniques and just use SIMD operations to search. You look at every byte, so it's O(n) but the overhead of more complicated approaches isn't worth it. See this comment from burntsushi: https://lobste.rs/s/ycydmd/why_gnu_grep_is_fast_2010#c_gpim7... .

For short patterns this is probably right. Longer patterns will be faster using a modern sublinear search algorithm.

As the author of ripgrep, I wouldn't necessarily buy this. I suppose I might agree with it in the extremes, but SIMD prefilters are quite exceptionally difficult to beat with scalar code in the common cases. Longer patterns are great for the SIMD algorithms in ripgrep because of its use of background frequency distribution heuristics. That is, the longer the pattern, the less likely your candidate detection is to produce a false positive in its hot path. (I say "less likely" here intentionally. One can of course pick specific needles and haystacks where a false positive is reported at every position for any length N.)

I don't mean to 100% disagree with you, but I think it's misleading to suggest a sort of one dimensional view of things where, as the pattern gets larger, SIMD gets worse compared to sublinear search algorithms. There are other factors at play here, and, importantly, what "long" means in this context.

In many practical circumstances, "short" might be a few bytes, while "long" is 16 bytes. But maybe your idea of "long" is actually much longer.

If you're curious how your own algorithm stacks up to ripgrep's, you can plug your implementation into the `memchr` crate's benchmark harness: https://github.com/BurntSushi/memchr

It uses rebar: https://github.com/BurntSushi/rebar

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

#34

Post by plesner »

This is a fine introduction to automata-based regexps but the framing of comparing "good" automata with "bad" perl-style is misguided. Automata and perl-style regexps are different beasts and solve different problems. The problem seems to be one of terminology: the perl style should never have been called regexps. That's not what they are. It's a pattern language that happens to have a variant of regexps as a subset.

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

#35

Post by nitely »

burntsushi wrote: post #27
eyelidlessness wrote: post #26

Earlier quoted context omitted.

FWIW, it seems pretty likely the same multi-NFA algorithm described in the article could be applied to other backtracking scenarios (and therefore to back references and lookaround). Since I’m just speculating, I’ll hazard a guess that it would result in a meaningfully more complex implementation to derive each state machine, and potentially much slower (while still “linear” complexity).

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

Look-arounds can be implemented in quadratic time for unbounded expressions (i.e: containing +, *), and linear time for bounded expressions quite easily. And I suspect they can be implemented in (super)linear time in general by matching them in parallel to the NFA.

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

#36

Post by MattPalmer1086 »

burntsushi wrote: post #33
MattPalmer1086 wrote: post #30

Earlier quoted context omitted.

For short patterns this is probably right. Longer patterns will be faster using a modern sublinear search algorithm.

As the author of ripgrep, I wouldn't necessarily buy this. I suppose I might agree with it in the extremes, but SIMD prefilters are quite exceptionally difficult to beat with scalar code in the common cases. Longer patterns are great for the SIMD algorithms in ripgrep because of its use of background frequency distribution heuristics. That is, the longer the pattern, the less likely your candidate detection is to pro…

Interesting, thanks for the detailed response. I'll have a look at the benchmark; I'm doing some work on algorithm benchmarking right now by coincidence.

I'd say a long pattern is more like 64 bytes (the benchmarking suite I use defines short patterns as 32 or under).

Edit: will also check out the frequency approach used in ripgrep, sounds fascinating.

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

#37

Post by burntsushi »

MattPalmer1086 wrote: post #36
burntsushi wrote: post #33

Earlier quoted context omitted.

As the author of ripgrep, I wouldn't necessarily buy this. I suppose I might agree with it in the extremes, but SIMD prefilters are quite exceptionally difficult to beat with scalar code in the common cases. Longer patterns are great for the SIMD algorithms in ripgrep because of its use of background frequency distribution heuristics. That is, the longer the pattern, the less likely your candidate detection is to pro…

Interesting, thanks for the detailed response. I'll have a look at the benchmark; I'm doing some work on algorithm benchmarking right now by coincidence. I'd say a long pattern is more like 64 bytes (the benchmarking suite I use defines short patterns as 32 or under). Edit: will also check out the frequency approach used in ripgrep, sounds fascinating.

You can read more about it at various points in these two blogs I've written:

https://blog.burntsushi.net/ripgrep/

https://blog.burntsushi.net/regex-internals/

64 bytes is decently long, but I'd still put my money on SIMD for "common" cases.

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

#38

Post by banish-m4 »

gliptic wrote: post #9
banish-m4 wrote: post #6

Earlier quoted context omitted.

NFAs are apparently undecidable since the same input can go to multiple states. DFA states can only go to one state when given a particular input sequence. The Dragon book contains an NFA to DFA algorithm (powerset) which explodes states with multiple exiting token transitions. PS: All your DAGs are belong to us.

NFAs are decidable. As you said, a NFA can be converted to a DFA which is decidable. Maybe you mean they are non-deterministic (that's in the name)?

You know what I meant. I used the wrong word.

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

#39

Post by banish-m4 »

mikhailfranco wrote: post #19
banish-m4 wrote: post #6

Earlier quoted context omitted.

NFAs are apparently undecidable since the same input can go to multiple states. DFA states can only go to one state when given a particular input sequence. The Dragon book contains an NFA to DFA algorithm (powerset) which explodes states with multiple exiting token transitions. PS: All your DAGs are belong to us.

It is possible to implement NFAs directly, in parallel: https://github.com/mike-french/myrex Just fan-out messages to all downstream states. Let a fair runtime system evaluate all progress, then tally results along all paths, for example: https://github.com/mike-french/myrex?tab=readme-ov-file#exec... The approach can also be adapted to captures and their many, many possible ambiguities. There is an example that gene…

That's identical to NFA->DFA conversion but with dynamic programming.

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

#40

Post by Aerbil313 »

I've recently discovered Lua Parsing Expression Grammars (LPEG)[1]. They are built on a different approach to parsing and are much more capable than conventional regexes, able to handle recursive sequences, able to include code, have debugging utilities, are often much more performant than regexes and they are an absolute delight to work with. It also has a module called re [2] which uses a similar syntax to regexes.

1: https://www.inf.puc-rio.br/~roberto/lpeg/

2: https://www.inf.puc-rio.br/~roberto/lpeg/re.html

Post reply on HN