You can do things with these backtracking algorithms that are difficult (capturing subexpressions, start of match) or impossible (backreferences, arbitrary lookarounds) to do efficiently in an automata based algorithm.
Sometimes users want these features more than they want theoretical purity. Who are we to tell them they are wrong?
That said, we do have some projects in mind to try to bridge these two worlds (feature-rich backtracking world vs speedy/streamable automata-based). Anyone interested should contact the Hyperscan team. Make a nice project at undergraduate or even postgraduate level depending on scale.
I don't really like this result. It's a bit like saying finding the maximum integer in a sorted list is actually order NN because... what if the N ints are all BIGNUMS WITH N bits, huh?
The fact that you have to grow the regex* to get this result has a similar vibe to it. All the regex matching we see - and most conventional regex matching - assumes the regular expressions are fixed. Every now any then you'll see an algorithm where the size of the regex contributes to the big-O notation but then it's usually broken out as a parameter.
I don't have a good method to actually do a fixed-number-of-backreferences in less than exponential time but it seems fairly clear that if you are willing to burn polynomial time gratuitously you should be able to handle a back-reference (i.e. for input of length N and M back-references, there are only O(N^(2M)) possible final places where those back-references could match for a single match... huge but if M fixed, not polynomial). So if you had an otherwise poly-time regex algorithm you could do it over and over again trying each possible back-ref location and still be poly-time.
oops should have been "unsorted list". Or order(NlgN) in a sorted list.
The point is that number of back-references are not typically something that varies as part of a regex workload, so this proof derives something that is correct in itself, but not applicable to the way most people view regex. This has led to a meme that "all regex with backtracking is NP-hard".
My rather labored analogy is that people view comparison of two numbers as O(1) and would be nonplussed if someone demanded to know if they'd considered O(N) sized bignums... it isn't what most people are talking about when they talk about the cost of doing arithmetic operations. Similarly, arbitrarily expanding regexes is not what most people are talking about when they talk about the cost of doing regex.
> It's a bit like saying finding the maximum integer in a sorted list is actually order NN because... what if the N ints are all BIGNUMS WITH N bits, huh?
I'm not sure I follow. Why would finding the max integer in a sorted list be anything other than the time to copy the last (or first, depending on sort order) element of the list?
Certainly a valid point, though, that this isn't a common use case, so that's just not how experts in this field think about this problem.
> there are only O(N^(2M)) possible final places where those back-references could match for a single match... huge but if M fixed, not polynomial).
Sure, that buys you a pseudo-polynomial algorithm. I just don't like the idea of calling something like that polynomial -- if we did that across the board, then we'd have a poly solution for knapsack (and consequently demonstrate P = NP).
Just wanted to draw your attention to a proof of concept regex engine that I wrote a few years ago that does handle backreferences and arbitrary look around using a Thomson NFA and with no backtracking.
The point of this engine was to show that, while it seems to be commonly believed that an automata-based regex engine cannot handle backreferences and arbitrary look around, that is not entirely true. It does use a stack when it encounters backreferences though.
I think the idea is interesting. I don't think most reasonable people believe that you can't handle backreferences and arbitrary lookaround in something that's largely based on automata; rather that if you're using automata you probably made the decision to use them to avoid having to allocate arbitrary amounts of memory, to "stream" or for multiple pattern support and/or performance reasons.
If those criteria frame why you are using an automata to begin with, then you either (a) can't use a stack either or (b) you at least need to make a performance argument that using NFA+stack is better than a back-tracker.
Arbitrary lookaround seems straightforward except in streaming mode, although efficient support for forward asserts for arbitrary regexes without "grows with the input size" side storage is IMO not trivial (it also breaks our ordering model). Backward lookaround seems easy if you are OK with adding logical AND to your NFA.
Sometimes users want these features more than they want theoretical purity. Who are we to tell them they are wrong?
That said, we do have some projects in mind to try to bridge these two worlds (feature-rich backtracking world vs speedy/streamable automata-based). Anyone interested should contact the Hyperscan team. Make a nice project at undergraduate or even postgraduate level depending on scale.