[Haskell-cafe] Efficient parallel regular expressions

[Mitchell, Neil]

Hi Martijn,

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.

Thanks

Neil

> -----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,
> 
> Martijn.
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
> 

==============================================================================
Please access the attached hyperlink for an important electronic communications disclaimer: 

http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html
==============================================================================