The term that came back

Every compressed index in this field exists to remove one term. A suffix array is $n\lceil\log_2 n\rceil$ bits; an FM-index replaces that with something proportional to an entropy; a run-length index replaces the entropy with a run count; a phrase index replaces the run count with a phrase count. Each step is the same move, made against a smaller measure of the same text.

What is still proportional to n is the essay about what survives it. This one is about a constraint that undoes it.

The number #

A collection of sixteen copies of five hundred and twelve characters of English-like text. 8,192 characters. Nineteen distinct symbols.

The greedy parse gives 156 phrases, which is 1.9% of the text. That is the whole case for the structure: an index with z in its size measures 8,892 bits for the index against 34,615 for a compressed FM-index over the same collection, and the reason is that 156 is a very small number.

The parse capped at depth one gives 7,351 phrases, which is 89.7% of the text. The index is 514,570 bits.

Sixty times the structure, and the text it is indexing has not changed by a character.

Why a cap of one is nearly a character-at-a-time enumeration #

Because there is almost nowhere left to copy from.

A phrase at depth one must copy from a region at depth zero, and depth zero is the literals. A text over $\sigma$ symbols has about $\sigma$ literal phrases — one per symbol, after which every character has been seen — so a cap of one restricts every copy to a source region of a few dozen scattered characters.

Nineteen of them here, and they are single characters. A source region of one character supports a match of length one. So almost every phrase is a single character copied from the one literal of that symbol, and the parse is a character-at-a-time enumeration with a pointer instead of a letter.

That is worse than storing the text, and the arithmetic says by how much: 7,351 phrases at $2\lceil\log_2 n\rceil + \lceil\log_2\sigma\rceil = 26+5 = 31$ bits each is 227,881 bits for the phrase table alone, against 8,192 characters at five bits, which is 40,960. A structure built to compress the text is twelve times the packed text.

The measure was never the point on its own #

The lesson is not “do not cap at one”. Nobody would. It is that a structure proportional to a measure of repetition is proportional to that measure under a specific set of allowances, and the allowances are part of the claim.

$z$ is small because the parse may copy from anywhere earlier, at any depth, with the source overlapping the phrase itself. Remove the depth allowance and $z$ is not small any more. The number 156 was never a property of the text alone; it was a property of the text and an unbounded chain, and the essay that introduced it said so in the sentence about what it was refusing to bound.

That is the same structure of claim a sampling that costs more than the array makes about the r-index’s run-boundary sampling: a structure built to remove a term proportional to the text costs, on four-symbol text, twice the whole suffix array it replaced. Both are cases where a measure’s smallness has a precondition and the precondition is where the interesting behaviour is.

What the intermediate settings do to the term #

Between the two ends the phrase count is a fraction of the text: 89.7% at a cap of one, 34.9% at two, 11.5% at four, 2.08% at eight, 1.92% at sixteen, 1.90% uncapped.

So the term proportional to $n$ does not come back suddenly. It is present at every cap and it is negligible above about eight, on this collection — which is the same elbow the previous essay measures, seen through a different denominator.

The right way to read that is as a statement about what the cap is for. A cap of eight on this collection is a bound on the read cost that costs nine per cent of the structure; a cap of one is a different kind of object entirely — a structure whose read cost is constant and whose size is linear in the text, which is to say an array of pointers, which is to say the text.

The thing that did not come back, which is the useful half #

One quantity is unmoved by all of this and it is worth putting on the record, because it is what separates a bad structure from a structure at a bad setting.

The text is still recoverable and still not stored. At every cap, including one, the index holds no characters except the literals and produces the whole text from the parse. It is a self-index at 514,570 bits and it is a self-index at 8,580, and the seal that enforces that — every read of the text during a query is an error — is unchanged.

So the collapse is a size collapse, not a correctness one. The structure keeps every property it was built for and loses the only reason to prefer it. That distinction matters when reading the plate: a curve running off the top of the axis is usually a structure breaking, and this one is a structure working exactly as specified at a setting nobody should choose.

The same shape appears in in place is a claim, and it is usually wrong about quicksort: an algorithm whose auxiliary space is $\Theta(\log n)$ rather than $\Theta(1)$ is not broken, it is described wrongly, and the fix is a measurement rather than a repair.

