The tree answers the question

The document array has been compressed into a wavelet tree because a wavelet tree of the right shape costs the entropy of the sequence. That was the size argument, and the size argument is the smaller half of what the representation is worth.

Here is the other half. The distinct documents in the rows [lo, hi) are the distinct symbols of the document array in [lo, hi). That is not an analogy; it is the same set, written twice.

And a wavelet tree enumerates the distinct symbols of an interval in one descent, at a cost proportional to how many there are. Asking about symbols that are not there is the operation: descend from the root carrying the interval, split it at each node by one pair of ranks, enter a child only if its half is non-empty, and report a symbol at each leaf reached.

So the range minimum goes, the chain stays gone, the answer-so-far bitmap goes, and the recursion over subranges goes. The apparatus is the compressed document array and one descent over it.

The four methods on one query #

The pattern occurs twenty-eight times across fifty-four rows, in eight documents.

Reading every occurrence and putting the documents in a set costs fifty-four operations — the rows. It holds only the document array.

The published range-minimum walk costs two hundred and sixty-seven operations inside the structure. It holds the document array, the previous-occurrence chain and a range minimum over the chain. Two hundred and sixty-seven is five times what reading every row cost, for an answer of eight, which is the constant the cost that is the size of the answer drew the crossing from.

Removing the chain — a document already in the answer — brings it to eighty-three, holding a range minimum and one bit per document.

The descent costs thirty-two, holding the document array in a tree and nothing else.

All four report the same eight documents, and the check is on the documents rather than on their number, because the descent produces them in a different order and a comparison of counts would hide a shape mistake.

The four rows are also a history, and reading them in order says something the individual essays did not. Every step of this strand made the apparatus smaller, and only the last step made it faster than reading every row. Three earlier essays reported improvements — a chain removed, a range structure made succinct, a factor of three on the whole apparatus — and at the end of all of them the method still cost more operations than the thing it was supposed to be an improvement on.

That is not a criticism of the earlier steps; asymptotic behaviour is worth having and a constant that is five can become a constant that is one. It is a warning about how such a strand reads from inside. Each essay measured a genuine gain against the previous structure, and none of them measured the structure against the alternative it was competing with, because the alternative had been dismissed in the first essay on asymptotic grounds.

Why the descent is the smallest as well as the fewest #

Two things are happening at once and they are worth separating because they have different reasons.

The structure is smallest because it holds one array and the others hold two or three. On sixty-four documents of two hundred and fifty-six characters the published apparatus is 838,797 bits, the chainless one 285,460, and the descent 119,972 — 14.3% and 42.0% respectively.

The work is smallest for an unrelated reason: the descent’s cost is the ancestors of the leaves present, and the ancestors of k leaves in a tree of depth log d number about k log(d/k) rather than k log d, because the paths overlap near the root. A range-minimum walk gets no such discount: each reported document costs a full query.

That second point is what makes the work per document fall as the answer grows, which is a property none of the other three methods has. At one document holding the pattern the descent costs 5.14 operations per document; at thirty-two it costs 1.94.

What “output-sensitive” turns out to mean here #

The strand’s whole claim has been that the apparatus’s cost follows the answer rather than the range. The descent satisfies that in a stronger form than the methods it replaces.

Reading every occurrence follows the range: 17 operations at an answer of 7 and 324 at an answer of 32, while the range went from 17 rows to 324. Exactly the range, because that is what it reads.

The range-minimum walk follows the answer with a logarithmic factor and a large constant: 154 to 886.

The descent goes 36 to 62 while the answer goes from 7 to 32 and the range from 17 to 324. It is sublinear in the answer, because of the ancestor overlap, and completely insensitive to the range.

That is a better shape than the method it replaces and it arrived as a side effect of a size decision. Nothing about compressing the document array was aimed at the query.

