One set, three orders

A wavelet tree’s leaves are its code words read as paths. A 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.

That gives two claims about the enumeration and they have to be kept apart, because one of them is a fact about intervals and the other is a fact about codes.

The set does not depend on the shape. Which symbols an interval holds is a property of the interval. Any tree over the same alphabet, however shaped, reports the same ones.

The order does. A balanced code assigns consecutive code words to consecutive symbols, so its leaves are in the alphabet’s order. A Huffman code assigns short words to frequent symbols wherever they fall, so its leaves are in frequency order.

What the two claims need separately #

The set claim is checked by running the descent on three shapes over the same text and requiring the sets to be equal — twenty-four intervals across three shapes, every set identical.

The order claim is checked by requiring the shapes to disagree. A balanced tree’s output must be sorted and a Huffman tree’s must not, and a check that only asked for the first would pass on a Huffman tree that happened to be ordered by accident on a small alphabet.

That second half is the part that makes this a two-ended check rather than a claim. On a uniform alphabet all three shapes are the same tree, so a check run there would report agreement and prove nothing. The measurement uses English-like text over twenty-one symbols, where the frequencies are skewed enough that the Huffman code’s order differs from the second symbol onward.

There is a third shape in the picture and it is the one that resolves the tension rather than illustrating it. An alphabetic code is the minimum-cost prefix code among those whose leaves are in order — so it is shaped by the frequencies like Huffman’s and ordered like a balanced one. Its output is sorted and it costs a few per cent more than Huffman.

Drawing all three makes the check’s two-endedness visible: two shapes ordered, one not, and one set among all three. A plate showing only two would leave a reader unsure whether the order is a property of frequency-shaping in general or of Huffman’s construction in particular. It is the latter, and the third row is the evidence.

What a caller does with the order #

For a caller that wants a set, none of this matters. Document listing wants a set: which documents hold this pattern, in any order, and the tree answers the question is that use.

For a caller that reads the output in sequence, accumulating something as it goes, it matters completely.

The case in hand is a bidirectional search. Extending an interval by a character at one end requires knowing, at the other end, how many characters sort before that one inside the interval — because in the mirrored index those extensions sit before this one and the interval’s start has to move past them.

The enumeration gives that for free: read the symbols in order, keep a running total of their counts, and the total before symbol c is exactly the smaller-count. One descent, every symbol’s smaller-count, no extra work.

Provided the order is the alphabet’s.

It is worth seeing why the running sum works at all, because it is not obvious that a descent produces the counts in a usable order.

The descent visits a node’s left subtree before its right, and every leaf in the left subtree has a code word beginning with zero while every leaf in the right begins with one. So the leaves come out in code-word order, and if the code preserves the alphabet’s order then they come out in the alphabet’s order.

The counts arrive with them — each leaf’s interval width is the count of that symbol in the range — so a running sum over the sequence is a running sum over the alphabet, which is the smaller-count.

Nothing about this required the tree to be balanced. It required the code to be order-preserving, which is a different property that a balanced code happens to have.

What goes wrong when it is not #

On a Huffman tree the running total is a running total of the frequency order, which is a plausible number with no meaning.

Measured on a twenty-one symbol alphabet over eight thousand characters: twenty of the twenty-one running totals are wrong, and the worst is out by 1,798 on an interval of two thousand.

Every count is a non-negative integer less than the interval’s width. Every one of them is the correct count of something — the characters preceding this one in code order. Nothing about the number looks wrong, and a search using it produces intervals that are the right width and in the wrong place.

That is the failure mode this collection has met before in the same shape. The tree the operation insists on found the compound walk producing a smaller-count wrong on 81% of queries when its tree was Huffman-shaped, worst 706 against 3,058 — the same defect, one operation earlier, on the same property.

The number 1,798 is worth a sentence because its size is the point. On an interval of two thousand positions, a smaller-count that should be a few hundred comes back as a few thousand or the reverse — the error is comparable to the interval itself.

That means the resulting interval is not merely displaced by a little; it is somewhere else entirely in the index. A search using it would report occurrences at positions that have nothing to do with the pattern, and would report the right number of them, because the interval’s width comes from the forward half and is correct.

The right count of wrong positions is the worst possible failure shape. A count that is wrong is caught by a test on the count; positions that are wrong are caught by a test on the positions; and this collection has tests of both kinds. What it caught this with was neither — it was a check comparing two tree shapes’ outputs directly, which exists because the shapes were suspected rather than because a symptom appeared.

Why it is caught here and not there #

The two instances differ in how they are prevented and the difference is instructive.

The compound walk requires an ordered tree to be correct at all, so the index that uses it refuses a Huffman shape in its constructor. An unordered tree cannot be handed to it.

The enumeration does not require one. Its set is correct on any shape, and only the sequential reading needs the order. So refusing an unordered tree would forbid a use that is perfectly valid — the document listing above, which uses a Huffman tree deliberately for its size.

That leaves the requirement in the caller rather than in the structure, which is a weaker place for it. A structure can enforce its own precondition; a caller has to be written correctly, and nothing checks that it was.

Where the requirement is written down #

The resolution this strand adopted is to put the constraint where the composition happens.

The bidirectional index that branches by enumeration checks its trees’ shape in its constructor and refuses an unordered one — the same guard the compound index has, for the same reason, on a different operation. So the index that reads the output sequentially will not build on a shape that would make the reading wrong.

The operation has no such guard, and is used unguarded by the document listing.

That splits the responsibility correctly: the structure that has a precondition enforces it, and the operation that does not have one does not impose it. What it leaves is a third party — some future caller reading the enumeration’s output in sequence without going through the bidirectional index — that nothing protects.

