Can anyone help with this problem I am having with finditer in python?

Question

Hi,

I have a somewhat complex regular expression which I'm trying to match against a long string (65,535 characters). I'm looking for multiple occurrences of the re in the string, and so am using finditer. It works, but for some reason it hangs after identifying the first few occurrences. Does anyone know why this might be? Here's the code snippet:

pattern = "(([ef]|([gh]d*(ad*[gh]d)*b))d*b([ef]d*b|d*)*c)"

matches = re.finditer(pattern, string)
for match in matches:
    print "(%d-%d): %s" % (match.start(), match.end(), match.group())

It prints out the first four occurrences, but then it hangs. When I kill it using Ctrl-C, it tells me it was killed in the iterator:

Traceback (most recent call last):
  File "code.py", line 133, in <module>
    main(sys.argv[1:])
  File "code.py", line 106, in main
    for match in matches:
KeyboardInterrupt

If I try it with a simpler re, it works fine.

I'm running this on python 2.5.4 running on Cygwin on Windows XP.

I managed to get it to hang with a very much shorter string. With this 50 character string, it never returned after about 5 minutes:

ddddddeddbedddbddddddddddddddddddddddddddddddddddd

With this 39 character string it took about 15 seconds to return (and display no matches):

ddddddeddbedddbdddddddddddddddddddddddd

And with this string it returns instantly:

ddddddeddbedddbdddddddddddddd

Ben

Answer 1

Could it be that your expression triggers exponential behavior in the Python RE engine?

This article deals with the problem. If you have the time, you might want to try running your expression in an RE engine developed using those ideas.

Answer 2

You already gave yourself the answer: The regular expression is to complex and ambiguous.

You should try to find a less complex and more distinct expression that is easier to process. Or tell us what you want to accomplish and we could try to help you to find one.

---

Edit   If you just want to allow ds in every position as you said in a comment to John Montgomery’s answer, you should remove them before testing the pattern:

import re

string = "ddddddeddbedddbddddddddddddddddddddddddddddddddddd"
pattern = "(([ef]|([gh](a[gh])*b))b([ef]b)*c)"
matches = re.finditer(pattern, re.sub("d+", "", string))
for match in matches:
    print "(%d-%d): %s" % (match.start(), match.end(), match.group())

Answer 3

I think you experience what is known as "catastrophic backtracking".

Your regex has many optional/alternative parts, all of which still try to match, so previous sub-expressions give back characters to the following expression on local failure. This leads to a back-and-fourth behavior within the regex and exponentially rising execution times.

Python (2.7+?, I'm not sure) supports atomic grouping and possessive quantifiers, you could examine your regex to identify the parts that should match or fail as a whole. Unnecessary backtracking can be brought under control with that.

Answer 4

catastrophic backtracking!

Regular Expressions can be very expensive. Certain (unintended and intended) strings may cause RegExes to exhibit exponential behavior. We've taken several hotfixes for this. RegExes are so handy, but devs really need to understand how they work; we've gotten bitten by them.

example and debugger:

http://www.codinghorror.com/blog/archives/000488.html

Answer 5

Definitely exponential behaviour. You've got so many d* parts to your regexp that it'll be backtracking like crazy when it gets to the long string of d's, but fails to match something earlier. You need to rethink the regexp, so it has less possible paths to try.

In particular I think:

([ef]d*b|d*)*

and

([ef]|([gh]d*(ad*[gh]d)*b))d*b

Might need rethinking, as they'll force a retry of the alternate match. Plus they also overlap in terms of what they match. They'd both match edb for example, but if one fails and tries to backtrack the other part will probably have the same behaviour.

So in short try not to use the | if you can and try to make sure the patterns don't overlap where possible.

Answer 6

Thanks to all the responses, which were very helpful. In the end, surprisingly, it was easy to speed it up. Here's the original regex:

(([ef]|([gh]d*(ad*[gh]d)*b))d*b([ef]d*b|d*)*c)

I noticed that the |d* near the end was not really what I needed, so I modified it as follows:

(([ef]|([gh]d*(ad*[gh]d)*b))d*b([ef]d*bd*)*c)

Now it works almost instantaneously on the 65,536 character string. I guess now I just have to make sure that the regex is really matching the strings I need it to match...

(Incidentally, I'm going to accept the answer from someone else that was most helpful to me, rather than accepting my own answer).

Ben