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

21–30 of 44 posts

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

#21

Post by andrewla »

chx wrote: post #11

> As mentioned earlier, no one knows how to implement regular expressions with backreferences efficiently, though no one can prove that it's impossible either. (Specifically, the problem is NP-complete, meaning that if someone did find an efficient implementation, that would be major news to computer scientists and would win a million dollar prize.) It really needs to be noted how NP-complete and an algorithm efficie…

And the converse as well -- an algorithm that is 10,000,000 * n^17 is going to be effectively intractable but falls neatly into P.

And the reality is that most NP-complete problems are well-solved by heuristics except in strange combinatorial corners. It's why we can't just create encryption systems based on knowing the correct answer to an NP-complete problem; most of the problem instances will be too easy to solve.

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

#22

Post by andrewla »

zeckalpha wrote: post #17
adrianN wrote: post #8

Regexes can be fast and simple, but sometimes it’s faster and simpler to use normal string search. I recently replaced a regex with two finds for 10x speedup.

Sounds like the regex library was not implemented as Russ describes... a linear find should be equivalent to a well implemented regex search for a specific string of characters.

Depending on the type of string search this is not completely true. A naive string search is O(kn) (where k is the length of the search string) which is actually slower than the O(n) that a DFA can get.

But KMP and similar algorithms can do better; they can get performance approaching O(n/k) for many cases by not even looking at every character of the input string.

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

#23

Post by hyperpape »

andrewla wrote: post #22
zeckalpha wrote: post #17

Earlier quoted context omitted.

Sounds like the regex library was not implemented as Russ describes... a linear find should be equivalent to a well implemented regex search for a specific string of characters.

Depending on the type of string search this is not completely true. A naive string search is O(kn) (where k is the length of the search string) which is actually slower than the O(n) that a DFA can get. But KMP and similar algorithms can do better; they can get performance approaching O(n/k) for many cases by not even looking at every character of the input string.

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....

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

#24

Post by bane »

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 :)

Many years ago, as a fresh out of college young coder, I had to come up with a way to check types on an text input file in C++ -- long before C++ had even a standard String type let alone regex libraries like pcre. The standard conversion functions at the time expected you to have done some type detection beforehand.

Each field in the file could contain a string, an int, or a float. In particular to figure out the floats, I remember sitting down for a few hours and coming up with a regular expression, testing it in Perl on a bunch of test cases, and then went about the hard work of slowly converting the regex into an NFA to a DFA and then finally to an adjacency graph in a 2d matrix. A little bit of code to read in things a byte at a time and some simple arithmetic and I had a stupid fast

   bool isFloat(char *)
Nobody at my work understood the code, they just sort of knew that if they submitted a character array with a field value into it, something happened with a big matrix, and it you let them know if it was a float or not and then they could call the appropriate conversion function -- I think stof() or whatever was in fashion back then.

I had to make one revision to it for an edge case I missed and then it found its way into pretty much all code for the company after that.

The tuition for the class that taught me how to do that payed for itself with that one function.

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

#26

Post by eyelidlessness »

kayodelycaon wrote: post #25

It's easy to miss in the article, but the reason most regex engines exhibit Perl's behavior is due to features like back referencing. (And I assume look behinds and look aheads.) PCRE and theoretically pure regular expressions are different things.

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).

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

#27

Post by burntsushi »

eyelidlessness wrote: post #26
kayodelycaon wrote: post #25

It's easy to miss in the article, but the reason most regex engines exhibit Perl's behavior is due to features like back referencing. (And I assume look behinds and look aheads.) PCRE and theoretically pure regular expressions are different things.

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

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

#28

Post by samatman »

banish-m4 wrote: post #6
kqr wrote: post #5

Earlier quoted context omitted.

And if you don't have a cursory understanding of NFAs and DFAs, they're still great for getting that cursory understanding. These articles were my introduction to finite automata (and almost the only place I've learned about them aside from practical use) and my intuition for them seem to often be better than my peers'.

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.

Decidability is whether one can statically determine if an algorithm halts for a given input. NFAs halt for all inputs, by construction.

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

#29

Post by MattPalmer1086 »

andrewla wrote: post #22
zeckalpha wrote: post #17

Earlier quoted context omitted.

Sounds like the regex library was not implemented as Russ describes... a linear find should be equivalent to a well implemented regex search for a specific string of characters.

Depending on the type of string search this is not completely true. A naive string search is O(kn) (where k is the length of the search string) which is actually slower than the O(n) that a DFA can get. But KMP and similar algorithms can do better; they can get performance approaching O(n/k) for many cases by not even looking at every character of the input string.

KMP always looks at every position, but it is linear.

There is a variant of Boyer Moore which is sublinear and linear in the worst case, but it's not that fast by modern standards.

The fastest sub linear search algorithms I know that remain linear in the worst case are Linear Weak Factor Recognition (LWFR) and Linear Hash Chain (LHC). LHC is currently unpublished (I'm writing a paper on it right now).

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

#30

Post by MattPalmer1086 »

hyperpape wrote: post #23
andrewla wrote: post #22

Earlier quoted context omitted.

Depending on the type of string search this is not completely true. A naive string search is O(kn) (where k is the length of the search string) which is actually slower than the O(n) that a DFA can get. But KMP and similar algorithms can do better; they can get performance approaching O(n/k) for many cases by not even looking at every character of the input string.

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.
Post reply on HN