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

Bounded depth parse — where it appears

A Lempel-Ziv parse whose phrases may only copy from regions shallower than a cap, so no character costs more than that many phrase follows to produce. It buys a bounded read cost with phrases, and at a cap of one the phrase count returns to being proportional to the text it was supposed to compress.

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

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

A parse that will not follow a long chain

A greedy self-referential parse bounds the copy depth by nothing at all — thirty-two copies of a text give a position costing twenty-two phrase follows. Restricting every phrase to sources no deeper than D holds it at D, and the whole question is what that costs.

text · Parse 11010⁴10⁵worst copy chain, phrases followedbits124816noneno capcap on each pointEnglish-like · 16 copies of 512z 156 to 7,351

What a ceiling costs in phrases

A cap of sixteen costs one phrase of a hundred and fifty-six and halves the worst chain. A cap of four costs six times the phrases. The curve between them is flat at one end and vertical at the other, and the elbow is where a structure should be built.

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

The term that came back

A phrase index is worth building because 8,192 characters parse into 156 phrases. Cap the copy depth at one and the same text parses into 7,351 — ninety per cent of the characters — and the structure is proportional to the text again.

space · Parse a text that repeats itself2.96xchain 13 · z 110English-like1.31xchain 10 · z 604four symbols, uniform1.28xchain 10 · z 816periodic, period 171.11xchain 9 · z 1,285phrases under a cap of four, against no cap4,096 characters each2.96x to 1.11x

The cap that binds on one text and not another

A periodic text looks like the one made of chains and pays 1.11 times the phrases for a cap of four. A text that repeats itself pays 2.96. The guess is backwards, and the reason is that depth measures nesting rather than repetition.

wrong · Parse

Named alongside it

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

Copy depthLempel ziv parseMeasurementPhraseTrade offCompressibilityIndex sizeRepetitionSelf-indexDistributionHonest limitParameter choice

All concepts