Algorithms & Data Structures
the bound is a claim, and it is checkable
The other axis

The apparatus, three times smaller again

Eight hundred and thirty-nine thousand bits became two hundred and eighty-five thousand, and now a hundred and twenty thousand. The listing apparatus is fourteen per cent of what it was and holds one array, which is the only part of it that was ever information.
20 min read 8 figures An index has a sizeSpace is the other axisMeasured, not assumedThe structure decides the count

Three prices for the same capability, on sixty-four documents of two hundred and fifty-six characters.

The published apparatus — a document array, a previous-occurrence chain and a segment tree over the chain — is 838,797 bits beyond the suffix array and the text.

The chainless one, with the chain removed and a succinct range minimum in place of the segment tree, is 285,460.

The descent, with the document array in a wavelet tree and nothing else, is 119,972.

That is 34.0% and then 42.0%, or 14.3% end to end. The capability is unchanged: all three report the same documents for the same query, checked on the documents rather than on their count.

Three apparatus for one question, and what each of them holdsThe bits each listing method needs beyond the suffix array and the text, on 64 documents of 256 characters. The published method holds the document array, a previous-occurrence chain of the same width as the suffix array, and a range minimum over that chain: 838,797 bits. Removing the chain — because the test it exists for is answerable from the answer so far — leaves 285,460. Putting the document array in a wavelet tree removes the range minimum too, because the distinct symbols of an interval are what the tree enumerates: 119,972, or 14.3% of where the strand started. What is left is the array itself, compressed, and one descent over it.range minimum and chain838,797255.0%range minimum, no chain285,46086.8%one descent over D119,97236.5%the document array, the chain and a range minimumthe document array, a range minimum and one bit per documentthe document array, in a wavelet tree64 documents · 16,447 characters14.3% of the published apparatus
Fig. 1 The three apparatus priced, with what each of them holds. The bar is bits beyond the suffix array and the text.

Where the bits were

The published apparatus’s 838,797 bits split four ways and the split is lopsided.

The chain is n⌈log₂ n⌉ bits — one row index per row, the same width as the suffix array itself. On this collection that is 16,449 rows at fifteen bits, or 246,735 bits.

The segment tree over the chain is the largest single part. A segment tree storing a minimum per node over n leaves is about 2n values of ⌈log₂ n⌉ bits, so roughly twice the chain: 493,470.

The document array is n⌈log₂ d⌉ — 16,449 rows at six bits, 98,694 bits.

So the chain and its index were 88% of the apparatus and the array was 12%.

That proportion is the reason the strand went in the order it did, and it is worth noticing that the order was not chosen — each removal was found when it was found. It happens that the largest parts went first.

There is a reason the segment tree is twice the chain rather than a fraction of it, and it is worth a sentence because succinct range minima are usually introduced as though the ordinary version were merely a little large. A segment tree over n leaves has n − 1 internal nodes, each holding a minimum, and each minimum is a value from the array — so a full-width value, ⌈log₂ n⌉ bits. Two n-sized arrays of full-width values.

The succinct alternative holds a Cartesian tree in 2n + o(n) bits — two bits a leaf rather than two values a leaf — which is a factor of ⌈log₂ n⌉/2, or seven and a half at this size. The shape a range question is about is where that representation was built here, and its measured gain on this part was 3.19 rather than 7.5, because the o(n) is not small at these sizes.

What each removal was worth

The chain, and its index. Removing the chain removes 246,735 bits directly. It also changes what the range structure is over: what the chain cost measured the pair and found the removal worth a factor of 1.93 on the whole apparatus, on top of the succinct range minimum’s 3.19 on its own part. Together: 838,797 to 285,460.

The range minimum entirely. The tree answers the question removes it, because the distinct symbols of an interval are what a wavelet tree enumerates. That is the whole remaining range structure gone — on this collection, 285,460 minus the array’s 98,694 minus the bitmap, so about 186,000 bits.

The array, compressed. The wavelet tree over the document array costs its entropy plus directories. On a collection of equal-length documents that is the plain array plus 20%; on a real one it is 83% of plain plus 20%, so about par. On this collection the tree is 119,972 including directories against a plain array of 98,694 — larger than the plain array.

