| 1 |
This document explains Crochemore and Perrin's Two-Way string matching |
| 2 |
algorithm, in which a smaller string (the "pattern" or "needle") |
| 3 |
is searched for in a longer string (the "text" or "haystack"), |
| 4 |
determining whether the needle is a substring of the haystack, and if |
| 5 |
so, at what index(es). It is to be used by Python's string |
| 6 |
(and bytes-like) objects when calling `find`, `index`, `__contains__`, |
| 7 |
or implicitly in methods like `replace` or `partition`. |
| 8 |
|
| 9 |
This is essentially a re-telling of the paper |
| 10 |
|
| 11 |
Crochemore M., Perrin D., 1991, Two-way string-matching, |
| 12 |
Journal of the ACM 38(3):651-675. |
| 13 |
|
| 14 |
focused more on understanding and examples than on rigor. See also |
| 15 |
the code sample here: |
| 16 |
|
| 17 |
http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260 |
| 18 |
|
| 19 |
The algorithm runs in O(len(needle) + len(haystack)) time and with |
| 20 |
O(1) space. However, since there is a larger preprocessing cost than |
| 21 |
simpler algorithms, this Two-Way algorithm is to be used only when the |
| 22 |
needle and haystack lengths meet certain thresholds. |
| 23 |
|
| 24 |
|
| 25 |
These are the basic steps of the algorithm: |
| 26 |
|
| 27 |
* "Very carefully" cut the needle in two. |
| 28 |
* For each alignment attempted: |
| 29 |
1. match the right part |
| 30 |
* On failure, jump by the amount matched + 1 |
| 31 |
2. then match the left part. |
| 32 |
* On failure jump by max(len(left), len(right)) + 1 |
| 33 |
* If the needle is periodic, don't re-do comparisons; maintain |
| 34 |
a "memory" of how many characters you already know match. |
| 35 |
|
| 36 |
|
| 37 |
-------- Matching the right part -------- |
| 38 |
|
| 39 |
We first scan the right part of the needle to check if it matches the |
| 40 |
the aligned characters in the haystack. We scan left-to-right, |
| 41 |
and if a mismatch occurs, we jump ahead by the amount matched plus 1. |
| 42 |
|
| 43 |
Example: |
| 44 |
|
| 45 |
text: ........EFGX................... |
| 46 |
pattern: ....abcdEFGH.... |
| 47 |
cut: <<<<>>>> |
| 48 |
|
| 49 |
Matched 3, so jump ahead by 4: |
| 50 |
|
| 51 |
text: ........EFGX................... |
| 52 |
pattern: ....abcdEFGH.... |
| 53 |
cut: <<<<>>>> |
| 54 |
|
| 55 |
Why are we allowed to do this? Because we cut the needle very |
| 56 |
carefully, in such a way that if the cut is ...abcd + EFGH... then |
| 57 |
we have |
| 58 |
|
| 59 |
d != E |
| 60 |
cd != EF |
| 61 |
bcd != EFG |
| 62 |
abcd != EFGH |
| 63 |
... and so on. |
| 64 |
|
| 65 |
If this is true for every pair of equal-length substrings around the |
| 66 |
cut, then the following alignments do not work, so we can skip them: |
| 67 |
|
| 68 |
text: ........EFG.................... |
| 69 |
pattern: ....abcdEFGH.... |
| 70 |
^ (Bad because d != E) |
| 71 |
text: ........EFG.................... |
| 72 |
pattern: ....abcdEFGH.... |
| 73 |
^^ (Bad because cd != EF) |
| 74 |
text: ........EFG.................... |
| 75 |
pattern: ....abcdEFGH.... |
| 76 |
^^^ (Bad because bcd != EFG) |
| 77 |
|
| 78 |
Skip 3 alignments => increment alignment by 4. |
| 79 |
|
| 80 |
|
| 81 |
-------- If len(left_part) < len(right_part) -------- |
| 82 |
|
| 83 |
Above is the core idea, and it begins to suggest how the algorithm can |
| 84 |
be linear-time. There is one bit of subtlety involving what to do |
| 85 |
around the end of the needle: if the left half is shorter than the |
| 86 |
right, then we could run into something like this: |
| 87 |
|
| 88 |
text: .....EFG...... |
| 89 |
pattern: cdEFGH |
| 90 |
|
| 91 |
The same argument holds that we can skip ahead by 4, so long as |
| 92 |
|
| 93 |
d != E |
| 94 |
cd != EF |
| 95 |
?cd != EFG |
| 96 |
??cd != EFGH |
| 97 |
etc. |
| 98 |
|
| 99 |
The question marks represent "wildcards" that always match; they're |
| 100 |
outside the limits of the needle, so there's no way for them to |
| 101 |
invalidate a match. To ensure that the inequalities above are always |
| 102 |
true, we need them to be true for all possible '?' values. We thus |
| 103 |
need cd != FG and cd != GH, etc. |
| 104 |
|
| 105 |
|
| 106 |
-------- Matching the left part -------- |
| 107 |
|
| 108 |
Once we have ensured the right part matches, we scan the left part |
| 109 |
(order doesn't matter, but traditionally right-to-left), and if we |
| 110 |
find a mismatch, we jump ahead by |
| 111 |
max(len(left_part), len(right_part)) + 1. That we can jump by |
| 112 |
at least len(right_part) + 1 we have already seen: |
| 113 |
|
| 114 |
text: .....EFG..... |
| 115 |
pattern: abcdEFG |
| 116 |
Matched 3, so jump by 4, |
| 117 |
using the fact that d != E, cd != EF, and bcd != EFG. |
| 118 |
|
| 119 |
But we can also jump by at least len(left_part) + 1: |
| 120 |
|
| 121 |
text: ....cdEF..... |
| 122 |
pattern: abcdEF |
| 123 |
Jump by len('abcd') + 1 = 5. |
| 124 |
|
| 125 |
Skip the alignments: |
| 126 |
text: ....cdEF..... |
| 127 |
pattern: abcdEF |
| 128 |
text: ....cdEF..... |
| 129 |
pattern: abcdEF |
| 130 |
text: ....cdEF..... |
| 131 |
pattern: abcdEF |
| 132 |
text: ....cdEF..... |
| 133 |
pattern: abcdEF |
| 134 |
|
| 135 |
This requires the following facts: |
| 136 |
d != E |
| 137 |
cd != EF |
| 138 |
bcd != EF? |
| 139 |
abcd != EF?? |
| 140 |
etc., for all values of ?s, as above. |
| 141 |
|
| 142 |
If we have both sets of inequalities, then we can indeed jump by |
| 143 |
max(len(left_part), len(right_part)) + 1. Under the assumption of such |
| 144 |
a nice splitting of the needle, we now have enough to prove linear |
| 145 |
time for the search: consider the forward-progress/comparisons ratio |
| 146 |
at each alignment position. If a mismatch occurs in the right part, |
| 147 |
the ratio is 1 position forward per comparison. On the other hand, |
| 148 |
if a mismatch occurs in the left half, we advance by more than |
| 149 |
len(needle)//2 positions for at most len(needle) comparisons, |
| 150 |
so this ratio is more than 1/2. This average "movement speed" is |
| 151 |
bounded below by the constant "1 position per 2 comparisons", so we |
| 152 |
have linear time. |
| 153 |
|
| 154 |
|
| 155 |
-------- The periodic case -------- |
| 156 |
|
| 157 |
The sets of inequalities listed so far seem too good to be true in |
| 158 |
the general case. Indeed, they fail when a needle is periodic: |
| 159 |
there's no way to split 'AAbAAbAAbA' in two such that |
| 160 |
|
| 161 |
(the stuff n characters to the left of the split) |
| 162 |
cannot equal |
| 163 |
(the stuff n characters to the right of the split) |
| 164 |
for all n. |
| 165 |
|
| 166 |
This is because no matter how you cut it, you'll get |
| 167 |
s[cut-3:cut] == s[cut:cut+3]. So what do we do? We still cut the |
| 168 |
needle in two so that n can be as big as possible. If we were to |
| 169 |
split it as |
| 170 |
|
| 171 |
AAbA + AbAAbA |
| 172 |
|
| 173 |
then A == A at the split, so this is bad (we failed at length 1), but |
| 174 |
if we split it as |
| 175 |
|
| 176 |
AA + bAAbAAbA |
| 177 |
|
| 178 |
we at least have A != b and AA != bA, and we fail at length 3 |
| 179 |
since ?AA == bAA. We already knew that a cut to make length-3 |
| 180 |
mismatch was impossible due to the period, but we now see that the |
| 181 |
bound is sharp; we can get length-1 and length-2 to mismatch. |
| 182 |
|
| 183 |
This is exactly the content of the *critical factorization theorem*: |
| 184 |
that no matter the period of the original needle, you can cut it in |
| 185 |
such a way that (with the appropriate question marks), |
| 186 |
needle[cut-k:cut] mismatches needle[cut:cut+k] for all k < the period. |
| 187 |
|
| 188 |
Even "non-periodic" strings are periodic with a period equal to |
| 189 |
their length, so for such needles, the CFT already guarantees that |
| 190 |
the algorithm described so far will work, since we can cut the needle |
| 191 |
so that the length-k chunks on either side of the cut mismatch for all |
| 192 |
k < len(needle). Looking closer at the algorithm, we only actually |
| 193 |
require that k go up to max(len(left_part), len(right_part)). |
| 194 |
So long as the period exceeds that, we're good. |
| 195 |
|
| 196 |
The more general shorter-period case is a bit harder. The essentials |
| 197 |
are the same, except we use the periodicity to our advantage by |
| 198 |
"remembering" periods that we've already compared. In our running |
| 199 |
example, say we're computing |
| 200 |
|
| 201 |
"AAbAAbAAbA" in "bbbAbbAAbAAbAAbbbAAbAAbAAbAA". |
| 202 |
|
| 203 |
We cut as AA + bAAbAAbA, and then the algorithm runs as follows: |
| 204 |
|
| 205 |
First alignment: |
| 206 |
bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| 207 |
AAbAAbAAbA |
| 208 |
^^X |
| 209 |
- Mismatch at third position, so jump by 3. |
| 210 |
- This requires that A!=b and AA != bA. |
| 211 |
|
| 212 |
Second alignment: |
| 213 |
bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| 214 |
AAbAAbAAbA |
| 215 |
^^^^^^^^ |
| 216 |
X |
| 217 |
- Matched entire right part |
| 218 |
- Mismatch at left part. |
| 219 |
- Jump forward a period, remembering the existing comparisons |
| 220 |
|
| 221 |
Third alignment: |
| 222 |
bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| 223 |
AAbAAbAAbA |
| 224 |
mmmmmmm^^X |
| 225 |
- There's "memory": a bunch of characters were already matched. |
| 226 |
- Two more characters match beyond that. |
| 227 |
- The 8th character of the right part mismatched, so jump by 8 |
| 228 |
- The above rule is more complicated than usual: we don't have |
| 229 |
the right inequalities for lengths 1 through 7, but we do have |
| 230 |
shifted copies of the length-1 and length-2 inequalities, |
| 231 |
along with knowledge of the mismatch. We can skip all of these |
| 232 |
alignments at once: |
| 233 |
|
| 234 |
bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| 235 |
AAbAAbAAbA |
| 236 |
~ A != b at the cut |
| 237 |
bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| 238 |
AAbAAbAAbA |
| 239 |
~~ AA != bA at the cut |
| 240 |
bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| 241 |
AAbAAbAAbA |
| 242 |
^^^^X 7-3=4 match, and the 5th misses. |
| 243 |
bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| 244 |
AAbAAbAAbA |
| 245 |
~ A != b at the cut |
| 246 |
bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| 247 |
AAbAAbAAbA |
| 248 |
~~ AA != bA at the cut |
| 249 |
bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| 250 |
AAbAAbAAbA |
| 251 |
^X 7-3-3=1 match and the 2nd misses. |
| 252 |
bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| 253 |
AAbAAbAAbA |
| 254 |
~ A != b at the cut |
| 255 |
|
| 256 |
Fourth alignment: |
| 257 |
bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| 258 |
AAbAAbAAbA |
| 259 |
^X |
| 260 |
- Second character mismatches, so jump by 2. |
| 261 |
|
| 262 |
Fifth alignment: |
| 263 |
bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| 264 |
AAbAAbAAbA |
| 265 |
^^^^^^^^ |
| 266 |
X |
| 267 |
- Right half matches, so use memory and skip ahead by period=3 |
| 268 |
|
| 269 |
Sixth alignment: |
| 270 |
bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| 271 |
AAbAAbAAbA |
| 272 |
mmmmmmmm^^ |
| 273 |
- Right part matches, left part is remembered, found a match! |
| 274 |
|
| 275 |
The one tricky skip by 8 here generalizes: if we have a period of p, |
| 276 |
then the CFT says we can ensure the cut has the inequality property |
| 277 |
for lengths 1 through p-1, and jumping by p would line up the |
| 278 |
matching characters and mismatched character one period earlier. |
| 279 |
Inductively, this proves that we can skip by the number of characters |
| 280 |
matched in the right half, plus 1, just as in the original algorithm. |
| 281 |
|
| 282 |
To make it explicit, the memory is set whenever the entire right part |
| 283 |
is matched and is then used as a starting point in the next alignment. |
| 284 |
In such a case, the alignment jumps forward one period, and the right |
| 285 |
half matches all except possibly the last period. Additionally, |
| 286 |
if we cut so that the left part has a length strictly less than the |
| 287 |
period (we always can!), then we can know that the left part already |
| 288 |
matches. The memory is reset to 0 whenever there is a mismatch in the |
| 289 |
right part. |
| 290 |
|
| 291 |
To prove linearity for the periodic case, note that if a right-part |
| 292 |
character mismatches, then we advance forward 1 unit per comparison. |
| 293 |
On the other hand, if the entire right part matches, then the skipping |
| 294 |
forward by one period "defers" some of the comparisons to the next |
| 295 |
alignment, where they will then be spent at the usual rate of |
| 296 |
one comparison per step forward. Even if left-half comparisons |
| 297 |
are always "wasted", they constitute less than half of all |
| 298 |
comparisons, so the average rate is certainly at least 1 move forward |
| 299 |
per 2 comparisons. |
| 300 |
|
| 301 |
|
| 302 |
-------- When to choose the periodic algorithm --------- |
| 303 |
|
| 304 |
The periodic algorithm is always valid but has an overhead of one |
| 305 |
more "memory" register and some memory computation steps, so the |
| 306 |
here-described-first non-periodic/long-period algorithm -- skipping by |
| 307 |
max(len(left_part), len(right_part)) + 1 rather than the period -- |
| 308 |
should be preferred when possible. |
| 309 |
|
| 310 |
Interestingly, the long-period algorithm does not require an exact |
| 311 |
computation of the period; it works even with some long-period, but |
| 312 |
undeniably "periodic" needles: |
| 313 |
|
| 314 |
Cut: AbcdefAbc == Abcde + fAbc |
| 315 |
|
| 316 |
This cut gives these inequalities: |
| 317 |
|
| 318 |
e != f |
| 319 |
de != fA |
| 320 |
cde != fAb |
| 321 |
bcde != fAbc |
| 322 |
Abcde != fAbc? |
| 323 |
The first failure is a period long, per the CFT: |
| 324 |
?Abcde == fAbc?? |
| 325 |
|
| 326 |
A sufficient condition for using the long-period algorithm is having |
| 327 |
the period of the needle be greater than |
| 328 |
max(len(left_part), len(right_part)). This way, after choosing a good |
| 329 |
split, we get all of the max(len(left_part), len(right_part)) |
| 330 |
inequalities around the cut that were required in the long-period |
| 331 |
version of the algorithm. |
| 332 |
|
| 333 |
With all of this in mind, here's how we choose: |
| 334 |
|
| 335 |
(1) Choose a "critical factorization" of the needle -- a cut |
| 336 |
where we have period minus 1 inequalities in a row. |
| 337 |
More specifically, choose a cut so that the left_part |
| 338 |
is less than one period long. |
| 339 |
(2) Determine the period P_r of the right_part. |
| 340 |
(3) Check if the left part is just an extension of the pattern of |
| 341 |
the right part, so that the whole needle has period P_r. |
| 342 |
Explicitly, check if |
| 343 |
needle[0:cut] == needle[0+P_r:cut+P_r] |
| 344 |
If so, we use the periodic algorithm. If not equal, we use the |
| 345 |
long-period algorithm. |
| 346 |
|
| 347 |
Note that if equality holds in (3), then the period of the whole |
| 348 |
string is P_r. On the other hand, suppose equality does not hold. |
| 349 |
The period of the needle is then strictly greater than P_r. Here's |
| 350 |
a general fact: |
| 351 |
|
| 352 |
If p is a substring of s and p has period r, then the period |
| 353 |
of s is either equal to r or greater than len(p). |
| 354 |
|
| 355 |
We know that needle_period != P_r, |
| 356 |
and therefore needle_period > len(right_part). |
| 357 |
Additionally, we'll choose the cut (see below) |
| 358 |
so that len(left_part) < needle_period. |
| 359 |
|
| 360 |
Thus, in the case where equality does not hold, we have that |
| 361 |
needle_period >= max(len(left_part), len(right_part)) + 1, |
| 362 |
so the long-period algorithm works, but otherwise, we know the period |
| 363 |
of the needle. |
| 364 |
|
| 365 |
Note that this decision process doesn't always require an exact |
| 366 |
computation of the period -- we can get away with only computing P_r! |
| 367 |
|
| 368 |
|
| 369 |
-------- Computing the cut -------- |
| 370 |
|
| 371 |
Our remaining tasks are now to compute a cut of the needle with as |
| 372 |
many inequalities as possible, ensuring that cut < needle_period. |
| 373 |
Meanwhile, we must also compute the period P_r of the right_part. |
| 374 |
|
| 375 |
The computation is relatively simple, essentially doing this: |
| 376 |
|
| 377 |
suffix1 = max(needle[i:] for i in range(len(needle))) |
| 378 |
suffix2 = ... # the same as above, but invert the alphabet |
| 379 |
cut1 = len(needle) - len(suffix1) |
| 380 |
cut2 = len(needle) - len(suffix2) |
| 381 |
cut = max(cut1, cut2) # the later cut |
| 382 |
|
| 383 |
For cut2, "invert the alphabet" is different than saying min(...), |
| 384 |
since in lexicographic order, we still put "py" < "python", even |
| 385 |
if the alphabet is inverted. Computing these, along with the method |
| 386 |
of computing the period of the right half, is easiest to read directly |
| 387 |
from the source code in fastsearch.h, in which these are computed |
| 388 |
in linear time. |
| 389 |
|
| 390 |
Crochemore & Perrin's Theorem 3.1 give that "cut" above is a |
| 391 |
critical factorization less than the period, but a very brief sketch |
| 392 |
of their proof goes something like this (this is far from complete): |
| 393 |
|
| 394 |
* If this cut splits the needle as some |
| 395 |
needle == (a + w) + (w + b), meaning there's a bad equality |
| 396 |
w == w, it's impossible for w + b to be bigger than both |
| 397 |
b and w + w + b, so this can't happen. We thus have all of |
| 398 |
the inequalities with no question marks. |
| 399 |
* By maximality, the right part is not a substring of the left |
| 400 |
part. Thus, we have all of the inequalities involving no |
| 401 |
left-side question marks. |
| 402 |
* If you have all of the inequalities without right-side question |
| 403 |
marks, we have a critical factorization. |
| 404 |
* If one such inequality fails, then there's a smaller period, |
| 405 |
but the factorization is nonetheless critical. Here's where |
| 406 |
you need the redundancy coming from computing both cuts and |
| 407 |
choosing the later one. |
| 408 |
|
| 409 |
|
| 410 |
-------- Some more Bells and Whistles -------- |
| 411 |
|
| 412 |
Beyond Crochemore & Perrin's original algorithm, we can use a couple |
| 413 |
more tricks for speed in fastsearch.h: |
| 414 |
|
| 415 |
1. Even though C&P has a best-case O(n/m) time, this doesn't occur |
| 416 |
very often, so we add a Boyer-Moore bad character table to |
| 417 |
achieve sublinear time in more cases. |
| 418 |
|
| 419 |
2. The prework of computing the cut/period is expensive per |
| 420 |
needle character, so we shouldn't do it if it won't pay off. |
| 421 |
For this reason, if the needle and haystack are long enough, |
| 422 |
only automatically start with two-way if the needle's length |
| 423 |
is a small percentage of the length of the haystack. |
| 424 |
|
| 425 |
3. In cases where the needle and haystack are large but the needle |
| 426 |
makes up a significant percentage of the length of the |
| 427 |
haystack, don't pay the expensive two-way preprocessing cost |
| 428 |
if you don't need to. Instead, keep track of how many |
| 429 |
character comparisons are equal, and if that exceeds |
| 430 |
O(len(needle)), then pay that cost, since the simpler algorithm |
| 431 |
isn't doing very well. |