Re: Regular Expression (Regex) Sieve

If I'm understanding your question correctly (and I may well not be), you may want to take a look at Regexp::Assemble, which is roughly similar to your #2, but it will produce a more efficient regex (e.g., (re[1234]) instead of (re1|re2|re3|re4)) and has an option for identifying which of the original source regexes was matched.

I've used Regexp::Assemble to good effect in relatively simple cases to locate all words present in a body of text from a list of a couple hundred target words, but have not had cause to use the 'report source regex' feature, so I can't comment on how well that works.

Comment on Re: Regular Expression (Regex) Sieve Select or Download Code

Replies are listed 'Best First'.
Re^2: Regular Expression (Regex) Sieve by Wiggins (Hermit) on Jul 14, 2009 at 18:45 UTC
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.	[reply]
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]
Re^2: Regular Expression (Regex) Sieve by ikegami (Patriarch) on Jul 14, 2009 at 18:36 UTC
Unless I'm missing something, R::A won't satisfy the requirement in the last para of the OP. That's why I didn't mention it.	[reply]