Algorithms & Data Structures
the bound is a claim, and it is checkable
What the libraries do

The smaller tree hands it back unsorted

A frequency-shaped tree is sixteen per cent smaller and returns its documents in code order. A balanced one is larger and returns them sorted. The trade is d log d comparisons against a saving, which is not close — until the answer is truncated.
20 min read 8 figures Measured, not assumedTwo counts, two rankingsThe order is the algorithmAn index has a size

The listing apparatus is one array in one tree, and the tree’s shape is the last thing left to choose.

A balanced tree gives every document a code of ⌈log₂ d⌉ bits and puts its leaves in the alphabet’s order. A frequency-shaped tree gives short codes to documents that contributed many characters and puts its leaves in frequency order.

The first costs exactly what the plain array costs. The second costs the array’s entropy, which on a collection whose lengths fall as one over rank is sixteen per cent less.

And the second hands its answer back in the wrong order.

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. 1 The same document array in two tree shapes on a collection of thirty-two documents: what each costs, and what order each returns its answer in.

The two numbers

On the one-over-rank collection the balanced tree is 49,593 bits and the Huffman-shaped one is 41,589 — 83.9% of it. Both report the same four documents for the same query at almost the same operation count: twenty-six against twenty-four.

The balanced tree’s output is sorted. The Huffman tree’s is not.

Sorting the answer costs d log d comparisons on an answer of size d. On an answer of four that is eight comparisons; on an answer of four hundred it is about three and a half thousand. The descent that produced the answer cost twenty-four operations for the first and would cost several hundred for the second.

So for a full answer the trade is not close. Eight thousand bits against eight comparisons, or against three and a half thousand on a large answer — and even there the sort is comparisons on values already in registers while the saving is bits held for the life of the structure.

Take the smaller tree.

There is a hidden term in that comparison worth surfacing, because it is the reason the answer is not simply “always sort”. The sort is d log d comparisons of small integers, which on any real machine is a few nanoseconds for an answer of a hundred. The sixteen per cent is bits held for the life of the structure, paid on every page fault and every cache miss the structure causes over its lifetime.

Those are not the same kind of cost and comparing them by counting is the error the unit of cost is not one exists to prevent. What makes the conclusion safe anyway is the direction: the smaller structure is smaller and the sort is cheap, so both currencies point the same way and the incommensurability does not have to be resolved.

It would have to be resolved if they pointed differently — a representation ten per cent smaller that made every query twice as expensive, say — and this collection has no principled way to do that. It reports both and names the trade.

Why the order differs at all

A wavelet tree’s leaves are its code words read as paths. The descent reports symbols in the order it reaches their leaves, which is left to right, which is the order the code words sort as strings.

A code is order-preserving when reading its code words in that order gives the symbols in their own order. A balanced code assigns consecutive code words to consecutive symbols, so it is. A Huffman code assigns short words to frequent symbols wherever they fall in the alphabet, so it is not: a frequent document with a low number gets a short code and sorts early, and a rare document with a lower number gets a long one and sorts late.

That property has a name in this collection because a different operation needed it. The tree the operation insists on is where the compound walk turned out to require an ordered tree — “everything that went left is smaller” is false in a frequency-shaped tree — and where a plausible number came out wrong on 81% of queries.

Here the requirement is weaker. The listing descent needs no order at all to be correct; it needs one only if the caller wants sorted output.

Four ways to divide the same text into the same number of documentsThe 32 document lengths of each collection, drawn as a stacked strip of 8,192 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 5.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.15. One document holding most of the text gives 1.69, and it is the only one of the four where the saving is worth the machinery.equal lengthsH0 = 5.00 bitslengths as one over rankH0 = 4.15 bitsa few long, many shortH0 = 4.31 bitsone document holding most of the textH0 = 1.69 bits32 documents, 8,192 characters, four apportionmentslongest document 6,595 characters5.00 to 1.69 bits
Fig. 2 What sets the code shape and therefore the leaf order: how a collection apportions its characters between documents.

Two things follow from the order being set by the frequencies. The order is a property of the collection rather than of the query, so it is stable across queries and a caller could in principle learn it — which is worse rather than better, because a caller that has learned it will break when a document is added.

And the order changes when the collection does. Adding one large document to a collection re-shapes the code, which permutes the leaf order, which changes the order every query’s answer comes back in. Nothing about the answers changes and everything about their presentation does.

Where the preference becomes a requirement

The trade above is settled for a full answer and it inverts completely for a truncated one.

A search interface showing ten results does not want all four hundred documents holding a pattern. The descent visits leaves in a definite order, so it can stop after ten — at a cost of about 2 × 10 × (1 + log₂(d/10)) operations rather than the full answer’s, which on ten thousand documents is a factor of twenty.

Stopping after ten on a Huffman tree reports the ten documents whose codes come first. That is not the ten smallest document numbers, not the ten with the most occurrences, and not any ordering a reader would recognise. It is decided by the collection’s length distribution, because the code shape is.

