The sampling that follows the runs

Two phases ago this collection built an index whose transform is stored as runs, measured it across a collection of thirty-two identical copies, and reported the finding that mattered rather than the one that looked good: the parts that follow the run count grew 1.45 times and the sampling grew 18.3 times, from seven per cent of the structure to half of it.

The structure had been described as proportional to $r$. Half of it was proportional to $n$.

What the sampling is for, and why it cannot simply be dropped #

An index answers three questions and they are three different costs. How many is answered by backward search, which narrows an interval of rows one pattern character at a time and never touches a suffix-array value. Where is answered by turning a row into a text position, and that is what a sampling is for. What — produce the text itself — is answered by walking the transform backwards.

The second question is the one with a dial on it. A row does not know its own position; the array that would say is $n\lceil \log_2 n\rceil$ bits, which is larger than the text and larger than the index. So a regular sampling keeps one value in every $s$ of them and walks: from an unsampled row, take LF steps until a sampled row is reached, and add the number of steps taken. At most $s$ steps, one value in $s$ kept, and the product of the two is fixed.

The sampling that goes the other way measured the same dial for extraction rather than for location, and an index larger than what it indexes is where this collection first weighed the thing the dial is spending.

Two values per run #

The replacement is one sentence long. Keep the suffix-array value at the first row of every run and at the last row of every run, and keep nothing else.

That is $2r$ values. There is no marking vector over the $n$ rows, because the rows that carry a value are not scattered through the array — they are the run boundaries, which the structure already knows where to find. There is no rate to choose, because the sampling is not a rate: it is a consequence of the transform’s shape.

On the collection above, $r = 233$ and $n = 16{,}385$. Four hundred and sixty-six values at fifteen bits each is 6,990 bits. The regular sampling at one value in thirty-two is 512 values, a marking vector over 16,385 rows, and 11,286 bits between them.

The 1.34 is not noise, and it is not zero either #

Across the sweep the regular sampling grows by a factor of nineteen and the run-boundary sampling by a factor of 1.34. The second number deserves a sentence, because a claim of “no term in $n$” would be false and the difference is worth being exact about.

$r$ does not move: 233 at two copies and 233 at thirty-two. What moves is the width each value is written in. A position in a text of 1,025 characters is eleven bits and a position in a text of 16,385 is fifteen, so 466 values cost 5,126 bits at one end of the sweep and 6,990 at the other. The predecessor structure grows for the same reason and one more: its low parts are $\lceil\log_2(n/r)\rceil$ bits each, and with $r$ fixed that width grows with the collection too.

So the honest statement is that the sampling is $O(r\log n)$ and the previous one was $O((n/s)\log n)$, and across a sixteenfold sweep the first grew by a third and the second by nineteen. That is the difference between a logarithm and a linear term, measured rather than asserted, which is what a limit is not a prediction asks of every claim of this shape here.

Why two values per run are enough for all $n$ positions #

They are not, on their own. Two values per run are enough because of a function, and the function is the subject of a function with r pieces, which is the essay this one hands off to.

The short version, because the size claim here is empty without it: $\varphi(i)$ is the text position that precedes $i$ in suffix order. It is piecewise linear with slope one, it breaks only at positions whose row begins a run, and the value at each break is the suffix-array value of the row above — which is the last row of the previous run, which is already stored. So $\varphi$ needs a predecessor structure over $r$ anchors and no values of its own, and applying it repeatedly walks an interval of rows without ever taking an LF step.

The other half is the toehold: one occurrence has to be known before $\varphi$ can produce the rest, and it is produced during the backward search rather than afterwards. That is the occurrence carried through the search, and it is what makes the run-end values load-bearing rather than decorative.

What the parts look like when they are all one measure #

The plate at the top of this essay is the structure opened up, and it is worth reading as an accounting rather than as a picture. Six parts, and every one of them is $r$ times a width:

