Every child at once

An interval extension in a bidirectional index needs one number that a plain backward search does not: the total width, inside the current interval, of the intervals belonging to every symbol that sorts before the one being added.

An interval that grows at both ends established why — in the mirrored index those extensions sit before this one, so the other interval’s start moves by their total. And it measured what that costs when it is done the obvious way: 16.5 ranks an extension on four symbols and 138.6 on twenty-six.

One walk down the tree returns the same number.

What the obvious way does #

A wavelet tree answers rank_c(i) — occurrences of symbol c before position i — by following c’s code word down a tree of bit vectors, one bit-vector rank per level. That is ⌈log₂ σ⌉ operations for a fixed-length code.

To get the smaller-symbol total, the loop asks for rank_d(i) for every d < c, and subtracts the same at the interval’s other end. So an extension costs 2σ walks of depth ⌈log₂ σ⌉ each, which is 2σ⌈log₂ σ⌉ bit-vector ranks — and that is where 139.7 comes from on a twenty-six-symbol alphabet.

The published accounts of bidirectional search do not mention it, because they count symbol ranks: an extension is “two ranks and a sum”, and the sum is over σ terms that are themselves ranks. The unit of cost is not one is the theme, and this is one of its sharpest instances in the collection.

What one walk does #

Follow c’s code, and keep a running total.

At each level the walk is at a position within a node’s bit vector. If the code says left, it takes rank₀ and moves on; everything that went right at this level is a larger symbol, and nothing is added.

If the code says right, it takes rank₁ and moves on — and everything that went left at this level is a smaller symbol, all of them, because the tree’s leaves are in the alphabet’s order. The number of them is the position minus the ones count, which is arithmetic on two numbers already in hand.

So the smaller-symbol total is the sum, over the levels where the code says right, of the zeros count at that level. And the walk that computes it is the same walk that computes the rank.

The count that costs nothing #

Not “costs less”: costs nothing. The operation count of rankAndLess is the operation count of rank, to the operation.

That is measured rather than argued: a counter records bit-vector ranks, a hundred calls of each are made on the same tree, and both report 500 operations — five per call, which is the depth of a twenty-one-symbol tree.

The reason is the arithmetic above. A rank₁ gives the ones before the position; the zeros are the position minus the ones; no second query is needed for the other child. The count that was already there is the page about why that is a property of bit vectors rather than an optimisation, and about the places in this collection where the same identity was available and not used.

What it is worth #

Measured on a search that finds a pattern within two substitutions under a covering scheme, on four alphabets:

Two symbols — 8.56 ranks an extension against 4.0. A factor of 2.14.

Four symbols — 18.19 against 6.0. A factor of 3.03.

Twenty symbols — 109.7 against 10.0. A factor of 10.97.

Twenty-six symbols — 139.7 against 10.0. A factor of 13.97.

The factor is σ⌈log₂ σ⌉ divided by ⌈log₂ σ⌉, which is σ — and the measured numbers are a little under it because the loop stops at c rather than running the whole alphabet, so on average it walks half of them.

Both structures find the same rows, at every alphabet, which is the check that makes the comparison a comparison.

Where it lands in a real search #

The extension count is what makes the factor matter. A search for a fifteen-character pattern within two errors, under the pigeonhole scheme, performs 1,614 extensions on a twenty-six-symbol alphabet.

At 139.7 ranks each that is 225,400 bit-vector operations. At 10.0 it is 16,140.

That is the single largest term in the cost of an approximate search on this structure, and it was a term nobody had written down — the strand that measured it called the compound operation the largest single term in this slate’s search costs and left it unbuilt.

The condition #

There is one, and it is the whole of the next two pages.

“Everything that went left is smaller” is a statement about the tree, not about the sequence. It holds when the leaves run left to right in the alphabet’s order — which is true of a fixed-length code, because the codes are assigned in alphabetical order by construction.

It is false of a Huffman-shaped tree. Huffman’s construction merges the two lightest weights wherever they are, so the leaves come out in frequency order, and a walk that adds up “everything to the left” adds up whatever happens to be there.

And it does not fail loudly. The walk runs, returns a number, and the number is a plausible-looking count that is wrong on 81% of queries — worst case 706 against a true 3,058 on twenty-one symbols. The tree the operation insists on is the page about what to do instead, and the answer costs a few per cent of the index.