That last line is the one worth reading twice. The final step made the apparatus 42% of what it was, and it did so entirely by removing the range minimum. The array itself got bigger.

What the document array can be compressed to is the length distributionThe zeroth-order entropy of the document array, for four collections of 64 documents and 16,384 characters. The array holds each document once per character it contributed, so its symbol distribution is the length distribution and nothing else. On equal-length documents H0 is 6.000 against a ceiling of log2 64 = 6.000 — the two are the same number, and a wavelet tree over that array is 100.0% of the plain n⌈log₂ d⌉ array, which is to say it saves nothing. On a collection where one document holds four fifths of the text H0 falls to 1.888 and the array to 36.3%. The dashed line is the ceiling every row is measured against.equal lengths6.00 bits100.0%lengths as one over rank4.86 bits81.6%a few long, many short5.31 bits88.9%one document holding most of the text1.89 bits36.3%log₂ 6464 documents · 16,384 characters100.0% to 36.3%
Fig. 2 Why the array can get bigger: its compressibility is the collection’s length distribution, and equal-length documents have none.
Four ways to divide the same text into the same number of documentsThe 64 document lengths of each collection, drawn as a stacked strip of 16,384 characters, with the entropy of the resulting document array beside it. The four hold the same text and the same document count; what differs is how the characters are apportioned, and that alone decides how far the array compresses. Equal lengths give a uniform distribution and 6.00 bits a symbol, which is the ceiling. Lengths falling as one over rank — the shape a real collection of documents tends to have — give 4.86. One document holding most of the text gives 1.89, and it is the only one of the four where the saving is worth the machinery.equal lengthsH0 = 6.00 bitslengths as one over rankH0 = 4.86 bitsa few long, many shortH0 = 5.31 bitsone document holding most of the textH0 = 1.89 bits64 documents, 16,384 characters, four apportionmentslongest document 13,148 characters6.00 to 1.89 bits
Fig. 3 Why this particular collection’s array does not compress: sixty-four documents of equal length, which is the one shape whose array has no redundancy at all.

That the array got bigger on this collection is a property of the collection rather than of the representation, and it is worth being precise. The documents here are equal length, so the array’s entropy is exactly log₂ d and the tree’s payload is exactly the plain array’s size. The directories are pure addition.

On a collection whose lengths fall as one over rank the payload would be 83% of plain and the total about par. On one with a dominant document it would be 40% and the total half. So the final step is a wash, a small win or a large one depending on a property of the collection that has nothing to do with the query — and this essay’s collection is the worst case for it.

Reporting the 42% on the worst case is the right choice and it should be said out loud: on a collection whose array compresses, the last step is worth more than 42%.

The step that costs and pays at once

The wavelet tree is a worse representation of the array considered as an array, and a better one considered as an apparatus. Separating those is the whole of the accounting.

As an array: plain costs n⌈log₂ d⌉ = 98,694 bits and supports a lookup in one read. The tree costs its entropy — here equal to n log₂ d, because the documents are equal length — plus rank directories at 20% of that, so 119,972, and supports a lookup in log d ranks.

Strictly worse, in both currencies, for the job of being an array.

As an apparatus: the tree also answers which distinct symbols are in this interval, which is the listing query, at a cost proportional to the answer. The plain array cannot answer that without reading every entry in the range, which is the naive method.

So the tree is buying the query with bits and with per-lookup cost, and the thing it is buying it from is the range minimum, which cost 186,000 bits. Net: 66,000 bits saved and the array’s lookups made log d times more expensive.

That is a real trade rather than a free improvement, and quoting the 42% without it would be quoting a saving that has a cost attached.

There is a smaller trade inside that one which is easy to miss. The chainless method needed a bitmap — one bit per document, cleared between queries — and the descent does not. That is d bits of working memory, negligible at sixty-four documents and not at two thousand, and it came with a trap: clearing the bitmap by walking it costs d per query, which on a query whose answer is three is worse than the array it replaced. A document already in the answer is where that trap is written out.

So the descent removes a structure, a bitmap and a clearing problem, and none of the three appears in the bar chart because two of them are query-time rather than resident.

What is left

The 119,972 bits are three parts and the shares are stable across collection shapes.

