Algorithms & Data Structures
the bound is a claim, and it is checkable
The index that replaces the text

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.
21 min read 9 figures An index has a sizeThe unit of cost is not oneMeasured, not assumedThe structure decides the count

A bound that has to be paid for ended with a structure and a complaint. The structure was a lower bound that removes seventy per cent of an index walk’s search tree; the complaint was that computing it needs an index of the reversed text, which is the same size as the index being walked — so the structure whose small size is the whole argument for walking it doubles.

The essay named what would fix it: a bidirectional index, in which the bound and the walk share one object. This is that index, and the next essay is why the fix does not fix what it was named to fix.

One substring, grown from each endThe same 7-character string built two ways: leftwards, one character at a time from its last, and rightwards from its first. At every step both the forward interval and the interval in the index of the reversed text are held, and the two are always the same width — they are the same occurrences counted twice, and the assertion that they are is what catches every off-by-one this structure can have. The widths fall from 1,047 to 1 either way, and the final interval is the same four numbers by either route. What the second index buys is not space: it is the freedom to add the next character at whichever end the search wants.1234567characters addedoccurrencesgrown leftwardsgrown rightwards"tgatatt"4,000 characters · four symbols1 occurrences
Fig. 1 The same seven-character string built two ways — leftwards from its last character and rightwards from its first — with both intervals held throughout.

What a search interval is, and what it cannot do

A search that runs backwards is where the machinery comes from. A backward search holds a pair of row numbers — the rows of a suffix array whose suffixes begin with the pattern so far — and narrows them one character at a time, from the back of the pattern.

Each step is two rank queries. To prepend character c to a pattern whose rows are [sp, ep), the new rows are C[c] + rank(c, sp) and C[c] + rank(c, ep), where C[c] is how many characters of the text sort before c. It performs no character comparison at all, which is the property the field is named for.

The direction is not a choice. The transform the index is built on puts the character preceding each row’s suffix in its last column, so a rank on that column answers “which rows begin with c followed by what these rows begin with”. There is no column answering the mirror question, and no amount of care makes one appear.

So a search that has matched the middle of a pattern and wants to extend rightwards cannot. It has to start over from the right end, and everything it learned is thrown away.

Two indexes, one interval

The fix is the obvious one and the interesting part is what it costs. Build a second index over the text read backwards. A rightward extension in the text is a leftward extension in the reversal, so the second index answers what the first cannot.

The two indexes have unrelated row numberings, so a search cannot simply switch between them: matching three characters in one leaves the other knowing nothing. What makes the structure work is that both intervals are maintained at every step, so at any moment the search holds the rows of its pattern in the forward index and the rows of its reversed pattern in the reverse index — and either can be extended next.

The two are always the same width, because they are the same occurrences counted twice. That single invariant is what catches every off-by-one this structure can have, and it is asserted rather than assumed.

One substring, grown from each endThe same 8-character string built two ways: leftwards, one character at a time from its last, and rightwards from its first. At every step both the forward interval and the interval in the index of the reversed text are held, and the two are always the same width — they are the same occurrences counted twice, and the assertion that they are is what catches every off-by-one this structure can have. The widths fall from 138 to 1 either way, and the final interval is the same four numbers by either route. What the second index buys is not space: it is the freedom to add the next character at whichever end the search wants.12345678characters addedoccurrencesgrown leftwardsgrown rightwards"vaakcfuj"4,000 characters · twenty-six symbols1 occurrences
Fig. 2 The same construction over a twenty-six-symbol alphabet, where the intervals narrow far faster. The two routes reach the same four numbers.

The step nobody writes down

Here is the part that is stated in one clause in most descriptions and turns out to be most of the cost.

Extending on the left is an ordinary backward-search step in the forward index: two ranks, as above. The reverse interval then has to move too, and where it moves to is not something a rank on the reverse index can say, because the reverse index has not been told about this character yet.

It moves by counting. In the reverse index the rows for a pattern P are grouped by the character that could be prepended to them in the reversed text — which is the character appended in the forward text — and those groups sit in alphabetical order. So extending the forward pattern to cP shifts the reverse interval’s start by the total width of the intervals for every symbol d that sorts before c.

Computing that total means asking, for each such d, how wide the forward interval for dP is. Each of those is two more ranks.

