A factor of fourteen, for four per cent

Two quantities, measured on the same structures with the same code, on four alphabets.

Two symbols: 5,720 bit-vector ranks become 2,672 — a factor of 2.14 — and the tree costs 0.00% more.

Four symbols: 9,060 become 2,988 — 3.03 — for 0.00%.

Twenty symbols: 120,750 become 11,010 — 10.97 — for 0.17%.

Twenty-six symbols: 225,400 become 16,140 — 13.97 — for 0.04%.

On real text, where the distributions are skewed rather than uniform, the size cost rises to between three and five per cent. The operations saved do not move.

Reading the plate honestly #

The two lines are not the same kind of quantity and the plate has to be read with that in mind.

The rising line is a factor: operations divided by operations, dimensionless, and it is the factor by which one term of a search’s cost falls. The flat line along the bottom is a percentage of a size, and it is permanent.

Putting them on one frame is a choice this collection makes deliberately, because the alternative — a plate of operations and a plate of bits, several pages apart — is how a trade gets reported as a win. What the shared frame shows is that at every alphabet the factor is at least two and the cost is under five per cent, which is a trade nobody has to think about very hard.

What it cannot show is whether the operations matter, because that depends on how often the operation is performed.

When it is a factor of fourteen #

Only under a bidirectional search, and that is a narrow condition worth stating precisely.

A plain backward search extends one interval at one end. It needs two ranks a character and no smaller-symbol count, so the compound operation gives it nothing at all.

A bidirectional search extends both intervals, which needs the smaller-symbol count at every step. Every extension pays σ ranks under the loop and log σ under the walk, and an approximate search performs thousands of extensions — 1,614 on a twenty-six-symbol alphabet for a fifteen-character pattern within two substitutions.

So the factor lands on searches under a search scheme, which is the family the search that starts in the middle is about: a list of searches, each consuming the pattern’s pieces in an order with an error bound each, together covering every way the errors can fall.

What is not saved #

Worth listing, because a factor of fourteen on one term is not a factor of fourteen on a query.

The nodes are the same. The search explores exactly the tree it explored before — same branches, same pruning, same dead ends — because the compound walk changes only how a number inside an extension is computed.

The locates are the same. Reading occurrences out of the final interval costs LF steps per occurrence, unchanged, and on a query returning many answers that is the dominant cost — which is what the half-index strand is about.

And the counting is the same. A count query never extends bidirectionally.

So the honest statement is: the compound operation removes a factor of σ from one of the three terms in an approximate search’s cost. Whether that is a factor of fourteen on the whole query depends on the ratio between extensions and occurrences, which is a property of the pattern and the text.

The size cost, more carefully #

Four per cent is the number on real text, and it is worth saying what four per cent of what.

The wavelet tree is one part of an FM-index: 18,377 bits of 35,305 at a four-symbol alphabet, and a larger share at a larger one. So a tree four per cent larger is an index about two per cent larger, and a bidirectional index — two of them — is two per cent larger overall.

Against that, on English, an approximate search’s extension cost falls by 13.97.

The comparison this collection would refuse to make is a factor against a percentage without saying what the percentage is of, and without saying that one of them is paid once and the other is paid per query. Both are here.

Why the cost is near zero on a uniform alphabet #

The plate’s flat line is exactly zero on the first two alphabets, and that is not a rounding.

On a uniform alphabet, Huffman’s construction produces a balanced tree — every symbol equally frequent means every merge is between equal weights — and a balanced tree’s leaves can be put in alphabet order without changing a single code length. The ordered optimum is the unconstrained optimum, and the constraint costs nothing.

The cost appears exactly where the distribution is skewed, which is where Huffman’s tree is worth having in the first place. So the trade is not “sometimes free and sometimes expensive”: it is free precisely where the alternative was worthless, and it costs a few per cent precisely where the alternative was worth a quarter.

That is a tidy shape and it is why the recommendation is unambiguous. Use an ordered tree. On a uniform alphabet nothing is lost; on a skewed one the cost is a few per cent of a tree and the operation is gained.

The workload that decides #

For completeness, the case where the trade is not worth taking.

An index built only for counting and locating — no approximate search, no bidirectional extension — pays the size and never performs the operation. On real text with a skewed alphabet that is three to five per cent of the tree for nothing.

