The apparatus that is smaller than its index

Three stages, one collection, the same answers throughout.

As shipped: a document array, a chain of previous occurrences, and a segment tree over the chain. 8,142,274 bits against an index of 3,020,521 — 2.70 times.

With a succinct range minimum in place of the segment tree: 4,898,356 — 1.62 times.

With no chain at all: 2,534,726 — 0.84 times.

The apparatus is now smaller than the thing it is an apparatus for.

What each stage changed #

The first change is a structure swap and nothing else. A segment tree over n values stores 2n numbers of ⌈log₂ n⌉ bits; a succinct range minimum stores the shape of the same array as 2n parentheses plus the machinery to query them, and answers in a constant number of steps rather than a logarithmic number of visits. The shape a range question is about is where that is built, and it is a factor of 3.19 on that part.

The second change is a reformulation of the walk. The test C[at] < lo is answerable from the answer so far, so the array it appears to be about is never read — and once it is never read it does not have to be kept, because the structure over it holds a shape rather than numbers. The array the walk never reads is the argument and a document already in the answer is the algorithm.

Neither change touches the work. Same queries, same visits, same documents, at every point on the sweep.

What is left #

Two parts, and the ratio between them is the interesting thing.

The range minimum, 1,483,854 bits — 59% of what remains. Most of that is its o(n) term: the payload is 2n parentheses and everything else is what makes them answerable, which on this collection’s own measurement is five times the payload.

The document array, 1,050,616 bits — 41%. One document number per row, n⌈log₂ d⌉ bits.

The bitmap, 256 bits. One per document, and invisible at this scale.

So the two remaining targets are different in kind. The range structure’s cost is machinery, and a better one would shrink it — this collection has already found that one layer of blocking is larger than the segment tree it replaces, and that two layers are what make it small, so the shape of that curve is known and not exhausted.

The document array’s cost is information. Every row belongs to a document and something has to say which, so the only way to make it smaller is to compress it — a wavelet tree over the document array would cost n·H₀ of the document distribution rather than n⌈log₂ d⌉, which on a collection with unequal document lengths is genuinely less. That is named here and not built.

Where the crossing is #

The saving is not one number, because one of the two remaining parts follows the document count and neither of the removed parts did.

At 4 documents: 2.43 with the chain, 0.58 without — a saving of 76.3%.

At 2,214: 2.87 and 1.01 — a saving of 64.7%, and the chainless apparatus has just crossed back above the index.

So on a collection of many short documents the apparatus is about the size of the index again, and the reason is entirely the document array: 12 bits a row rather than 4.

And whether it is worth building at all #

Which is where this strand meets the one about real collections, and the answer is uncomfortable.

The crossing that never arrives measures, on a real collection of 2,214 short documents, how many times a pattern occurs per document holding it: 1.04. Output-sensitive listing wins when that ratio exceeds the cost of one range-minimum query in array reads — about ten with a succinct structure — and on that collection it is nowhere near.

So the shape where the apparatus costs the most in relative terms is the shape where it buys the least. On 82 long documents of the same prose the ratio is 4.38, which is still under the crossing; on twelve long documents of a version history it reaches 32, which is well over.

The recommendation that comes out of both strands together:

A collection of few, long, repetitive documents — a version history, a book collection, a log — build the apparatus. It is 0.6 to 0.8 times the index, the ratio is far past the crossing, and the walk wins on most queries rather than the extreme ones.

A collection of many short documents — keep the document array, drop the range structure, scan the occurrences. The scan was winning anyway, and the apparatus is a structure the size of the index buying nothing.

What the three stages say about accounting #

A last observation, because the shape of this result is more portable than the result.

The apparatus went from 2.70 to 0.84 without a single change to what it computes. Nothing got faster, nothing got more accurate, no query changed its answer. What changed is that two parts were priced honestly and then found to be replaceable — a structure storing numbers where a shape would do, and an array answering a question the answer could answer.

Both were findable only because the size was reported in parts. A structure quoted as one number is a structure nobody can subtract from: the earlier accounting said the listing apparatus is 2.7 times the index, and the parts table under it said which 2.7, and the parts table is what made two of them removable.

That is the practice this collection has settled on and it is worth stating as one: report a size as a sum of things that answer different questions. Somebody will then ask which of the questions their system puts, and the answer is sometimes none.

The arithmetic, in full #

Worth setting out completely once, since the whole strand is an accounting.