Why this was not obvious #

Worth a paragraph, because the operation is three lines and had been named and not built.

The reason is that the two quantities look like different questions. rank_c(i) is how many c before here, and the smaller-symbol total is how many symbols below c before here — one is about a symbol and the other is about a set of symbols, and the natural way to answer a question about a set is to loop over it.

What collapses them is that a wavelet tree’s structure is a binary search over the alphabet: descending it is exactly narrowing the range of symbols under consideration, and at every step the discarded half is entirely above or entirely below. So the walk that finds c is also a walk that partitions the alphabet around c, and the partition’s sizes are the counts the loop was computing one symbol at a time.

That is the same observation that makes a wavelet tree answer range-quantile and range-counting queries, which this collection has not built. Seen that way the compound operation is not a trick — it is the tree being used for what it is.

What it does not change #

The size. The tree is the same tree; the operation reads it differently. What changes the size is the condition — an ordered tree is not the smallest tree — and that is a few per cent, measured on the page after next.

The search’s shape. Same extensions, same nodes, same pruning, same answers. The compound walk is a cheaper way to compute a number the search was already computing.

Or the asymptotics anybody quotes. A bidirectional search is O(m σ) per branch either way if σ is treated as a constant, and this operation removes exactly the factor that everybody agreed to treat as a constant. The constant is the content is the theme; twenty-six is the constant.

What the walk looks like on a real alphabet #

Worth following one descent all the way down, because the mechanism is easier to believe with numbers on it.

Take a wavelet tree over English text, twenty-one symbols, five levels deep, and ask for the symbol m at position 400. The code for m in an alphabetically-assigned fixed-length code is 01100.

Level 0, the code says left: take rank₀, and everything that went right is larger — nothing added. Level 1, the code says right: take rank₁, and everything that went left at this level is smaller — add the zeros count. Level 2, right again: add. Levels 3 and 4, left: nothing added.

Five bit-vector ranks, two of them contributing to the running total, and the total is the number of characters before position 400 that sort before m. A loop over the twenty symbols below m would have made a hundred ranks to get the same number.

The plate draws that descent with the interval narrowing at each level and the contribution beside it, which is the clearest way this collection has found to show that the second quantity is a by-product rather than a second computation.

Where the extensions come from #

The factor is worth having only because the operation is performed so often, and it is worth being specific about why an approximate search performs thousands of extensions.

A search under a scheme cuts the pattern into k + 1 pieces and walks them in a stated order with an error bound per piece. At each character of each piece, the search tries every symbol of the alphabet — the matching one at no cost, the others at the cost of one error — and each attempt is an interval extension.

So the branching factor is σ and the depth is m, pruned hard by the error bounds. On a twenty-six-symbol alphabet with a fifteen-character pattern and two errors, the pigeonhole scheme explores 1,614 extensions; on four symbols it is 498, because the branching is smaller.

That is the multiplier the per-extension cost is multiplied by, and the two both grow with σ — which is why the total cost of an approximate search grows as σ² under the loop and as σ log σ under the walk.

What a published account counts #

The gap between 139.7 and 10.0 lives entirely inside a phrase.

A published description of a bidirectional extension says: two rank queries, plus the total width of the intervals of all smaller symbols. Counted as symbol ranks that is σ + 2, and counted as bit-vector ranks it is (σ + 2)⌈log₂ σ⌉ — and the second is what a machine performs.

This collection counts both, because they are the two units this field slides between: the unit of cost is not one is the theme, and it has already produced two other instances. A comparison of two strings is not one comparison — it is a character comparison per character until they differ. A cache miss is not one access.

Both units are on the operation counter here, and every plate says which one it is drawing. The published bound is not wrong in its own unit; it is that the unit hides a factor of five on English and a factor of five is what an implementation feels.

Both columns, closed form #

The four measured pairs are close enough to arithmetic that the arithmetic is worth writing down, because it explains a feature of the table that otherwise looks like a coincidence: twenty symbols and twenty-six cost the walk exactly the same 10.0.

The alphabet carries a sentinel, so a tree over $\sigma$ text symbols has $\sigma + 1$ leaves and depth $\lceil\log_2(\sigma+1)\rceil$. An extension walks both ends of the interval, so