The collapse is a property of the collection as well #

The 90% figure is measured on a collection of sixteen identical copies, which is the case where an unbounded parse does best and therefore where a cap does most damage.

On four thousand characters of English-like text with no copying at all, the greedy parse gives 604 phrases — 14.7% of the text — and a cap of one gives 3,764, or 91.9%. The ratio between capped and uncapped is 6.2 rather than 47, because the uncapped parse was not small to begin with.

So the collapse’s size is the collection’s repetitiveness and the collapse’s existence is not. Every text ends up with $z$ near $n$ at a cap of one, because every text has about $\sigma$ literals and a cap of one leaves nothing else to copy from. The measure that separates texts at the top of the dial does not separate them at the bottom.

What this says about the family of measures #

Three quantities have been used in this field to size a structure: an empirical entropy $nH_k$, a run count $r$, and a phrase count $z$. The phrases a text copies from itself puts all three on one collection and finds two of them flat under copying and one of them not.

The cap adds a fourth reading. $z$ is the only one of the three whose smallness depends on an unbounded resource, and the resource is the chain a reader walks. $nH_k$ has no such dependency — an entropy is a function of a distribution and there is nothing to bound. $r$ has none either: a run-length index walks a transform, and the number of steps is a property of the query rather than of the parse.

The phrase index is the one structure in the family whose size and whose read cost are traded against each other by the construction, and the cap is the dial that makes the trade explicit. That is worth having even if nobody ever sets it below eight: a measure whose smallness has a hidden cost is better with the cost drawn.

The arithmetic of the collapse, written down #

It is short enough to state exactly, and stating it says which quantity in it is the text’s and which is the structure’s.

At a cap of $D$, a phrase’s source region must lie entirely at depth below $D$. The positions available at depth 0 are the literals, about $\sigma$ of them. The positions at depth below 2 are those plus everything the depth-1 phrases produced — and the depth-1 phrases are short, because their sources were single characters — so the available region grows roughly geometrically in $D$ and the achievable phrase length grows with it.

The phrase count is $n$ divided by the mean phrase length, so $z(D)$ falls roughly as the mean achievable match length rises. Measured, the mean phrase length runs 1.11, 2.87, 8.66, 48.2, 52.2 and 52.5 characters at caps of 1, 2, 4, 8, 16 and none — which is the geometric growth, flattening once the cap stops binding.

The quantity that is the text’s in all of this is where it flattens. A text whose repetition is a few long copies flattens early, because a shallow source region already contains a long match; a text whose repetition is copies of copies flattens late. That is the next essay, and it is the one place on this ladder where the measurement contradicts the obvious guess.

The bits, itemised, at the two ends #

At a cap of one, over 8,192 characters:

• phrase lengths: $7{,}351 \times 13$ = 95,563 bits
• phrase sources: $7{,}351 \times 13$ = 95,563 bits
• phrase literals: $7{,}351 \times 5$ = 36,755 bits
• boundary orders: $3 \times 7{,}351 \times 13$ = 286,689 bits

Uncapped, over the same characters, the same four rows are 2,028, 2,028, 780 and 3,744.

The boundary orders are the largest row at both ends and they are the row nobody thinks about: three permutations of $z$ boundaries at $\lceil\log_2 z\rceil$ bits each. At $z = 156$ that is 3,744 bits, 44% of the index. At $z = 7{,}351$ it is 286,689, 56% of it.

There is a reading of that which flatters the cap and it should be resisted: the boundary orders are cheaper per phrase at a small $z$, so a structure with fewer phrases spends proportionally more of itself on the parse and less on the apparatus. It is still sixty times larger overall.

The reason the row is worth naming is that the orders are not the parse. They are the search apparatus — the two orderings a crossing search needs and the rank array the intersection filter reads — and they scale with $z\log z$ while the parse scales with $z\log n$. So a cap does not merely make the parse larger; it makes the search structures larger faster than the parse, which is the point the structure paid for before the first query makes about grids from the other direction.

Why the two-copy case is where the whole family lives #

