A function with r pieces

Here is a function on the positions of a text. $\varphi(i)$ is the position that comes immediately before $i$ when every suffix of the text is sorted — the suffix-array value of the row above $i$’s own row.

It looks like a function that requires the suffix array. It does not. It requires $r-1$ pairs of numbers, where $r$ is the number of equal-letter runs in the Burrows-Wheeler transform, and on the collection drawn below that is 25 pairs for 129 positions.

The one line of algebra #

The transform’s LF mapping sends a row to the row whose suffix begins one character earlier. Inside a run of equal characters it is order-preserving by construction: if rows $x-1$ and $x$ carry the same character then $\mathrm{LF}(x) = \mathrm{LF}(x-1) + 1$, because the rank of that character at $x$ is one more than at $x-1$ and the two land in the same block of the first column.

Now take suffix-array values through that. Write $i = \mathrm{SA}[x]$, so that $\varphi(i) = \mathrm{SA}[x-1]$ by definition. The row of $i-1$ is $\mathrm{LF}(x)$ and the row of $\varphi(i)-1$ is $\mathrm{LF}(x-1)$, and if those two rows are adjacent then the positions they name are adjacent in $\varphi$ as well:

$$\varphi(i-1) = \varphi(i) - 1 \qquad \text{unless the row of } i \text{ begins a run.}$$

That is the whole derivation, and everything else in this essay is a consequence of it. Between two consecutive positions whose rows begin runs, $\varphi$ is a straight line of slope one. There are $r$ run beginnings, so there are at most $r$ segments, so the function is determined by $r$ numbers.

Short by exactly one, every time, and the reason is not rounding #

The plate above measures the pieces rather than assuming them: walk every position, compare $\varphi(i)$ against $\varphi(i-1)+1$, and count the disagreements. On a repetitive text of two thousand characters there are 124 of them for 126 runs; on English 640 for 642; on a four-symbol text 1,515 for 1,517.

Two short, every time, and both are accounted for.

The first run’s beginning is row 0, which has no row above it, so it anchors nothing: there are $r-1$ anchors rather than $r$. The second is subtler and it is worth stating because it looks like an off-by-one and is not. One anchor is always at text position 0, and position 0 has no predecessor to compare against, so it cannot register as a jump. The anchor is real, the structure stores it, and the audit that counts jumps cannot see it.

So the identity is $\text{jumps} = r - 2$ and the anchors are $r-1$, and a check demanding equality would fail on every text. This collection’s standing rule about assertions applies exactly here: the count somebody chose is about picking the quantity deliberately, and the quantity worth asserting is that the jumps are a subset of the anchors, which is the claim the structure rests on.

What an anchor stores, which is less than it looks #

An anchor is a pair: a text position where the function jumps, and the value it takes there. The positions are a sparse bit vector over the text and the values are — nothing new.

$\varphi$ at an anchor $\mathrm{SA}[p]$, where $p$ begins a run, is $\mathrm{SA}[p-1]$. And $p-1$ is the last row of the previous run, whose suffix-array value the structure already keeps for a different purpose. So the anchor carries a run index rather than a position, at $\lceil\log_2 r\rceil$ bits, and the value is read out of an array that exists anyway.

That is why the sampling in the sampling that follows the runs is $2r$ values and not $3r$. Two arrays, three uses, and the essay’s headline size would be half as large again if the sharing were not exact.

What it costs to evaluate #

A $\varphi$ is a predecessor query over $r$ anchors and one addition. The predecessor is a binary search here — $\lceil\log_2 r\rceil$ comparisons, charged as a rank in the index counter, because that is what the field charges a directory lookup as.

It is worth being clear about what this is not. It is not an LF step. An LF step walks the transform: it accesses a character, ranks it, and moves one position back in the text. A $\varphi$ step moves one row up the suffix array, which is a different direction through a different structure, and the two happen to be inverse-ish in a way that is easy to misremember and would produce a working-looking search that returns the wrong positions.

The plate that compares them says which operation it is counting for that reason. Rank is the only thing it does is where this collection established that a rank, a select and a character comparison are three acts rather than three names, and the same discipline is what keeps this comparison honest.

Applying it repeatedly is the locate #

The rows of a search interval are consecutive, and $\varphi(\mathrm{SA}[x]) = \mathrm{SA}[x-1]$ by definition. So from one known occurrence — the suffix-array value at the interval’s last row — every other occurrence is one $\varphi$ away from the one before it.