The run starts are a sparse bit vector with $r$ ones over $n$ positions — 2,097 bits. The run heads are a wavelet tree over $r$ symbols — 1,538. The run lengths, one sparse vector per symbol, are 1,970. The sampled positions are $2r$ values — 6,990. The predecessor structure for $\varphi$ is 3,952. The $C$ table is 500.

The parts sum to 17,047, and the plate asserts that they do. That check is cheap and it is not decorative: an index larger than what it indexes records that the commonest way a compressed structure is reported smaller than it is, is a part left out of the sum.

The two structures are nearly the same size, and that is not the finding #

At thirty-two copies the r-index is 17,047 bits and the run-length index at one value in thirty-two is 17,391. Two per cent apart. A plate that stopped there would have shown a great deal of machinery bought for nothing.

The size is not the finding because the two structures do not answer the second question at the same price. The regular sampling walks up to thirty-two LF steps for every occurrence it locates; the r-index takes one predecessor query and no LF step at all. To match that, the regular sampling has to raise its rate, and raising the rate is what its size is made of.

Put the other way round: the comparison that means something is at equal locate cost, not at equal size, and it is the whole of every occurrence at the same price. The short answer is that a regular sampling reaching one step per occurrence on this collection costs 69,649 bits against the r-index’s 10,244.

Where it loses, stated here rather than left for the reader to find #

At one copy — an ordinary English text of 512 characters, nothing repeated — the r-index is 10,974 bits and the run-length index at one in thirty-two is 3,939. Nearly three times larger, and the reason is arithmetic: $r$ is 229 on that text, so $2r$ is 458 values against the regular sampling’s 16.

The condition is $2r < n/s$, which is a fact about the text. On English $r$ is 0.29 runs per character and on a four-symbol text it is 0.75, so a sampling proportional to $r$ is proportional to $n$ with a constant of a half or one and a half. A sampling that costs more than the array is that measurement in full, including the case where the sampling is twice the size of the whole suffix array it was invented to avoid storing.

The crossing has a formula, and the formula has somebody’s parameter in it #

The condition for the run-boundary sampling to be the smaller of the two is $2r < n/s$, and left in that form it reads as a property of the text. Solved for the collection instead, it says something sharper.

A collection of $c$ copies of a base text of length $b$ has $n = cb$, and $r$ does not move with $c$ — that is the whole premise of a run-length index. So the condition becomes

$$c \;>\; \frac{2rs}{b}$$

and every quantity on the right is known before the collection is built. On the collection measured here, $r = 229$ on the base text, $s = 32$ and $b = 512$, which puts the crossing at 28.6 copies. The measurement agrees: at thirty-two copies the two structures are within two per cent of each other and the r-index is on the smaller side of the crossing it was predicted to have just passed. The whole-structure crossing sits slightly later than the sampling’s own, because outside the sampling the r-index is paying for a wavelet tree and a predecessor structure that the other one does not have.

The formula is worth having for the term it contains rather than for the number it produced. The crossing is linear in $s$, and $s$ belongs to the other structure. A deployment sampling one row in eight moves the crossing to seven copies; one sampling one in a hundred and twenty-eight moves it to a hundred and fifteen. The question “which index is smaller” therefore has no answer that is a property of the two designs. It is a question about a number somebody typed, and a threshold somebody chose is exactly the kind of quantity a comparison must not be allowed to rest on.

That is the arithmetic behind the refusal above to treat the two-per-cent size gap as the finding. A comparison whose outcome is linear in the loser’s free parameter is not a comparison of structures; the parameter’s owner can put the crossing wherever the argument needs it. Fixing the locate cost first and asking what each structure spends to achieve it removes the dial, which is why that is the measurement every occurrence at the same price makes.

One consequence of the same inequality is worth stating because it closes off a hope. Divide through by $n$: the run-boundary policy wins when the run density $r/n$ is below $1/(2s)$. English runs at 0.29 boundaries a character before any copying, which would require $s$ under 1.7 — a sampling rate that keeps more than one row in two. On a four-symbol text at 0.75 the requirement is impossible outright. So on a text that does not repeat, no choice of rate makes the run-boundary sampling the smaller policy, and the crossing is not something a parameter can reach. It has to be earned by the collection.