An extension therefore costs about 2σ ranks, not 2. Measured on the same pattern against three alphabets: 16.5 ranks an extension on four symbols, and 138.6 on twenty-six — a factor of 8.4 for a factor of 6.5 in the alphabet.

An extension is not one rankA 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, because that total is how far the other interval's start moves — so an extension costs about 2σ ranks rather than 2. Measured on the same pattern against three alphabets: 10.3 ranks an extension at 3 symbols and 141.6 at 27, of which 18% are spent on the smaller symbols alone. A wavelet tree asked for all its children at once would answer them together; that is a different operation from the one this collection has been counting, and it is not built here.050100150510152025symbols in the alphabetranks an extension10.316.8141.6two symbolsfour symbolstwenty-six symbols15 characters · k = 214x apart
Fig. 3 Ranks an extension, against the size of the alphabet. Two of them are the extension itself; the rest are spent working out where the other interval’s start moved to.

The operation that would fix it, and why it is not here

A wavelet tree can be asked for all of a node’s children at once — a single descent that returns the counts for every symbol rather than one symbol’s count — and that operation answers the whole of the smaller-symbols total in the work of about one rank.

It is a real operation and every serious implementation uses it. It is not built here, for the reason the operations a candidate count leaves out gives about a different structure: a comparison must state what one act is on each side, and this collection has been counting ranks since the index field opened. Introducing a compound operation that costs “about one rank” and answers σ of them would put a number on the plate that no earlier number in this collection can be compared with.

So what is measured is what this structure does, and what it does is σ ranks. The consequence is stated rather than hidden: every node count in this strand is an honest count of a tree, and every rank count is an upper bound on what an implementation with that operation would spend. The trees are what the strand is about.

What the second index costs

Two indexes over the same text are the same size, to the bit: the reversal has the same symbols in the opposite order, so its transform has the same alphabet, the same frequencies and — as it happens here — the same number of runs.

Over eight thousand characters that is 35,335 bits each and 70,670 together, exactly twice one index. In bits a character: 8.63 against 4.31.

Nothing was halvedA bidirectional index is an index of the text and an index of the reversed text, held together. Over 8,192 characters that is 35,335 bits and 35,335 — the same size to within a bit, because the two texts have the same symbols in the opposite order — for a total of 70,670, exactly 2.00x one index. The strand that named this structure hoped it would let the pruning bound and the walk share one object and stop the index doubling. It does let them share one object. The object holds both transforms, so the doubling is not removed; it is reused.one index35,3354.31 bits/charthe forward half35,3354.31 bits/charthe reverse half35,3354.31 bits/charboth, which is the structure70,6708.63 bits/charbits8,192 characters · sample 322.00x one index
Fig. 4 One index, its two halves, and the structure. The ratio is exactly two and the two halves agree to within a bit.

There is no version of this structure that is not two indexes. A bidirectional search needs to extend in two directions and each direction needs its own transform; a single transform answers one of them. That is the whole content of the next essay, and it is why the deferral that named this structure was answered by building it and then reporting that the thing it was named for does not happen.

What it buys instead

Not space. Order.

A search that can add a character at either end is a search that can choose where to start, and choosing where to start is worth a great deal when errors are allowed. The branch that cannot reach an answer measured a walk with an error budget multiplying its tree by ten per error; the way to fight that is to spend the early characters — the ones near the root of the tree, where a branch is most expensive — under the tightest possible constraint.

The tightest constraint available is no errors at all, and a pattern cut into k + 1 pieces has at least one error-free piece by the pigeonhole. A unidirectional search cannot use that: it must begin at one end, and the error-free piece is somewhere in the middle. A bidirectional search can begin at the middle piece, insist on matching it exactly, and grow outwards.

The search that starts in the middle is what that is worth, and the number is a factor of 2.7 on the size of the tree.

The same occurrences, at four sizes of treeA pattern of 15 characters within 2 substitutions, over 4,000 characters of four symbols. All four schemes found the same 6 positions — that is checked against comparing the pattern at every position — and they walked 830, 877, 447 and 303 interval extensions to do it. The gap between the first and the last is 2.74x, and it comes from one thing: a search that begins at a piece it insists is exact spends nothing on the errors that piece cannot have.right to left8302.74xleft to right8772.89xone per piece4471.48xthe scheme3031.00xinterval extensionsall four found the same 6 positions15 characters · k = 22.74x apart
Fig. 5 What the choice is worth. Four ways of consuming the same pattern, all finding the same six positions, at four sizes of tree.

