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

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.

主站蜘蛛池模板: 漳平市| 丹江口市| 新乡市| 葫芦岛市| 乡宁县| 芦山县| 奉贤区| 临西县| 中牟县| 安塞县| 福州市| 布尔津县| 京山县| 大关县| 伊宁市| 松桃| 汉阴县| 安国市| 淮阳县| 兰考县| 盘锦市| 漳浦县| 繁昌县| 桓台县| 进贤县| 台安县| 体育| 阿坝| 吉首市| 陆河县| 五指山市| 罗田县| 大洼县| 滕州市| 霍城县| 项城市| 花莲市| 滁州市| 翼城县| 海阳市| 秦安县|