Re: [Haskell-cafe] Substring replacements

15 Dec 2005

      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" 
To: bmaxa@hotmail.com, daniel.is.fischer@web.de
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Thu, 15 Dec 2005 01:39:57 +0000
...
From: "Branimir Maksimovic" 
To: daniel.is.fischer@web.de
CC: Haskell-Cafe@haskell.org
Subject: Re: [Haskell-cafe] Substring replacements
Date: Thu, 15 Dec 2005 00:55:02 +0000
...
From: Daniel Fischer 
To: "Branimir Maksimovic" 
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/