Lesson · Strings and Pattern Matching · Skipping, and its worst case

Shifting by More Than One

Horspool builds one table from the pattern's first m − 1 characters and uses it to shift past positions rather than sliding one at a time. On the lab's prose it examines 14 of the 61 alignments, compares 19 characters at 18 distinct positions of the 66, and makes 19 comparisons against naive matching's 66. Every one of those numbers is a fact about which characters this text happens to contain, and the algorithm's proved worst case is the same m(n − m + 1) naive matching has.

Open the interactive lesson Practice

compare the window right to left; stop at the first disagreement shift by the table entry for the text character under the last position the table is built from p[0..m−2], so p's own last character shifts the full m measured: 14 alignments of 61, 19 comparisons, 52 alignments skipped outright 19 comparisons at only 18 distinct positions: 48 characters are never read naive 66 and KMP 66 on the same text; Horspool's worst case is still m(n − m + 1)

One table, a shift that can be the whole pattern, and no guarantee behind it

Core ideas

What this lesson establishes

The hard idea is that the saving comes from the text as much as from the pattern. The other two are the table and the direction of comparison that makes it usable.

Comparing from the right is what makes a jump computable

The window sits over t[s..s+m−1] and the first comparison is t[s+m−1] against p[m−1]. If that fails, the character t[s+m−1] still has to line up with some occurrence of itself in the pattern at any future alignment that can match, so the next plausible offset is found by asking where that character last occurs in the pattern. Comparing left to right gives no such handle: the character that failed is at an unknown distance from the window's end.

The table is one entry per character, and it is built from m − 1 of them

For each character c, the shift is m − 1 − j where j is the largest index below m − 1 with p[j] = c, and m if there is none. On mainly that gives m → 5, a → 4, i → 3, n → 2, l → 1, and m for everything else — including y, the pattern's own last character, because the table deliberately excludes position m − 1. Excluding it is what lets the algorithm shift the full m when the window's last character is the pattern's last character and everything else failed.

The saving is a property of the text, and nothing is proved by it

The panel reports 52 alignments skipped outright at an average shift of 4.71 out of a maximum of 6, and 19 comparisons where the naive matcher makes 66. All of that is because this text is English and most of its characters do not appear in mainly. The proved worst case is unchanged from the naive matcher's: m(n − m + 1) comparisons, attained on a text this page's sibling “The Text Where Nothing Is Skipped” loads with one click.

The material

One table, one direction of comparison, and a shift that is usually large

The algorithm, the correctness argument for the shift, the measured saving, and the fact that no bound improved.

Definition · The Horspool shift table

For a pattern p of length m over an alphabet A, the shift table is defined for every c in A by: shift[c] = m − 1 − j, where j is the largest index with 0 ≤ j ≤ m − 2 and p[j] = c; and shift[c] = m if c does not occur among p[0..m−2]. Every entry lies between 1 and m.

Definition · Horspool matching

Start with the window at offset s = 0. Compare t[s+k] with p[k] for k = m − 1 downwards, stopping at the first disagreement or reporting a match when k falls below 0. Then set s to s + shift[t[s+m−1]] and repeat while s + m ≤ n. The shift is read from the text character under the window's LAST position, whatever position the comparison actually failed at.

Theorem · The shift skips no match

If the window is at offset s and c = t[s+m−1], then no offset s' with s < s' < s + shift[c] can begin an occurrence of p.

Suppose an occurrence begins at such an s'. The character c sits at text position s + m − 1, which lies inside the occurrence's window because s' ≤ s + m − 1 ≤ s' + m − 1, at pattern index i = s + m − 1 − s', and 0 ≤ i ≤ m − 2 because s' > s.

So p[i] = c for some i ≤ m − 2, and therefore shift[c] is m − 1 − j for the largest such index j, giving i ≤ j and s + m − 1 − s' ≤ m − 1 − shift[c] + ... . Rearranged: s' ≥ s + m − 1 − j = s + shift[c], contradicting s' < s + shift[c].

If c does not occur in p[0..m−2] at all then no such i exists, so no occurrence can begin strictly after s and before s + m, which is the case shift[c] = m.

□

The lab checks that argument empirically on every keystroke rather than resting on it, because the failure mode of a skipping algorithm is to jump over an answer and return a shorter list of positions, and a shorter list of correct positions looks exactly like a correct answer. The match positions are compared with a scan that tests every offset.