The collection: 131,327 characters, 256 documents, alphabet of about a hundred symbols.

The index — a suffix array at n⌈log₂ n⌉ = 2,363,886 bits, and the text at n⌈log₂ σ⌉ = 656,635. Total 3,020,521, and this is the denominator of every ratio on this page.

Stage one. Document array 1,050,616 + chain 2,363,886 + segment tree 4,727,772 = 8,142,274. Ratio 2.70.

Stage two. The segment tree becomes a succinct range minimum at 1,483,854, so 1,050,616 + 2,363,886 + 1,483,854 = 4,898,356. Ratio 1.62.

Stage three. The chain goes and a bitmap of 256 bits arrives: 1,050,616 + 1,483,854 + 256 = 2,534,726. Ratio 0.84.

Two changes, a factor of 1.66 and then a factor of 1.93, and the product is 3.21 — which is what takes 2.70 to 0.84.

Neither change touched a query #

Worth restating because the plate is a size plate and a reader may reasonably wonder what was given up.

Stage one changed a query’s shape and not its count. A segment tree answers a range minimum in a logarithmic number of node visits; the succinct structure answers in a constant number of steps. The number of queries is identical — it is determined by the walk — and what changed is what one costs, which is the crossing this strand’s companion pages are about.

Stage two changed nothing at all. Same queries, same visits, same positions returned, same documents reported. The chainless walk takes identical decisions at identical subranges, which is checked step for step rather than inferred from the answers agreeing.

So the whole of the three-stage improvement is size, and the honest summary is that the apparatus computes exactly what it computed and holds a third of what it held.

The two remaining parts, in proportion #

Of the 2,534,726 bits that remain:

The range minimum is 1,483,854 — 59%. Its payload is 262,654 bits of parentheses and the rest is what makes them answerable, which is the o(n) term dominating exactly as its own strand found.

The document array is 1,050,616 — 41%. One document number per row.

The bitmap is 256 bits — 0.01%, and it replaced 2.36 million.

That last line is the one worth carrying. The structure that answers whether a document has been reported is four ten-thousandths of a per cent of the apparatus, and it replaced the largest part of it — not by being a clever encoding of the same information, but because the information was already present in the output.

What a system should build #

The recommendation depends on the collection’s shape, and both halves of it are measured rather than reasoned.

Few, long, repetitive documents — a version history, a book collection, a large log. Occurrences per document reach 32 on real text of this shape, which is well past the crossing where a range-minimum walk beats a scan. Build the apparatus: it is 0.58 to 0.84 times the index, and it wins most queries rather than the extreme ones.

Many short documents — captions, records, messages. Occurrences per document is 1.04 on real text of this shape, which is what two thousand documents of two hundred characters measures. The walk has nothing to win, the apparatus is about the size of the index, and the right structure is a document array and a scan.

And in between, which is where most collections are, measure. A hundred of the collection’s own frequent strings, an occurrence count and a document count for each, and the median ratio: that is a loop over a suffix array, it is three orders of magnitude cheaper than the structures it decides about, and it is the measurement this strand should have made first.

What is left open #

Compressing the document array, which is the largest remaining part that is information rather than machinery. A wavelet tree over it costs n·H₀ of the document distribution, which on a collection with unequal document lengths is less than n⌈log₂ d⌉ — and a real collection’s document lengths are unequal by a factor of seven.

Shrinking the range minimum’s o(n) term, which is 82% of that structure. Its strand walked the blocking curve twice and found that one layer is worse than a segment tree and two layers are five times better; whether three layers help is a measurement nobody has taken.

And the same substitution on the phrase index’s chain, which has the same name for a different object and is the largest part of a different apparatus. Whether the walk there has the property this one’s walk has is not obvious, and it is the first question this strand’s method would ask of it.

The first of those closes, and it closes negative #

The document array is the largest remaining part that is information rather than machinery, and the suggestion above is to compress it with a wavelet tree at n·H₀ of the document distribution rather than n⌈log₂ d⌉. That much is standard. What is worth doing before building it is the arithmetic, because entropy is far more robust to a skew than the sentence proposing it assumes.

Start with this collection, where it is exact. 131,327 rows, 256 documents, 1,050,616 bits — which is 8.000 bits a row, because 131,327 × 8 is 1,050,616 and log₂ 256 is 8. The documents here are equal-length by construction, so the distribution is uniform, H₀ is 8 exactly, and a wavelet tree saves nothing at all. Not a little: nothing. The proposal has no purchase on the collection it was written beside.