The invariant, and what checks it

The two halves of an interval are the same occurrences counted twice, so they must have the same width at every step. That is asserted directly: a substring is grown leftwards from its last character and rightwards from its first, and the two routes are required to produce the same four numbers — not merely the same width.

It is worth saying why the check is written that way. A defect in the reverse half is invisible to a search that only ever extends leftwards, because such a search never reads the reverse interval. It is nearly invisible to a search that does, because a covering scheme is redundant: the occurrences one search loses another search finds.

Measured, with the reverse interval’s start deliberately left where it was: the in-step check fails on all thirty-nine substrings it examines, and the scheme’s answer does not change at all — eight positions found either way. A test written against the output would pass.

Every way the errors can fall, and which search takes itWith 2 errors over 3 pieces there are exactly 10 ways the errors can be distributed, counting the ones that use fewer than the whole budget. A scheme is valid when every row has at least one search against it, and that is a finite check rather than an argument — which is how the 3 searches here were chosen, by enumerating every order whose prefixes are contiguous against every pair of bound vectors and keeping a covering set. 0 of the 10 rows are covered twice, and that redundancy is what makes a defect in one search invisible in the answer: the other search hands the occurrences back.errors, by piecetaken by(0, 0, 0)1(0, 0, 1)1(0, 0, 2)1(0, 1, 0)1(0, 1, 1)1(0, 2, 0)3(1, 0, 0)2(1, 0, 1)2(1, 1, 0)3(2, 0, 0)30 of 10 covered more than once · the numbers are the searchesk = 2 · 3 pieces10 distributions
Fig. 6 Why the output cannot be the test. Several distributions of the errors are covered by two searches, so a search that loses occurrences has them handed back by another.

The alphabet, cutting both ways

A larger alphabet makes an extension dearer — that is the σ ranks — and it also makes intervals empty sooner, so the tree of a search with errors has fewer live branches.

Which effect wins is a measurement, not an argument, and it is the same question the branches an error opens asked of the unidirectional walk. Here: 625 extensions on two symbols, 772 on four, and 4,560 on twenty-six, for the plain right-to-left search. The tree grows with the alphabet, so the branching wins — but the ranks grow faster than the tree does, because each extension is dearer, and a plate counting only nodes would show a factor of 7 where the rank count shows 123.

The tree against the alphabet, with and without a scheduleA larger alphabet cuts both ways and this is the plate that shows which way wins. Each extra symbol is another branch to try at every node, so the tree grows; and each extra symbol makes an interval empty sooner, so the branches die faster. Measured over 3 alphabets at 2 errors: 625 extensions at 3 symbols and 4,560 at 27 for the plain search, against 298 and 904 for the scheme. Both axes are logarithmic.1010³symbols in the alphabetinterval extensionsright to leftthe scheme18 characters · k = 25.04x apart
Fig. 7 The tree against the alphabet, with and without a schedule. Both lines rise; what the schedule changes is how fast.

Where the intervals actually sit

It is easy to picture the two intervals as two windows onto one thing. They are not: they are windows onto two different sorted orders, and only their widths are guaranteed to agree.

The forward interval’s rows are positions in the suffix array of the text. The reverse interval’s rows are positions in the suffix array of the reversal, which orders the same occurrences by what precedes them rather than by what follows. An occurrence is at row 400 in one and row 12 in the other, and there is no cheap map between them — which is why the structure carries both rather than converting.

That also settles what can be reported. Positions come out of the forward index, by the ordinary walk to a sampled position that the sampling that goes the other way prices. The reverse index is machinery: it is never asked where anything is.

