[Haskell-cafe] Substring replacements
bmaxa at hotmail.com
Wed Dec 14 04:16:36 EST 2005
>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: Tue, 13 Dec 2005 11:23:29 +0100
After seeing that your program is fastest (I've also tried one from
http://haskell.org/hawiki/RunTimeCompilation but perhaps I'm not
that good in converting to search replace?) I've decided to
try with Rabin-Karp algorithm.
This algorithm performs same operation as straightforward search,
but compares hashes instead of chars.
With ability to rotate hash (remove first, add next) characters
there is also optimisation, that hash is calculated only for single
next character rather again for whole substring.
Unfortunatelly on my machine it is very cheap to compare
characters so with my test hashing overweights character compare,
except in your test when hash searching is faster then straightforward
This is best I can write in terms of performance and readability.
I've tried with getFst that returns Maybe but it was slower so I decided
to return '\0' in case that argument is empty list, which renders '\0'
unusable, but then I really doubt that 0 will be used in strings.
-- Rabin-Karp string search algorithm, it is very effective in searching of
-- of patterns of length n on same string
-- this program is for single pattern search, but can be crafted
-- for multiple patterns of length m
hSearchReplace :: String -> String -> String -> String
hSearchReplace sr rp xs
| not (null remaining) = found ++ rp
++ hSearchReplace sr rp (drop (length sr)
| otherwise = found
(found,remaining) = hSearch sr xs
hSearch :: String -> String -> (String,String)
hSearch sr xs = hSearch' sr xs hcmp ""
hsrch = hash sr
hcmp = hash $ take ls xs
cmp = take ls xs
ls = length sr
hSearch'  xs _ _= (xs,)
hSearch' sr  _ fndFail = (reverse fndFail,)
hSearch' srch xxs@(x:xs) hcmps fndFail
= if hsrch == hcmps
then if isPrefixOf srch xxs
then (reverse fndFail,xxs)
= hSearch' srch xs
(hashRotate (getFst xxs) (getFst nextxxs) (ls-1)
nextxxs = drop ls xxs
getFst :: String -> Char
getFst  = '\0'
getFst (a:as) = a
hash :: String -> Int
= hash' str (length str - 1)
hash' :: String -> Int -> Int
hash'  _ = 0
hash' (s:str) pow = (101 ^ pow) *(fromEnum s)
+ hash' str (pow-1)
hashRotate :: Char -> Char -> Int -> Int -> Int
hashRotate cout cin pow hsh
= (hsh - ((101 ^ pow) * (fromEnum cout)))*101
+ (fromEnum cin)
Express yourself instantly with MSN Messenger! Download today it's FREE!
More information about the Haskell-Cafe