The payload — the tree’s levels, one bit per symbol per level of its code — is about 80%. That is where the length distribution’s entropy lives and where any further compression has to come from.

The rank directories are about 20%. They are a function of the levels’ total length rather than of their contents, which is why the share barely moves: 19.5%, 20.7%, 20.9% and 23.3% across the four collection shapes measured.

The code table is one code length and one symbol per document, so d(2⌈log₂ d⌉) bits. At sixty-four documents that is 768 bits — under one per cent, and it stops being negligible somewhere in the thousands.

There is no fourth part, which is what “the apparatus is one array” means.

The shape reaches the entropy down to a bit a symbol, and the vector below itThree quantities per collection: the entropy of the document array, what a Huffman-shaped wavelet tree of plain bit vectors costs, and what the same tree with compressed blocks costs. On the first three collections the plain tree is within 0.6% of the entropy, which is Huffman's redundancy and is all it should be. On the skewed collection it is 1.98 bits against an entropy of 1.69 — because a Huffman code word is at least one bit, so a plain-vector tree cannot cost less than n bits however low the entropy goes. Compressed blocks reach 1.57, because a level that is nearly all zeros is a run and a run is where a block class costs nothing.024bits a symbolequalzipftwoSizesoneLargeone bit a symbolentropyplain vectorscompressed blocks32 documents1.26x on the skewed collection
Fig. 4 Where the remaining payload can still go: a plain-vector tree against the entropy, with the one-bit floor a code cannot get under and the representation that does.

Against the base it sits on

Every number above is bits beyond the suffix array and the text, and that base is what decides whether any of it matters.

On this collection the suffix array is n⌈log₂ n⌉ = 246,735 bits and the text is n⌈log₂ σ⌉ = 82,245, so the base is 328,980.

The published apparatus was 2.55 times its base. That is the number the apparatus that is smaller than its index is named after: an apparatus larger than the index it sits on is not an optimisation, it is a second index.

The chainless one is 87% of its base. The descent is 36.5%.

So the arc is a structure going from two and a half times its base to a third of it. That is the honest headline, and it is a better one than the 14.3%, because a share of an earlier version of oneself is a share of something a reader has no independent feel for.

The arc is also worth reading as four numbers rather than three, because the first structure this problem had is not on the chart. Reading every occurrence needs no apparatus at all: the document array alone, at 98,694 bits, and a scan of the range. That is the cheapest structure by a wide margin and it has the wrong asymptotic behaviour.

So the sequence is 98,694 for the naive method, 838,797 for the published output-sensitive one, 285,460 after two removals and 119,972 after the third. The apparatus started at eight and a half times the naive structure and is now at 1.22 times it — which is a fair summary of what three passes of removal achieved and is not the summary any of the three essays gave.

The base is the wrong base

There is a caveat that undermines every share in this essay and it should be stated rather than left for a reader to find.

The base is an uncompressed suffix array and an uncompressed text. Nobody builds that. The whole point of the surrounding field is that the base can be a self-index — the index that is smaller than the text — which on this collection would be around 6.4 bits a character, or 105,000 bits, against the 328,980 above.

Against that base the descent’s apparatus is not 36.5%; it is 114%. Still larger than the thing it sits on.

That changes the conclusion of this essay and it does not change the arc. Three removals took the apparatus from 800% of a self-index to 114% of one, which is a factor of seven and is worth having. It is not the “a third of the index” a reader would take away from the plate, because the plate’s base is what the earlier essays used and consistency with them was the reason to keep it.

The honest summary is two numbers: 36.5% of an uncompressed base and 114% of a compressed one, with the second being the one that describes a system anybody would build.

Four methods, one query, the same documentsThe pattern " until" on a collection of 24 documents: 54 occurrences spread over 8 documents. Reading every occurrence costs the occurrences — 54 — and is proportional to the range rather than to the answer. The published range-minimum walk costs 267 operations inside the tree, which is the log the method's own account leaves in the constant. Removing the chain brings it to 83. One descent over the document array costs 32. All four report the same 8 documents, and the check is on the documents and not on their number, because the descent produces them in a different order and a comparison of counts would hide a shape mistake.every occurrence548 documentsrange minimum and chain2678 documentsrange minimum, no chain838 documentsone descent over D328 documentsthe document arraythe document array, the chain and a range minimumthe document array, a range minimum and one bit per documentthe document array, in a wavelet tree54 occurrences in 8 documentsoperations inside the structure
Fig. 5 The capability all three prices buy: four methods answering one query and reporting the same eight documents.