The only instrument available for that is a rejection test that demonstrates the failure, so that a reader who finds the operation and reaches for a running sum has been told. That test is in the strand: feed the enumeration a Huffman tree, take the running sums, compare against the truth, and require them to differ.

The check that would have been vacuous #

Two versions of the order check were written and the first one could not fail, which is worth recording because the reason is subtle.

The first version compared a balanced tree’s output against a Huffman tree’s and required them to differ. Run on a uniform alphabet — four symbols, equal frequencies — the two trees are the same tree, so the outputs are identical and the check reports that the shapes agree. Which is true, and says nothing about the claim.

The repair is not a different comparison but a different input: the check has to be run on a text whose frequencies are skewed enough that Huffman’s code is genuinely not the balanced one, and it has to verify that the two differ before concluding anything from the fact that they do.

So the check has three parts rather than two. The sets must agree; the orders must differ; and the shapes must actually be different shapes, which on a uniform alphabet they are not.

That third part is the one this collection keeps having to add. The tree the operation insists on records the same repair on the compound walk: an assertion that “the best ordered tree is ordered and Huffman’s is not” fails on a uniform alphabet, where all three shapes are the same tree — which is the case the essay is about. Split into two claims, the second conditional on the sizes differing.

The general form #

Stated without wavelet trees, this is a property that a representation gives up for a size and a caller relies on without saying so.

A Huffman code loses the alphabet’s order. A hash table loses the key order. A frequency-sorted posting list loses the document order. A compressed bit vector loses the ability to read a range of bits directly. In each case the structure is correct and something built on it silently is not.

The pattern is hard to catch because the property is rarely written down. Nobody specifies that an enumeration returns its symbols sorted, because the obvious implementation over a balanced tree does, and a caller written against that implementation depends on it without noticing.

The instruction is a writing rule rather than a checking one: when a representation is chosen for its size, write down which properties it gave up, in the place a caller will read. Here that is a sentence in the operation’s own description, and the reason it took a rejection test to arrive at is that the property was not missing from the implementation — it was missing from the account.

Why the set is shape-free #

The set claim gets less attention than the order claim and it deserves a paragraph, because it is what makes the operation usable at all and it is not obvious.

A descent enters a child when that child’s half of the interval is non-empty. Which positions are in which half depends entirely on the code — a different code sends different symbols left — so two shapes send the interval down completely different paths.

What they agree about is the leaves. A symbol is present in the interval if and only if at least one position of the interval carries it, and that is a fact about the interval and the sequence rather than about the tree. Every path from the root to that symbol’s leaf therefore has a non-empty interval at every step, whichever path it is, so the descent reaches the leaf on any shape.

The converse is the same argument backwards: a leaf reached has a non-empty interval, and a non-empty interval at a leaf means at least one position carrying that symbol.

So the set is the interval’s alphabet and the tree is a way of enumerating it. Three shapes, three sets of intervals along the way, one answer.

What the shapes cost each other #

Since the order is a property of the shape and the shape has a size, it is worth putting the two together once.

On a text where the symbol frequencies are skewed, a Huffman tree’s payload is n·H₀ and a balanced one’s is n⌈log₂ σ⌉. On English-like text over twenty-one symbols that is about 4.2 bits a symbol against 5, a saving of sixteen per cent.

An alphabetic code — the minimum-cost prefix code among those preserving order — gets most of that saving and keeps the order. A factor of fourteen, for four per cent measured it in another strand: 1.43% over Huffman on generated English, 3.5–5.0% on real text, and the same mean depth.

So the trade is not size against order; it is size against order against construction complexity, and the third option gets both for an interval dynamic program instead of a merge.

That is the right answer wherever the order is needed, and it is the answer neither of this strand’s two uses takes: the search uses a balanced tree because it is over DNA and there is nothing to shape, and the listing uses a Huffman tree because it does not need the order.

What a sorted answer is worth elsewhere #

The order matters to one more caller and it is the one a real system is most likely to be, so it belongs beside the search.

A document listing that reports a truncated answer — the first ten of four hundred — chooses which ten by the order the descent produces. On a Huffman tree that is the ten documents with the shortest codes, which is the ten largest documents that happen to hold the pattern. That is a biased sample with a bias nobody chose, and the smaller tree hands it back unsorted is where it is priced.

So the same property that makes a search wrong makes a truncated listing arbitrary. The difference is that the search’s failure is loud once anybody checks a position and the listing’s is silent forever, because ten correct documents are indistinguishable from ten other correct documents.

That gives three uses of the enumeration with three different relationships to the order: a full listing does not care, a truncated listing cares and cannot tell, and a sequential reader is wrong. Only the third is guarded by anything.

Three shapes, three uses #

The strand ends with a clean division and it is worth stating because it explains why all three shapes are in the code.

Balanced where the alphabet is small or uniform, and where the order is needed. The search’s index.

Huffman where the sequence is skewed and only the set is needed. The document array.

Alphabetic where both — skewed and ordered — which is where neither of the two uses landed and which is the shape a third use would want.

Every child at once is where the compound walk’s own shape requirement was worked out, a factor of fourteen, for four per cent is where the alphabetic code was priced, and the array is the length distribution is where the Huffman shape earns its place on a sequence that needs no order.

Three shapes, one operation, and the choice decided by a property of the caller rather than of the data. That is the unusual part: every other representation decision in this collection was decided by what was being represented. A compressed bit vector is chosen because the sequence has runs; a sampling rate is chosen because the text has a length; a code shape is chosen because the symbols have frequencies. Here two of the three shapes are chosen for the frequencies and which of the two depends on what somebody downstream is going to do with the answer, which is information the structure does not have and cannot measure.