An interval of width 80 costs 79 applications and no walks. Measured on a collection of sixteen copies, a six-character pattern with 112 occurrences costs 111 $\varphi$ steps, zero LF steps, and 144 ranks in total, against a regularly sampled index’s 1,136 LF steps for the same eighty occurrences at one value in thirty-two.

The known occurrence has to come from somewhere, and it comes from the search rather than from a walk: the occurrence carried through the search is that half. Without it, $\varphi$ has nothing to start from and the structure has to walk to a boundary — which is every occurrence at the same price, where the walk is measured and is thousands of steps long.

The exactness check, and why it is the whole function #

An identity like the one above is exactly the sort of claim that is true, is believed, and is implemented backwards. So it is checked the way this collection checks a claim it depends on: at every position of four texts, against the real suffix array, with no sampling and no tolerance.

Eight thousand positions, four texts, zero disagreements. That is not a spot check and it is not a property test with a seed — it is the function, compared against the definition, everywhere it is defined.

The check is cheap because the texts are small, and it is worth its cost because the failure mode is silent. A $\varphi$ built wrongly still returns numbers in range, still returns positions in the text, and still produces the right answer for patterns whose occurrences happen to lie inside one segment. A search over a repetitive collection has many such patterns.

Two functions that both move by one, and are not each other #

The commonest way to implement this wrongly is not a wrong anchor. It is to reach for the function the structure already has.

An index of this kind carries LF, and LF is a step of one: one character earlier in the text. $\varphi$ is also a step of one: one row earlier in the suffix array. Both are cheap, both are already implemented, both return something plausible, and they are not inverses of one another in any sense that a locate can use.

The distinction is worth drawing out because it is the same confusion the two costs of an index rest on. Walking LF from a row reaches a sampled row, and what it produces is the current row’s own position once the number of steps taken is added. Applying $\varphi$ to a position reaches another occurrence, and it produces that occurrence directly with nothing to add. The first is a walk whose length is set by a rate somebody chose; the second is a single query whose cost is set by $\log r$.

That is why the two are drawn on plates that name their operation, and why the total for a locate is reported as phi steps and LF steps separately in every measurement here. Summing them would give a number belonging to neither policy, which is the failure one run, two counts is about and the count is not the time is the older statement of.

There is one more reason to keep them apart. LF’s cost depends on the transform’s representation — on a run-length structure it is a rank on the run heads and a select on the lengths, which is three counted operations rather than one — while $\varphi$’s cost does not depend on the transform at all. A change to how the transform is stored moves one of these numbers and not the other.

The check that must fail #

The exactness check is only worth what its counterexample is worth, so there is one, and it is one character of code.

The segments are anchored at the predecessor: $\varphi(i) = \varphi(s) + (i - s)$ where $s$ is the largest anchor at or below $i$. Anchor them at the successor instead — the smallest anchor at or above $i$, which is the same array read from the other end — and the function is wrong at 506 of 800 positions on an ordinary English text.

Not all of them. That is the point of quoting the number: a third of the positions still come out right, because a position whose block happens to be short lands in the same segment either way. A test on a handful of positions has a real chance of passing, and the assertion that catches it is the one that walks the whole function.

The direction of the algebra is the entire content of the structure, and it is a single comparison operator in a binary search. This collection has recorded that shape before — measured, not asserted is the standing rule and a search that runs backwards is where it first mattered in this field.

A second check, from the other end of the interval #

There is a second way to get this wrong that the exactness check cannot see, and it needs its own counterexample.

The occurrences of a pattern are the suffix-array values of the rows in its interval. Enumerating them with $\varphi$ requires starting at the interval’s last row and walking up, because $\varphi$ goes up. Start at the first row instead — also an occurrence, also correct, also easy to reach — and the walk leaves the interval immediately and returns positions belonging to other patterns entirely.

Measured: a five-character pattern with twelve occurrences returns twelve positions either way, and the wrong twelve are not the right twelve. The count is right, the type is right, every value is a position in the text, and the answer is wrong. Only a comparison against exhaustive search catches it, which is why the gate compares against exhaustive search rather than against the other index.

Where the pieces come from, and where they do not #

One more property is worth stating because it is what makes this a claim about repetition rather than about suffix arrays in general.

The pieces are the runs, and the runs are what a repetitive collection has few of. On a text of two thousand characters over four symbols the transform has 1,517 runs and the function has 1,515 pieces — nearly one per position, and the structure that stores them is storing the suffix array by another name. On thirty-two copies of one text the runs stay at 233 whatever the length, and the function over sixteen thousand positions is 232 anchors.