Three ways to quote one number

This essay has now quoted the same structure five ways and every one of them is defensible, which is a problem worth naming rather than resolving quietly.

14.3% of the published apparatus. True, and it compares the structure against an earlier version of itself, which a reader has no independent feel for.

36.5% of an uncompressed suffix array and text. True, and the base is one nobody builds.

114% of a self-index over the same collection. True, and it is the number that describes a system, and it is not what any of the three essays reported.

1.22 times the naive method’s document array. True, and it is the comparison against the alternative rather than against a predecessor.

A wash on this collection and half on a skewed one. True of the last step alone.

Five numbers, one structure, and the spread between the smallest and the largest is a factor of eight. A sixth of what, exactly made the general argument in a different strand: a share carries what it is a share of, and one that does not is a number about nothing.

The rule that comes out of having done it wrong here is narrower than that. When a strand improves a structure over several passes, the share against the previous version is the one that gets quoted and the share against the alternative is the one that matters. Every essay in this strand quoted the first, and the second is the one that would have said, three passes ago, that the method was still losing.

The smaller tree hands its answer back in the wrong orderThe same document array in two tree shapes, on a collection of 32 documents whose lengths fall as one over rank. The balanced tree costs 49,593 bits and returns the documents sorted, because its leaves are in the alphabet's order. The Huffman tree costs 41,589 — 83.9% of it — and returns them in frequency order. Both report the same 4 documents for the same query at almost the same operation count. So the trade is 8,004 bits against sorting an answer of 4, which is d log d comparisons on a walk that already cost more than that — and it is stated rather than hidden, because a plate showing only the Huffman column is showing a saving and not a choice.bits heldbalanced49,593huffman41,589the answer comes backbalanced: sorted · 26 operationshuffman: sorted · 24 operations32 documents · zipf lengths83.9% of the ordered tree
Fig. 6 The one decision left inside the last array: two tree shapes with the same answer, sixteen per cent apart in size and different in the order they return it.

What would move it further

Three things could, and they are of decreasing plausibility.

A compressed vector representation of the levels. On a collection whose array has a dominant symbol this is worth a quarter — 1.976 bits a symbol to 1.571 on the dominated collection. On an even collection it is worth four per cent. It costs several times the work per rank and the directory grows as a share.

A different code shape. The tree’s payload is the weighted path length of its code, and Huffman minimises that among prefix codes. Nothing beats it here except giving up the prefix property, which gives up random access.

A different formulation. An inverted index over documents answers this query without a suffix array, a document array, or any of it — for indexed terms only. That is not a smaller version of this apparatus; it is a different design whose costs are not comparable, and it is not measured here.

None of the three removes an array, because there is one array and it is the input.

What each method's work is proportional toThree methods against the number of documents in the answer, on a collection where the range grows from 17 rows to 324. Reading every occurrence follows the range: 17 to 324, a factor of 19x. The range-minimum walk follows the answer with a logarithmic factor on top. The descent follows the answer with the least of the three: 36 operations for 7 documents and 62 for 32, which is 5.14 per document down to 1.94 — the work per document FALLS as the answer grows, because the ancestors of many leaves overlap near the root.1010010³documents in the answeroperations inside the structureevery occurrencerange minimumone descent17 to 324 rows5.14 to 1.94 per document
Fig. 7 The other axis every one of these prices should be read against: what each method costs per query, which did not move in the same direction as the sizes.

What the sizes do not say

Sizes are one axis and this strand has been measured on two, so it is worth putting the other one beside these numbers before drawing any conclusion from them.

The published apparatus costs two hundred and sixty-seven operations inside the structure to report eight documents. The chainless one costs eighty-three. The descent costs thirty-two. So the operation count fell by a factor of eight over the same three passes that took the size down by a factor of seven, which is a happier outcome than a strand of this shape usually gets — a size reduction that also reduces work is the exception rather than the rule.

