The tree the operation insists on

The compound walk down a wavelet tree returns, from one descent, both the rank of a symbol and the count of every symbol smaller than it.

The second half of that is a claim about the tree. At a level where the code goes right, the walk adds the number of positions that went left — and calls them smaller. That is true when the tree’s leaves run left to right in the alphabet’s order, and false otherwise.

Huffman’s tree does not have that property, and Huffman’s tree is the smallest one there is.

Why Huffman’s leaves are not in order #

The construction takes the two lightest weights and merges them, wherever they are in the alphabet. If q and z are the two rarest letters they become siblings, and they sit at the bottom of the tree next to each other regardless of everything between them.

The result is optimal — no binary tree over those weights has a smaller weighted path length, which is what makes n·H₀ the size of a Huffman-shaped wavelet tree — and its leaf order is the order the merges happened to produce, which is a frequency order and not a symbol order.

So a compound walk in it still runs and still returns a count. The count is of whatever went left, which is a set of symbols with no relation to the one being asked about: measured over two hundred queries on twenty-one symbols, the answer is wrong on 81% of them, worst case 706 against a true 3,058.

That is the worst kind of failure — a plausible number, silently — and it is why the index that uses the compound operation refuses a Huffman-shaped tree at construction rather than at query time.

The best tree that is in order #

If order is a constraint, the question becomes: among trees whose leaves are in the alphabet’s order, which is smallest?

That is a different optimisation and it has a different algorithm. Huffman’s merge is unavailable, because merging two non-adjacent symbols is exactly what breaks the order. What is available is a split: the best tree over symbols i…j is a split point k, plus the best trees over i…k and k+1…j, and every symbol below a split pays one more bit.

That recurrence is a dynamic program over intervals, cubic in the alphabet with the plain form. At 90 symbols it is 121,485 steps; at 104 symbols, 187,460. Both are nothing, and both are measured rather than assumed — the step count is returned by the construction so that “cheap at this alphabet” is a number rather than a feeling.

Hu and Tucker’s construction finds the same optimum in n log n and is not built here, in the same way this collection names every structure it prices without implementing.

What order costs #

On generated English at 21 symbols: Huffman 76,789 bits, the ordered optimum 77,890, a fixed-length code 97,718.

Order costs 1.43%. A fixed-length code costs 27%.

On real text the alphabet is larger and the distribution more skewed, so the numbers move — and they move in the direction that matters, which is up:

Twelve real essays, 90 symbols: Huffman 352,475, ordered 369,940 — order costs 4.95%.

Eight source modules, 104 symbols: 386,772 against 400,185 — 3.47%.

Ten revisions of one file, 79 symbols: 355,886 against 368,600 — 3.57%.

So the price of the compound operation is between one and five per cent of the wavelet tree, and the wavelet tree is about half of an FM-index. Call it one to two and a half per cent of an index.

And what it saves in query depth #

The size is only half of what a tree’s shape decides. The other half is how deep the average symbol’s leaf is, which is how many bit-vector ranks an access costs.

A fixed-length code: 5.00 ranks an access on 21 symbols, 7.00 on 90.

Huffman’s tree: 3.92 and 4.49 — because the mean depth of a Huffman tree is the entropy, which is the tidiest result in this collection’s index strand and the reason a Huffman-shaped tree is used at all.

The ordered optimum: 3.98 and 4.72.

The ordered tree keeps almost all of the depth saving. Against a fixed-length code it is 33% shallower on real prose; against Huffman it is 5% deeper. So choosing it costs a few per cent of bits and a few per cent of query depth, and buys the operation that removes a factor of fourteen from an extension.

Assigning the code words #

There is a step between the lengths and the tree that is easy to get wrong, and getting it wrong produces a tree that is the right size and the wrong order.

Given lengths satisfying Kraft’s equality, the canonical assignment hands out code words in increasing numeric order — and canonical Huffman sorts the symbols by length first, which is what makes its code words compact and is exactly what destroys the order this page needs.

The assignment for an alphabetic code takes the symbols in alphabet order instead, and shifts in both directions: the lengths of an alphabetic code do not increase along the alphabet, because a frequent symbol can sit between two rare ones.

