Re: Bad performance of back-references

In article <101hfq7$22v3c$1@dont-email.me>,
Janis Papanagnou  <janis_papanagnou+ng@hotmail.com> wrote:

In a recent application case I used back-references to find duplicate
strings in large data sets. I tested that with grep as in
>
 grep -E -o '(.{42}).*\1'
>
While this is obviously a neat way to formulate and solve the task in
principle it is impractical for performance reasons.[*]
>
Applied on my MB sized data the task did not terminate and I killed
the process after a day.
>
I also implemented the desired function explicitly (using two nested
loops) in a couple of languages (interpreted or compiled). All those
hand-crafted and non-optimized implementations terminated and did
that within minutes or up to only few hours (depending on the pattern
length).
>
My astonishment is why the back-reference implementation performs so
badly here with 'grep'.
>
Janis
>
[*] Note: Back-references are not from the Regular Expression functions
class so they cannot be done in O(N) or O(N+K); so I don't expect this
complexity where I use them. This is not the question here, just to be
clear.

Your results don't surprise me in the the least.

First, "back references" make "regular expressions" not regular,
in the formal sense sense that they are no longer isomorphic to
deterministic finite automata or their NDFA simulations.
Matching DFA is inherently linear, but _creating_ DFAs can be
exponential; NDFAs can be created in reasonable time (I forget
the exact complexity, I'm afraid) though executing them may be
superlinear; regardless it's much better than exponential.

Second, most implementations that support backreferences use
backtracking to do so, which can be exponential in both space
and time.

There's some good background information here:
https://swtch.com/~rsc/regexp/regexp1.html

The bottom line is that regexp that use back tracking are not
actually regular expressions, and there is no known way to make
them fast generally.

- Dan C.