What the chain cost

The chain of previous occurrences is an array of n row numbers, one per row of the index.

That is n⌈log₂ n⌉ bits — exactly the width of the suffix array it sits beside, because both store a number in the same range once per row. On 131,327 characters in 256 documents it is 2,363,886 bits, and so is the suffix array.

It was the largest single part of the apparatus that answers “which documents”, and it is now not there at all.

The parts, at the start #

A document index over 131,327 characters in 256 documents, as the document strand shipped it:

Suffix array — 2,363,886 bits. The index proper.

Text — 656,635 bits at ⌈log₂ σ⌉ per character.

Document array — 1,050,616 bits, ⌈log₂ d⌉ per row.

Previous-occurrence chain — 2,363,886 bits.

Range minimum over the chain — 4,727,772 bits, as a segment tree: 2n values of ⌈log₂ n⌉ bits.

The last three are the listing apparatus, and together they are 8,142,274 bits against a base — the suffix array and the text — of 3,020,521.

The apparatus was 2.70 times the index it sits on, which is the honest counterweight the document strand recorded when it built the thing: answering the collection’s own question at a price proportional to its answer costs about three times what answering it slowly costs.

The first stage: a smaller range structure #

The segment tree is 2n values of ⌈log₂ n⌉ bits, which is the cost of storing a structure that keeps numbers.

A succinct range minimum stores the shape instead: the Cartesian tree of the array written as 2n parentheses, plus enough machinery to answer excess queries on them. The shape a range question is about is the construction, and its own strand’s finding is that the o(n) term dominates at every size drawn — 131,072 bits of payload against 651,800 of overhead at 65,536 values.

Even so it is a factor of 3.19 against the tree: 1,483,854 bits against 4,727,772 here.

That takes the apparatus to 4,898,356 bits — 1.62 times the index. Still larger than the index, and the largest remaining part is the chain.

The second stage: the chain #

Removing it is 2,363,886 bits, and what replaces it is 256 bits — one per document.

Apparatus: 2,534,726 bits. Base: 3,020,521.

The ratio is 0.84, and the sign of the comparison has changed: the machinery that answers “which documents hold this pattern, at a price proportional to the answer” is now smaller than the suffix array and text it sits beside.

That is the strand’s headline and it is worth stating precisely, because the change came in two steps and only the second is new. Replacing the range structure was a factor of 1.66 on the apparatus; removing the chain was another factor of 1.93. Together they took 2.70 to 0.84.

Where the remaining bits are #

With the chain gone, the apparatus is two things and one of them is nearly all of it.

The document array, 1,050,616 bits — 41% of what remains, and the only part that knows how many documents there are.

The range minimum, 1,483,854 bits — 59%.

The bitmap, 256 bits — 0.01%, which does not appear on a plate at this scale.

So the next place to look is either of the first two, and they are different kinds of target. The range minimum’s cost is mostly its o(n) term, which is a machinery question. The document array’s cost is n⌈log₂ d⌉, which is information: it says, for every row, which of d documents it belongs to, and a collection with d documents needs that.

How the saving moves with the collection #

The document array is the reason the saving is not one number.

At four documents, the apparatus with the chain is 2.43 times the index and without it 0.58 — a saving of 76.3%.

At 2,214 documents it is 2.87 and 1.01 — a saving of 64.7%.

The saving shrinks because what remains grows: the chain and the range structure do not depend on d at all, and the document array does. So on a collection of many documents the removed part is a smaller share of a larger whole.

And at about two thousand documents the chainless apparatus crosses back above the index it sits on, for the same reason. That crossing is a fact about the shape of a collection rather than about this construction, and two thousand documents of two hundred characters is the page about what else moves at that shape.

What the chain was doing there #

Worth saying, because “the largest part of the apparatus was unnecessary” invites the question of why anybody stored it.

It is necessary at build time. The range minimum is a structure over the chain: its parentheses are the Cartesian tree of the chain’s values, so the values have to exist while it is constructed. What the substitution removes is the need to keep them afterwards.

And it is necessary to the published algorithm, which compares C[at] against the range’s start. That comparison is answerable from the walk’s own output only under a left-first traversal, which is an invariant the published form does not need and does not state — so an implementation following the published description faithfully has to keep the array.

So the chain is not a mistake in the earlier work. It is a part that a different formulation of the same algorithm does not require, and finding that out took writing down what the comparison was asking.

