A search that runs backwards

A text of 16,384 characters is searched for the six-character string s than. It occurs 23 times. Finding that took twelve rank queries and zero character comparisons.

The zero is not an artefact of instrumentation. Character comparisons are counted here in the same field a naive scan and a binary search over a suffix array are charged in — the same unit the strings field opened with — and a suffix-array search over the identical text and pattern spends ninety-one of them. The backward search spends none, because it never asks whether two symbols are equal. It asks a different question entirely.

One property of the sorted order, and only one #

A suffix array sorts every suffix of the text. That gives the structure a property the binary search exploits and a different property that this search exploits instead:

The suffixes beginning with any given string are contiguous. All of them, always, in one block. If two suffixes both begin with abr then everything sorting between them also begins with abr, because sorting is lexicographic and there is nothing between abr… and abr… that is not abr….

So the answer to where does this pattern occur is an interval — a first row and a last row — rather than a set. Its width is the number of occurrences. And a search is the business of narrowing that interval one character at a time.

The binary search narrows the interval from the outside, by comparing the pattern against candidate suffixes. That needs the text. The backward search narrows it from the inside, by extending the pattern one character at a time to the left, and that needs something else.

The two arrays it needs #

Write $L$ for the last column of the sorted rotations — the transform — and $F$ for the first, which is just the text’s characters in sorted order.

Two things are kept:

• $C[c]$, how many characters of the text sort strictly before $c$. That is one number per symbol of the alphabet: for a twenty-one-symbol text, twenty-one integers.
• the ability to answer $\mathrm{rank}_c(i)$: how many times symbol $c$ occurs in the first $i$ positions of $L$.

Given those, if $[sp, ep)$ is the interval of rows whose suffixes begin with some string $P$, then the interval for $cP$ — the same string with $c$ stuck on the front — is

$$\begin{aligned} sp' &= C[c] + \mathrm{rank}_c(sp) \\ ep' &= C[c] + \mathrm{rank}_c(ep) \end{aligned}$$

Two rank queries. That is the whole step, and it is why the pattern is consumed from its last character to its first: each step prepends.

Two rows of that table are worth reading twice. Between han and than the width does not move: every han in this text is a than. And the interval jumps around the array wildly between steps — 9,888 to 3,385 to 7,342 — because each step is a lookup into a different part of the sorted order, not a refinement of a region.

Why there is no comparison #

The absence of character comparisons follows from the two formulas above and is worth stating as a fact about what the algorithm knows.

$C[c]$ is a lookup by symbol. $\mathrm{rank}_c(i)$ is a count of occurrences of a symbol before a position. Neither is an equality test between two unknown symbols; both are addressed by the pattern’s character. The algorithm is told which symbol it wants and asks how many there are. At no point does it hold two characters and compare them, and at no point does it read any character of the text.

That last clause is enforced rather than asserted. The text is taken away after the structure is built, and a query that reads it is stopped. Measured: zero text reads for the backward search and ninety-one for the binary search over the same pattern.

The count arrives before any occurrence does #

This is the part that has no analogue in any earlier structure here, and it is easy to read past.

When the pattern is exhausted, the width of the interval is the number of occurrences. Twenty-three, known exactly, with no occurrence located. The structure has not computed a single position in the text. It has an interval of rows, and rows are not positions.

Every other matcher this collection has measured produces occurrences and counts them by having produced them. A scan finds them one by one; a suffix-array search finds a range of the array whose entries are the positions and reads them off. Here the count and the positions are two separate questions with two separate prices, and the count is the cheap one.

That separation is the reason a search engine can report 40,000 results in the time it takes to render ten of them. It is not a caching trick; it is a property of the structure.

Turning rows into positions is what the sampling dial is for, and it is where the other half of the cost lives.

The cost does not depend on the text #

Twelve rank queries for six characters. Sixteen for eight. Two per character consumed, and nothing else in the formula.

Not the length of the text. Not the number of occurrences. Not the alphabet, except through the cost of one rank query, which is the subject of the next essay.

The flatness is asserted rather than admired: the count is required to be identical at every text length in the sweep, and to equal exactly twice the pattern’s length. A structure whose backward search had picked up a dependence on n would be refused.

When the pattern is not there #

An interval that has narrowed to zero rows is the answer absent, and it can happen at any step.

Two things follow, and both are the opposite of what an exact matcher does. The search stops early — the moment $sp \ge ep$ there is nothing left to narrow and the remaining characters of the pattern are never read — so a pattern absent because of its last two characters costs four rank queries rather than two per character. A scan, by contrast, does the most work on a text where the pattern nearly occurs everywhere.

And a symbol the text does not contain at all costs nothing: it is not in the $C$ table, so the interval is empty before any rank query is made. That is a small thing which turns out to matter for the instrumentation, because a trace that reported “two ranks per character” would be contradicted by a step that made none. The plates count the steps that performed a rank rather than the characters of the pattern, and where the two differ the caption says which it is showing.

There is no partial credit and no near miss. The interval is either non-empty or it is not, and the structure has no notion of nearly. Everything the approximate search does is unavailable here without building something else on top — which is why approximate matching over compressed indexes is a subject rather than an option.

What it costs to run backwards #

The pattern is consumed from its last character to its first. That is forced by the arithmetic — each step prepends a character to the front of the matched string — and it has a consequence worth naming.

An exact matcher that scans a text left to right can report an occurrence the moment it completes one, and can be handed the text a piece at a time. Backward search cannot be handed the pattern a piece at a time from the front; it needs the last character first. For a fixed pattern searched in a fixed text that is a non-issue, and for anything incremental — a user typing a query, a pattern being extended as it is refined — it means the interval is rebuilt rather than extended.