Example · Fourteen alignments out of sixty-one

The lab opens on the rain in spain stays mainly in the plain and never in the hills, 66 characters, searched for mainly. Naive matching would try 61 alignments; Horspool examines 14, at offsets 0, 4, 7, 13, 19, 24, 30, 36, 39, 43, 45, 51, 57 and 60. The shifts it takes are 4, 3, 6, 6, 5, 6, 6, 3, 4, 2, 6, 6, 3, 6 — seven of the fourteen are the full m. The single match is at offset 24, and it is examined.

Those fourteen alignments cost 19 comparisons in total, and the breakdown is lopsided: thirteen of them fail on their very first comparison and cost 1 each, and the fourteenth is the match at offset 24, which compares all 6. Thirteen plus six is 19.

Those 19 comparisons landed on only 18 distinct positions of the text, because position 24 is compared twice — once as the last position of the window at offset 19, and again inside the matching window. So 48 of the 66 characters of this text were never compared to anything at all. That is the property the algorithm is famous for, and it is why characters skipped entirely is the counter the panel leads with.

Why the average shift is 4.71 and what it is an average of

The panel's average shift is the sum of the shifts divided by the number of alignments examined, which is 66/14, printed as the exact fraction 33/7. The sum of the shifts is the text length because the window walks from 0 past the end exactly once, so that average is n over the number of alignments — a different quantity from the average over the alphabet, which would be a fact about the pattern alone.

The letters that shift the full six, including one of the pattern's own

The shift table has m → 5, a → 4, i → 3, n → 2, l → 1, and 6 for the space and for d, e, h, p, r, s, t, v and y. The y is worth a second look, because y is in the pattern — it is p[5], the last character. The table is built from p[0..4] only, so y is absent from it and gets the default m. That is deliberate: if the window's last character is y and the comparison still failed, the failure was further left, and no alignment before s + m can succeed either.

The l → 1 entry is the other end of the same table. l occurs at p[4], one place before the end, so a window ending in l can only be advanced by one. A pattern whose penultimate character is common in the text therefore loses most of the benefit, which is the mechanism the next page pushes to its limit.

What did not improve

Naive matching takes 66 comparisons on this text and KMP takes 66 as well. Horspool takes 19, which is better by a factor of three and a half — and its worst case is m(n − m + 1), exactly the naive matcher's, while KMP's remains 2n. So on the page's own numbers the fastest algorithm here has the weakest guarantee of the three, and the slowest has the strongest.

There is no contradiction and there is also no ranking. Three measurements and three bounds are six statements about different things, and the only ones that hold for texts nobody has typed yet are the bounds.

Interactive

Shifting by more than one, and the text that stops it

Characters skipped and comparisons made, against naive matching and KMP

Type a text and a pattern, and watch which characters are never read

The bar chart is one bar per alignment EXAMINED, which on this text is fourteen of sixty-one. The shift table below is built from the pattern's first m − 1 characters, and the step table shows where each window sat, how far the comparison got from the right, and how far it then jumped.

Worked example

The text

The pattern

Show the alignment at1

Alignments examined—

Alignments naive would try—

Characters compared—

Characters skipped entirely—

Average shift—

Comparisons, naive—

Comparisons, KMP—

Matches, and matches by definition—

Horspool compares the window right to left and then shifts by the last occurrence of the text character under the window's last position, looked up in a table built from the pattern's first m − 1 characters. A character the pattern does not contain at all shifts the full m. The saving comes from the TEXT as much as from the pattern: pick the third worked example, where the last character of every window matches and the shift is always 1.

Method

Building the table, then reading the shift off the right character

The commonest mistake here is reading the shift from the character that failed. It is read from the window's last position, always.

Build the table from p[0..m−2], and check the last character's entry

Write the pattern out, number the positions, and for each character record m − 1 − j for its largest index below m − 1. Then confirm that the pattern's own final character got the default m, because that entry is the one that looks like a bug and is not.

Compare from the right and record how far you got

The count for one alignment is the number of characters matched from the right plus one for the disagreement, or m for a match. The panel's step table prints that middle number, and it is usually 0.

Read the shift from the window's last position, not the mismatch

On this text the two coincide, because every failing alignment fails at the last position. Switch to the four-letter preset to see them part: at offset 2 the window is TTACAGA, the comparison fails at position 5 on a G whose table entry is 6, and the window's last character is an A whose entry is 2. The shift taken is 2, and the wrong rule would have jumped to offset 8.