What this does to the earlier sentence #

One published claim is now wrong in a specific way, and it is worth quoting rather than quietly correcting.

The chain is as wide as the suffix array and the range minimum is wider, so answering the collection’s own question at the price of its answer costs about three times what answering it slowly costs.

The first clause is exactly right and is measured on this page. The second was right about the structure that existed then. The conclusion — three times — is now 0.84 times, and the two changes that got it there are a different range structure and a different formulation of the walk.

What has not changed is the work: the same number of range-minimum queries, the same visits inside them, the same answers. This is a size result throughout, and an index has a size is the theme it belongs to.

Why the chain is exactly as wide as the suffix array #

It is not a coincidence and it is worth a paragraph, because it says why this part was always going to be one of the two largest.

A suffix array stores, for each of n rows, a position in a text of n characters: n⌈log₂ n⌉ bits.

The chain stores, for each of n rows, a row number — the previous row holding the same document — and there are n rows: n⌈log₂ n⌉ bits.

Same count, same width, same total. Any structure with one number per row, where the number ranges over the rows or over the text, costs exactly what the index costs. That is a useful thing to notice when reading a size table: parts that are “one number per row” are all the same size, and parts that are one number per document or one bit per row are in a different class entirely.

On the collection measured here that class contains the suffix array and the chain, at 2,363,886 bits each; the class below contains the document array at 1,050,616, because ⌈log₂ d⌉ is 8 rather than 18; and the class below that contains the bitmap, at 256.

The range structure’s own accounting #

The middle stage of this page’s arithmetic deserves its own numbers, because a factor of 3.19 on the largest part is the change that made the second stage worth looking for.

A segment tree over n values holds 2n numbers of ⌈log₂ n⌉ bits and answers in ⌈log₂ n⌉ visits. On 131,327 values that is 4,727,772 bits — larger than the suffix array, larger than the chain, the largest single part of the whole index.

The succinct range minimum holds the Cartesian tree of the same values as 2n parentheses and answers in a constant number of steps. On the same array it is 1,483,854 bits, of which the parentheses are 262,654 and everything else is the machinery that makes them answerable.

So the succinct structure is five to six times its own payload, which is the finding its own strand recorded — 2n + o(n) is a statement about a limit, and at every size drawn here the second term dominates. It is still a factor of three smaller than the tree.

What it looks like per character #

Bits are hard to hold; bits per character are easier, and the comparison against the text is the one that makes the sizes real.

The collection here is 131,327 characters over an alphabet of about 100 symbols, so the text is 7 bits a character — 656,635 bits if packed, and 1,050,616 if stored as bytes.

The index proper is 23 bits a character: 18 for the suffix array and 7 for the packed text taken together, which is why an index of this shape is usually described as several times its text.

The apparatus, as shipped, was 62 bits a character. With the succinct range structure, 37. Without the chain, 19 — less than the index it sits beside, and about two and a half times the text.

The saving against the collection’s shape #

The chain does not depend on the document count and the document array does, so the saving’s share moves even though its absolute size does not.

At 4 documents the apparatus with the chain is 2.43 times the index, without it 0.58: a saving of 76.3%.

At 64 documents: 2.61 and 0.75, saving 71.2%.

At 1,024: 2.78 and 0.93, saving 66.7%.

At 2,214: 2.87 and 1.01, saving 64.7%.

Two thirds of the apparatus, at every shape measured — and the reason the share declines is that what remains grows. On a collection with more documents the document array is wider, so the same removed bits are a smaller fraction of a larger structure.

The crossing is a step, and it is at 2,048 #

“At about two thousand documents the chainless apparatus crosses back above the index” is a reading of a sweep, and the arithmetic gives the crossing exactly — along with the fact that it is not a point.

Everything in the comparison is bits per row. The index is the suffix array plus the packed text: $\lceil\log_2 n\rceil + \lceil\log_2 \sigma\rceil$, which is 18 and 5 here, so 23 bits a row. The chainless apparatus is the document array plus the range minimum: $\lceil\log_2 d\rceil$ plus the range structure’s 1,483,854 bits over 131,327 rows, which is 11.30 bits a row. So the apparatus exceeds the index when

$$\lceil\log_2 d\rceil \;>\; 23 - 11.30 \;=\; 11.70.$$