The reverse is true too and is more useful: extending a pattern on the left is free. Having the interval for than, the interval for s than is two more rank queries, and nothing about the first computation is discarded. A structure that answers queries about progressively longer left-extensions gets each one for a constant price.

The $C$ table, meanwhile, is not worth thinking about. One integer per symbol, twenty-one of them for the text above, at fifteen bits each: 315 bits, against the tens of thousands everything else costs. It appears on the size plates because leaving a part out is how a size claim becomes wrong, not because it matters.

The identity underneath #

Everything above rests on one fact about the transform, and it deserves its own paragraph because it is what makes the structure possible rather than merely convenient.

The $k$-th occurrence of a symbol $c$ in the last column and the $k$-th occurrence of $c$ in the first column are the same character of the text.

The reason is that both columns list rotations sorted by what follows the character in question. In $F$, the rows starting with $c$ are sorted by the rest of the rotation — that is, by what comes after that $c$. In $L$, the rows ending in $c$ are sorted by the row they are in, which is sorted by what comes after that $c$ as well. Two lists of the same characters, ordered by the same key, so they are in the same order.

That gives the LF mapping: from a row, one rank query and one addition produce the row whose suffix begins one character earlier.

Backward search is the LF mapping applied to a whole interval at once rather than to a single row. That is the entire idea, and everything else — the counting, the locating, the extraction — is a use of the same two arrays.

What is being paid instead #

Nothing here is free, and it is worth being clear about where the bill went.

A rank query is not one operation. Answering how many $c$ before position $i$ requires a structure, and the obvious structure — a counter array per symbol — is sixty-six times the size of the text. The whole art of this field is answering rank queries in a structure that is smaller than what it indexes rather than vastly larger.

Twelve rank queries for a symbol became forty-four rank queries on bit vectors in the run at the top of this page, because the structure that answers a symbol rank does so by walking a tree of bit vectors, one bit-vector rank per level. Which level count, and therefore which constant, is decided by the shape of that tree — and the shape turns out to be the text’s own entropy.

The widths on the way down are answers too #

The trace table reports a width at every step — 881, 320, 110, 110, 110, 23 — and those are usually read as progress towards the answer. They are answers in their own right, and having them costs nothing.

The interval after $j$ steps is the interval of the pattern’s last $j$ characters. So its width is the number of occurrences of that suffix of the pattern, exact, in the same text. One backward search over a six-character pattern therefore reports the occurrence count of every one of its six suffixes, and the only thing separating those numbers from the final answer is that nobody asked for them.

The widths are non-increasing, and that is a fact rather than an observation about this text: every occurrence of $cP$ contains an occurrence of $P$ one position along, so the set can only shrink as characters are prepended. The two consecutive 110s are the interesting kind of shrinkage — none — and they say that every han in this text is a than, which is a statement about the source that fell out of a search that was not asking.

That by-product is worth more than a curiosity, because it answers a question this collection left open in a different field. A seed-and-extend filter chooses its seed length from a formula in the pattern length, the error budget and the alphabet, and the formula predicts the expected number of chance occurrences on uniform text. Real text is not uniform, and the essay that measured the filter says exactly that: the variance of the candidate count on real data is larger than anything a mean can show.

The widths remove the need to predict. Extend a seed leftwards one character at a time and watch the width fall; stop when it is small enough to verify. That is a seed chosen by its measured occurrence count in the actual text rather than by an expectation over a text nobody has, it costs two rank queries per character of seed — the search that was going to be performed anyway — and it adapts automatically to a seed that happens to land in a common region. A quantity that a filter was estimating from parameters is available exactly, for free, as a side effect of the search.

Three things the interval is not #

The interval is a range of rows and it is easy to treat as though it were the answer. It is not the answer to three separate questions, and each of them costs something different to get.

It is not a set of positions. Rows are not text positions, and turning one into the other is the sampling walk. That is the split the essay has already drawn — the count is cheap and the locations are not — and it is the largest of the three gaps.

It is not a set of documents. A collection concatenated into one text gives an interval whose width counts occurrences, and a reader who wants how many documents contain this has been given a different number. Twenty-three occurrences might be twenty-three documents or one document twenty-three times, and nothing about the interval distinguishes them; recovering the document count is its own construction with its own cost.

And it is not in text order. This one is the quietest and it catches people. The rows of the interval are sorted lexicographically by the text that follows each occurrence, which has no relation whatever to where the occurrences sit. So the first row of the interval is not the first occurrence in the text, and there is no way to get the earliest occurrence without locating all twenty-three and taking the minimum.

That last point turns a common optimisation upside down. A scan that wants only the first match stops at the first match and is cheaper for it. An index that wants only the first match must do all the work of finding every match and then sort, so asking for less is not cheaper here — and a system that reports a leftmost occurrence from an index has paid the full price of reporting all of them.

The check #

The occurrences are required to agree with a scan. Every index in this collection is asked for the same patterns as a naive left-to-right search over the same text, and the two answers must match in count and in position — not because the arithmetic is doubted, but because a backward search that is subtly wrong returns a plausible interval containing a plausible number of rows, and every figure drawn from it would be a wrong figure that draws perfectly.

That is the failure mode this whole collection is arranged against, and it is sharper here than usual: the count is produced without any occurrence being examined, so there is nothing in the answer that could look wrong.

The check is run at four pattern lengths and three positions in the text, on every index in this collection, including the deliberately enormous counter table — which is there partly as a control. Two structures with completely different internals producing identical answers is much stronger evidence that both are right than either one agreeing with itself, and when a rank directory was quietly broken during construction it was this comparison that reported it rather than any figure looking wrong.

Beside it sits the check that matters most for the claim this essay makes: the search must examine zero characters, and the suffix-array search over the same pattern must examine more than zero. Without the second half, an implementation in which the character counter had stopped incrementing would pass.