That two-directional shift is the whole difference, and it has a trap in it worth recording: a left shift by a negative amount, in this language, shifts by thirty-two minus it and returns a plausible wrong number rather than failing. The first version of the assignment did exactly that, and it produced a “tree” that was 2.38 times Huffman’s on source code — a number large enough to notice, which is the only reason it was caught rather than shipped.

The check standing on it now takes the lengths of an optimal alphabetic code, hands them out canonically, and requires the result not to be in order: 17 of 21 code words move, and a construction that produced the same words either way would mean the check was testing nothing.

Why the constraint is not obviously worth it #

Stated as a trade it sounds one-sided — a few per cent of bits for a factor of fourteen in operations — and it is worth being careful, because the two are not the same kind of quantity.

The bits are permanent. An index is built once and held; a few per cent larger is a few per cent larger for its whole life, on every machine that loads it.

The operations are per query, and only per bidirectional query. An index used for plain backward search never performs an extension of the kind this operation accelerates, so it pays the size and gets nothing. An index used for approximate search under a covering scheme performs thousands per pattern and gets the factor.

So the answer depends on the workload, which is the honest form of nearly every trade here: the cost model is an input, and the input is what the index is for. What the measurement does is give both numbers, so that the decision is arithmetic rather than taste.

When the constraint is free #

There is one case where the whole page is unnecessary, and it is the case this collection measured first.

On a uniform alphabet — DNA, or any text whose symbols are equally frequent — Huffman’s tree is the balanced tree, its leaves are in whatever order the tie-breaking produces, and an ordered tree of the same shape has the same size. Order costs exactly 0.00%.

That is why the compound operation never came up while the strand was measuring DNA. At four equally frequent symbols there is no size argument for a Huffman shape, no ordering to lose, and a loop over four symbols is cheap enough that nobody counts it.

Every part of this page’s difficulty appears together: a large alphabet, a skewed distribution, and a search that performs thousands of extensions. That is English, or source code, or any real text.

Where the dynamic program comes from #

The recurrence deserves a paragraph, because it is the reason this is a different algorithm rather than a variation on Huffman.

Huffman builds bottom-up: take the two lightest weights, merge them into a node whose weight is their sum, repeat. The merge is a choice of which two, and it is unconstrained — the two lightest can be anywhere in the alphabet.

An alphabetic tree cannot merge non-neighbours, because the leaves must stay in order. So the natural formulation is top-down: choose where the root splits the alphabet, and every symbol below that split pays one more bit. The best tree over symbols i…j is then the best split k plus the best trees on either side, and the cost of a subtree is its own weighted path length plus the total weight beneath it — the second term being the extra bit every symbol under the split pays.

That is an interval dynamic program of exactly the shape used for optimal binary search trees and for matrix-chain multiplication, and it is cubic without Knuth’s monotonicity optimisation. At the alphabets this field runs on — under 128 symbols — cubic is 350,000 steps, which is nothing, and the construction reports its own step count so that “nothing” is a number.

What the sizes mean in an index #

Bits in a wavelet tree are not bits in an index, and the conversion is worth doing once.

The tree is one part of an FM-index. On the measurements here it is 18,377 bits of 35,305 at a four-symbol alphabet — about half — and a larger share at a larger alphabet, because the other parts do not grow with σ.

So an ordered tree costing 4.95% more on real prose makes the tree 4.95% larger and the index about 2.5% larger. A bidirectional index is two of them, so 2.5% again.

Against that, a factor of fourteen, for four per cent is the operation count the ordering buys. Both numbers are on one plate there, which is the only way this collection is willing to report a trade.

What Hu and Tucker did #

Named rather than built, and worth knowing what is being skipped.

The dynamic program above finds the optimal alphabetic tree in cubic time. Hu and Tucker’s algorithm finds the same optimum in n log n by a construction that is genuinely surprising: it merges pairs the way Huffman does, but only pairs that are tentatively adjacent in a sequence that ignores already-merged internal nodes — and then, having found the code lengths, it rebuilds the tree from the lengths alone in alphabet order.

