1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
-- |
-- Module : Data.ByteString.Search.BoyerMoore
-- Copyright : Daniel Fischer
-- Chris Kuklewicz
-- Licence : BSD3
-- Maintainer : Daniel Fischer <daniel.is.fischer@googlemail.com>
-- Stability : Provisional
-- Portability : non-portable (BangPatterns)
--
-- 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 googlemail.com) and
-- Chris Kuklewicz (haskell at list.mightyreason.com).
module Data.ByteString.Search.BoyerMoore
{-# DEPRECATED "Use the new interface instead" #-} (
-- * Overview
-- $overview
-- ** Changes
-- $changes
-- ** Deprecation
-- $deprecation
-- ** Parameter and return types
-- $types
-- ** Lazy ByteStrings
-- $lazy
-- ** Performance
-- $performance
-- ** Complexity
-- $complexity
-- ** Partial application
-- $currying
-- ** Integer overflow
-- $overflow
-- * Functions
matchLL
, matchLS
, matchSL
, matchSS
) where
import Data.ByteString.Search.Internal.BoyerMoore
(matchLS, matchSS)
import Data.ByteString.Lazy.Search.Internal.BoyerMoore
(matchLL, matchSL)
-- $overview
--
-- This module exists only for backwards compatibility. Nevertheless
-- there have been small changes in the behaviour of the functions.
-- The module exports four search functions: 'matchLL', 'matchLS',
-- 'matchSL', and 'matchSS'. All of them return the list of all
-- starting positions of possibly overlapping occurrences of a pattern
-- in a string.
-- $changes
--
-- Formerly, all four functions returned an empty list when passed
-- an empty pattern. Now, in accordance with the functions from the other
-- modules, @matchXY \"\" target = [0 .. 'length' target]@.
-- $deprecation
--
-- This module is /deprecated/. You should use the new interface provided
-- in "Data.ByteString.Search" resp. "Data.ByteString.Lazy.Search".
-- $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
--
-- '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.
-- $currying
--
-- These functions can all be usefully partially applied.
-- Given only a pattern the partially applied version will compute
-- the supporting lookup tables only once, allowing for efficient re-use.
-- Similarly, the partially applied 'matchLL' and 'matchLS' will compute
-- the concatenated pattern only once.
-- $performance
--
-- In general, the Boyer-Moore algorithm is the most efficient method to
-- search for a pattern inside a string. The advantage over other algorithms
-- (e.g. Naïve, Knuth-Morris-Pratt, Horspool, Sunday) can be made
-- arbitrarily large for specially selected patterns and targets, but
-- usually, it's a factor of 2–3 versus Knuth-Morris-Pratt and of
-- 6–10 versus the naïve algorithm. The Horspool and Sunday
-- algorithms, which are simplified variants of the Boyer-Moore algorithm,
-- typically have performance between Boyer-Moore and Knuth-Morris-Pratt,
-- mostly closer to Boyer-Moore. The advantage of the Boyer-moore variants
-- over other algorithms generally becomes larger for longer patterns. For
-- very short patterns (or patterns with a very short period), other
-- algorithms, e.g. "Data.ByteString.Search.DFA" can be faster (my
-- tests suggest that \"very short\" means two, maybe three bytes).
--
-- In general, searching in a strict 'S.ByteString' is slightly faster
-- than searching in a lazy 'L.ByteString', but for long targets the
-- smaller memory footprint of lazy 'L.ByteStrings' can make searching
-- those (sometimes much) faster. On the other hand, there are cases
-- where searching in a strict target is much faster, even for long targets.
--
-- On 32-bit systems, 'Int'-arithmetic is much faster than 'Int64'-arithmetic,
-- so when there are many matches, that can make a significant difference.
--
-- Also, the modification to ameliorate the case of periodic patterns
-- is defeated by chunk-boundaries, so long patterns with a short period
-- and many matches exhibit poor behaviour (consider using @indices@ from
-- "Data.ByteString.Lazy.Search.DFA" or "Data.ByteString.Lazy.Search.KMP"
-- in those cases, the former for medium-length patterns, the latter for
-- long patterns; only 'matchLL' and 'matchSL' suffer from
-- this problem, though).
-- $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 for the original
-- Boyer-Moore algorithm.
--
-- The searching functions in this module contain a modification which
-- drastically improves the performance for periodic patterns.
-- I believe that for strict target strings, the worst case is now
-- /O/(@targetLength@) also for periodic patterns and for lazy target
-- strings, my semi-educated guess is
-- /O/(@targetLength@ * (1 + @patternLength@ \/ @chunkSize@)).
-- $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.
|
