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

Parse — where it appears

The cutting of a text into phrases, each copied from somewhere earlier or emitted as a literal. It is the object every phrase-based index is built on, and its phrase count is a property of the text rather than of the construction that produced it — which is why two constructions must agree phrase for phrase.

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

11010³cap on the depthphrases9.8% more phrasesevery occurrence consideredthe earliest only4,096 charactersworst at cap 4

The cap an automaton cannot see

A state of a suffix automaton stands for a set of occurrences and hands back one of them. So a capped parse driven by it can ask whether the earliest occurrence is shallow enough and cannot ask whether any occurrence is — which costs up to 9.8% of the phrases, and only at the caps that bind.

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

The parse in one pass of the text

The same parse, phrase for phrase, from 1,324,336 character comparisons or from 25,420 transitions and suffix-link steps. One of those numbers grows with the text and the other grows with its square, and the difference is why every measurement about a depth cap here was taken on a few thousand characters.

text · 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.

ExtractionCorpusDepthPhrase countConstructionCopyHistogramLempel zivMeasurementPhraseSuffix automatonTrade off

All concepts