Re: multiple-string matching & regular expressions
- From: "A.G.McDowell" <mcdowella@xxxxxxxxxxxx>
- Date: Wed, 25 Jan 2006 20:12:56 +0000
In article <1138212299.439248.19670@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
luseng <SevilSen@xxxxxxxxx> writes
>Hello,
>I am looking for an efficient multiple-string matching algorithm. But,
>the set of strings can contain both literal strings and regular
>expressions. Is it possible?
>thanks..
>
Theoretically, if e1 and e2 are regular expressions, then (e1 | e2) is
also a regular expression. But I have no idea if that leads to a
practical solution, and the answer may depend on what your regular
expressions and your input data are like anyway. Aho-Corasick is
practical but caters only for multiple literal strings.
Depending on your input data and regular expressions, one way to apply
this would be to compute a set of literal strings such that any regular
expression match implies a literal string match, and use this as a
coarse filter to pick out bits of interesting input.
For much better but more detailed info see e.g. section 5.5.1/ P 126 and
later of "Flexible Pattern Matching In Strings" by Navarro and Raffinot.
--
A.G.McDowell
.
- Follow-Ups:
- Re: multiple-string matching & regular expressions
- From: luseng
- Re: multiple-string matching & regular expressions
- References:
- multiple-string matching & regular expressions
- From: luseng
- multiple-string matching & regular expressions
- Prev by Date: Re: project management: scheduling of tasks
- Next by Date: Re: knapsack approximation
- Previous by thread: multiple-string matching & regular expressions
- Next by thread: Re: multiple-string matching & regular expressions
- Index(es):
Relevant Pages
|
