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

Lempel ziv — where it appears

The family of parses that cut a text into phrases, each the longest string that has already occurred earlier in it. The number of phrases is one of the two measures of repetition this collection weighs texts by, and it is the one that counts places where copying has to restart.

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

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

Two copies of a text have exactly the same symbol statistics as one, so every entropy on this site doubles when the second copy arrives and the second copy carries no information at all. The number of runs in the Burrows-Wheeler transform is 224 at two copies and 224 at thirty-two.

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

MeasurementPhraseRepetitionSuffix automatonTrade offConstructionDepth capParseDefinitionExtractionAlphabetAmortised

All concepts