From: Martin Kay <mjkay@...>
Date: 2004-08-13T05:29:19+09:00
Subject: Re: Implementation ideas?  Flexible string matching

--Apple-Mail-5-218701513
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed

In general, this is am intractable problem.  After all, a single 
regular expression can match any substring and, in the worst case, they 
could all do this.  The best solution I know to this problem needs a 
more powerful facility for handling regular expressions than is 
normally provided by a programming language.

In what follows, I will talk about the finite-state automata (fsa) 
equivalent to regular expressions because that is what we need.  So ...
1. Make a fsa E = e1 | e2 ... en for the union of the set you are
    interested in.
2. From this create F = Sigma* E by creating a loop for every character
    in the alphabet at the start state of E.  Make F deterministic.
3. Create R as the reverse of E, that is, its recognizes strings that
    match the regular expressions of interest, but read from right to
    left. We need to annotate the final states of this automaton with a
    list of the original expressions that are recognized when the
    automaton enters that state. R also needs to be deterministic.
4. If we run F against the string, it will be in a final state just
    in case the character it has just examined ends a substring that
    matches (at least) one of the original expressions.  Since F is
    deterministic, it is therefore possible to find all these places in
    linear time and, in fact, after examining each character exactly
    once. The trouble is that you cannot tell which expressions match
    at such a location, because, if you are k characters into the string,
    there could be k different places at which a match began.
5. Starting at each location identified in step 4, run R backwards
    through the string.  Every time it enters a final state, it
    identifies the starting point of a substring that ends
    where this backwards match started and, thanks to its special
    annotations, tells you which re(s) you have matched.
This is, of course, intractable in perverse cases because step 5 can 
still start and finish everywhere.  But it is close to linear in all 
but very worst cases. Notice, for what it is worth that, for each 
string position at which you run step 5, at least one match is 
guaranteed.  The problem is that you cannot stop when you find the 
first one because there could be more.

--Martin

On Aug 12, 2004, at 6:11 PM, Kirk Haines wrote:

> Here is the puzzle.  You have a string.  You have a list of strings 
> and/or
> regular expressions.  You want to find the match, if any, between your
> string and an element in the list.
>
> If the list is also just strings, you can create a hash with the 
> strings as
> keys then do a hash lookup to do the match.  That's fast, even if the 
> list
> is very long.
>
> However, what is most of the list is string literals, but you want to 
> be
> able to use regexps or some sort of wildcard matching for some of the
> matches, too.  Does anyone have any bright ideas about how to do this 
> as
> quickly as possible?
>
> The only idea that I have come up with is to put the literal matches 
> in a
> hash, and then have the regular expressions in an array.  If there 
> isn't a
> literal match, then one has to accept the time consuming process of
> iterating through each regexp and checking it.  Can anyone think of any
> other approaches that might be faster?
>
>
> Thanks,
>
> Kirk Haines
>
>

--Apple-Mail-5-218701513--