So $\varphi$ is not a compression trick that works on any text. It is the same measurement the rest of this strand is about, applied to a function rather than to a structure: the number of pieces is $r$, and $r$ is what a copy does not increase.

What this makes possible that a rate cannot #

It is worth saying plainly what the function buys, because “the same answer with fewer bits” undersells it and “constant-time locate” overstates it.

A regular sampling has one dial and it moves two costs together. Halve the rate and the sampling doubles and the walk halves; there is no setting at which both are small, and the product is fixed by the structure rather than by the text. Every point on that curve is available and none of them is off it. The frontier between time and space is this collection’s name for that shape, met here in a structure rather than in a sort.

The function moves the whole curve. Its cost per occurrence is a predecessor query whatever the text, and its size is $r$ anchors — so the trade is not between the two, it is between the size and a property of the text. A collection that repeats has few anchors and the structure is small and fast at once; a text that does not repeat has many, and the structure is large and still fast.

That is a different kind of statement from a rate, and it is the reason the r-index is described by its own literature as achieving something a sampling cannot rather than as a better-tuned sampling. What this essay adds is the measurement: on a collection of sixteen copies the sampling is 10,244 bits at one predecessor query an occurrence, and the nearest regular rate reaching that step count is one value in two, at 69,649 bits.

The piece count is the compression factor, written out #

“The number of pieces is $r$” is the claim, and turning it into a size takes one ratio — which is worth doing, because the ratio spans a factor of ninety across the four texts this essay already measures.

The suffix array the function replaces is $n$ entries of $\lceil\log_2 n\rceil$ bits. The anchors are $r$ entries of $\lceil\log_2 r\rceil$ bits, since an anchor carries a run index rather than a position. So the function’s payload against the array it stands in for is

$$\frac{r}{n}\cdot\frac{\lceil\log_2 r\rceil}{\lceil\log_2 n\rceil}.$$

Evaluate it on the audit’s own texts, all at two thousand characters. The four-symbol text has 1,517 runs: $(1517/2000)\times(11/11) = \mathbf{0.76}$. English has 642: $(642/2000)\times(10/11) = \mathbf{0.29}$. The repetitive text has 126: $(126/2000)\times(7/11) = \mathbf{0.04}$. And thirty-two copies of one text hold 233 runs over sixteen thousand positions: $\mathbf{0.008}$.

Ninety-fold, from one quantity, on four texts that are all the same length.

That makes the essay’s closing warning precise rather than rhetorical. On a four-symbol text the function is not “storing the suffix array by another name” — it is storing 76% of it, which is a genuine 24% saving and is nowhere near enough to justify the machinery around it. The predecessor structure, the run heads and the toehold’s arrays are all themselves proportional to $r$, so at $r/n$ near one every term in the structure is proportional to $n$ and nothing asymptotic is left: what remains is a compressed index that is a constant factor smaller than an uncompressed one, competing against structures designed for that regime.

At the other end the ratio is what the field is for. Eight thousandths means an object a hundred and twenty times smaller than the array it replaces, with the same locate cost per occurrence, and the whole of that comes from $r$ not growing when a copy is added.

Two things follow that are worth carrying.

The break-even is a property of the text and is computable in one pass. The run count is a scan of the transform; $n$ is the length; the ratio decides whether the structure is worth building before any of it is built. That is the same instruction a sampling that costs more than the array arrives at from the sampling’s side, where the same quantity decides whether $2r$ values are smaller than the array they index.

And the second factor is not negligible. The ratio of logarithms is $\lceil\log_2 r\rceil/\lceil\log_2 n\rceil$, which is 0.64 on the repetitive text and 0.57 at thirty-two copies — so a third of the saving on a highly repetitive collection comes from the anchors being narrower, not from there being fewer of them. That term disappears from any account written as $O(r)$, and it is worth a third of the structure. The sampling that follows the runs charges it explicitly for the same reason.

The honest limit #

The predecessor query here is a binary search over an array of anchors. A published r-index uses a structure with a better bound, and the difference matters for the constant rather than for the claim — but it means the operation counts in this essay are a binary search’s, and a plate that compared them against an implementation using a faster predecessor would be comparing two things.

The other limit is that the segments are drawn and measured at sizes where the whole function fits on a page. The identity is exact at every size and the picture is only legible at a hundred positions, so the plate that shows the shape and the sweep that establishes it are different measurements on different texts, which is stated on both rather than blurred.