Generator

What each rule reads, as the pattern set grows

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
What each rule reads, as the pattern set growsCharacters examined in 20,000 characters of four symbols, by pattern set size. The bad-character rule alone stops skipping almost at once; the published rules and the exact rules run together, apart at the smallest sets — 1.06x at 2 patterns — and identical from 32 upward. Both axes are logarithmic.101001,00010⁴10⁵characters of pattern in the setcharacters examinedno shift (step one)bad character onlythe 1979 shift functionsboth rules, exactlyfour symbols · patterns of 10n = 20,000

What each rule reads, as the pattern set grows

Characters examined in 20,000 characters of four symbols, by pattern set size. The bad-character rule alone stops skipping almost at once; the published rules and the exact rules run together, apart at the smallest sets — 1.06x at 2 patterns — and identical from 32 upward. Both axes are logarithmic.

Drawn at 700 × 430, wide on the page. Everything above is what published-shift returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

8 essays call published-shift. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.

Where it is called

Changing this generator changes every one of these figures.

101001,00010010³10⁴10⁵characters of pattern in the setcomparisons before the scanboth rules, exactlybad character onlythe 1979 shift functionsfour symbols · patterns of 10137.35x at 128 patterns What a bound is

The table that walks every pair

1,00010,00010³10⁴characters of textcomparisons, built and scannedcrossing at n = 32,000both rules, exactlythe 1979 tables2 patterns of 10 · four symbolscrossing n = 32,000 What the libraries do

The rule that pays on a long enough text

·1, 4b1, 3b1, 2b4, 2a4, 2a2, 2a4, 2b4, 2b4, 2b4, 2patterns abbb, baab, bbab · shortest 4d₁, d₂ under each node · a filled node ends a patternthe reversed-pattern trie10 nodes The data that is not a number

The shift somebody published

1,00010,00010³10⁴characters of textsteps, precomputation plus scancrossing at 8,000published rulesexact rules2 patterns · four symbolscrossing 8,000 · was 32,000 What the libraries do

Where the exact rules pay now

good suffix, defined757,058good suffix, from links3,824bad character, defined12,666bad character, swept5,168128 patterns · 1,280 characters of patternfour symbols · m = 10198x and 2.5x What a bound is

The case a failure link does not cover

101001,00010010³10⁴10⁵total length of the pattern setprimitive stepsthe definitionfrom the linksthe published rulefour symbols · m = 1085.60x apart at 128 patterns The data that is not a number

The table the links already knew

short by 133.6% of pairsshort by 211.2% of pairsshort by 411.2% of pairsthe same shift7994.0% of pairspatterns of 10 over four symbolsthe published rule is never the larger of the twoshift decisions84 pairs · 21 nodes What is taught wrongly

What the approximation gives up

101001,00010100total length of the pattern settimes the published rule's precomputationwritten as a definitionbuilt from the linksthe published rulefour symbols · m = 10137x becomes 1.60x What is taught wrongly

The ratio that was an implementation

The library, page 3 of 5 — where published-shift sits