But the units are not the same. A segment-tree node visit and a bit-vector rank on a compressed level are different amounts of real work, and this collection charges both as one operation. The comparison that is not one comparison is the essay that made that distinction the site’s own habit, and it cuts against the descent here: a rank is the more expensive of the two.

So the honest statement about the query is a factor of eight in operations and something smaller in time, and the difference between those two numbers is not measured anywhere in this strand.

What the document array can be compressed to is the length distributionThe zeroth-order entropy of the document array, for four collections of 32 documents and 8,192 characters. The array holds each document once per character it contributed, so its symbol distribution is the length distribution and nothing else. On equal-length documents H0 is 5.000 against a ceiling of log2 32 = 5.000 — the two are the same number, and a wavelet tree over that array is 100.0% of the plain n⌈log₂ d⌉ array, which is to say it saves nothing. On a collection where one document holds four fifths of the text H0 falls to 1.688 and the array to 39.5%. The dashed line is the ceiling every row is measured against.equal lengths5.00 bits100.0%lengths as one over rank4.15 bits83.4%a few long, many short4.31 bits86.7%one document holding most of the text1.69 bits39.5%log₂ 3232 documents · 8,192 characters100.0% to 39.5%
Fig. 8 The property that decides how much of the last step is a saving: the entropy of the document array on four collections of the same size and document count.

One number that did not move

Across all three passes one quantity stayed exactly where it started, and it is the one that decides whether any of this is used.

The crossing — the density at which an output-sensitive method beats reading every occurrence — fell from 10.8 occurrences a document to somewhere around three and a half. The collections this field has, measured on every shape available, sit at 1.84 to 1.88.

So the apparatus went from losing by a factor of six to losing by a factor of two, and it is still losing. Seven times smaller, eight times fewer operations, and the naive method still wins on every corpus in hand.

That is not a reason to undo the work: a factor of six becoming a factor of two is most of the distance, and one more improvement of the same size would cross it. It is a reason to be careful about what the three essays mean together. Each of them reported a real gain against the previous structure and none of them reported the comparison that decides.

The shape of a strand that ends

An apparatus that shrank by a factor of seven over three passes did not need a new idea about document listing. Each pass found that something already present answered a question an extra array had been built for: the traversal order, then a better representation, then a neighbouring structure.

What that means for a reader with a different apparatus is a short checklist rather than a technique. For each derived array, ask whether the traversal knows, whether the representation can be tighter, and whether something else present already answers the question. Three for three here.

And when the checklist runs out, the strand is over — not because nothing more is possible, but because what remains is the input and a representation of it, and neither of those is machinery to be removed.

Where this goes next

every occurrence5610 documentsrange minimum and chain32510 documentsrange minimum, no chain9610 documentsone descent over D3810 documentsthe document arraythe document array, the chain and a range minimumthe document array, a range minimum and one bit per documentthe document array, in a wavelet tree56 occurrences in 10 documentsoperations inside the structure The tree answers the question The distinct documents in a range of rows are the distinct symbols of the document array in that range. A wavelet tree enumerates those in one descent, so the range minimum, the chain, the bitmap and the recursion all go at once. a segment tree over the chain2.70x8,142,274 bitsa succinct range minimum over the chain1.62x4,898,356 bitsno chain at all0.84x2,534,726 bitsthe dashed rule is the index itself: a suffix array and the text131,327 characters · 256 documents2.70x → 0.84x The apparatus that is smaller than its index Answering "which documents hold this" at a price proportional to the answer used to cost 2.70 times the index it sits beside. Two changes later it costs 0.84, and the largest thing left is an array that says which document each row belongs to. range minimum and chain838,797255.0%range minimum, no chain285,46086.8%one descent over D119,97236.5%the document array, the chain and a range minimumthe document array, a range minimum and one bit per documentthe document array, in a wavelet tree64 documents · 16,447 characters14.3% of the published apparatus The last array in the apparatus The document-listing apparatus began as three arrays beside a suffix array. Two of them turned out to be machinery for reading the third, and both have gone. What is left is the document array, and it is the only one of the three that was information.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

What links here

Every essay whose body links to this one.

The objects this essay names

Each one links to every other essay that touches it.

Document arrayDocument listingIndex sizePrevious occurrence chainRange minimumSpace accountingSuffix arrayWavelet tree