Re^2: Regular Expression (Regex) Sieve

Yes!! This is the sort of guidance I was looking for... "That path goes by a nice lake; the one over there leads into the abyss".

The balance of simplicity and functionality must also be considered.

It is always better to have seen your target for yourself, rather than depend upon someone else's description.

Comment on Re^2: Regular Expression (Regex) Sieve

Replies are listed 'Best First'.
Re^3: Regular Expression (Regex) Sieve by Anonymous Monk on Aug 20, 2009 at 02:34 UTC
My suggestion is to build a FSM with all the REs and then identify shift/reduce conflicts which will identify multiple matches. When you parse through the document you memorize the reduces and force a shift to potentially identify a longer match. This way you will only have to traverse the document once. If you have multiple matches of the same length you may have reduce/reduce conflicts, but they should be easy to identify since you can check for other reductions every time you reach one. Another alternative is to find nested REs. Run a regex for each RE over the set of remaining REs which should be O(n log n) with respect to the set of REs. Once you find a match you take out either the matched or the matching RE and go on. If you find more than one matching RE then repeat the process saving all the sets. Once you don't find any more matches you run each of the sets over the document. In the worst case it may be more expensive than running each regex separately. In the best case, you will run through the document only once, but you'll pay a little to do regex over the REs.	[reply]

Replies are listed 'Best First'.

Re^3: Regular Expression (Regex) Sieve
by Anonymous Monk on Aug 20, 2009 at 02:34 UTC

My suggestion is to build a FSM with all the REs and then identify shift/reduce conflicts which will identify multiple matches. When you parse through the document you memorize the reduces and force a shift to potentially identify a longer match. This way you will only have to traverse the document once. If you have multiple matches of the same length you may have reduce/reduce conflicts, but they should be easy to identify since you can check for other reductions every time you reach one. Another alternative is to find nested REs. Run a regex for each RE over the set of remaining REs which should be O(n log n) with respect to the set of REs. Once you find a match you take out either the matched or the matching RE and go on. If you find more than one matching RE then repeat the process saving all the sets. Once you don't find any more matches you run each of the sets over the document. In the worst case it may be more expensive than running each regex separately. In the best case, you will run through the document only once, but you'll pay a little to do regex over the REs.

[reply]