The occurrence carried through the search

Backward search answers how many and refuses to answer where. It narrows an interval of rows one pattern character at a time, and when the pattern is exhausted the interval’s width is the number of occurrences — a number that arrives without a single occurrence having been located.

That separation is the first thing this collection measured about the structure, in a search that runs backwards, and it is usually described as a virtue. It is also the reason a sampling exists: something has to turn a row into a position, and the interval does not know how.

One occurrence is enough, and it has to arrive during the search #

A function with r pieces shows that every occurrence after the first is one predecessor query away from the one before it. What it needs is a place to start: the suffix-array value of one row of the final interval.

Getting that by walking is the thing the whole design is avoiding. Run boundaries are not spread through the text, so a walk from an arbitrary row to the nearest sampled row is bounded by nothing — measured at 6,907 LF steps for a single occurrence in every occurrence at the same price, on the collection where the structure is otherwise at its best.

So the starting occurrence has to be maintained rather than found: carried along with the interval, one step at a time, from a state where it is trivially known.

The invariant, and the two cases #

The state carried is $\mathrm{SA}[ep-1]$: the text position of the last row of the current interval. At the start the interval is every row, its last row is row $n-1$, and that row’s value is stored — it is the last row of the last run, which the sampling keeps anyway.

A step extends the interval by a character $c$. The new interval’s last row is $\mathrm{LF}(q)$, where $q$ is the last row in the current interval carrying $c$; and $\mathrm{SA}[\mathrm{LF}(q)] = \mathrm{SA}[q] - 1$. So the whole step is: find $q$, read its suffix-array value, subtract one.

There are two cases and they cost differently.

The character is already at the end. If the transform’s character at $ep-1$ is $c$, then $q$ is $ep-1$ itself and its value is the one being carried. Nothing is looked up; the state is decremented.

It is not. Then $q$ is the last $c$ before $ep$, and the character after $q$ is not $c$ — so $q$ is the last row of a run, and its suffix-array value is one of the $r$ values the sampling stores. Finding which run it is costs a rank on the run heads and a lookup, charged here as a select.

Why the expensive case lands on a stored value #

The second case is the reason the sampling stores the ends of runs and not only their beginnings, and it is worth spelling out because the argument is what turns “keep $2r$ values” from a guess into a construction.

$q$ is defined as the largest row below $ep$ carrying $c$, in a situation where row $ep-1$ does not carry $c$. Every row strictly between $q$ and $ep$ therefore carries something else. So the run containing $q$ ends at $q$: a run is a maximal stretch of equal characters, and the character changes immediately after.

The set of rows that can ever be $q$ in the expensive case is therefore a subset of the run ends. There are $r$ of those and the structure keeps all of them. The sampling is not sized to be small; it is sized to be exactly the set the search can land on, and that it is also small is a fact about the transform rather than about the design.

What it costs, measured rather than argued #

The two cases are not equally common, and which is common is a property of the text and the pattern rather than of the index.

Forty patterns of each length, drawn from a collection of eight copies of a 512-character English text, give the free case on 25% of steps at two characters, 41% at four, 63% at eight and 82% at sixteen. On a four-symbol text the same sweep runs 24%, 56%, 78%, 85%.

The direction is the same and the reason is the same. A long pattern narrows its interval quickly, and a narrow interval is likely to be inside a single run — at which point every remaining step finds its own character at the end and costs nothing. A two-character pattern is still ranging over thousands of rows, and the row at the end of that range is whatever it happens to be.

So the toehold is nearly free for the queries that return few answers and costs a lookup per character for the queries that return many. That is the opposite shape from the walk it replaces, whose cost is per occurrence, and it is why the two cannot be compared by counting operations in one column.

The lookup is not a rank, and the difference is charged #

The expensive case costs “a lookup”, and this collection’s rule is that a plate reporting a cost says which act it counted. So: it is a rank on the run heads, followed by an indexed read.

The rank asks how many runs of character $c$ begin at or before the run containing $ep-1$. That is a symbol rank on a wavelet tree over $r$ symbols — a handful of bit-vector ranks, not one, since a wavelet tree turns a symbol rank into as many binary ranks as the symbol’s code is long. The read then takes the last such run’s end row and its stored suffix-array value.

