Orchid Win7 v1 <voi### [at] devnull> wrote:
> OK, so here's an interesting thought...

> I've been looking at string searching algorithms, and regular 
> expressions, and generally at pattern matching on data. There are lots 
> of ideas about how to find a specific pattern as fast as possible. But 
> what I don't see anywhere is how to look for *several* patterns and see 
> which one is present. (Especially patterns occurring [or not] at a 
> specific location.)

> If I'm looking at some data which will contain one of 1,000 possible 
> patterns, it sounds like it would be quite inefficient to run 1,000 
> different checks on it. I suppose I could try building a decision tree, 
> but if most of the patterns are at least half a dozen bytes long, 
> there's a danger that tree could become really, really big.

> Anyone have any other suggestions?

IIRC a regular expression can be (and is usually) converted into a state
machine that traverses the input data linearly once. When the state machine
ends up in one of specific nodes, you know that a match was found (and the
node in question uniquely identifies which pattern was matching.)

-- 
                                                          - Warp

Post a reply to this message