Programming Praxis – String Search: Rabin-Karp

Today’s Programming Praxis problem marks the end of the string search series. In this final entry, we have to implement the Rabin-Karp search algorithm. Let’s see what we can do.

First some imports:

import Data.Char
import Data.List

We need the ascii values of the characters in the string, and since the hash values we’re going to be using can get quite large, we’re going to use Integers.

asciis :: String -> [Integer]
asciis = map (fromIntegral . ord)

The hash function treats the list of ascii values as a base 256 number.

hash :: Num a => [a] -> a
hash = sum . zipWith (*) (iterate (* 256) 1) . reverse

For the algorithm, we need the hashes of all the pattern-length substrings of the search string.

hashes :: Int -> String -> [Integer]
hashes p xs = scanl (\s (f,t) -> 256*s - 256^p*f + t) (hash $ take p ascs) .
              zip ascs $ drop p ascs where ascs = asciis xs

With those helper functions defined, the search algorithm becomes fairly straightforward:

rabinKarp :: String -> Maybe Int -> String -> Maybe Int
rabinKarp p s = lookup (hash $ asciis p) . drop (maybe 0 id s) .
                flip zip [0..] . hashes (length p)

And as before, we run our algorithm through the test suite:

test :: (String -> Maybe Int -> String -> Maybe Int) -> IO ()
test f = do assertEqual (f ""   Nothing  "Hello World") (Just 0)
            assertEqual (f "He" Nothing  "Hello World") (Just 0)
            assertEqual (f "od" Nothing  "Bonsai Code") (Just 8)
            assertEqual (f "ef" Nothing  "Bonsai Code") (Nothing)
            assertEqual (f ""   (Just 1) "Hello World") (Just 1)
            assertEqual (f "He" (Just 1) "Hello World") (Nothing)
            assertEqual (f "od" (Just 1) "Bonsai Code") (Just 8)
            assertEqual (f "ef" (Just 1) "Bonsai Code") (Nothing)
         where assertEqual a b = print (a == b, a, b)

main :: IO ()
main = test rabinKarp

Everything’s working correctly. Not bad for 6 lines of code.

About these ads

Tags: , , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: