Data.ByteString.Search.BoyerMoore

Fast overlapping Boyer-Moore search of both strict and lazy ByteString values.

Descriptions of the algorithm can be found at http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140 and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm

Original authors: Daniel Fischer (daniel.is.fischer at web.de) and Chris Kuklewicz (haskell at list.mightyreason.com).

Overview

This module exports 4 search functions: matchLL, matchLS, matchSL, and matchSS.

If given an empty pattern, a search will always return an empty list.

Parameter and return types

The first parameter is always the pattern string. The second parameter is always the target string to be searched. The returned list contains the offsets of all overlapping patterns.

A returned Int or Int64 is an index into the target string which is aligned to the head of the pattern string. Strict targets return Int indices and lazy targets return Int64 indices. All returned lists are computed and returned in a lazy fashion.

Lazy ByteStrings

matchLL and matchLS take lazy bytestrings as patterns. For performance, if the pattern is not a single strict chunk then all the the pattern chunks will copied into a concatenated strict bytestring. This limits the patterns to a length of (maxBound :: Int).

matchLL and matchSL take lazy bytestrings as targets. These are written so that while they work they will not retain a reference to all the earlier parts of the the lazy bytestring. This means the garbage collector would be able to keep only a small amount of the target string and free the rest.

Performance

Operating on a strict target string is faster than a lazy target string. It is unclear why the performance gap is as large as it is (patches welcome). To slightly ameliorate this, if the lazy string is a single chunk then a copy of the strict algorithm is used.

Complexity

Preprocessing the pattern string is O(patternLength). The search performance is O(targetLength/patternLength) in the best case, allowing it to go faster than a Knuth-Morris-Pratt algorithm. With a non-periodic pattern the worst case uses O(3*targetLength) comparisons. The periodic pattern worst case is quadratic O(targetLength*patternLength) complexity. Improvements (e.g. Turbo-Boyer-Moore) to catch and linearize worst case performance slow down the loop significantly.

Currying

These functions can all be usefully curried. Given only a pattern the curried version will compute the supporting lookup tables only once, allowing for efficient re-use. Similarly, the curried matchLL and matchLS will compute the concatenated pattern only once.

Integer overflow

The current code uses Int to keep track of the locations in the target string. If the length of the pattern plus the length of any strict chunk of the target string is greater or equal to maxBound::Int then this will overflow causing an error. We try to detect this and call error before a segfault occurs.

Functions

matchLL

Arguments

:: ByteString

lazy pattern

-> ByteString

lazy target string

-> [Int64]

offsets of matches

matchLS

Arguments

:: ByteString

lazy pattern

-> ByteString

strict target string

-> [Int]

offsets of matches

matchSL

Arguments

:: ByteString

strict pattern

-> ByteString

lazy target string

-> [Int64]

offsets of matches

matchSS

Arguments

:: ByteString

strict pattern

-> ByteString

strict target string

-> [Int]

offsets of matches