Algorithms & Data Structures
the bound is a claim, and it is checkable
Field

The data that is not a number

A string comparison costs characters, and how many depends on what the two strings share. A symbol stream repeats, and repetition is the only thing any compressor has ever used. Both are invisible to a counter that charges one for a comparison, and both change which algorithm wins.
048162432characters every key sharesoperations072,581145,162Character comparisonsRadix sort, characters readElement comparisonsone unit = one character comparisonelement comparisons constant at 3,955

The comparison that is not one comparison

What happens to a comparison count when the elements are strings — why the element count cannot move while the character count grows seventeenfold, and why a radix sort that never compares anything is the honest comparison.

 characters examinedNaive scan520,25663.51 per text characterKnuth–Morris–Pratt16,3211.99 per text characterBoyer–Moore–Horspool8,1290.99 per text characterRabin–Karp00.00 per text characterone unit = one character comparisonone matcher read no characters at all

The shift the pattern already knows

KMP's failure function, the exact 2n bound on characters examined, why the bound is worth almost nothing on the inputs it is usually quoted for, and what a worst-case guarantee actually buys.

 one read per text character24816326495alphabet size, m = 8characters read ÷ text length0.01.12.2Naive scanKnuth–Morris–PrattBoyer–Moore–Horspoolone unit = one character comparison · n = 20,000, m = 8Horspool's best here: 0.132 per character

The text that answers without reading it

Why a string search can be sublinear, what the bad-character table actually measures, why the advantage saturates at the alphabet size rather than growing with the pattern, and where the floor under all of it sits.

 H0H1H2H3H4model order — symbols of contextbits per symbol0.02.14.2Uniform over 8 symbolsOrder-1 Markov chainWords from a fixed vocabulary32,768 symbols · at H4 the deepest source has 709 contexts, 0 seen oncemodels: orders 0, 1, 2, 3, 42.06 bits found by one symbol of context

The model is the compressor

Conditional entropy as a measured quantity, why every model gives a different and correct floor, what an adaptive coder pays for not being told the model in advance, and where the estimate stops being an estimate.

 8 patterns of 10 characters over four symbols02,0004,0006,0008,00010,00012,00014,00016,00018,000one cell = 10 positions · shade = fraction read61.6% of the text

The shift a set of patterns allows

Commentz-Walter, the multi-pattern matcher that skips — the two shift conditions computed exactly, the bad-character rule doing almost nothing, and what the tables cost to build.

 each row is one rotation · the table is sorted · the transform is the last columnfirstlast◇the-order-is-the-message-is-the-message◇the-order-message◇the-order-is-the-order-is-the-message◇the-the-message◇the-order-isage◇the-order-is-the-messder-is-the-message◇the-ore◇the-order-is-the-message-message◇the-order-is-the-order-is-the-message◇ther-is-the-message◇the-ordessage◇the-order-is-the-mge◇the-order-is-the-messahe-message◇the-order-is-t… 11 further rotationsmeasured on 8,192 symbols of the same source:H₀ of the text3.899 bitsH₀ of the last column3.899 bitsH₀ after move-to-front, before4.156 bitsH₀ after move-to-front, after1.802 bitsmodel: order 0, before and after a permutationmean run 1.01 → 3.38

The transform that emits nothing

How a permutation lowers a floor it cannot change — sorted rotations, the clustering that follows, move-to-front, and why the inverse is the only proof the transform is real.

 —gactacgat—gattacagt0123456789101234567821012345673211123456432212345554332123456543321234765443222387655432339876554333one unit = one subproblem given a value100 cells, 100 held at once

A distance that is a path through a grid

Edit distance as a shortest path, why it is a metric and which of the four conditions is doing work, and what changes when a substitution is priced at two.

 pattern of 24, 3 errors allowedpositions in the text20,000candidates proposed140candidates verified140occurrences7pattern 24 · 3 errors · 28,700 cells against 480,000selectivity 5.0%

The filter that feeds the table

Seed-and-extend over a compressed self-index — the pigeonhole that makes it correct, the funnel from twenty thousand positions to seven, and the two numbers that decide whether the filter paid.

 roothseirhesssolid: a transition on a character · dashed: a suffix or failure link10 states for 12 pattern characters

One pass for every pattern at once