There is a bound worth writing for the descent’s work because it is unusually clean. A binary tree with d leaves, of which k are marked, has at most k(1 + log₂(d/k)) marked ancestors — a standard counting argument, and tight when the marked leaves are spread evenly. At d = 32 and k = 8 that is 8 × 3 = 24 nodes; the measured figure for a comparable query is in that neighbourhood.

Two ranks a node gives 2k(1 + log₂(d/k)) bit-vector operations, which at k = d degenerates to 2d — every node of the tree — and at k = 1 is 2 log d, one root-to-leaf path. Both ends behave sensibly and the middle is where the discount lives.

The comparison worth making is against σ separate rank queries, which is what a loop over the documents would cost: d log d operations, or 160 at d = 32, against the descent’s 24 for eight documents. The ratio is the whole of what the operation buys and it is measured across alphabets in asking about symbols that are not there.

Why nothing was left to remove #

The three removals in this apparatus each had a different reason, and this one’s is the most general of the three.

The chain went because a traversal order made its test answerable from the answer so far. That is specific to this problem.

The range minimum got smaller because a succinct representation held the same information in fewer bits. That is a general technique applied to a specific structure.

The range minimum goes entirely because a structure already present answers its question. That is the most general move of the three and it required nothing new to be built: the wavelet tree was already there for the size, and the operation it supports was already defined.

What made it invisible for as long as it was is that the two things were described in different vocabularies. “Find the distinct documents in a row range” and “enumerate the distinct symbols of an interval” are the same sentence in two dialects, and the second one lives in a paper about wavelet trees while the first lives in a paper about document listing.

There is a fourth question the habit above does not cover and it is the one that has not been asked here: whether the problem could be posed differently so that no array is needed. An inverted index over documents answers “which documents contain this pattern” without a suffix array, a document array or any of this — at the cost of only answering it for indexed terms rather than for arbitrary substrings. That is a different design with different costs and it is not compared here, which is the honest boundary of everything above.

The one thing the descent needs and the walk did not #

A range-minimum walk over a chain does not care what order it visits subranges in — a document already in the answer established that the chainless version does and the chained version does not.

The descent does not care about order either, but it does care about something the walk was indifferent to: it returns its symbols in the tree’s leaf order, which is the alphabet’s order only if the code is order-preserving. A Huffman-shaped tree puts its leaves in frequency order, so the documents come back unsorted.

For a set that is fine. For a caller that wants them sorted it is d log d comparisons on an answer of size d, which is nothing against a walk that cost more than that. The smaller tree hands it back unsorted is where that trade is priced, and it is the one remaining choice in this apparatus.

The failure mode is worth naming because it is silent. A caller that reads the descent’s output as sorted — reporting the first k, merging two lists, binary-searching — gets a wrong answer that every count agrees with. It is the same shape as the defect the tree the operation insists on found one strand ago in a different operation, where reading a Huffman tree’s leaf order as the alphabet’s produced a plausible number wrong on 81% of queries.

The arithmetic that makes a node cheap #

One detail decides whether the descent is worth anything and it is easy to get wrong.

At each node the interval splits into the positions whose bit is zero and the positions whose bit is one. The right child’s interval is [rank₁(lo), rank₁(hi)) and the left child’s is [lo − rank₁(lo), hi − rank₁(hi)). So both children come from two bit-vector ranks rather than four, because rank₀(x) is x − rank₁(x).

A version calling rank₀ separately costs twice as much and produces exactly the same answer. Nothing about the output can see it and the operation count must.

That is checked directly: the ranks a descent spends must equal twice the internal nodes it entered, exactly, and a mismatch is a defect. It is the kind of claim that would otherwise be a comment.

There is an interaction between the shape and the descent’s cost that is worth noticing, because it cuts the other way from the size argument. A Huffman-shaped tree is shallower for frequent symbols and deeper for rare ones. The documents holding a pattern are not drawn from the length distribution — a pattern is as likely to be in a short document as a long one, roughly — so the descent’s leaves are a uniform sample of the documents while the tree’s depths are frequency-weighted.