$$\text{walk} \;=\; 2\lceil\log_2(\sigma+1)\rceil$$

which is 4, 6, 10 and 10 at two, four, twenty and twenty-six symbols — every measured value, to the operation. Twenty-one leaves and twenty-seven leaves both need five levels, and five levels is the entire cost.

The loop makes one descent per symbol below $c$, at both ends, and $c$ averages the middle of the alphabet, so

$$\text{loop} \;\approx\; (\sigma+1)\lceil\log_2(\sigma+1)\rceil$$

giving 6, 15, 105 and 135 against the measured 8.56, 18.19, 109.7 and 139.7 — within a few per cent everywhere, the residual being that the symbols a real search asks for are not drawn uniformly from the alphabet.

Two things follow that the table alone does not say.

The absolute cost is a staircase and the alphabet’s position on it matters. Both columns carry the same $\lceil\log_2(\sigma+1)\rceil$, so both are flat between powers of two and step together. An alphabet of thirty-one symbols costs an extension 10 operations and one of thirty-two costs 12 — a fifth more work for a three per cent larger alphabet — and a text that could be coded into thirty-one symbols rather than thirty-two is buying a real thing. That is the same step function documents that are not the same length finds deciding a separator’s cost, arriving here in the query rather than in the size.

And the ratio has no staircase at all, because the depth cancels. Dividing the two expressions leaves

$$\frac{\sigma+1}{2},$$

which is 1.5, 2.5, 10.5 and 13.5 against the measured 2.14, 3.03, 10.97 and 13.97. So the saving is half the alphabet, not the alphabet — the factor of two from the loop stopping at $c$ is not a small correction to be waved at, it is half the headline, and it is the whole difference between “a factor of twenty-six” and the 13.97 the measurement reports.

That is worth being exact about precisely because the number is the essay’s result. The constant is the content cuts both ways: a factor quoted as $\sigma$ when it is $\sigma/2$ is the same species of error as a bound quoted in symbol ranks when the machine performs bit-vector ranks, and rank is the only thing it does is where this collection fixed the unit that makes either statement checkable.

What is deferred #

The compound operation on every child at once, rather than on one path. What this page builds returns the rank of one symbol and the total below it. A fuller version — the one published accounts call interval_symbols — returns, in one traversal, every distinct symbol present in an interval with its rank at both ends, at a cost proportional to the number of distinct symbols rather than to σ. That is the operation an approximate search would really want, because it would let a branch enumerate only the symbols that actually occur beneath it, and the dead branches on the plate above would never be taken.

And the same operation on a compressed vector. Every measurement here uses plain bit vectors. On an entropy-compressed representation a rank costs more and the tree is smaller, so the factor this page reports would move — in which direction is not obvious, and it is a measurement rather than an argument.

Where this sits in the strand #

Four pages. This one is the operation. The count that was already there is why it costs nothing extra, measured on a counter. The tree the operation insists on is the ordering constraint and the price of satisfying it — an optimal alphabetic code, computed by dynamic programming, three to five per cent above Huffman’s on real text. A factor of fourteen, for four per cent is both currencies on one plate.

The measurement that named the deferral is in an interval that grows at both ends, and the structure it applies to — a bidirectional index whose reverse half is asked only for ranks — is being taken apart from a different direction in the half that is never asked where. The two strands are about the same object and they do not interact: one removes a factor from the extensions and the other removes a sixth of the bits.

What the operation is called elsewhere #

Worth naming, because this collection is not the first to want it and the published name is useful for anybody reading further.

An operation returning, for one interval of a wavelet tree, the counts of every symbol present — together with their ranks at both ends — is usually called interval_symbols, and it is the general form of what this page builds. The version here is narrower: it returns one symbol’s rank and the total count below it, which is what a bidirectional extension needs and is one path rather than a traversal.

The narrow version costs a descent. The general version costs a traversal of every node the interval touches, which is O(d log(σ/d)) for d distinct symbols — cheaper than σ when the interval is small, which is exactly when a search’s branches are deep.

So the general operation would remove the dead branches rather than making them cheaper, and on the plate of nodes explored per scheme that is a larger result than this one. It is named here and not built, which is this collection’s standing convention for a structure it prices without implementing.

The reason the narrow version came first is that it is three lines and needed no new traversal — the walk was already there, and the count was already computed.