The left side is an integer. It is 11 for every collection from 1,025 to 2,048 documents and 12 for every collection from 2,049 to 4,096, so the crossing is exactly at 2,048 — the ninth doubling — and nothing between 2,049 and 4,096 crosses it any harder.

That explains the shape of the sweep’s own numbers. At 1,024 documents the ratio is 0.93, which is $(11 + 11.30)/23$; at 2,214 it is 1.01, which is $(12 + 11.30)/23$. Both are exact, and 2,214 is not a threshold — it is where the sweep sampled inside a band that runs to 4,096.

Two consequences worth carrying.

The apparatus’s size is flat within a power-of-two band and steps between them. A collection of 2,000 documents and one of 2,100 differ by five per cent in document count and by eight per cent in apparatus size, and one of them is under its index while the other is over. The quantity a reader would naturally interpolate does not interpolate. That is the same step function documents that are not the same length finds deciding a separator’s cost — the ceiling of a logarithm, evaluated at where the collection happens to sit — and it turns up here in the size of an apparatus rather than in the width of a symbol.

And the crossing moves with the text, not only with the documents. The 11.70 on the right is $\lceil\log_2 n\rceil + \lceil\log_2\sigma\rceil$ less the range structure’s per-row cost, so a longer collection raises it by a bit per doubling of $n$ and pushes the crossing out by a factor of two in $d$. A collection twice as long tolerates twice as many documents before its apparatus outgrows its index, which is a considerably more forgiving relationship than the sweep’s rising curve suggests when read on its own.

So the honest form of the finding is a condition rather than a document count: the apparatus is smaller than the index while $\lceil\log_2 d\rceil$ stays under $\lceil\log_2 n\rceil + \lceil\log_2\sigma\rceil - 11.3$, with the last term being what the range structure costs a row. All four quantities are known before anything is built, and two thousand documents of two hundred characters is the shape where they are closest.

What could still go #

Two candidates remain and they are different in kind, which is worth saying because only one of them is a machinery question.

The range minimum’s overhead. Its payload is 2n bits and its total is five to six times that. The structure’s own strand found that one layer of blocking is larger than the segment tree it replaces and two layers are what make it small, so the curve of overhead against blocking depth is known, has been walked twice, and is not obviously exhausted.

The document array. n⌈log₂ d⌉ bits, one document number per row, and it is information rather than machinery: something has to say which document each row belongs to. It could be compressed — a wavelet tree over the document array costs n·H₀ of the document distribution, which on a collection with unequal document lengths is less than n⌈log₂ d⌉ — and it could be replaced by a rank over a bit vector marking document boundaries in the text, which trades a read for a rank.

Neither is built here. Both are named, which is this collection’s standing convention for a structure it prices and does not implement.

What this does not say #

The apparatus being smaller than the index does not make it worth having, and the two questions are separate.

Worth having is a question about the query: does the walk beat a scan over the occurrences? That depends on how many times a pattern occurs per document holding it, and on a real collection of many short documents the answer is 1.04, which is nowhere near the crossing. The crossing that never arrives is that measurement, and the apparatus that is smaller than its index is where the two strands meet.

What this page settles is the size, and it settles it in the direction that makes the structure defensible: the honest counterweight the document strand recorded — three times what answering it slowly costs — is now 0.84 times, and the change came from replacing one structure and removing another.

Where this sits #

Four pages make the strand. The array the walk never reads is what the test is asking; a document already in the answer is the algorithm and its two deliberate defects; this page is the size; and the apparatus that is smaller than its index is the accounting all together with the recommendation attached.

The one before all of them is the shape a range question is about, which is where the succinct range minimum was built and where the first of this page’s two factors comes from.

The chain’s other appearance in this collection #

The name occurs twice here for two different objects, and it is worth separating them because one of them is untouched by any of this.

In a document index, the chain of previous occurrences runs through the rows of the index: C[i] is the previous row holding the same document. That is the array this page removes.

In a phrase index, a chain of previous occurrences runs through the phrases of a parse, and it is what lets a secondary occurrence be propagated to the occurrences that copy from it. It is the largest part of that apparatus, it was priced in its own strand and not questioned, and whether the same substitution applies is genuinely unclear: the walk there is a propagation rather than a range decomposition, and it has no obvious “answer so far” to test against.

Same name, different object, different question. This collection has been caught by that before — three implementations of one word turning out to be three functions — and the discipline is to read the bodies rather than the names.