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

Extraction — where it appears

Producing a stretch of the original text from a structure that does not store it. Its cost is what a depth cap bounds and what a sampling rate trades against space, and it is the operation that makes an index self-indexing rather than an accelerator sitting beside a text.

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

1101001,00010010³position in the textLF stepsspan + sample = 64row sampling onlywith the secondsampling8,192 characters · sample one in 32 · span 32second sampling 3,598 bits

The sampling that goes the other way

An FM-index hands the text back, and the way it does it is to walk from the last character to the first. So thirty-two characters from the end cost thirty-three steps and thirty-two characters from the beginning cost eight thousand one hundred and ninety-two. The repair is a second array the same size as the first, indexed the other way round.

indexes · Index 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 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

Four essays here are about capping how far an extraction follows a chain of copies, and every number in them came from a generated collection. Here is the depth histogram of a real version history, which is a bell, and of twelve unrelated essays, which is nearly the same bell.

text · Parse 05101520510revisions in the collectiondepthone revision alone: 8worst depthmean depthfourteen revisions of another9 generations added exactly one

One revision, one level

The cap ladder assumed depth is generations of copying. On a real file it is exactly that — one more revision, one more level, nine times running — plus eight levels the first revision already had before any history existed.

structures · Parse 73 characters long24 runsto depth 7270 characters long24 runsto depth 69longest: 73 × "-" at position 11,0162,685 positions below depth 20, 2,685 of them inside a runeight source modules · worst depth 78100.0% in runs

The deepest text is punctuation

Eight source files reach depth 78 in a parse, on a collection with no version history in it at all. The positions between depth 20 and depth 72 are the same 48 characters at every level, and every one of them is a dash in a comment separator.

wrong · Parse 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 11010⁴cap on the depthphrasesno capcap 165,536 characters · 16 copies26x at cap 1

What a quadratic construction was setting

A depth cap of one costs 90% of an 8,192-character text in phrases, and 86% of a 65,536-character one. The ladder's conclusions hold at thirty-two times the size — and the number the ladder could not reach, the deepest chain a real collection produces, turns out to be fourteen.

wrong · Parse

Named alongside it

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

ParseCorpusDepthHistogramPhrase countCopyMeasurementTrade offVersion historyCapControlDepth cap

All concepts