Regular Expression Backtracking Problem

"There a HUGE potential for backtracking in that regex."

I know :-) Good point about the greediness. I'll try making them reluctant.

But it all keys off the last part of the pattern. If the <input> element occurs in the string, I know for sure the regular expression as a whole will match (quickly). If the <input> element does not occur in the string, I know for sure the regular expression will not match.

So all I need is a way to get the parser to check the end of the pattern (the <input> element) before the complex part that's prone to backtracking.

rcauvina at 2007-7-10 11:24:36 >

"Yes, you need that last part of the pattern but even if you know that that part exists in the text you will still do a huge amount of backtracking to get to that point."

As the expression stands, yes.

But the whole point of this question is to find out how to modify the pattern to get the parser to check the last part first, recognize when it fails, and not bother to check the first part of the pattern that backtracks.

If I put the last part of the pattern first, for example, it fails immediately. This fact shows that the parser needn't necessarily do backtracking in order to recognize that the pattern fails.

rcauvina at 2007-7-10 11:24:36 >

"Which is why I suggest 'positive lookahead'!"

Thanks, how do you suggest I incorporate positive lookahead?

"But my point is that even if you first check that the last part matches and it passes then the rest of your pattern will still backtrack heavily once you get past the initial check."

When the expression matches, it does so quickly. I've only experienced significant delays when the expression doesn't match.

rcauvina at 2007-7-10 11:24:36 >

Okay, so now I have

(?=.*?<input type="hidden" name="numOfLegs" value='1' />)<b>From:</b>\s*</td>\s*<td [^>]*?>\s*([^\n]+?)\s*</td>(?:[^\n]*?\n){30,50}[^\n]*?<b>To:</b>\s*</td>\s*<td [^>]*?>\s*([^\n]+?)\s*</td>(?:[^\n]*?\n){12,22}[^\n]*?- begin message -(?:[^\n]*?\n){111,131}[^\n]*?- received -..\s*<table [^>]*?>\s*<tr>\s*<td [^>]*?>\s*([^\n]+?)\s*</td>(?:[^\n]*?\n){5,15}[^\n]*?- sent -..\s*([^\n]+?)\s*</td>(?:[^\n]*?\n){9,15}[^\n]*?end.gif[^>]*?/>\s*</td>\s*<td [^>]*?>\s*(.+?)\s*</td>\s*<td [^>]*?>\s*(?:<img [^>]*?Msg_Images/)?(.+?)(?:.gif"\s*[^>]*?>)?\s*</td>\s*<td [^>]*?>\s*<img [^>]*?/>\s*</td>\s*<td [^>]*?>\s*(.+?)\s*</td>.*?<input type="hidden" name="numOfParts" value='1' />

Now, for an expression that DOES match, it takes several minutes. If I eliminate the lookahead, it matches immediately. But then nonmatching expressions take forever.

rcauvina at 2007-7-21 18:43:19 >

(?=.*?<input type="hidden" name="numOfLegs" value='1' />) The reluctant quantifier is what makes this part so slow. You know the part you're looking for will be at the end of the string (that's the whole point), so you want the .* to consume the whole input initially, then backtrack: (?=.*<input type="hidden" name="numOfLegs" value='1' />) The way a reluctant quantifier works is, each time it's supposed to try to match, it first tries to let the next part of the regex match instead. So it's effectively doing a lookahead at the beginning of each iteration, which can get pretty expensive, especially when the quantified part only matches one character per iteration, like .*?. As a matter of fact, in most places where you're using reluctant quantifiers in your regex, the quantified part can't possibly match the same thing as the next part, for example: (?:[^\n]*?\n) The reluctant quantifier only serves to slow this regex down. What you should be using is a possessive quantifier: (?:[^\n]*+\n) Wherever you find yourself looking for "an unknown number of not-X, followed by X", you should be using a possessive quantifier. In such a situation a normal, greedy-but-accomodating quantifier will slow things down when no match is possible, but a reluctant quantifier makes a successful match much slower than it needs to be. Also, everywhere that you have \s* followed by a tag or by [^\n], you should change it to \s*+. Anytime you know the quantified part can never match the same text as the next part of the regex, you should use a possessive quantifier. However, in the case of [^>]*?/>, you should just remove the question mark. Making that quantifier possessive would break your regex, but you know [^>]*/> will only ever have to backtrack one character.

If you make those changes, I think you'll find that the lookahead isn't necessary after all.

uncle_alicea at 2007-7-21 18:43:19 >

> "Ever tried String.endsWith() or indexOf(), instead

> of complicating that regex even more? :)"

>

> I'm plugging into an existing framework that uses

> regular expressions from a configuration file. I can

> change these expressions but not the Java code that

> parses them.

You should consider filing an RFE on that framework to suggest additional functionality. I suspect you are using it in a way that the authors did not invision. So to achieve acceptable performance something else is needed.

That you found a solution this time does not mean that it will happen the next time (particularly given the complexity of the regex.)

As an analogy database frameworks often (perhaps always these days) provide methods to pass SQL straight through rather than using the framework to construct what it normally does. The reason for this is that the generic framework is not capable of dealing with all possible scenarios while a custom SQL statement call allow significant performace improvements.

jschella at 2007-7-21 18:43:19 >

Another way to boost performance of your regexes is to always use non-capturing parentheses if you're only using them for grouping. However, it looks like capturing is the the reason for all the parens in your regex. In fact, the purpose of <td [^>]*+>\s*+(.+?)\s*+</td> is obviously to capture the contents of the TD element, trimming any leading and trailing whitespace while you're at it. There are ways to avoid the perfomance penalty of the reluctant quantifier, but to find the best one, it helps to know what you're likely to find between those tags. If you know there will only be plain text (no tags), you can do this: <td\b[^>]*+>\s*+([^\s<]++(?:\s++[^\s<]++)*+)\s*+</td> If there might be tags, but not nested TD tags (i.e., no nested tables), it gets even uglier, but still doable. We're already pretty deep in "is it worth it" territory though, so I'll leave it at that unless you express a desire for more punishment. ^_^

uncle_alicea at 2007-7-21 18:43:19 >

Get ready for the regex equivalent of the cat o' nine tails! <td\b[^>]*+>\s*+((?:[^\s<]++|<(?!/?td\b))++(?:\s++(?:[^\s<]++|<(?!/?td\b))++)*+)\s*+</td> But seriously, let me break that down into a before-and-after shot of just the part that changed. Before: ([^\s<]++(?:\s++[^\s<]++)*+) After: ((?:[^\s<]++|<(?!/?td\b))++(?:\s++(?:[^\s<]++|<(?!/?td\b))++)*+) Most of that godawful complexity comes from the need to scrape off surrounding whitespace in the process of matching. Without that requirement, the Before regex would be ([^<]*+) and After, ((?:[^<]++|<(?!/?td\b))*+) I think a good candidate for inclusion in jschell's RFE would be automatic trimming. ;-)

uncle_alicea at 2007-7-21 18:43:19 >