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

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.

主站蜘蛛池模板: 北川| 嵊泗县| 邛崃市| 循化| 无锡市| 胶南市| 寿宁县| 石首市| 肃北| 宣汉县| 南陵县| 遵义县| 沈阳市| 西宁市| 林甸县| 疏附县| 绩溪县| 高雄县| 南乐县| 雷州市| 昌江| 安达市| 焦作市| 山东| 南昌市| 麻城市| 田阳县| 肃宁县| 大余县| 平邑县| 彭山县| 大同县| 乌海市| 白山市| 大渡口区| 富阳市| 平江县| 烟台市| 含山县| 枝江市| 建德市|