| This document explains Crochemore and Perrin's Two-Way string matching |
| algorithm, in which a smaller string (the "pattern" or "needle") |
| is searched for in a longer string (the "text" or "haystack"), |
| determining whether the needle is a substring of the haystack, and if |
| so, at what index(es). It is to be used by Python's string |
| (and bytes-like) objects when calling `find`, `index`, `__contains__`, |
| or implicitly in methods like `replace` or `partition`. |
| |
| This is essentially a re-telling of the paper |
| |
| Crochemore M., Perrin D., 1991, Two-way string-matching, |
| Journal of the ACM 38(3):651-675. |
| |
| focused more on understanding and examples than on rigor. See also |
| the code sample here: |
| |
| http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260 |
| |
| The algorithm runs in O(len(needle) + len(haystack)) time and with |
| O(1) space. However, since there is a larger preprocessing cost than |
| simpler algorithms, this Two-Way algorithm is to be used only when the |
| needle and haystack lengths meet certain thresholds. |
| |
| |
| These are the basic steps of the algorithm: |
| |
| * "Very carefully" cut the needle in two. |
| * For each alignment attempted: |
| 1. match the right part |
| * On failure, jump by the amount matched + 1 |
| 2. then match the left part. |
| * On failure jump by max(len(left), len(right)) + 1 |
| * If the needle is periodic, don't re-do comparisons; maintain |
| a "memory" of how many characters you already know match. |
| |
| |
| -------- Matching the right part -------- |
| |
| We first scan the right part of the needle to check if it matches the |
| the aligned characters in the haystack. We scan left-to-right, |
| and if a mismatch occurs, we jump ahead by the amount matched plus 1. |
| |
| Example: |
| |
| text: ........EFGX................... |
| pattern: ....abcdEFGH.... |
| cut: <<<<>>>> |
| |
| Matched 3, so jump ahead by 4: |
| |
| text: ........EFGX................... |
| pattern: ....abcdEFGH.... |
| cut: <<<<>>>> |
| |
| Why are we allowed to do this? Because we cut the needle very |
| carefully, in such a way that if the cut is ...abcd + EFGH... then |
| we have |
| |
| d != E |
| cd != EF |
| bcd != EFG |
| abcd != EFGH |
| ... and so on. |
| |
| If this is true for every pair of equal-length substrings around the |
| cut, then the following alignments do not work, so we can skip them: |
| |
| text: ........EFG.................... |
| pattern: ....abcdEFGH.... |
| ^ (Bad because d != E) |
| text: ........EFG.................... |
| pattern: ....abcdEFGH.... |
| ^^ (Bad because cd != EF) |
| text: ........EFG.................... |
| pattern: ....abcdEFGH.... |
| ^^^ (Bad because bcd != EFG) |
| |
| Skip 3 alignments => increment alignment by 4. |
| |
| |
| -------- If len(left_part) < len(right_part) -------- |
| |
| Above is the core idea, and it begins to suggest how the algorithm can |
| be linear-time. There is one bit of subtlety involving what to do |
| around the end of the needle: if the left half is shorter than the |
| right, then we could run into something like this: |
| |
| text: .....EFG...... |
| pattern: cdEFGH |
| |
| The same argument holds that we can skip ahead by 4, so long as |
| |
| d != E |
| cd != EF |
| ?cd != EFG |
| ??cd != EFGH |
| etc. |
| |
| The question marks represent "wildcards" that always match; they're |
| outside the limits of the needle, so there's no way for them to |
| invalidate a match. To ensure that the inequalities above are always |
| true, we need them to be true for all possible '?' values. We thus |
| need cd != FG and cd != GH, etc. |
| |
| |
| -------- Matching the left part -------- |
| |
| Once we have ensured the right part matches, we scan the left part |
| (order doesn't matter, but traditionally right-to-left), and if we |
| find a mismatch, we jump ahead by |
| max(len(left_part), len(right_part)) + 1. That we can jump by |
| at least len(right_part) + 1 we have already seen: |
| |
| text: .....EFG..... |
| pattern: abcdEFG |
| Matched 3, so jump by 4, |
| using the fact that d != E, cd != EF, and bcd != EFG. |
| |
| But we can also jump by at least len(left_part) + 1: |
| |
| text: ....cdEF..... |
| pattern: abcdEF |
| Jump by len('abcd') + 1 = 5. |
| |
| Skip the alignments: |
| text: ....cdEF..... |
| pattern: abcdEF |
| text: ....cdEF..... |
| pattern: abcdEF |
| text: ....cdEF..... |
| pattern: abcdEF |
| text: ....cdEF..... |
| pattern: abcdEF |
| |
| This requires the following facts: |
| d != E |
| cd != EF |
| bcd != EF? |
| abcd != EF?? |
| etc., for all values of ?s, as above. |
| |
| If we have both sets of inequalities, then we can indeed jump by |
| max(len(left_part), len(right_part)) + 1. Under the assumption of such |
| a nice splitting of the needle, we now have enough to prove linear |
| time for the search: consider the forward-progress/comparisons ratio |
| at each alignment position. If a mismatch occurs in the right part, |
| the ratio is 1 position forward per comparison. On the other hand, |
| if a mismatch occurs in the left half, we advance by more than |
| len(needle)//2 positions for at most len(needle) comparisons, |
| so this ratio is more than 1/2. This average "movement speed" is |
| bounded below by the constant "1 position per 2 comparisons", so we |
| have linear time. |
| |
| |
| -------- The periodic case -------- |
| |
| The sets of inequalities listed so far seem too good to be true in |
| the general case. Indeed, they fail when a needle is periodic: |
| there's no way to split 'AAbAAbAAbA' in two such that |
| |
| (the stuff n characters to the left of the split) |
| cannot equal |
| (the stuff n characters to the right of the split) |
| for all n. |
| |
| This is because no matter how you cut it, you'll get |
| s[cut-3:cut] == s[cut:cut+3]. So what do we do? We still cut the |
| needle in two so that n can be as big as possible. If we were to |
| split it as |
| |
| AAbA + AbAAbA |
| |
| then A == A at the split, so this is bad (we failed at length 1), but |
| if we split it as |
| |
| AA + bAAbAAbA |
| |
| we at least have A != b and AA != bA, and we fail at length 3 |
| since ?AA == bAA. We already knew that a cut to make length-3 |
| mismatch was impossible due to the period, but we now see that the |
| bound is sharp; we can get length-1 and length-2 to mismatch. |
| |
| This is exactly the content of the *critical factorization theorem*: |
| that no matter the period of the original needle, you can cut it in |
| such a way that (with the appropriate question marks), |
| needle[cut-k:cut] mismatches needle[cut:cut+k] for all k < the period. |
| |
| Even "non-periodic" strings are periodic with a period equal to |
| their length, so for such needles, the CFT already guarantees that |
| the algorithm described so far will work, since we can cut the needle |
| so that the length-k chunks on either side of the cut mismatch for all |
| k < len(needle). Looking closer at the algorithm, we only actually |
| require that k go up to max(len(left_part), len(right_part)). |
| So long as the period exceeds that, we're good. |
| |
| The more general shorter-period case is a bit harder. The essentials |
| are the same, except we use the periodicity to our advantage by |
| "remembering" periods that we've already compared. In our running |
| example, say we're computing |
| |
| "AAbAAbAAbA" in "bbbAbbAAbAAbAAbbbAAbAAbAAbAA". |
| |
| We cut as AA + bAAbAAbA, and then the algorithm runs as follows: |
| |
| First alignment: |
| bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| AAbAAbAAbA |
| ^^X |
| - Mismatch at third position, so jump by 3. |
| - This requires that A!=b and AA != bA. |
| |
| Second alignment: |
| bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| AAbAAbAAbA |
| ^^^^^^^^ |
| X |
| - Matched entire right part |
| - Mismatch at left part. |
| - Jump forward a period, remembering the existing comparisons |
| |
| Third alignment: |
| bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| AAbAAbAAbA |
| mmmmmmm^^X |
| - There's "memory": a bunch of characters were already matched. |
| - Two more characters match beyond that. |
| - The 8th character of the right part mismatched, so jump by 8 |
| - The above rule is more complicated than usual: we don't have |
| the right inequalities for lengths 1 through 7, but we do have |
| shifted copies of the length-1 and length-2 inequalities, |
| along with knowledge of the mismatch. We can skip all of these |
| alignments at once: |
| |
| bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| AAbAAbAAbA |
| ~ A != b at the cut |
| bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| AAbAAbAAbA |
| ~~ AA != bA at the cut |
| bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| AAbAAbAAbA |
| ^^^^X 7-3=4 match, and the 5th misses. |
| bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| AAbAAbAAbA |
| ~ A != b at the cut |
| bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| AAbAAbAAbA |
| ~~ AA != bA at the cut |
| bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| AAbAAbAAbA |
| ^X 7-3-3=1 match and the 2nd misses. |
| bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| AAbAAbAAbA |
| ~ A != b at the cut |
| |
| Fourth alignment: |
| bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| AAbAAbAAbA |
| ^X |
| - Second character mismatches, so jump by 2. |
| |
| Fifth alignment: |
| bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| AAbAAbAAbA |
| ^^^^^^^^ |
| X |
| - Right half matches, so use memory and skip ahead by period=3 |
| |
| Sixth alignment: |
| bbbAbbAAbAAbAAbbbAAbAAbAAbAA |
| AAbAAbAAbA |
| mmmmmmmm^^ |
| - Right part matches, left part is remembered, found a match! |
| |
| The one tricky skip by 8 here generalizes: if we have a period of p, |
| then the CFT says we can ensure the cut has the inequality property |
| for lengths 1 through p-1, and jumping by p would line up the |
| matching characters and mismatched character one period earlier. |
| Inductively, this proves that we can skip by the number of characters |
| matched in the right half, plus 1, just as in the original algorithm. |
| |
| To make it explicit, the memory is set whenever the entire right part |
| is matched and is then used as a starting point in the next alignment. |
| In such a case, the alignment jumps forward one period, and the right |
| half matches all except possibly the last period. Additionally, |
| if we cut so that the left part has a length strictly less than the |
| period (we always can!), then we can know that the left part already |
| matches. The memory is reset to 0 whenever there is a mismatch in the |
| right part. |
| |
| To prove linearity for the periodic case, note that if a right-part |
| character mismatches, then we advance forward 1 unit per comparison. |
| On the other hand, if the entire right part matches, then the skipping |
| forward by one period "defers" some of the comparisons to the next |
| alignment, where they will then be spent at the usual rate of |
| one comparison per step forward. Even if left-half comparisons |
| are always "wasted", they constitute less than half of all |
| comparisons, so the average rate is certainly at least 1 move forward |
| per 2 comparisons. |
| |
| |
| -------- When to choose the periodic algorithm --------- |
| |
| The periodic algorithm is always valid but has an overhead of one |
| more "memory" register and some memory computation steps, so the |
| here-described-first non-periodic/long-period algorithm -- skipping by |
| max(len(left_part), len(right_part)) + 1 rather than the period -- |
| should be preferred when possible. |
| |
| Interestingly, the long-period algorithm does not require an exact |
| computation of the period; it works even with some long-period, but |
| undeniably "periodic" needles: |
| |
| Cut: AbcdefAbc == Abcde + fAbc |
| |
| This cut gives these inequalities: |
| |
| e != f |
| de != fA |
| cde != fAb |
| bcde != fAbc |
| Abcde != fAbc? |
| The first failure is a period long, per the CFT: |
| ?Abcde == fAbc?? |
| |
| A sufficient condition for using the long-period algorithm is having |
| the period of the needle be greater than |
| max(len(left_part), len(right_part)). This way, after choosing a good |
| split, we get all of the max(len(left_part), len(right_part)) |
| inequalities around the cut that were required in the long-period |
| version of the algorithm. |
| |
| With all of this in mind, here's how we choose: |
| |
| (1) Choose a "critical factorization" of the needle -- a cut |
| where we have period minus 1 inequalities in a row. |
| More specifically, choose a cut so that the left_part |
| is less than one period long. |
| (2) Determine the period P_r of the right_part. |
| (3) Check if the left part is just an extension of the pattern of |
| the right part, so that the whole needle has period P_r. |
| Explicitly, check if |
| needle[0:cut] == needle[0+P_r:cut+P_r] |
| If so, we use the periodic algorithm. If not equal, we use the |
| long-period algorithm. |
| |
| Note that if equality holds in (3), then the period of the whole |
| string is P_r. On the other hand, suppose equality does not hold. |
| The period of the needle is then strictly greater than P_r. Here's |
| a general fact: |
| |
| If p is a substring of s and p has period r, then the period |
| of s is either equal to r or greater than len(p). |
| |
| We know that needle_period != P_r, |
| and therefore needle_period > len(right_part). |
| Additionally, we'll choose the cut (see below) |
| so that len(left_part) < needle_period. |
| |
| Thus, in the case where equality does not hold, we have that |
| needle_period >= max(len(left_part), len(right_part)) + 1, |
| so the long-period algorithm works, but otherwise, we know the period |
| of the needle. |
| |
| Note that this decision process doesn't always require an exact |
| computation of the period -- we can get away with only computing P_r! |
| |
| |
| -------- Computing the cut -------- |
| |
| Our remaining tasks are now to compute a cut of the needle with as |
| many inequalities as possible, ensuring that cut < needle_period. |
| Meanwhile, we must also compute the period P_r of the right_part. |
| |
| The computation is relatively simple, essentially doing this: |
| |
| suffix1 = max(needle[i:] for i in range(len(needle))) |
| suffix2 = ... # the same as above, but invert the alphabet |
| cut1 = len(needle) - len(suffix1) |
| cut2 = len(needle) - len(suffix2) |
| cut = max(cut1, cut2) # the later cut |
| |
| For cut2, "invert the alphabet" is different than saying min(...), |
| since in lexicographic order, we still put "py" < "python", even |
| if the alphabet is inverted. Computing these, along with the method |
| of computing the period of the right half, is easiest to read directly |
| from the source code in fastsearch.h, in which these are computed |
| in linear time. |
| |
| Crochemore & Perrin's Theorem 3.1 give that "cut" above is a |
| critical factorization less than the period, but a very brief sketch |
| of their proof goes something like this (this is far from complete): |
| |
| * If this cut splits the needle as some |
| needle == (a + w) + (w + b), meaning there's a bad equality |
| w == w, it's impossible for w + b to be bigger than both |
| b and w + w + b, so this can't happen. We thus have all of |
| the inequalities with no question marks. |
| * By maximality, the right part is not a substring of the left |
| part. Thus, we have all of the inequalities involving no |
| left-side question marks. |
| * If you have all of the inequalities without right-side question |
| marks, we have a critical factorization. |
| * If one such inequality fails, then there's a smaller period, |
| but the factorization is nonetheless critical. Here's where |
| you need the redundancy coming from computing both cuts and |
| choosing the later one. |
| |
| |
| -------- Some more Bells and Whistles -------- |
| |
| Beyond Crochemore & Perrin's original algorithm, we can use a couple |
| more tricks for speed in fastsearch.h: |
| |
| 1. Even though C&P has a best-case O(n/m) time, this doesn't occur |
| very often, so we add a Boyer-Moore bad character table to |
| achieve sublinear time in more cases. |
| |
| 2. The prework of computing the cut/period is expensive per |
| needle character, so we shouldn't do it if it won't pay off. |
| For this reason, if the needle and haystack are long enough, |
| only automatically start with two-way if the needle's length |
| is a small percentage of the length of the haystack. |
| |
| 3. In cases where the needle and haystack are large but the needle |
| makes up a significant percentage of the length of the |
| haystack, don't pay the expensive two-way preprocessing cost |
| if you don't need to. Instead, keep track of how many |
| character comparisons are equal, and if that exceeds |
| O(len(needle)), then pay that cost, since the simpler algorithm |
| isn't doing very well. |
