Wavelet tree — where it appears
Named by 37 essays across 9 fields — each of them below, with the objects they name alongside it.
A search that runs backwards
Twenty-three occurrences of a six-character pattern in sixteen thousand characters, found in twelve rank queries and zero character comparisons. Not few comparisons — none. The algorithm never asks whether two symbols are equal, and it knows how many matches there are before it has located one.
The index that is smaller than the text
The Burrows–Wheeler transform is a permutation, so it changes no symbol frequency and a plain index over it is the same size whether the text has deep structure or none — 6.29 bits a character against 6.16, on texts whose third-order entropies differ fourfold. What the transform changed was the runs, and a structure that charges one bit per bit cannot see a run.
The index that stores the runs
A compressed self-index over thirty-two copies of a text is 30,557 bits, because its size follows an entropy that cannot see a copy. An index that stores the transform as its runs is 11,900 — and at a single copy it is the larger of the two, which is what makes the comparison a claim about repetition rather than about size.
Rank is the only thing it does
Constant time and o(n) extra space — a phrase true of a rank directory costing 163% overhead and reading three words, and equally true of one costing 3% and reading eighteen. Both numbers are decided by two integers somebody typed into a header, and the phrase names neither.
Work that falls as the answer grows
Output-sensitive usually means the cost rises with the answer instead of with the input. A descent over a document array costs five operations per document at an answer of seven and two at an answer of thirty-two, because the paths to many leaves share their tops.
Proportional to the answer, not the alphabet
At a fixed alphabet of thirty-two, a loop costs three hundred and twenty ranks whether one symbol is present or all of them. The descent costs ten and sixty-two. The experiment has to move the answer without moving the alphabet, and the obvious sweep moves both.
The structure paid for before the first query
The two grids that make a phrase index's search proportional to its answer are 3,240 bits on an 8,892-bit index — twenty-seven per cent of the whole structure, answering nothing on their own, and 38% of them is rank directory rather than payload — the lower-order term of the published bound, measured.
An interval that grows at both ends
A backward search step is two ranks. A bidirectional step is two ranks and the width of the interval for every symbol that sorts before the one being added — 16.5 ranks on four symbols and 138.6 on twenty-six, which is a cost no account of the structure mentions.
A block, a class and an offset
Replacing each block of a bit vector by how many ones it holds and which arrangement it is takes 7.6% off the grid. On a permutation with no structure at all it takes 2.6%, so five of the seven points are the data and two of them are the encoding.
One separator, or one for each
A shared separator costs one alphabet symbol and is free. Fifteen distinct ones take the alphabet from twenty-two to thirty-five, which crosses a power of two, so every character of every document costs a sixth bit — 1.2 times the packed collection, to tell the boundaries apart.
A rectangle over a permutation
Two orderings of one set of boundaries are two permutations, so a phrase index's intersection is a rectangle over a permutation grid — the one point set a wavelet tree stores exactly, at one bit per point per level and no coordinates at all.
A bit for every bit
A grid over 3,612 points is 43,344 bits of payload. The smallest any structure can be that distinguishes one permutation of 3,612 things from another is 37,485. There is 16% to play for, and the deferral that asked for a compressed grid assumed there was much more.
The runs a permutation does not leave
A run of length L costs 2⌊log₂ L⌋ + 1 bits and replaces L, so coding runs pays above a mean run of six. This grid's mean run is 2.34, chance gives 1.90, and coding its runs makes it 17.8% larger.
The array is the length distribution
The document array holds each document once per character it contributed, so its symbol distribution is the collection's length distribution exactly. On equal-length documents its entropy is log d and no coding saves anything.
The half that is never asked where
A bidirectional index is two indexes and one interval. One of them is asked for ranks several hundred times a search and for a position never — and the parts that answer "where" are two of the five it is made of.
The operations a candidate count leaves out
The grid examines 33 candidates where the scan examines 4,355 — a factor of 132. Counted in the operations each of them performs, the same query is 2,471 against 4,355, and the factor is 1.8.
An index that cannot locate
Take an FM-index, remove the sampled positions and the bit vector marking them, and refuse every request for a position. What is left still counts, still extends intervals, still runs a whole search — and is a third smaller.
Every child at once
A bidirectional extension counts the occurrences of every symbol smaller than the one being added, and this collection did it with one rank per symbol — 139.7 operations an extension on a twenty-six-letter alphabet. One walk down the tree gives the same number.
The count that was already there
A bit vector's rank of one is the position minus its rank of zero. Every walk down a wavelet tree computes one of them at every level, and this collection asked for the other separately for years.
The tree the operation insists on
The compound walk means "everything that went left is smaller", which is true only if the leaves are in the alphabet's order. Huffman's tree is the smallest and its leaves are in frequency order, so the operation that makes a bidirectional search affordable costs the shape that makes an index small.
A node costs two ranks
The left child's interval is the position minus the right child's. A descent that calls rank on both children returns exactly the same symbols at twice the cost, and nothing about the answer can see it.
The level where compression stops paying
Choosing the best coding for every level of the grid separately, rather than one for all twelve, saves 26 bits out of 47,668 — five hundredths of one per cent. The apparatus for choosing costs more than that to describe.
A factor of fourteen, for four per cent
The compound walk removes a factor of σ from every interval extension. It requires a tree whose leaves are in order, which costs between nothing and five per cent of the wavelet tree. Both numbers on one plate, and the trade is not close.
A code word is at least one bit
A wavelet tree of plain vectors reaches the entropy by its shape, and a Huffman code word cannot be shorter than one bit. On a collection whose document array has an entropy of 1.69 the tree costs 1.98, and the gap is a floor rather than an inefficiency.
Two at binary, five at twenty-six
The saving is a factor in the alphabet, so a two-symbol alphabet gets two. Approximate matching in this field is mostly done on DNA, which sits near the bottom of the list at 2.7.
The index that does not notice
Three compressed indexes over the same characters. One is flat at six and a half bits a character however many copies the collection holds; the other two fall by factors of five and six. At one copy the two that fall are the largest of the three.
The tree answers the question
The distinct documents in a range of rows are the distinct symbols of the document array in that range. A wavelet tree enumerates those in one descent, so the range minimum, the chain, the bitmap and the recursion all go at once.
The last array in the apparatus
The document-listing apparatus began as three arrays beside a suffix array. Two of them turned out to be machinery for reading the third, and both have gone. What is left is the document array, and it is the only one of the three that was information.
Asking about symbols that are not there
A search extends an interval by every character of the alphabet, and on a deep branch almost all of them produce an empty interval. That is a full rank walk whose entire result is the discovery that nothing was there.
The apparatus, three times smaller again
Eight hundred and thirty-nine thousand bits became two hundred and eighty-five thousand, and now a hundred and twenty thousand. The listing apparatus is fourteen per cent of what it was and holds one array, which is the only part of it that was ever information.
The smaller tree hands it back unsorted
A frequency-shaped tree is sixteen per cent smaller and returns its documents in code order. A balanced one is larger and returns them sorted. The trade is d log d comparisons against a saving, which is not close — until the answer is truncated.
A saving quoted without its collection
A check asking whether a compressed document array is smaller than the plain one passes on the rounding whenever the document count is not a power of two. It would report a saving of nothing as sixteen per cent, on a collection that has no redundancy at all.
The branches that find nothing
An approximate search over a twenty-symbol alphabet attempts sixteen thousand eight hundred extensions and nine thousand two hundred of them produce an empty interval. That is a full rank walk whose entire result is the discovery that nothing was there.
One set, three orders
The symbols an interval holds do not depend on the tree's shape. The order they come out in does, and a search that accumulates a running count as it reads them computes a plausible number that is wrong on eighty per cent of queries.
A walk that does not prune
Remove the emptiness test and the descent visits every node of the tree, returns exactly the same symbols with exactly the same intervals, and costs sixty per cent more. No test of the answer can see it.
Two factors that do not multiply
Eleven times and seventy-eight times against the same baseline, so an index with both should be eight hundred and sixty. It is seventy-eight, and the shortfall is eleven — the first factor, exactly, because the second operation already contains it.
The saving that is a loss
An operation that is seventy-eight times cheaper on a branching search costs twice as much on an exact one. It reports every symbol present in order to hand back the one that was asked for, and a search that knows its character needs none of the rest.
Named alongside it
The objects these essays reach for when they reach for this one.
Index sizeRankMeasurementBit vectorDescentInterval symbolsSelf-indexDocument arrayEntropyTrade offBidirectional indexBackward search