So a truncated listing on a frequency-shaped tree returns an arbitrary subset presented as an answer. Every count agrees, every document reported is genuinely there, and the ten shown are chosen by file sizes.

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. 3 The four methods on one query, all reporting the same eight documents. The check is on the documents rather than on their number, because two of the methods produce them in different orders.

Which is the silent failure

That is worth separating from the ordinary case, because the two failures have different visibility.

On a full answer, reading the descent’s output as sorted is caught immediately by anything that checks: the first two documents come back out of order and a caller merging two lists gets a wrong merge on the first query.

On a truncated answer nothing is caught. Ten documents come back, all of them correct, and the only wrong thing is which ten. There is no assertion that fires, no count that disagrees, and no ordering to inspect — the caller asked for ten and got ten.

This collection has a habit for exactly this shape: an assertion that has never rejected anything proves nothing, so a check that cannot see a defect is a check that has to be replaced rather than trusted. The check here is on the set for the full answer, and on a truncated answer the set is not the thing that went wrong.

There is a second truncation shape with the same problem and it is more common than the first: reporting a count and a sample. A system saying “found in 412 documents, including these ten” is truncating, whether or not it calls it that, and the ten are chosen by the same arbitrary criterion.

The count is right. The sample is not a sample of anything a reader would recognise — it is the ten documents with the shortest codes, which is to say the ten largest documents that happen to hold the pattern, on a collection whose lengths vary. That is a biased sample with a bias nobody chose, and it is the kind of defect that looks like a feature: the large documents are often the interesting ones, so the output looks better than it should.

What a system should actually do

Three options, and the first two are the ones worth considering.

A balanced tree, and pay the sixteen per cent. Truncation is then safe, because the leaf order is the document order, and the ten reported are the ten lowest-numbered documents holding the pattern — which is at least an ordering somebody chose.

A frequency-shaped tree, and never truncate. Report the whole answer, sort it, and let the caller truncate. The sort costs d log d on an answer the descent already spent more than that on.

An alphabetic code — the minimum-cost prefix code among those that preserve order. That gets most of the size saving and the order, and it is a real construction: an interval dynamic program over the frequencies rather than Huffman’s merge.

The third is the right answer and this collection has already measured its cost in another strand: a factor of fourteen, for four per cent found an optimal alphabetic code costing 1.43% over Huffman on generated English and 3.5–5.0% on real text, while keeping the depth. Applied here, that is most of the sixteen per cent for a few per cent back, with sorted output.

It is named and not built in this apparatus, which is the honest state.

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. 4 What the size saving actually is: the entropy of the document array on four collections, which is what a frequency-shaped tree costs and a balanced one does not.

There is a fourth option that avoids the question by moving it, and it is worth naming because a real system might reach for it. Keep the frequency-shaped tree and store a permutation mapping code order to document order — d⌈log₂ d⌉ bits, which at a thousand documents is ten thousand bits against a saving of sixteen per cent of a much larger array. Truncation then reports the ten documents whose permuted positions come first, which is document order.

That works and it is a strange thing to build, because a permutation of d elements is exactly what a balanced code is. Storing the saving and then storing the thing the saving cost is a pattern worth being suspicious of, and here it is nearly a wash: the permutation is a fixed d log d while the saving is a fraction of n log d, so it pays when n is much larger than d and not otherwise.

The collection decides how big the choice is

The sixteen per cent is one collection’s number and the spread is large.

On equal-length documents the two shapes cost exactly the same, because the entropy is log₂ d and Huffman’s code is the balanced one. There is no choice to make.

On a collection whose lengths fall as one over rank, sixteen per cent.

On a collection where one document holds four fifths of the text, sixty per cent — the balanced tree spends five bits a symbol and the Huffman one spends two.

So the decision’s stakes are the length distribution’s entropy deficit, which is the array is the length distribution again, and on the collection where the stakes are highest the order problem is also worst — because a dominated collection’s code order is furthest from its document order.

What the operation count says

The two shapes differ in size and barely in work: twenty-four operations against twenty-six for the same query.

That is not obvious in advance and the direction is worth explaining. A Huffman tree is shallower for frequent documents and deeper for rare ones. The documents holding a pattern are roughly a uniform sample of the documents — a pattern is about as likely to be in a short document as a long one — so the descent’s leaves are uniform while the depths are frequency-weighted, which should make the Huffman descent deeper on average.

It comes out slightly cheaper here because the dominant document is in the answer and its one-bit code saves more than the rare documents’ long codes cost. On a query whose documents are all rare the ordering reverses.

So the operation count is a wash with a small, unsigned dependence on which documents are in the answer, and the choice is decided by the size and the order alone.

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. 5 The work the shape does not change: what each listing method costs against the number of documents in the answer.
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,727 bits and returns the documents sorted, because its leaves are in the alphabet's order. The Huffman tree costs 20,376 — 41.0% 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 29,351 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,727huffman20,376the answer comes backbalanced: sorted · 22 operationshuffman: sorted · 26 operations32 documents · oneLarge lengths41.0% of the ordered tree
Fig. 6 The same two shapes on a collection where one document holds most of the text, and the size gap is sixty per cent rather than sixteen.