None of this touches the $n$ rows. The run heads are $r$ symbols and the arrays are $r$ entries, so the whole toehold apparatus lives inside the structure’s $O(r)$ part — which matters, because a toehold implemented against the transform’s $n$ characters would have reintroduced the term the sampling was replaced to remove.

That distinction between a symbol rank and a bit-vector rank is the one rank is the only thing it does is built around, and it is why the counter here keeps them in separate fields rather than adding them up. A plate that summed them would report the Huffman-shaped tree and the balanced one as costing the same.

The invariant is checked at every step, not at the end #

A toehold is easy to get subtly wrong in a way that produces the right answer most of the time, so the check is not on the answer.

At every step of every search, the carried value is compared against the real suffix array at the interval’s last row. Four pattern lengths, twenty-five patterns each, 450 steps on a collection of four copies: every one of them agreed.

Checking only the final answer would be much weaker, because the error that matters here is an interior one. A toehold that is wrong at step three and right at step four returns a correct occurrence and a correct count, and the walk that produced it is nonsense — and on a repetitive collection, where the occurrences of a pattern are spread evenly, a wrong toehold has a real chance of landing on another genuine occurrence.

This is the same discipline the counted structures elsewhere here are built with. Counting instead of timing is the collection’s founding version of it, and the invariant that was wrong for seven years is the case that most argues for checking an interior condition rather than an output.

The wrong end of the interval #

The interval’s first row is also an occurrence, and it is just as easy to carry. Starting the enumeration there is a bug that no type system, no range check and no count comparison can see.

Applying $\varphi$ from $\mathrm{SA}[sp]$ walks upwards out of the interval: $\varphi(\mathrm{SA}[sp]) = \mathrm{SA}[sp-1]$, which is a suffix that does not begin with the pattern. The enumeration then returns exactly as many positions as there are occurrences, all of them positions in the text, and the wrong ones.

Measured on a five-character pattern with twelve occurrences: twelve positions returned, and the twelve are not the twelve. The gate’s rejection test is exactly this, and the only check that catches it is agreement with exhaustive search.

Two ways to be wrong that produce the right count #

The wrong end is one of a pair, and the other is worth naming because it fails in the opposite direction.

The first is the one above: carrying $\mathrm{SA}[sp]$ instead of $\mathrm{SA}[ep-1]$. The interval is right, the enumeration starts at a real occurrence, and every subsequent step leaves the interval. Every returned position is a position and the set is wrong.

The second is to maintain the toehold only on the steps where it is free — to take the decrement when the character is already at the end of the interval and to skip the lookup otherwise, on the reasoning that the value is “still an occurrence of a suffix of the pattern”. It is, and it is an occurrence of the wrong one. The result is a position that occurs somewhere in the text and does not begin with the pattern, and on a repetitive collection it will often be near one that does.

Both produce an answer set of exactly the right size. Both survive any check that asks whether the count matches the interval’s width, which is the check an implementation naturally writes first because the width is right there. The only thing that separates a correct locate from either of them is a comparison against exhaustion, on a text small enough to exhaust — which is why this collection keeps such a text in every gate it can.

Where the count still comes for free #

One property survives all of this and is worth stating, because it is the reason an index of this kind is worth having for queries that are not locates.

How many still costs two ranks per pattern character and nothing else. The toehold rides along on the same steps and adds a lookup on some of them; it does not change the interval, does not change the count, and does not touch a suffix-array value unless the search is going to be asked for positions.

So a query that only needs a count can skip the whole apparatus, and a query that needs positions pays for the toehold once and then one predecessor query per answer. Three questions, three costs, no dial — which is what an index has a size has been arguing since the field opened, and what rank is the only thing it does established about the primitive underneath.

What this does to the shape of a locate #

Put the three costs together and the structure’s locate has a shape no rate-based sampling has.

A regularly sampled index pays $O(s)$ per occurrence: the cost is linear in the answer and the constant is the rate. An r-index pays one lookup on some fraction of $m$ steps, then one predecessor query per occurrence. The first term is a property of the query and the second is one operation per answer, and neither of them contains a number somebody chose.

On the collection measured above, an eighty-occurrence query costs twelve selects for the toehold and seventy-nine predecessor queries for the rest, against 1,136 LF steps at one value in thirty-two. That is not a constant-factor improvement in the same shape; it is a different function of the same inputs.

