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

Finding all regex matches has always been O(n²)

iev.ee

Post reply on HN
Print view View original

51–60 of 82 posts

Re: Finding all regex matches has always been O(n²)

#51

Post by hyperpape »

conartist6 wrote: post #37

@ievev Have you ever seen an implementation like @bablr/regex? https://github.com/bablr-lang/regex-vm It's an NFA system so it isn't going to be winning any awards for throughput, but in this particular case it does seem to completely avoid the complexity blowup. It will run your heap out of memory though on really big inputs. The strategy this engine uses is just to evolve the state as a function of time. A match ca…

Returning no results is going to be linear in any DFA or NFA based implementation, though. You go character by character, and confirm that there are no matches.

It's only when you return multiple matches that the engines have a problem and become superlinear.

Re: Finding all regex matches has always been O(n²)

#53

Post by mjmas »

zahlman wrote: post #16

> search a document for a pattern and it takes a second. search one a hundred times larger and it doesn't take a hundred seconds - it can take almost three hours. Most of this is about quadratic time find-all operations where a search operation is linear. But it's also still possible to get quadratic behaviour out of a single search without catastrophic backtracking, more easily than you might expect. In late January…

> the search is quadratic because it has to repeat that O(n) work at every position

The problem is that this is one of the regexes that backtracking engines have a bad time with.

With a NFA implementation it can be done in O(regexlen * haystacklen) time, though that only holds for true regular expressions (no backreferences).

https://swtch.com/~rsc/regexp/regexp1.html

And then for re.search, since the NFA wants to just do it once, it should run it with the pattern as

  ^.*?(\d+\s+).*$
(where *? is a non-greedy repeat)

Re: Finding all regex matches has always been O(n²)

#56

Post by coldtea »

gpvos wrote: post #34

I find it weird to have the Perl innovation (?:...) be called "traditional regex". Perl was rather innovative back then, even if it's more than 30 years ago now. Traditional regex is what came before it (grep -E being the most advanced form). I wonder what counts as nontraditional in the author's eyes.

>even if it's more than 30 years ago now.

Here's your answer.

>Traditional regex is what came before it

No, that's "ancient regex".

Re: Finding all regex matches has always been O(n²)

#57

Post by HawtAds »

The original Kleene Star Regex was invented to model neural networks. Have you tried throwing a transformer at the problem /s? Also O(n²) but at least you get hardware acceleration ¯\(ツ)/¯

Here's Kleene's Representation of Events in Nerve Nets and Finite Automata:

https://www.rand.org/content/dam/rand/pubs/research_memorand...

Re: Finding all regex matches has always been O(n²)

#58

Post by hrmtst93837 »

nine_k wrote: post #23

> nearly everything that matters in practice: where the matches are, how long they are, and how many there are I would say that regexes that matter in practice, e.g. when digging through logs, have clear boundaries that curb the pathological backtracking behavior. In particular, I find it difficult to imagine a practical need to find all matches of an expression like /.*a|b/, as shown in the article. Realistically yo…

[flagged]

Re: Finding all regex matches has always been O(n²)

#59

Post by p0w3n3d »

I always thought that finite automata can go with O(n) through the string, with some perks like multistate (i.e. when finding [ab](b)+a in abba you get first state at character 1 and second first state at the 2nd character. Although I understand that regex syntax can be complicated and you can do really O(n^2) in it, but maybe the easier regex could be compiled the easier way...

Re: Finding all regex matches has always been O(n²)

#60

Post by gilleain »

tzs wrote: post #48
conartist6 wrote: post #37

@ievev Have you ever seen an implementation like @bablr/regex? https://github.com/bablr-lang/regex-vm It's an NFA system so it isn't going to be winning any awards for throughput, but in this particular case it does seem to completely avoid the complexity blowup. It will run your heap out of memory though on really big inputs. The strategy this engine uses is just to evolve the state as a function of time. A match ca…

Do any RE implementations do anything like the query planning that databases do or the rewrites that compilers do that can replace the RE with a different sequence of REs or string searches that might execute faster? For example in the expression in your example (I'm assuming based on your description of the test data that /d+s+/ means the same as /\d+\s+/ in the RE engines I've used) any match must contain a digit f…

Not an answer, but related, I was looking at Memgraph (graph db) query planning for Cypher, which is similar (ish) to what you are asking about:

https://memgraph.com/docs/querying/query-plan

The reason why I was looking was to do query planning for a declarative pattern-finding in atomic structures (hierarchical labelled graphs, I suppose) although I'm slowly realising just how insanely hard it might be to get it to work efficiently!

Post reply on HN