On the dominated collection the two shapes are furthest apart and the order is worst, which is the unhelpful combination. A code word is at least one bit is where that collection’s floor was measured, and it is the same collection: the one where the frequency-shaped tree is most worth having is the one where its leaf order is least like the document order, because one document has a one-bit code and everything else has five or six.

The general form

The pattern here is one this collection keeps meeting and it is worth stating once in general terms.

A representation chosen for its size may lose a property the caller was relying on, and the property is usually an order. A Huffman code loses the alphabet’s order. A hash table loses the key order. A frequency-sorted posting list loses the document order. In every case the structure is correct and something built on top of it silently is not.

What makes it hard to catch is that the property is rarely written down. Nobody specifies that a document listing returns its documents in order, because the obvious implementations do, and a caller written against those implementations depends on it without saying so.

The instruction is to write the property down when the representation changes, and to make the check test it. Here that means a check that the balanced tree’s output is sorted and the Huffman tree’s is not — a two-ended check, because one that only required the first would pass on a tree that happened to be ordered by accident, and one that only required the second would be testing nothing.

The same defect, three strands apart

It is worth putting the three instances side by side, because they are the same mistake made about three different objects and the third one is the one that would not have been caught.

In the tree the operation insists on, a bidirectional extension read a Huffman tree’s leaf order as the alphabet’s to accumulate “how many characters sort before this one”. The number came back plausible and wrong on 81% of queries, worst 706 against 3,058. Caught because a plate drew three tree shapes side by side.

In one set, three orders, the interval enumeration returns the same set on every shape and a different order, and a search reading the output as sorted computes the same wrong smaller-count. Caught by requiring the two shapes to disagree.

Here, the listing’s full answer is a set and the order is a presentation detail — until it is truncated, at which point the order chooses the answer. Not caught by anything, because the failure is in what a caller does with a correct result.

The three form a progression in how hard the defect is to see. In the first the structure computes a wrong number. In the second the structure computes a right number that a caller misreads. In the third the structure and the caller are both right and the composition is wrong.

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. 7 The other axis a shape decision moves: what a plain-vector tree costs against the entropy, with the one-bit floor a prefix code cannot get under.

Nothing in this collection’s checking habit reaches the third. An assertion lives inside a generator or a library and tests a claim about an object; a defect that only exists when two correct objects are composed is outside every one of them. The instruction that comes out is not a new kind of check but a writing rule: when a representation is chosen for its size, write down which properties it gave up, in the place a caller will read.

What the apparatus looks like with the choice made

Putting the pieces together, the apparatus a reader should build depends on one question: will the answer ever be truncated?

If no — a system that always consumes the whole document list, an offline analysis, a count — take the frequency-shaped tree, sort when a sorted answer is wanted, and the apparatus is the apparatus, three times smaller again’s 119,972 bits with sixteen per cent off on a collection whose lengths vary.

If yes, take the balanced tree and pay the sixteen per cent, or build the alphabetic code and pay a few per cent. The second is better and is more work, and the difference between them is a dynamic program over the document frequencies that runs once at construction time.

Either way the apparatus is one array in one tree and one descent, which is what three passes of removal left. The shape is the only parameter, it has two settings and a third that is better than both, and the setting is decided by a property of the interface rather than of the collection.

That last point is the unusual one. Every other decision in this strand — which structures to keep, how far the array compresses, whether the method beats reading every row — was decided by the collection. This one is decided by what the caller does with the answer, and no measurement of the corpus can settle it.

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. 8 Where the sixteen per cent applies: the three listing apparatus priced, with the last one being the array whose shape is in question.

The state of the choice

The apparatus ships with the frequency-shaped tree and a sort, which is the second option above.

That is the right choice for a full answer and it forecloses truncation, which is the operation a real search system wants most. The alphabetic code would give both, at a few per cent of the saving, and it is the one remaining piece of this apparatus that is named and unbuilt.

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 fixed-length code97,718 bits5.00 ranks · in orderthe best ordered tree77,890 bits3.98 ranks · in orderthe best tree of any shape76,789 bits3.92 ranks · unorderedσ 21 · the ordered tree is 1.43% above the unordered optimum16,384 characters of englishorder costs 1.43% The tree the operation insists on The compound walk means "everything that went left is smaller", which is true only if the leaves are in the alphabet's order. Huffman's tree is the smallest and its leaves are in frequency order, so the operation that makes a bidirectional search affordable costs the shape that makes an index small. 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% The array is the length distribution The document array holds each document once per character it contributed, so its symbol distribution is the collection's length distribution exactly. On equal-length documents its entropy is log d and no coding saves anything.

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.

CorrectnessDescentDocument arrayDocument listingHuffman codeIndex sizeOrdered codeWavelet tree