So the case has to be made on unequal lengths, and the figure the strand quotes is a real collection whose documents differ by a factor of seven. Take lengths spread evenly across that range — a document’s share of the rows is proportional to its length, so the shortest holds a seventh of what the longest does — and the entropy comes out at 7.80 bits a row against 8.

That is a deficit of 0.197 bits, or 2.5%. On the document array it is about 26,000 bits; on the apparatus as a whole it is one per cent.

Against which a wavelet tree is not free. It is log₂ d bit vectors with rank support over each, and rank support in practice costs a quarter or more of the vector it sits on — the same o(n) term that is 82% of the range minimum on this very page, arriving again in a smaller structure. A 2.5% saving against a 25% overhead is a net loss of a fifth, and the compressed array would be larger than the plain one.

The general statement is the useful part, because it is what makes this a decision rather than a measurement. Entropy is a logarithm of a ratio, so a length spread of a factor f costs at most about log₂ f bits in the worst arrangement and far less in an even one — a sevenfold spread is under a fifth of a bit, and reaching a full bit of saving takes a collection where a handful of documents hold most of the text. A version history or a log has that shape. Captions and records do not.

Which sharpens the recommendation this page already makes rather than adding to it. The collection where compressing the document array pays is the collection of few, long, repetitive documents — the same one the crossing that never arrives says the apparatus is worth building for at all. On many short documents the array is nearly incompressible and the walk has nothing to win, so both halves of the answer point the same way.

And the shape of the check is the one what the chain cost established: a part of a size table is worth attacking only after somebody has computed what the attack would return. Two of the three parts here fell to that question. The third answers it and survives.

What the strand adds up to #

Four pages and two changes, and it is worth having the whole of it in one place.

The array the walk never reads is the observation: the test C[at] < lo asks whether a document is new, and a left-first walk already knows.

A document already in the answer is the algorithm, with the two defects that must be caught — a right-first walk, which loses nine documents of seventeen without failing, and a bitmap left dirty between queries, which reports none of three.

What the chain cost is the size: n⌈log₂ n⌉ bits, exactly the width of the suffix array, and the largest single part of the apparatus.

This page is the accounting, and the sentence it replaces is one the document strand wrote when it built the thing: answering the collection’s own question at the price of its answer costs about three times what answering it slowly costs. It costs 0.84 times.

Why the two changes are worth separating #

They are different kinds of result and a reader deciding what to build should be able to take one without the other.

The first — a succinct range minimum in place of a segment tree — is a structure substitution. It is available to anybody, it needs no invariant, it changes a query from a logarithmic descent to a constant number of steps, and its own strand found that its overhead is five times its payload at every size drawn. A factor of 3.19 on one part.

The second — removing the chain — is an algorithmic reformulation. It needs a left-first walk, it needs the bitmap cleared by the answer, and it is wrong in a silent way if either is missed. A factor of 1.93 on the whole apparatus.

A system that wants the size without the invariant can take the first and stop at 1.62. A system that takes both gets 0.84 and an invariant somebody has to know about. Stating them separately is what makes that choice available.

The habit, stated once #

Every result in this strand came from one question asked of a size table: which of these parts answers a question my callers actually put?

The chain answers “what is the previous row of this document” — which nothing asks. The range minimum’s values answer “what is the smallest chain entry” — which nothing asks, since the walk uses only the position. The document array answers “which document is this row” — which every step asks.

Three parts, one question each, and two of the three questions turned out to be unasked. Neither was hidden: both were in the size table the earlier strand published, and both were removable only because the table listed them separately.

That is the practice, and it is portable to any structure with a parts table under it. A size quoted as one number is a number nobody can subtract from.

What the reader should do with this #

Two things, and the second is the one that generalises past document listing.

Measure the ratio before building the apparatus. A hundred of the collection’s own frequent strings, an occurrence count and a document count for each, and the median ratio: if it is near one, the apparatus is bits spent on nothing, and on a real collection of short documents it is 1.04. That measurement is a loop over a suffix array, and it decides a structure three orders of magnitude larger than itself.

And read size tables as sums. Everything this strand removed was visible in a table published when the structure was built. The chain’s row said 2,363,886 bits; the question “what asks for this” was answerable in a paragraph; and the answer was “one comparison, which the output already knows”. Neither the removal nor the substitution before it needed a new idea — they needed somebody to read a table and ask what each row was for.