The second half is the part this page uses anyway: an alphabetic code is determined by its lengths, and the assignment from lengths to code words in alphabet order is what orderedCodesFromLengths does. So the two constructions differ only in how the lengths are found.

At σ = 128 the cubic version is 350,000 steps and Hu–Tucker is about 900. Both are instant, and the reason to name the second is that this field’s alphabets are small and somebody else’s are not: a wavelet tree over words rather than characters has an alphabet of a hundred thousand, and cubic is then a million million.

The trap in the assignment, in full #

Worth recording properly, because it is the kind of defect that ships.

Canonical code assignment walks the symbols in some order and computes each code word from the previous one: add one, then shift left by the difference in lengths. That works when the lengths are non-decreasing along the walk, which is exactly what sorting by length guarantees — and canonical Huffman sorts by length.

An alphabetic code’s lengths are not monotone along the alphabet. A frequent letter sits between two rare ones and has a shorter code than both, so the walk sometimes shifts left and sometimes right.

Written as a single left shift by a possibly negative amount, this language evaluates x << -2 as x << 30, which is a plausible number rather than an error. The result was a code that satisfied Kraft’s inequality, produced a tree, and measured 2.38 times Huffman’s size on source code — large enough to notice only because a plate drew it beside two other shapes.

The fix is three lines and the check is one: hand the same lengths out in canonical order and require the result not to be in alphabet order. Seventeen of twenty-one code words move, and a construction that produced the same words either way would mean the check was testing nothing.

Where this sits in the strand #

Every child at once is the operation this tree exists to support, and the count that was already there is why it costs nothing in operations. This page is the price in bits, and a factor of fourteen, for four per cent puts the two together.

The shape being given up is the one a floor on the bits is about — Huffman’s tree, whose mean depth is the text’s zeroth-order entropy — and the structure all of it lives in is the index that is smaller than the text.

What an alphabetic code is worth outside this #

A last note, because optimal alphabetic codes have a life of their own and this page uses them for one purpose.

They are the right code whenever the order of the symbols carries meaning that has to survive the encoding: search trees over ordered keys, where a comparison has to be answerable from the code; range queries over an alphabet, where “everything below c” has to be a subtree; and any structure that wants to be both a code and an index, which is exactly what a wavelet tree is.

Huffman’s code is better where order does not matter, which is nearly everywhere a code is used for compression alone. So the two constructions are not competitors: they answer different questions, and this collection needed the second only when it wanted a tree to be searched as well as stored.

That is a tidy way to hold the whole page. A wavelet tree is a code being used as an index, and the moment it is used as an index, the order of its leaves stops being an implementation detail.

The three shapes, as a decision #

Put plainly, since the page has three constructions in it and a reader has to choose one.

Use a Huffman-shaped tree when the index will only ever be searched in one direction. It is the smallest and the shallowest, and the compound operation is not needed — rank is the only thing it does is the whole requirement, and a plain backward search never asks for a smaller-symbol count.

Use the optimal alphabetic tree when the index supports bidirectional search. It costs three to five per cent more on real text, keeps most of the depth saving, and makes every child at once available — which is a factor of fourteen on the operation that dominates an approximate search.

Use a fixed-length code when the alphabet is uniform, or when the construction has to be trivial. On uniform text it is the same tree as the other two; on skewed text it costs a quarter more in bits and half again in depth, and a factor of fourteen, for four per cent is where that comparison is drawn.

The middle option is the one this collection now builds, and it is worth noticing that it did not exist here until an operation demanded it. A constraint arriving from the query side, changing which code a structure is built with, is the tidiest example this collection has of the structure decides the count running in the other direction.

Which collapses to one question, and it is worth saying so because a three-way decision reads as harder than it is.

The two costs are wildly asymmetric. The middle option costs three to five per cent of the bits and buys a factor of fourteen on the operation an approximate search spends most of its time in. No plausible weighting makes four per cent of a structure worth more than an order of magnitude on its dominant query, so the only thing to decide is whether that query is ever asked.

Is the index searched bidirectionally? If yes, the alphabetic tree; if no, the Huffman one; and the fixed-length code only where the construction has to be trivial or the alphabet is already uniform, in which case all three are the same tree anyway.