The rows beginning with "abra": 2 of 12Every rotation of the text, sorted. The rows beginning with the pattern are contiguous, which is the only property of the sorted order the search uses, so a search is the narrowing of an interval and a count is its width. The shaded band is rows 2 to 3, found in 8 rank queries and 0 character comparisons. The last column is the transform; the first is the same text sorted.0$abracadabra1a$abracadabr2abra$abracad3abracadabra$4acadabra$abr5adabra$abrac6bra$abracada7bracadabra$a8cadabra$abra9dabra$abraca10ra$abracadab11racadabra$aball 12 rotations of "abracadabra$", sorted0 character comparisons
Fig. 8 The ordinary backward search, one character at a time. Everything above is this operation performed twice over, with a rule for keeping the two in step.

What is checked, and what must fail

Three things are asserted and one is required to be catchable.

The widths agree — the invariant above, checked on eight substrings grown both ways, with all four numbers compared.

Every scheme finds what exhaustive comparison finds, at two budgets and on four ways of consuming the pattern, positions and error counts both. A search framework that loses occurrences is the failure this whole strand is most exposed to, and it is checked against comparing the pattern at every position rather than against another search.

And the two halves are the same size, within two per cent, which is what makes the next essay’s claim a measurement rather than an assumption.

The rejection is the unsynchronised interval above: a reverse half left where it was, which fails the in-step check thirty-nine times out of thirty-nine and changes no answer at all.

How much of each tree finds nothingEvery extension either narrows the interval or empties it. An emptied one is the search learning that a branch holds no occurrence, which is work done to rule something out — and it is where a scheme's benefit shows up, because a tighter bound turns a whole subtree into one dead extension. 47% of the right-to-left search's extensions are dead against 68% of the scheme's, on trees whose sizes differ by 2.74x.right to left830391 deadleft to right877423 deadone per piece447323 deadthe scheme303205 deadextensions · solid is the ones that narrowed an interval15 characters · k = 26 occurrences
Fig. 9 How much of each search tree is an extension that finds nothing. Ruling a branch out is work, and it is where the difference between the schedules shows up.

Two ways of being wrong that look the same

There are two independent things a bidirectional extension can get wrong, and they produce the same symptom.

The first is the one above — the reverse interval’s start not moved, or moved by the wrong total. The second is subtler: moving it by the total width of the intervals for symbols sorting before c in the reverse index’s alphabet ordering rather than the forward one. On an alphabet whose symbols sort the same way in both, which is every alphabet, those are the same ordering and the bug does not exist. On a structure that stores a permuted alphabet — a Huffman-shaped wavelet tree assigns code words by frequency, not by symbol — the tree’s internal order and the alphabet’s order are different things, and reading one for the other is a defect that fires on some texts and not others.

This collection has one recorded instance of that shape already: the measure that cannot see the alphabet is a whole essay about a quantity that changes when the symbols are relabelled and a quantity that does not. Here the answer is that the count must be over the alphabet’s order, because it is the reverse index’s rows that are being shifted and those are sorted by symbol.

The check that separates the two cases is the same in-step assertion, run on a text over twenty-six symbols rather than four — a wider alphabet makes more symbols sort before an average one, so more of the total is at stake and a wrong ordering has more to be wrong about.

What a structure like this is for

It is worth stating plainly what problem is being solved, because “an index that extends both ways” sounds like a convenience and it is not.

Approximate matching over an index is a tree search: at each pattern character the search either matches or spends an error, and spending an error branches over the alphabet. The tree’s size is what everything costs, and it multiplies by roughly ten per error on the alphabets measured here — which is the finding the branches an error opens records.

Anything that cuts the tree near its root is worth far more than anything that cuts it near its leaves, because a branch removed at depth two removes everything beneath it. The strongest available constraint is that some piece of the pattern contains no error at all, and the pigeonhole guarantees one exists. Using it requires beginning the search at that piece, wherever it is.

That is the whole argument, and every part of it was available before this structure existed. What was missing was the ability to act on it, and that is what an interval with two ends provides.

The extension is σlog⁡σ\sigma\log\sigma, and the upper bound is loose by σ/2\sigma/2

Two numbers on this page deserve to be pinned down, because one of them is stated as a puzzle and the other as an unmeasured caveat.

The puzzle is a factor of 8.4 for a factor of 6.5 in the alphabet. The loop performs one descent per symbol below the one being added, at both ends of the interval, and a descent costs the tree’s depth — so with a sentinel the cost is about

(σ+1)⌈log⁡2(σ+1)⌉/2(\sigma + 1)\lceil\log_2(\sigma+1)\rceil / 2