That means the descent on a Huffman tree visits, on average, deeper leaves than a balanced tree would, and its operation count is slightly higher. Measured on the one-over-rank collection: twenty-four operations on the Huffman tree against twenty-six on the balanced one for the same query — which is the opposite direction, because the frequent document is in the answer and its short code saves more than the rare ones’ long codes cost. On a query whose documents are all rare the ordering reverses.

So the shape’s effect on the query is small and not signed, and the choice remains what the size and the order say it is.

Where the crossing is now #

The strand has been moving a crossing rather than crossing it, and this is the first step that puts the method below the naive alternative.

The crossing that never arrives measured the published apparatus against reading every occurrence and found the crossing at 10.8 occurrences a document, against a measured 1.04 on the collection in hand. The method lost by a factor of two and a half.

On the query above, the descent costs thirty-two operations against reading every occurrence’s fifty-four, at a density of 3.5 occurrences a document. So the crossing has moved below 3.5 — the first time in this strand’s history that the apparatus is cheaper than the naive method at a density a real collection has.

Whether it is below 1.87, which is the density one copy per document is one occurrence per document measures on every collection shape available here, is the open question. At a density of one the descent visits one leaf and its ancestors, which is log d operations against one row read — so the naive method wins at the very bottom, and the crossing is somewhere between one and three and a half.

Two things would move that crossing further and neither is measured here. A compressed-block representation of the levels makes the array smaller and each rank more expensive, so it moves the size down and the crossing up. And a descent that stops early — reporting the first k documents rather than all of them — would make the cost proportional to k rather than to the answer, which is a genuinely output-sensitive listing in the strongest sense and which the range-minimum walk also supports.

That second one is the more interesting and it is where a real system would start. A search interface showing ten results does not want all four hundred documents; it wants ten. A descent that visits leaves in an order and stops gives that, and its cost is then the ancestors of ten leaves rather than of four hundred.

The habit, three times #

The three removals share a habit even though they do not share a technique, and it is worth stating as an instruction.

When a structure holds an array whose entries are derived from another array it holds, ask what question the derived array answers, and then ask three things: whether the traversal order already answers it, whether a better representation of the same information is available, and whether a neighbouring structure answers it as a side effect.

Three times out of three in this apparatus one of those was yes. The third — a neighbouring structure — is the one that removed the most, and it is the one that required no new idea at all: the neighbouring structure had been added for a different reason and its published operation set already contained the answer.

The two vocabularies #

The most instructive part of this result is how long it stayed unavailable, and the reason is worth writing down because it is not about anybody being slow.

Document listing is a problem posed over a suffix array: given a row range, report the distinct documents. Its literature is about chains, range minima, and the tricks that make a walk output-sensitive.

Interval symbols is an operation on a wavelet tree: given a position range, report the distinct symbols. Its literature is about sequence representations, ranks and selects, and what a hierarchical decomposition of an alphabet supports.

They are the same problem. A document array is a sequence; a row range is a position range; a distinct document is a distinct symbol. Every word in the first sentence has a synonym in the second, and none of them is spelled the same way.

That is a translation failure rather than a conceptual one, and this collection has hit it before. The count that was already there found a quantity a bidirectional search had been computing with σ separate ranks sitting inside a walk it was already performing — the same shape, one strand ago, on a different pair of vocabularies.

The instruction that comes out is not “read more widely”. It is narrower and more usable: when a structure is added for one reason, read its published operation set against the problems already in hand. A wavelet tree was added here to compress an array. Its operation set contains an answer to a question a separate structure had been built for, and nothing about the compression suggested looking.

What this leaves #

The apparatus is one array in one tree and one descent. There is no derived structure left to remove and no machinery left to represent better.

What remains open is the choice of shape, which trades sixteen per cent of the array against an ordered answer; the floor a plain-vector tree cannot get under, which decides whether a compressed vector is worth its directory; and the crossing, which decides whether any of it beats reading every row on the collections that actually exist.

None of those is a structure. The strand has run out of things to delete, which is what the end of a line of this kind looks like.