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: bonsai, code, Haskell, karp, kata, praxis, programming, rabin, search, string