What a run boundary knows that a rate does not #

There is a reason a sampling at the run boundaries can be smaller than a regular one and answer faster, and it is not that somebody found a cleverer rate. The two policies are sampling different things.

A regular sampling picks positions in the text: every thirty-second position, whichever rows they happen to land in. It knows nothing about the transform, so a row’s distance from the nearest sampled row is arbitrary and is bounded only by the rate. That bound is the whole of its guarantee, and it is why the rate appears in both of its costs.

A run boundary is a position in the transform, and the transform is the thing the structure is built out of. A run is a maximal stretch of rows carrying the same character, so a boundary is exactly a place where LF stops being order-preserving — which is exactly where a piecewise-linear function of suffix-array values has to break. The sampling and the function are the same set of $r$ places, seen from two sides.

That is why nothing has to be tuned. There is no rate here that a deployment could get wrong, and no measurement in this essay sweeps one, because the structure has no parameter of that kind at all. What it has instead is a dependence on the text: the whole cost is $r$, and $r$ is not something an implementation chooses.

The term that dominates is the one the structure is not about #

This is the third time in four fields, and the pattern is worth naming because it has now been found from three different directions.

The compressed FM-index’s $o(n)$ term — the rank directories, the thing every description calls negligible — is a third of that structure. A windowed estimator’s timestamps, the bits that say when rather than what, are the part that grows. And a run-length index’s sampling, which has nothing to do with runs, becomes half of a structure sized by runs.

In every case the part that eventually dominates is the part the structure is not named after, and in every case it dominates precisely where the structure is at its best. A collection that repeats itself thirty-two times is where the transform’s representation is cheapest, so it is where anything not following the transform is most visible. The better the structure gets at what it is for, the larger the share of it that is doing something else.

What is stored, and what is derived #

One detail of the accounting is worth pulling out because it is the reason the sampling is $2r$ rather than $3r$.

The predecessor structure for $\varphi$ needs, at each anchor, the value $\varphi$ takes there. That value is the suffix-array value of the row above a run’s first row — which is the last row of the previous run, whose value is already in the run-end array. So the anchors carry a run index rather than a position, and the position is read from a table that exists for the toehold.

The two halves of the sampling would each be $r$ values on their own and they share one of the two arrays. If they did not, the structure would be half as big again, and the essay’s headline number would be 10,942 rather than 6,990 for the same information. Which array a value is read from is not an implementation detail when the structure’s whole claim is a size.

The check this leaves behind #

The claim is two-sided and is checked as one: across a collection that grows sixteenfold the run-boundary sampling must grow by less than half, and the regular sampling must grow by at least eight. Either half alone passes on something that is not the claim.

A check that only required the flat line would pass on a structure that had quietly stopped storing samples at all — which is not a hypothetical failure, because a structure with no sampling still answers how many correctly and only fails at where. A check that only required the growing line would pass on any pair of structures at all.

The second check is that the three structures agree on every occurrence of every pattern: the r-index, the regularly sampled index, and exhaustive search. That is the one that catches an off-by-one in the toehold, and it caught two.

The honest limit #

Everything above is measured on collections of a few thousand to a few tens of thousands of characters, and the constants at that scale are large. At one copy the r-index is 21 bits a character; at thirty-two it is one. Neither number is what a real index over a real repetitive corpus achieves, and the sweep is short enough that a term growing like $\log n$ and a term growing like $\log^2 n$ would be hard to separate.

What the measurement does establish is the shape: one policy’s size is a function of a property of the text and the other’s is a function of the text’s length, and on a collection that repeats, those are different functions. The size claim is checked at every point of the sweep and the correctness claim — that the smaller sampling answers the same question — is checked against exhaustion rather than against the other index.

What is not measured here is a real corpus with document boundaries, where $r$ behaves differently because each document’s transform contributions interleave. That is named in the direction and not built, as it was when the run-length index was first weighed.