Aho–Corasick as KMP's failure function applied to a trie, what the output links are for, and the measured gap between one pass and one pass per pattern.

 1,00010,00010³10⁴bits · runs12481632characters in the collection · copies aboven·H₃, bitsr, runs in thetransformEnglish-like · base 512 · divergence 0n·H₃ x15.8 · r x1.00

The entropy that cannot see a copy

Why Hₖ is blind to repetition at a distance, what r and z measure instead, and the three orderings five texts get from three measures of compressibility.

 —ttacgggacgtaccagt—acgt000000000000000000111011110111011011222101221012101112333210122101211212433321123210122221one unit = one subproblem given a value90 cells, top row zero, answer read from the last row

The row that starts at zero

Approximate search as the edit-distance table with its top row zeroed — why the global distance says nothing about occurrence, what the last row is, and what the threshold does and does not change.

 is·holds·no·the·the·of·of·rather·count·class·that·is·algorithm·o1111111211111151141131111111211122213111111212phrase lengths below each block · a shaded block is a literalEnglish-like · 64 charactersz = 46 · 17 literals

The phrases a text copies from itself

What the greedy self-referential parse counts, how its phrase count compares with the run count on the same texts, and why neither is an entropy.

 1,00010,000110occurrences12481632characters in the collection · copies aboveall occurrencessecondaryprimarypattern "ss is un" · z = 1561 primary · 31 secondary

The occurrences that cross a boundary

Why an index built on a parse only has to search for the occurrences that straddle a phrase boundary, and what producing the rest costs.

 k = 0k = 1k = 2k = 3k = 4k = 5k = 6q = 223211917151311q = 3221916131074q = 4211713951-3q = 520151050-5-10q = 6191371-5-11-17q = 81791-7-15-23-31a shaded cell is a threshold of zero or less: every window proposedt = m + 1 − q(k+1) · m = 2411 collapsed cells

The q-grams an error cannot destroy

The counting filter, the pigeonhole argument behind its threshold, and why its saving is in a different currency from the seed filter's.

 ·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 shift somebody published

What Commentz-Walter's published shift functions actually compute, why they are cheap, and how they are checked against the exact rules they approximate.

 124816nonephrasescap on the copy chainphrasesworst chainEnglish-like · 8,192 charactersz 156 to 7,351

A parse that will not follow a long chain

How a depth-bounded Lempel-Ziv parse is constructed, why the bound has to be checked over the whole source region rather than at its start, and what the dial does at each end.

 atgaattcatgagtgacaag00000111111112222222errorsthe pattern, left to right · D belowleast errors neededD, the bound4 symbols · m = 2090 ranks · 2 resets

The errors the rest of the pattern needs

How a one-pass lower bound on the errors in each pattern prefix is computed, why it is safe, and how close it comes to the true minimum.

 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 table the links already knew

How the exact Commentz-Walter shift rule splits into a case the failure links already compute and a case they do not, and what the second case is.

 right to left8302.74xleft to right8772.89xone per piece4471.48xthe scheme3031.00xinterval extensionsall four found the same 6 positions15 characters · k = 22.74x apart

The search that starts in the middle

Search schemes over a bidirectional index, why beginning at a piece that must match exactly cuts the tree by a factor of nearly three, and how the saving grows with the budget.

 1,00010⁴10⁵10⁶charactersoperationscharacter comparisonstransitions and linksrepetitive · 8 copies346 phrases at 8,192

The parse in one pass of the text

The greedy Lempel-Ziv parse driven by a suffix automaton, the one ordering that makes it reproduce the quadratic construction exactly, and what it costs per character.

 twelve essays — runs0.491generated, matched0.109twelve essays — phrases0.213generated, matched0.046eight source modules — runs0.461generated, matched0.122eight source modules — phrases0.210generated, matched0.050ten revisions of one file — runs0.126generated, matched0.113ten revisions of one file — phrases0.067generated, matched0.047per character24,576 characters a partdivergence 0.02

A corpus that was not generated

The frozen real corpus, its three parts and why they repeat for three different reasons, and the first measurements of a collection nobody in this collection made.

 ① prose144,617 chars12 docs · median 12,335① code106,283 chars8 docs · median 13,150① revisions75,658 chars10 docs · median 7,774② essays1,004,822 chars82 docs · median 12,335② captions549,210 chars2,214 docs · median 230② history174,282 chars14 docs · median 12,963① the first freeze · ② the second6 parts

A million characters of the same thing

