Searching a string using the Rabin-Karp algorithm

The Rabin-Karp algorithm finds a pattern in a body of text by matching a unique representation of the pattern against a moving window. The unique representation, or hash, is computed by considering a string as a number written in an arbitrary base of 26 or greater.

The advantage of Rabin-Karp is in searching for many needles in a haystack. It's not very efficient to search for just a single string. After the initial preprocessing of the corpus, the algorithm can quickly find matches.

Getting ready

Install the Data.ByteString.Search library from Cabal as follows:

$ cabal install stringsearch

How to do it...

1. Use the OverloadedStrings language extension to facilitate the ByteString manipulations in our code as follows. It essentially allows polymorphic behavior for strings so that the GHC compiler may infer it as a ByteString type when necessary:

   {-# LANGUAGE OverloadedStrings #-}

2. Import the Rabin-Karp algorithms as follows:

   import Data.ByteString.Search.KarpRabin (indicesOfAny)
   import qualified Data.ByteString as BS

3. Define a couple of patterns to find and obtain the corpus from a big.txt file, as shown in the following code snippet:

   main = do
     let needles = [ "preparing to go away"
                   , "is some letter of recommendation"]
     haystack <- BS.readFile "big.txt"

4. Run the Rabin-Karp algorithm on all the search patterns as follows:

     print $ indicesOfAny needles haystack

5. The code prints out all indices found for each needle as a list of tuples. The first element of the tuple is the position in the haystack that the needle was found. The second element of the tuple is a list of indices of the needles. In our recipe, we find one instance of "preparing to go away" and two instances of "is some letter of recommendation."

   $ runhaskell Main.hs
   
   [(3738968,[1]),(5632846,[0]),(5714386,[0])]
   

How it works...

In Rabin-Karp, a fixed window moves from left to right, comparing the unique hash values for efficient comparisons. The hash function converts a string to its numerical representation. Here's an example of converting a string into base b equal to 256: "hello" = h' * b4 + e' * b3 + l' * b2 + l' * b1 + o' * b0 (which results in 448378203247), where each letter h' = ord h (which results in 104), and so on.

See also

To see another efficient string searching algorithm, refer to the Searching a string using the Boyer-Moore-Horspool algorithm recipe.