官术网_书友最值得收藏!

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.

主站蜘蛛池模板: 三都| 资源县| 东明县| 渝北区| 巴里| 泰兴市| 和龙市| 阿城市| 新源县| 新泰市| 福州市| 中卫市| 南岸区| 阳曲县| 托克逊县| 靖宇县| 哈巴河县| 剑河县| 涟水县| 乐都县| 东乡县| 嘉义市| 建阳市| 兴海县| 平邑县| 德昌县| 民勤县| 静海县| 镇江市| 离岛区| 彭水| 晋州市| 景洪市| 池州市| 龙井市| 伊通| 都安| 白玉县| 吉安县| 青铜峡市| 北碚区|