The second frozen corpus at a million characters, both measures of repetition swept across two orders of magnitude, and the control that says how much of the movement is the collection.

 02468101214mean 5.71depthshare of the collectionten revisionstwelve essays75,658 characters · 2,966 phrasesworst 14, mean 5.71

The shape of a real history's depth

The depth profile of two real version histories and two collections that are not histories at all, measured position by position, against the generated collection every earlier number was taken on.

 one text16 short documentsprosecopies of one baseprose, one textr/n 0.2996z/n 0.1273prose, many short documentsr/n 0.3053z/n 0.1301copies of one base, run togetherr/n 0.0638z/n 0.0354one copy per documentr/n 0.0768z/n 0.04188,192 characters throughoutthe outlined cell is the one that was empty

The cell nobody filled

The four cells of repetition against document count, measured on one text arranged four ways, and why the empty corner had to be built rather than predicted.

 10⁴0.1charactersphrases of the parse, per charactershuffled: 1.45xthe collection: 4.71x4,111 to 65,551 charactersworth 3.24x after the control

What repetition is worth once the logarithm is gone

The size sweep drawn on a repetitive collection with its own shuffled control, and the difference between a text that repeats and one that is merely predictable.

 equal lengths5.00 bits100.0%lengths as one over rank4.15 bits83.4%a few long, many short4.31 bits86.7%one document holding most of the text1.69 bits39.5%log₂ 3232 documents · 8,192 characters100.0% to 39.5%

The array is the length distribution

How far a document array compresses, decided in advance by how a collection apportions its characters, with the null case measured rather than mentioned.

 both halves locate250,584 · 100.0%the reverse half counts only226,504 · 90.4%and its marks are Elias-Fano210,934 · 84.2%and its levels are block-coded167,707 · 66.9%the saving spent on one in eight198,258 · 79.1%protein text, 16,384 characterseach change on top of the last

The part every saving left alone

A bidirectional FM-index over 16,384 characters of four texts — DNA and protein letters at random, English words, and a repetitive collection — with the reverse half counting only and Elias–Fano marks on the forward half, its wavelet-tree levels held plain or coded in blocks of 63 bits: the sequence of size reductions one change longer, bits a character for plain balanced, plain Huffman-shaped and coded balanced trees, where on each level the coding saves, vector reads an extension of exact searches, the superblock's trade between bits and reads, and where the bits go once the levels are coded.

 six bits a classone entropy coderuns of a class0.2870.2770.258DNA0.4810.4610.535protein0.4800.3440.323English0.4800.2660.295repetitivebits a character, classes of both trees, per halfclasses, with their pointers16,384 characters a text

Six bits a class

The bidirectional index of 16,384 characters with block-coded wavelet-tree levels, on random DNA and protein letters, English words and a repetitive collection, with each block's class held in six bits, by one entropy code over every level, or as runs of one value, each with a pointer into the class stream at every superblock: the classes' bits under each coding, the levels as a whole, uniform and mixed blocks and the mean run of one class, the class values themselves, vector reads an extension walking classes or runs, and what the pointers cost.

 the arrangement's indexthe gaps between changesthe shorter, behind a flagEnglish1.2771.3251.008repetitive0.4680.2570.213DNA1.8842.6281.919protein4.0865.5924.15616,384 characters, both treesbits a character of text

A flag for the blocks that change once

The bidirectional index of 16,384 characters with block-coded wavelet-tree levels and run-coded classes, on random DNA and protein letters, English words and a repetitive collection, with each mixed block's offset held as its arrangement's index, as the gaps between its value changes in Elias-gamma codes, or as the shorter of the two behind a one-bit flag: the offsets' bits a character under each coding, how many times a mixed block changes value, the two codings' cost against a block's changes, the levels as each coding is applied, and what a rank reads inside a mixed block.

 01234block length, bits (log scale)levels' bits a character1531631272555111,023English words, as first builtrepetitive collection, as first builtEnglish words, runs and the flagrepetitive collection, runs and the flagdashed: a class a block, arrangements only16,384 characters, both trees

The optimum the flag took away

The wavelet-tree levels of a bidirectional index over four texts of 16,384 characters, re-cut into blocks of 15 to 1,023 bits and coded with classes as runs and each mixed block's offset the shorter of its arrangement's index and its value-change gaps behind a flag, beside the coding as first built: bits a character under both codings; bits against each text's own total at 63; English words by part; the share of mixed blocks that change value once; a rank's work against length; bits against work; and the saving from each doubling.

All essays