This is what I got for BM. Performance dissapoints as BM is really
suited for indexed strings like arrays.It mainly operates on indexes.
This is simple BM, as I didn't want to go
for more complex variant,becauses takes and drops and recalculation of next
position
is too pricey for non indexed structure. So, clear winner is KMP for
non indexed strings. There is also finite automaton algorithm
but this works well if search strings are precompiled, so I'll
implement it only for education purposes. I hope my Haskell improves
as I've learned how to reduce number of paramaters.
searchReplaceBM :: String -> String -> String -> String
searchReplaceBM "" _ str = str
searchReplaceBM sr rp str = searchReplace str
where
table :: UArray Int Int
table = array (0,255) ([(i,0) | i <- [0..255]] ++ proc sr 1)
proc [] _ = []
proc (s:st) i = (ord s,i):proc st (i+1)
len = length sr
rsrch = reverse sr
searchReplace str
| null remaining = if found then rp
else passed
|found = rp ++ searchReplace remaining
| otherwise = passed ++ searchReplace remaining
where
(passed,remaining,found) = searchReplace' str
searchReplace' str
= if j == 0
then ("",drop len str,True)
else failed
where failed = case drop (j-1) str of
[] -> (str,"",False)
(c:_) -> (take sk str, drop sk str, False)
where md = j - table ! ord c
sk = if md > 0
then md
else 1
j = srch rsrch (reverse $ take len str) len
where srch "" "" _ = 0
srch _ "" l = l
srch (s:str) (s':str') l
| s == s' = srch str str' (l-1)
| otherwise = l
Greetings, Bane.
From: "Branimir Maksimovic" <[EMAIL PROTECTED]>
To: [EMAIL PROTECTED], [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Thu, 15 Dec 2005 01:39:57 +0000
From: "Branimir Maksimovic" <[EMAIL PROTECTED]>
To: [EMAIL PROTECTED]
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Thu, 15 Dec 2005 00:55:02 +0000
From: Daniel Fischer <[EMAIL PROTECTED]>
To: "Branimir Maksimovic" <[EMAIL PROTECTED]>
CC: Haskell-Cafe@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.
Forget what I've said.
Boyer-Moore *can* be implemented efficiently, it is similar to KMP it goes
forward, but when it finds last character in pattern, than starts to search
backwards.
This can be implemented easilly as Haskell lists naturaly reverse order
when putting from one list to other.
Heh, never say never :)
As I see from documents Boyer-Moore has best performance on average
and should be better than KMP.
Greetings,Bane.
_________________________________________________________________
FREE pop-up blocking with the new MSN Toolbar - get it now!
http://toolbar.msn.click-url.com/go/onm00200415ave/direct/01/
_________________________________________________________________
Don't just search. Find. Check out the new MSN Search!
http://search.msn.click-url.com/go/onm00200636ave/direct/01/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