Whether that matters is a question about the index rather than about this operation, and the answer is usually no: three per cent is inside the noise of choosing a block size for the rank directories. But it is a real cost and it is the reason “always use an ordered tree” is a recommendation about bidirectional indexes rather than about wavelet trees in general.

What this closes #

The bidirectional strand ended with a measurement and a deferral. The measurement: an extension is not one rank — 16.5 on four symbols, 138.6 on twenty-six. The deferral: the compound wavelet-tree operation that answers every child at once, which would take a bidirectional extension from σ ranks to about one, and is the single largest term in this slate’s search costs.

Both halves are now numbers. The operation takes an extension from 139.7 ranks to 10.0 on twenty-six symbols — not to one, because the walk is log σ deep, and the deferral’s “about one” was about symbol ranks rather than bit-vector ranks.

And the cost the deferral did not anticipate is the ordering constraint, which is the whole of the middle page in this strand: a Huffman-shaped tree cannot support the operation, the best ordered tree is a different construction, and it costs between nothing and five per cent.

Both numbers, on real text #

The plate above sweeps a generated alphabet, which is the right axis for showing that the factor is σ. The sizes on real text are the ones a system would pay, and they are larger.

Twelve real essays, 90 symbols: an ordered tree costs 4.95% more than Huffman’s.

Eight source modules, 104 symbols: 3.47%.

Ten revisions of one file, 79 symbols: 3.57%.

The reason real text costs more than the generated alphabets is the distribution. On a uniform alphabet Huffman’s tree is the balanced one and ordering is free; the more skewed the distribution, the more Huffman’s freedom to put rare symbols anywhere is worth, and the more the constraint costs.

So the honest headline for real text is a factor of fourteen for four per cent, and the four per cent is of the wavelet tree — about two per cent of an index, about two per cent of a bidirectional index.

What the depth column adds #

There is a third number on that plate and it changes the reading.

A fixed-length code is ordered — its leaves are in alphabet order by construction — so a system unwilling to compute an alphabetic code can have the compound operation for free by using a balanced tree.

It costs 27% in bits on generated English and 48% on real prose, against Huffman. And it costs in depth: 7.00 ranks an access against 4.49, which is 56% more work on every rank the index performs, including the ones inside the compound walk.

So the choice is not between Huffman and balanced. It is between three points, and the ordered optimum is close to Huffman on both axes while the balanced tree is far from it on both:

The middle row is the one to take, and the plate’s whole job is to make that visible in one look.

The two columns of the shape table are one measurement #

The three-row table is presented as two axes — bits and ranks an access — with the ordered tree described as close to Huffman on both. Divide the columns and they turn out not to be two axes at all.

547,650 ÷ 7.00 is 78,236. 369,940 ÷ 4.72 is 78,377. 352,475 ÷ 4.49 is 78,502. The same number, three times, which is the length of the text: a wavelet tree’s size in bits is the text length times the mean code depth, because every character contributes one bit at every level its code passes through. Bits and mean access depth are one quantity in two units, up to the rank directories that account for the fractional differences.

So the percentages are the same percentages. The ordered tree is 4.96% larger than Huffman’s and 5.12% deeper; the fixed-length tree is 48.0% larger and 48.3% deeper. Not two costs that happen to move together — one cost, reported twice.

That simplifies the recommendation and sharpens the case against the shortcut.

Simplifies, because the trade has one number on the cost side rather than two. The ordering constraint costs five per cent of the tree, which is five per cent of every rank the index performs, and it buys a factor of fourteen on the extension term. There is nothing to weigh against anything.

Sharpens, because the fixed-length tree looks much worse once the identity is seen. Its 48% is easy to read as a size penalty paid once at build time, which for a structure held in memory for a long time is a defensible thing to accept. It is not paid once. It is 48% more bit-vector ranks on every operation the index ever performs — every backward-search step, every locate’s LF steps, and every level of the compound walk the constraint was adopted to enable. A system taking the fixed-length shortcut to get the operation for free is paying for it forty-eight per cent at a time, on the operation itself.

That last point is the one worth carrying, because it inverts the apparent bargain. The fixed-length tree is ordered by construction, so it supports the compound walk with no alphabetic-code machinery at all — and its walk is seven levels deep where the ordered optimum’s is 4.72. So the factor of fourteen becomes a factor of ten on that tree, and every other operation is half as fast again. The free route to the operation makes the operation worse.

