THE FOLD / GLITCH / OFF BY ONE / THE BOYER-MOORE
THE BOYER-MOORE
search by skipping — learn most from a mismatch
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Boyer–Moore string search is counter-intuitively fast because it matches the pattern right to left and, on a mismatch, skips ahead — often by the whole pattern length. The bad-character rule: if the text character that caused the mismatch does not occur in the pattern, jump the pattern entirely past it; if it does, align the pattern’s last occurrence of that character.
This can make the search sublinear — examining fewer characters than the text length — the only common exact-match algorithm that routinely does. It runs
LIT verified live: over 500 random texts and patterns, the bad-character (Horspool) search returns exactly the same match positions as a naive scan (window.__boyermoore). FIG no framing; exact string matching.
This can make the search sublinear — examining fewer characters than the text length — the only common exact-match algorithm that routinely does. It runs
grep -F and editors’ find.LIT verified live: over 500 random texts and patterns, the bad-character (Horspool) search returns exactly the same match positions as a naive scan (window.__boyermoore). FIG no framing; exact string matching.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at off-by-one — the skip-table index arithmetic where one miscounted shift breaks everything. Boyer–Moore lives or dies by getting those jumps exactly right. AVAN (AI) built the instrument: the bad-character skip table, the right-to-left compare, the exact check against a naive scan.
Credit as content: Robert S. Boyer & J Strother Moore (1977); the simpler bad-character-only variant is Nigel Horspool (1980). The weave: David names the off-by-one; I precompute the skip table, compare from the right, and prove the leaping search finds exactly the matches a full scan does.
Credit as content: Robert S. Boyer & J Strother Moore (1977); the simpler bad-character-only variant is Nigel Horspool (1980). The weave: David names the off-by-one; I precompute the skip table, compare from the right, and prove the leaping search finds exactly the matches a full scan does.
3 ONE DIMENSION
A mismatch at the right end: the offending text character is looked up in the skip table, and the pattern jumps ahead so its last occurrence of that character lines up — or leaps clear past if it is absent.
4 TWO DIMENSIONS · INTERACTIVE
A text and a pattern. Step the search and watch the pattern leap ahead on mismatches. All occurrences are found, and checked against a naive scan.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the alignments the search actually tests, sparse across the text as the pattern leaps.
AVAN’s addition (the inverse-companion): knowing where the pattern is not lets you skip. A mismatch carries more information than a match — it proves a whole range of alignments impossible at once, because comparing from the right and precomputing each character’s last position means one failed comparison can leap the pattern’s full width. The inverse of ‘check every position’ is ‘use each failure to rule out many positions.’ Magenta is the alignments never tested — leapt over on the strength of a single mismatch; green is the few the algorithm actually checks. Search faster by learning the most from what does not match — the rare algorithm that reads less than its input.
LIT Genuine Boyer-Moore string search (Boyer & Moore 1977; bad-character variant Horspool 1980). Verified live: the bad-character skip-table search, comparing right-to-left, returns exactly the same set of match positions as a naive O(nm) scan for 500 random texts and patterns (window.__boyermoore.matchesNaive); 'abr' in 'abracadabra' -> 0,7.
FIG No framing: the skip table, the right-to-left compare, and the exact check against naive search run in-browser and agree. The AVAN inverse is honest — a mismatch rules out many alignments at once, so comparing from the right with a precomputed last-occurrence table lets one failure leap the pattern's full width; magenta is the alignments skipped, green the few actually tested.
FIG No framing: the skip table, the right-to-left compare, and the exact check against naive search run in-browser and agree. The AVAN inverse is honest — a mismatch rules out many alignments at once, so comparing from the right with a precomputed last-occurrence table lets one failure leap the pattern's full width; magenta is the alignments skipped, green the few actually tested.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of OFF BY ONE · David Lee Wise (ROOT0), with AVAN