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

Practice — where it appears

What an implementation does, as against what an analysis says it does. It is where a constant, a threshold and a cache live, and most of the distance between a bound and a duration is here — measurable, rather than anecdotal.

Named by 7 essays across 2 fields — each of them below, with the objects they name alongside it.

depth 0190.1%depth 19642.9%depth 24,92915.0%depth 37,00921.4%depth 48,47325.9%depth 56,24119.0%depth 63,31010.1%depth 71,2503.8%depth 84221.3%depth 91240.4%depth 10270.1%positions32,768 characters · 1172 phrasesmean 3.98

The number that would choose a cap

A depth histogram is one linear pass — 3.16 operations a character over thirty-two thousand of them — and it says the whole text sits at a mean depth of 3.98 with a worst of ten. Nobody prints it, and every choice of cap in this collection was made without it.

practice · Parse 100100occurrences of the patternreadsmost frequent ", and " · 388 occurrencesthe scanthe chain12 documents · 144,617 characters3 of 6 won

What the generated collection was right about

Five strands of conclusions, drawn on collections made by one line with one dial, checked against a corpus nobody made. Most hold. One headline was a property of the generator's alphabet, and one crossing that was guessed at turns out to be met — but only with the structure the strand on range minima built.

practice · Document 0200400200400occurrences of the patternrows read, and documents in the answerrows readdocuments in the answertwo thousand short documents · 2,214 documents1.04 occurrences a document

The crossing that never arrives

Output-sensitive document listing exists because a pattern can occur four thousand times in eight documents. On a real collection of two thousand short documents it occurs 1.04 times per document, and the whole apparatus buys nothing at all.

practice · Document ten revisions of one filecap 10worst 14 · mean 5.7fourteen revisions of anothercap 10worst 17 · mean 7.2twelve unrelated essayscap 10worst 14 · mean 4.9eight source modulescap 10worst 78 · mean 5.9a generated collectioncap 10worst 13 · mean 4.6within a twentieth of the free parsefour to eight was the model

The cap that would ship

The published sweep put the knee at four to eight. On four real collections it is at nine to twelve, a cap of one costs forty-eight times the free parse rather than twenty-one, and the number a system should actually set is none of those.

practice · Parse 0102030255075100125one sampled position in every …of both halves saved, per cent"about a sixth"the marks alone: 14.0%8,192 characters16.7% at one in 32

A sixth of what, exactly

The saving from a counting-only reverse half is 30.5% at one sampled position in four and 14.0% at one in a hundred and twenty-eight. A number quoted without its sampling rate is a number about a setting somebody chose.

wrong · Distance both halves, one in 3215.0 steps100.0% the sizeforward sampled one in 3215.0 steps83.3% the sizeforward sampled one in 167.0 steps88.4% the sizeforward sampled one in 83.0 steps98.5% the sizeforward sampled one in 41.7 steps118.8% the size8,192 characters · 6 occurrences5.0x faster, 98.5% the size

The saving, spent

A bidirectional index whose reverse half cannot locate is a sixth smaller. Give that sixth back to the half that does locate, and the same total size answers a locate five times faster.

practice · Distance a segment tree over the chain2.70x8,142,274 bitsa succinct range minimum over the chain1.62x4,898,356 bitsno chain at all0.84x2,534,726 bitsthe dashed rule is the index itself: a suffix array and the text131,327 characters · 256 documents2.70x → 0.84x

The apparatus that is smaller than its index

Answering "which documents hold this" at a price proportional to the answer used to cost 2.70 times the index it sits beside. Two changes later it costs 0.84, and the largest thing left is an array that says which document each row belongs to.

practice · Index

Named alongside it

The objects these essays reach for when they reach for this one.

Index sizeCorpusDocument listingOutput-sensitiveParameterRange minimumSpaceTradeBidirectional indexDocument collectionExtractionFM-index

All concepts