Count the characters never touched, not just the comparisons

19 comparisons landed on 18 distinct positions here, because one position was compared twice. The second figure is the one that explains why the algorithm is fast on large alphabets — 48 characters unread — and it is not what the comparison counter measures.

Where the shift comes from, and what it is worth

Score 0 / 0

Choose the answer you can justify.

The first five alignments, and the shift each one takes

The text is the rain in spain stays mainly in the plain and never in the hills and the pattern is mainly, so m = 6 and the shift table is built from mainl.

shift table m 5 a 4 i 3 n 2 l 1 everything else 6 (y is 6) step at window last char comparisons shift 1 0 'the ra' a 1 4 2 4 'rain i' i 1 3 3 7 'n in s' s 1 6 4 13 'pain s' s 1 6 5 19 'tays m' m 1 5 6 24 'mainly' y 6 6 a match 7 30 ' in th' h 1 6 8 36 'e plai' i 1 3 9 39 'lain a' a 1 4 10 43 ' and n' n 1 2 11 45 'nd nev' v 1 6 12 51 'er in ' space 1 6 13 57 'the hi' i 1 3 14 60 ' hills' s 1 6 alignments examined 14 (of 61) shifts taken 4 3 6 6 5 6 6 3 4 2 6 6 3 6 sum = 66 comparisons 13 x 1 + 1 x 6 = 19 distinct positions compared position 24 twice = 18 (of 66) characters never compared to anything 66 - 18 = 48 alignments skipped outright 66 - 14 = 52 average shift 66/14 = 33/7 = 4.71 naive 66 KMP 66 Horspool 19

Thirteen of the fourteen rows have a 1 in the comparisons column, and every one of those thirteen failed at the window's last position — which is why the shift and the mismatch agree on this text and why it is a bad text for learning the difference between them. The four-letter preset is the one to use for that: at its offset 2 the window is TTACAGA, the failure is at position 5 on a G whose table entry is 6, and the shift taken is 2 because the window's last character is an A.

The other row worth a second look is the sixth. The match at offset 24 costs 6 comparisons, not 1, so the 19 total is 13 plus 6 rather than 14 plus something — and those 19 comparisons land on 18 distinct positions, because position 24 is the last position of the window at offset 19 and is compared again inside the matching window.

For a faded rehearsal, keep the text and change the pattern to plain. The supplied first move is the table: it is built from plai, so p → 4, l → 3, a → 2, i → 1, and 5 for everything else including n. Predict whether the number of alignments examined goes up or down, and say which entry of the table is responsible.

Then try hills. It occurs at the very end of the text, and its table entry for l is 1 because l is p[3]. Predict what happens to the comparison count relative to mainly before running it, and then say whether the change is about the pattern, the text, or both.

Common mistakes

Reading the shift from the mismatching characterThis is the error that makes the algorithm wrong rather than slow. Boyer–Moore has a rule of that shape and it needs a second table to stay correct; Horspool's one-table version works only because the shift is read from a fixed position, the window's last. The lab's scan over every offset is there to catch the difference.

Concluding that a large alphabet guarantees large shiftsIt makes them likely and promises nothing. The DNA preset has four letters, all of which occur in the pattern, and no shift there is ever the full m; the average drops to 2.71 from this page's 4.71. Whether a character is in the pattern is not a function of how many characters there are.

Quoting the comparison count as the characters examinedThey are not the same figure even here: 19 comparisons landed on 18 distinct positions, because position 24 is compared once as a window's last character and again inside the match. On the four-letter preset the gap is wider — 43 comparisons at 35 positions — and the figure that explains the algorithm's reputation is the second one, which the panel does not print.

Check your understanding

✓

Finish when you can build the table for a pattern you have not seen and take four shifts by hand without consulting the mismatch.

You should be able to define shift[c] including the exclusion of p[m−1], prove that no offset before s + shift[c] can begin a match, read a shift from the window's last position rather than the failure, distinguish 19 comparisons from 18 positions touched, and state Horspool's worst case without hedging it.

Note: The whole of this page's saving rests on the window's last character usually shifting far. “The Text Where Nothing Is Skipped” takes the same algorithm to a 30-character text where that character always shifts by 1, and the comparison count goes to five times the naive matcher's on the same input — the largest reversal on this course.