What the toehold says about the sampling’s shape #

There is a temptation to describe the $2r$ values as “the samples”, one array with two uses. The measurement above says they are two arrays with one use each, and the distinction matters for anybody sizing the structure.

The run ends exist for the toehold. They are the set the search can land on in its expensive case, and no other part of the structure reads them for that purpose. The run starts exist for $\varphi$: they are the positions where the function jumps, and its anchors point at them.

They are stored together because they are the same kind of thing and because $\varphi$’s values are run-end entries — which is the sharing that keeps the sampling at $2r$ rather than $3r$, as the sampling that follows the runs accounts for in full. But the two halves answer different questions, and a structure that dropped either one would fail on a different query.

That is worth saying because the obvious economy is to keep only the run starts, since those are what $\varphi$ needs and $\varphi$ is what produces the occurrences. An index built that way answers how many correctly, answers where correctly whenever the search’s last step happens to be a free one, and is wrong the rest of the time.

The share is a rate; the cost is three lookups #

The plates report a share of free steps, and a share is not a cost. Multiplying it out is one line and it produces a number far more useful than the percentages, because the number does not move.

Take the English row: 75% of steps expensive at two characters, 59% at four, 37% at eight, 18% at sixteen. Multiply each by its pattern length and the expensive steps come to 1.5, 2.4, 3.0 and 2.9. The four-symbol row: 76%, 44%, 22% and 15% at four, eight, sixteen and twenty-four characters, which is 3.0, 3.5, 3.5 and 3.6.

The toehold costs about three lookups a query, at every pattern length, on both alphabets. The share rises with the pattern only because the denominator does; the numerator has stopped moving.

That is exactly what the mechanism predicts once it is read as a statement about when the expensive case happens rather than how often. The lookup is needed while the interval is still wide enough that its last row carries an arbitrary character, and an interval stops being wide after about $\log_\sigma n$ characters have been matched — six on four symbols over four thousand rows, three on a twenty-symbol alphabet. After that the interval is inside a run and every remaining step is free, however many remain.

So the share is $1 - (\log_\sigma n)/m$ to a good approximation, and checking it against the measurements: on English at sixteen characters the formula gives 0.82 against a measured 0.82, and at eight it gives 0.65 against 0.63. On the four-symbol text with the measured constant of 3.5 it gives 0.78 and 0.85 at sixteen and twenty-four, against 0.78 and 0.85.

Three consequences, and the first changes how the cost should be quoted.

The toehold is $O(\log_\sigma n)$ and not $O(m)$. Quoting it as a share invites a reader to multiply by their own pattern length and arrive at a term that grows; it does not grow. A sixteen-character pattern and a hundred-character one pay the same three lookups.

It is therefore negligible against everything else in a locate. Three lookups, once, against one predecessor query per occurrence — so on the eighty-occurrence query this essay measures, the toehold is under four per cent of the locate’s operations and falls as the answer grows. A function with r pieces’s per-occurrence term is the whole cost for any query worth calling a locate.

And the comparison with the walk is not close at any pattern length. The alternative this apparatus replaces is 2,955 LF steps per occurrence, with a worst walk of 6,907, measured in every occurrence at the same price. Three lookups against thousands of steps per answer is not a trade with a crossing in it; the toehold is what makes the run-boundary sampling usable, and its own cost is a rounding error in the structure it makes possible.

Which is worth stating because the plates, read as shares, make the toehold look like a term that might matter at short patterns. At two characters it costs one and a half lookups.

The honest limit #

Everything above assumes the toehold’s lookup is a select on the run heads, and the implementation here answers it with a per-symbol array of run indices and a binary search rather than with a select structure over the wavelet tree. The bits are charged as $r\lceil \log_2 r\rceil$, which is what such an array costs; a select structure would be smaller and its query would be slower, and the plates in this essay do not sweep that choice.

The share measurements are also a property of these texts. Forty patterns per length is enough to establish the direction and not enough to quote a share for a corpus this collection does not contain. What is robust is the mechanism — a narrow interval agrees with its own last character more often — and that is stated as the finding rather than the percentages.

The measurement that is missing is the one on a collection with document boundaries, where the intervals of a pattern occurring once per document are wide and shallow rather than narrow and deep, and the free case should be rarer for a reason that has nothing to do with pattern length.