One more reading of the sweep, and it is the one that decides whether the cap is a curiosity or a parameter.

The phrase count of an uncapped parse stops growing at the second copy: 155 at one copy, 156 at every point from two to thirty-two. The worst chain does not stop — it is 10 at four copies, 22 at sixteen and 38 at thirty-two. So the gap between what the structure costs and what it costs to read grows without bound as a version history accumulates, and every new version makes the oldest content dearer to reach.

That is the case a bounded-depth parse is actually for. Not a text, and not a collection of a fixed size, but a collection that is still growing — a log, a version-controlled tree, a document with a history — where the size holds still and the read cost quietly does not.

A cap converts that unbounded growth into a fixed premium: nine per cent of the phrases at a cap of eight, at every collection size measured. Whether nine per cent is worth it depends on how often the collection is read, which is what a second pass buys arriving in a different field — a cost paid once against a cost paid per query, and no answer without both counts.

The honest limit of these numbers #

Three, and the second is the one that would move the headline.

The collection is copies of a generated text. A version history is near-copies, and at one substitution per hundred characters per copy the uncapped phrase count no longer stops growing — which means the 47-fold ratio at a cap of one is measured at the most favourable point for the uncapped parse and is an upper bound on what a real corpus would show.

The sizes are what this accounting charges. A phrase costs $2\lceil\log_2 n\rceil + \lceil\log_2\sigma\rceil$ bits here, which is a fixed-width encoding of the source and the length. A real implementation encodes lengths with a variable-width code, and short phrases — which is what a tight cap produces — are exactly where such a code wins most. So the collapse at a cap of one is real and its measured size is a property of the encoding as much as of the parse.

And nothing here is timed. Every quantity is a count: phrases, bits, phrase follows, character comparisons. That is this collection’s method rather than a limitation, and it is what makes a factor of sixty a statement about structure rather than about a machine — but it also means the question “is a cap of eight worth nine per cent” cannot be settled here, because the answer depends on the relative price of a bit and a follow on hardware nobody has specified.

Where else a constraint has undone a compression #

Two neighbours in this collection, both of which are the same arithmetic under other names.

A sampling that costs more than the array is the closest. A run-boundary sampling exists to remove a term proportional to the text and, on four-symbol text where runs are short, costs 2.07 times the whole suffix array it replaced. Same shape: a structure sized by a measure, and a text where the measure is not small.

The optimal code that is beaten is the version in coding. A prefix code is optimal among prefix codes and is beaten by an arithmetic coder, because the optimality was conditional on a constraint — whole numbers of bits per symbol — that the comparison did not share.

And the model a bound was quoted in is the general statement: every bound in this collection is conditional on a model, the model is usually implicit, and a claim carried outside its model is a claim about nothing. The phrase count’s smallness is conditional on an unbounded chain, and the cap is what makes the condition visible by removing it.

What is being claimed #

A cap of one takes the phrase count from 1.9% of the text to 89.7% of it, on a collection of sixteen copies, and the index from 8,580 bits to 514,570.

The reason is the alphabet-sized floor. Depth zero is the literals, there are about $\sigma$ of them, and a source region of one character supports a match of one character.

Every text ends up there. The multiplier is the text’s repetitiveness — 47 on a collection of copies, 6.2 on ordinary text — and the destination is about 90% of the characters in both cases.

And the term comes back gradually. It is 2.1% of the text at a cap of eight and 11.5% at four, so the collapse is a feature of the tight end of the dial rather than of capping as such. A reader who wanted one sentence for it: the phrase count is small because the parse may reach arbitrarily far back through arbitrarily many copies, and any bound on how far it reaches is a bound on how small it can be.

The knee has a location, and the four measurements bracket it tightly. The phrase count is 1.9% of the text uncapped, 2.1% at a cap of eight, 11.5% at four, and 89.7% at one — so it is flat, then a factor of five, then a factor of eight.

The collapse happens between a cap of four and a cap of two, and everything looser than four is indistinguishable from no cap at all. That is a narrower statement than the tight end of the dial and it is the one a reader choosing a cap needs: eight is free, four is a fivefold cost that may still be worth a bounded read, and anything below it is the term returning in full.