for a symbol averaging the middle of the alphabet. At four symbols that is 5×3/2×2=155 \times 3 / 2 \times 2 = 15 against the measured 16.5; at twenty-six it is 27×5/2×2=13527 \times 5 / 2 \times 2 = 135 against 138.6. Both to within a few per cent, with nothing fitted.

So the growth is σlog⁡σ\sigma\log\sigma rather than σ\sigma, and the discrepancy the essay notices is the logarithm: the tree’s depth steps from three to five between the two alphabets, and 6.5×5/3=10.86.5 \times 5/3 = 10.8 brackets the measured 8.4 from above because the average symbol is not quite the middle one. The extension is 2σ2\sigma symbol ranks and σlog⁡σ\sigma\log\sigma bit-vector ranks, and every plate in this strand is counting the second.

The caveat is the compound operation, named here and not built, with its consequence stated as every rank count in this strand is an upper bound. That bound has a size. One descent answers the whole smaller-symbols total, so an extension with the compound walk costs 2⌈log⁡2(σ+1)⌉2\lceil\log_2(\sigma+1)\rceil — six at four symbols and ten at twenty-six — and the ratio to the loop is

σ+12.\frac{\sigma+1}{2}.

Two and a half at four symbols, thirteen and a half at twenty-six. Every child at once measures it at 3.03 and 13.97 on the same structures, which is the same expression with the same small correction for where in the alphabet the symbol sits.

That turns a caveat into a usable statement. A reader taking this strand’s rank counts to an implementation that has the compound operation should divide by about half the alphabet — and the node counts, which are what the strand is actually about, should be taken unchanged, because the compound walk changes how a number inside an extension is computed and not which extensions happen.

It also says which of the two costs a wider alphabet moves. The tree grows with σ\sigma because the branching does; the per-extension cost grows with σlog⁡σ\sigma\log\sigma under the loop and with log⁡σ\log\sigma under the walk. So the loop makes the alphabet’s penalty quadratic-ish and the walk makes it nearly linear, and the difference between a plate showing a factor of 7 in nodes and one showing 123 in ranks is entirely which of those two an implementation uses.

Both statements are the same discipline the operations a candidate count leaves out asks for, applied to the unit rather than to the operation: a count is a number and a statement of what one act is, and here the act’s price is itself a function of the alphabet.

What this leaves

An index that can be extended at either end, at two ranks plus a count over the smaller symbols, holding two transforms and reporting from one of them.

The two essays after this are what it is for and what it is not. It is not a way of holding one index instead of two — the structure that was supposed to halve is that finding, measured. It is a way of choosing the order a pattern is consumed in, and the search that starts in the middle is what the choice is worth.

Where this goes next

0$abracadabra1a$abracadabr2abra$abracad3abracadabra$4acadabra$abr5adabra$abrac6bra$abracada7bracadabra$a8cadabra$abra9dabra$abraca10ra$abracadab11racadabra$aball 12 rotations of "abracadabra$", sorted0 character comparisons 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. one index35,3354.31 bits/charthe forward half35,3354.31 bits/charthe reverse half35,3354.31 bits/charboth, which is the structure70,6708.63 bits/charbits8,192 characters · sample 322.00x one index The structure that was supposed to halve A bidirectional index holds the transform of the text and the transform of its reversal — 35,335 bits each, 70,670 together, exactly twice one index. The deferral that named it hoped it would stop the index doubling. It does not remove the doubling; it reuses it. ranks to compute D72extensions removed27,906extensions remaining12,051one search · k = 3 · 4,000 charactersand one more index: 17,033 bits4,000 characters · m = 16388 extensions a rank A bound that has to be paid for The pruning removes seventy per cent of a search tree for seventy-two rank operations. It also needs an FM-index of the reversed text — 17,033 bits against the forward index's 17,032 — which doubles the structure whose small size was the entire argument for walking an index.

What this makes readable

Essays that name this one as a prerequisite.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

What links here

Every essay whose body links to this one.

The objects this essay names

Each one links to every other essay that touches it.

AlphabetBackward searchBidirectional indexConstant factorFM-indexIndex sizeIntervalMeasurementRankReverse indexTrade offWavelet tree