Perl Regular Expression Matching Is NP-Hard | Hacker News Reader

Perl Regular Expression Matching Is NP-Hard

perl.plover.com

44 pointsbrudgers18 comments

This result was (as far as I know) first published in 1990 by Aho. [1]

In 2001 I posted online a reduction from SUBSET-SUM to regular expression matching with back-references (which I worked out on paper while on holiday, in the days before the internet was readily accessible from Greek islands). [2]

1. A. Aho. Algorithms for finding patterns in strings. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A, chapter 5, pages 255–300. Elsevier, Amsterdam, 1990.

2. http://bumppo.net/lists/fun-with-perl/2001/06/msg00008.html

For those that don't know, Alfred Aho is the "a" in awk (Aho, Weinberger, and Kernighan).

I'm not sure the date of the linked page, but this is why RE2[0] was created. Russ Cox has some examples where PCRE falls over flat[1].

EDIT: Looks like the original linked page was first published in 2001[2].

[0] https://github.com/google/re2

[1] https://swtch.com/~rsc/regexp/regexp1.html

[2] https://web.archive.org/web/*/http://perl.plover.com/NPC/

From the Cox article:

As far as the theoretical term is concerned, regular expressions with backreferences are not regular expressions. The power that backreferences add comes at great cost: in the worst case, the best known implementations require exponential search algorithms, like the one Perl uses. Perl (and the other languages) could not now remove backreference support, of course.

Cox then proposes a hybrid engine that can be quicker when capture groups aren't needed. TCL has this sort of hybrid implementation, http://wiki.tcl.tk/396. It's worst case performance won't be big-O better than Perl's for pathological cases that require backtracking.

If P no more or less equals NP today than in 2001, the article's conclusion has not lost correctness.

> Cox then proposes a hybrid engine that can be quicker when capture groups aren't needed.

Capture groups aren't the same thing as backreferences. You can do capturing groups fine in linear time (or at least, something close to linear time).

Thanks for the clarification. This page was helpful: https://msdn.microsoft.com/en-us/library/thwdfzxy(v=vs.110)....

Actually at the 4th Ed. of the Camel Book, there is a page or two devoted to rsc's engine

CHAPTER 5 Pattern Matching

Fancy Patterns - Alternate Engines

Starting with v5.10, you can even swap out Perl’s entire regex engine and replace it with an alternate pattern-matching library.

...

Table 5-18. Alternate regex engines

re::engine::RE2 - Russ Cox’s RE2 regex engine

...

One engine of special note is Russ Cox’s RE2 library. It’s a C and C++ library that’s used in the Go programming language, among many other places. The interesting thing is that it maintains a high level Perl compatibility, including good UTF-8 support, while avoiding the potential pitfalls of catastrophic backtracking. It does this because unlike Perl, whose engine is a recursive backtracker, RE2 uses a hybrid NFA/DFA approach that never gets bogged down in pathological cases.

This can be critical in time-sensitive applications where you want to let users provide their own pattern, but you cannot risk letting their search take forever. First written for Google’s Code Search, where time is of the essence, RE2 is also used via its Perl interface at http://grep.cpan.me. This site lets you enter a search pattern that runs over everything in CPAN.

...

The possibility of exponential runtimes can only be eliminated by limiting the input language in ways that Perl Regular Expressions do not [i.e. eliminating the NP-hard languages]. Swapping out the engine for one that does not bog down means reducing the expressive power. See this answer on SE-Computer Science: http://cs.stackexchange.com/a/46837 or this discussion on lambda-the-ultimate: http://lambda-the-ultimate.org/node/2961

> [i.e. eliminating the NP-hard languages]

You have to eliminate even harsher. Prime factoring is also expressible in Perl regular expression.

I believe the GNU regex library also uses a hybrid algorithm.

The linked page was first published 1 February 1998. The reduction from 3COL was added 12 June 1999.

This result has always been a bit of a head-scratcher for me, in that it seems to require that we increase the pattern size (specifically, the number of back-references). While the result is correct, it seems to run counter to common usage of regular expressions, where the regular expression is fixed and the interest is generally in how fast a given regular expression runs over N bytes of input data.

It feels a bit like informing people that comparing two integers is O(N) because maybe the integers are bignums with N bits each; true, but counter to common usage.

For a given piece of text, pattern-matching is (if P!=NP) exponential in the number of back-references (one measure of "size of the pattern"), in the general non-lucky cases of patterns.

This seems plausible, but is the inverse of the traditional expectation of what grows and what stays the same. I refer only to a pragmatic experience of regex implementation (as opposed to a theoretical refutation of the point) - the size of the pattern is typically a constant and the metric of interest is usually the difficulty of scanning a fixed pattern over an arbitrary and increasing-sized input buffer with worst case input.

Maybe relevant: Regular Expression Denial of Service (ReDoS): https://en.wikipedia.org/wiki/ReDoS

Almost every knows that supporting backrefs makes it slow, i.e. exponential. I'm tired of these excuses which come up all the time.

What is perl5's solution to this problem? Saying that is unsolvable (like here), and supporting external matchers. Nobody uses them because it's a joke.

What it should of course do is to check for abnormal backrefs and use a fast matcher without backrefs. 90% of the regexes have no backrefs.

There would be a tiny performance problem if perl5 would use a normal dynamic one-pass compilation, something a modern matcher does. But it uses old-style two-pass compilation, so it's trivial to check if there's a backref, and use a proper Thompson NFA if not. Or a faster jitted variant. Instead p5p still holds on to their awful Spencer DFA with longjmp's all over the place to fix the broken architecture, and engages heavily in badmouthing better algorithms and implementations.

The few changes that were done there made it even slower. Davem's conversion from recursion to iteration caused a significant performance bump. Davem's support for proper /e (eval rhs expressions) caused another significant performance bump. You are not allowed to critize that. The p5p zealots will come all over you. Ross Cox ran away very fast.

If it's NP-hard, it's not really a "regular expression". It's more like a SNOBOL pattern, but with worse syntax. In SNOBOL, backing up was referred to as "pulling the needle back" as it backed out of a failed subpattern to try a different one.

The title says "Perl regular expression". It is well known that they have important extensions compared to the things known as regular expressions in theory.

Reply on news.ycombinator.com