[Haskell-cafe] Substring replacements

[Branimir Maksimovic]

>From: Daniel Fischer <daniel.is.fischer at web.de>
>To: "Branimir Maksimovic" <bmaxa at hotmail.com>
>CC: Haskell-Cafe at haskell.org
>Subject: Re: [Haskell-cafe] Substring replacements
>Date: Wed, 14 Dec 2005 20:40:06 +0100
>
>Hi Bane,
>
>nice algorithm. Since comparing chars _is_ cheap, it is to be expected that
>all the hash-rotating is far more costly for short search patterns. The
>longer the pattern, the better this gets, I think -- though nowhere near 
>KMP
>(or would it?).

Yes,KMP is superior in single pattern search. We didn't tried Boyer-Moore
algorithm yet, though. But I think it would be
difficult to implement it in Haskell efficiently as it searches backwards
and jumps around, and we want memory savings.
Though, I even didn't tried yet, but it is certainly very interesting.

However, I don't see how to (efficiently) do a multiple
>pattern search with KMP, so there -- if all patterns have the same length,
>otherwise I don't see -- Rabin-Karp would probably be the method of choice.

Yes, this algorithm can search in parallel patterns of same length.
Different search patterns have to be searched same way as with KMP.

>
>I tuned it up somewhat:
>import Data.List (isPrefixOf)
>import Data.Char (ord)  -- using ord instead of fromEnum oddly makes it
>-- faster for my test, but slower for yours, but only a whiff.

Wow, on my machine your version of Rabin-Karp gives 30% boost to my test.
This helps me learn Haskell , too .

Greetings, Bane.

_________________________________________________________________
Express yourself instantly with MSN Messenger! Download today it's FREE! 
http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/