Which leaves the three shapes ordered exactly as the essay concludes, for a reason it can now state in one currency: Huffman is cheapest and cannot support the operation; the ordered optimum is five per cent dearer on everything and can; the fixed-length tree is half as expensive again on everything and buys nothing the ordered one does not. The tree the operation insists on is where the middle row is constructed, and rank is the only thing it does is why the depth column is the operation count rather than a proxy for it.

What a system pays if it never searches approximately #

The case against, stated fairly.

An index used only for exact search — count and locate, no error budget, no bidirectional extension — performs no operation this strand accelerates. It pays 2 to 5% of its wavelet tree for an operation it never calls.

Whether that is worth avoiding depends on what else is being decided. It is smaller than the difference between two reasonable block sizes for the rank directories, smaller than the difference between two sampling rates, and far smaller than the difference between a Huffman-shaped tree and a balanced one. In a table of index-size decisions it is near the bottom.

But it is not nothing, and the honest recommendation is conditional: build the ordered tree if the index will ever be searched bidirectionally. Which, for an index built to support approximate matching, it will.

What is left to measure #

The two savings together. This strand removes a factor of σ from the extensions; the half-index strand removes a sixth of the structure and spends it on a five-fold faster locate. Both apply to the same object, both were measured separately, and a search performing thousands of extensions and returning hundreds of occurrences pays both costs. Nothing here measures the combination, and the combination is what a real query is.

The compound operation over an interval’s distinct symbols, which would let a search branch enumerate only the symbols that actually occur rather than all σ of them — removing dead branches rather than making them cheaper. That is a bigger result than this one if it holds, and it is a different traversal.

And the same trade on a compressed vector representation, where a rank costs more and the tree costs less, so both columns of the trade move by amounts nothing here computes.

Where this sits in the strand #

Four pages. Every child at once is the operation; the count that was already there is why it is free rather than cheap; the tree the operation insists on is the ordering constraint and what the best ordered tree costs; this one puts both currencies on one plate.

The measurement that started it is in an interval that grows at both ends, which found that an extension is not one rank, and the structure it applies to is the one the search that starts in the middle is about.

What a factor of fourteen is not #

Worth one more pass, because the number is large enough to be misread.

It is not a factor of fourteen on a query. A query is a search plus a locate, and the locate is untouched — the saving, spent is the strand that addresses that half, and on a pattern returning many occurrences the locate dominates.

It is not a factor of fourteen on every search. A plain backward search performs no bidirectional extension and gains nothing at all.

And it is not a factor of fourteen at every alphabet. It is 2.14 at two symbols, 3.03 at four, and the collections this field is actually about — DNA at four symbols, protein at twenty, text at a hundred — span the whole range.

What it is: a factor of σ removed from one of the three terms in an approximate search’s cost, on an index that already exists, for a few per cent of the wavelet tree.

The arithmetic a reader can redo #

Every number on this page comes from two functions and a counter, and it is worth saying what they are so that the result is reproducible rather than merely reported.

The operation count: build a bidirectional index over a planted text, run a covering search scheme for two errors, and read the bit-vector rank counter before and after. Do it twice — once with an index whose extension loops over the smaller symbols, once with an index whose extension takes one compound walk — and divide. Both indexes are the same class with one method overridden, so nothing else can differ.

The size: build a wavelet tree over the same text three ways, and read each one’s own size accounting. The three differ only in their code lengths; the vectors, the directories and the shape table are computed identically.

Both halves are then checked rather than trusted. The two searches must return the same rows, at every alphabet; the ordered tree must be at least as large as Huffman’s and no larger than a fixed-length code; and the saving must grow with the alphabet, since the thing being removed is σ. A run where any of those failed would mean the plate is drawing something other than what its caption says.

That is the whole method, and it is short enough that the interesting part of the page is the trade rather than the measurement.

The two indexes differ in one overridden method and nothing else, which is what makes the comparison a comparison rather than two implementations being raced.

A note on what the plate cannot show, since it is the one thing a reader has to supply: how many extensions a query performs against how many occurrences it returns. That ratio decides whether this strand’s factor or the neighbouring strand’s is the one a workload feels, and it is a property of the patterns being searched rather than of either structure.