[Haskell-cafe] Efficient parallel regular expressions
neil.mitchell.2 at credit-suisse.com
Tue Nov 4 12:38:45 EST 2008
It's not that tricky if you do a regular expression state machine yourself, but that's probably a bit too much work. One way to get a speed up might be to take the regular expressions a,b,c,d and generate a regex a+b+c+d, and one a+b. You can then check any string s against a+b+c+d, if that matches check a+b, if that matches check a. At each stage you eliminate half the regular expressions, which means a match will take log n, where n is the number of regular expressions.
This assumes the underlying regular expression engine constructs a finite state machine, making it O(m) where m is the length of the string to match.
> -----Original Message-----
> From: haskell-cafe-bounces at haskell.org
> [mailto:haskell-cafe-bounces at haskell.org] On Behalf Of
> Martijn van Steenbergen
> Sent: 04 November 2008 5:05 pm
> To: Haskell Cafe
> Subject: [Haskell-cafe] Efficient parallel regular expressions
> Hello all,
> For my mud client Yogurt (see hackage) I'm currently working
> on improving the efficiency of the hooks. Right now several
> hooks, each consisting of a regex and an action can be active
> at the same time.
> Every time a line of input is available (usually several
> times a second) I run the line through all the available
> regexes and execute the first matching action.
> I figured this is not the cleverest approach and it'd be better if I
> |'ed all regexes into one big DFA. However, how do I then
> find out which
> of the original hooks matched and so which action to execute?
> As far as I know there's no way to do that with Text.Regex.
> Alex looks promising but is really only an executable and
> doesn't offer an API.
> I've also found mr. João Saraiva's HaLex but I don't know if
> that was meant to be used seriously.
> Does anyone have any experience with this? What's the best
> way to achieve this?
> Thanks much,
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
Please access the attached hyperlink for an important electronic communications disclaimer:
More information about the Haskell-Cafe