Searching a string using the Boyer-Moore-Horspool algorithm

When searching for a pattern in a string, we refer to the pattern as the needle and the whole corpus as the haystack. The Horspool string search algorithm implemented in this recipe performs well for almost all pattern lengths and alphabet sizes, but is ideal for large alphabet sizes and large needle sizes. Empirical benchmarks can be found by navigating to the following URL:

http://orion.lcg.ufrj.br/Dr.Dobbs/books/book5/chap10.htm

By preprocessing the query, the algorithm is able to efficiently skip redundant comparisons. In this recipe, we will implement a simplified version called Horspool's algorithm, which achieves the same average best case as the Boyer-Moore algorithm, benefits from having a smaller overhead cost, but may in very rare circumstances suffer the same worst-case running time as the naive search when the algorithm performs too many matches. The Boyer-Moore algorithms should only be used if the extra prepossessing time and space required are acceptable.

How to do it...

1. We will be using a couple Data.Map functions as follows:

   import Data.Map (fromList, (!), findWithDefault)

2. For convenience, define tuples representing character indices as follows:

   indexMap xs = fromList $ zip [0..] xs
   
   revIndexMap xs = fromList $ zip (reverse xs) [0..]

3. Define the search algorithm to use the recursive bmh' function as follows:

   bmh :: Ord a => [a] -> [a] -> Maybe Int
   
   bmh pat xs = bmh' (length pat - 1) (reverse pat) xs pat

4. Recursively find the pattern in the current index until the index moves past the length of the string, as shown in the following code snippet:

   bmh' :: Ord a => Int -> [a] -> [a] -> [a] -> Maybe Int 
   
   bmh' n [] xs pat = Just (n + 1)
   bmh' n (p:ps) xs pat 
     | n >= length xs   = Nothing
     | p == (indexMap xs) ! n = bmh' (n - 1) ps xs pat
     | otherwise              = bmh' (n + findWithDefault
                                     (length pat) (sMap ! n) pMap) 
                                     (reverse pat) xs pat
     where sMap = indexMap xs
           pMap = revIndexMap pat

5. Test out the function as follows:

   main :: IO ()
   main = print $ bmh "Wor" "Hello World"

6. The following printed output displays the first index of the matching substring:

   Just 6
   

How it works...

This algorithm compares the desired pattern to a moving window through the text. The efficiency comes from how quickly the moving window shifts left to right through this text. In the Horspool algorithm, the query is compared to the current window character by character from right to left, and the window shifts by the size of the query in the best case.

Another version of the Horspool algorithm designed by Remco Niemeijer can be found at http://bonsaicode.wordpress.com/2009/08/29/programming-praxis-string-search-boyer-moore.

There's more...

The Boyer-Moore algorithm ensures a faster worst case, but also endures slightly more initial overhead. Refer to the following commands to use the Boyer-Moore algorithm from the Data.ByteString.Search package:

$ cabal install stringsearch

Import the following libraries:

import Data.ByteString.Search
import qualified Data.ByteString.Char8 as C

Feed two ByteString types to the indices function to run the search as follows:

main = print $ indices (C.pack "abc") (C.pack "bdeabcdabc")

This will print out the following indices:

[3,7]

By benchmarking the performance of this library, we can see that longer search needles really improve runtime. We modify the code to search through a huge corpus of words from a file called big.txt to find multiple needles. Here, we use the deepseq function to force evaluation, so Haskell's lazy nature won't ignore it, as shown in the following code:

shortNeedles = ["abc", "cba"]
longNeedles = ["very big words", "some long string"]

main = do
  corpus <- BS.readFile "big.txt"
  map (\x -> (not.null) (indices x corpus)) shortNeedles     
    'deepseq' return ()

We can compile this code with special runtime system (RTS) control for easy profiling as follows:

$ ghc -O2 Main.hs –rtsopts

$ ./Main +RTS -sstder

We use the text from norvig.com/big.txt as our corpus. Searching for 25 long needles takes just about 0.06 seconds; however, searching for 25 short needles takes a sluggish 0.19 seconds.

See also

For another efficient string searching algorithm, refer to the Searching a string using the Rabin-Karp algorithm recipe.