A sampling that costs more than the array

Two essays ago this strand replaced a suffix-array sampling proportional to the text with one proportional to the number of runs in the transform, and the collection it was measured on repeats itself thirty-two times.

Here is the same structure on eight thousand characters of four-symbol text, which repeats itself hardly at all. The sampling is 271,565 bits. Keeping every suffix-array value — the thing a sampling exists to avoid — costs 131,088.

The condition, which is arithmetic and not a caveat #

A run-boundary sampling keeps $2r$ suffix-array values. A regular sampling at one value in $s$ keeps $n/s$ of them. So the first is smaller exactly when

$$2r < n/s, \qquad \text{that is} \qquad \frac{r}{n} < \frac{1}{2s}.$$

At one value in thirty-two that threshold is 0.0156 runs per character. Measured: a collection of thirty-two copies is at 0.017, an eight-copy collection at 0.045, an internally repetitive text at 0.029, ordinary English at 0.292, and a four-symbol text at 0.753.

One of those five is near the threshold and four are above it, three of them by more than an order of magnitude. The structure is smaller on the collections it was designed for and larger on everything else, which is a sentence its own literature contains and which is easy to read as a hedge rather than as a factor of fifty.

Two point zero seven #

The last row of the plate at the top is the one worth dwelling on, because it is not a near miss.

On four-symbol text, $r/n$ is 0.753. Two values per run is therefore 1.5 values per character, and the whole suffix array is one value per character. The sampling is half as large again as the array it stands in for, before the predecessor structure that $\varphi$ needs is added, and with it the ratio reaches 2.07.

A structure in that state is not a compressed index with a poor constant. It is a suffix array with extra machinery, answering the same questions more slowly, and its locate is one predecessor query per occurrence where an array’s is a read.

The reason is not subtle and it does not need a proof. The transform of a text with no long repeats does not cluster: neighbouring rows in the suffix array begin with the same character and their preceding characters are unrelated, so a run of length one is the normal case. The measure the structure is proportional to has degenerated to the length of the text, and a structure proportional to a degenerate measure is proportional to $n$.

The floor underneath, and what it does not say #

There is a lower bound in this collection on structures sized by a run count, and it is worth putting beside the failure above because it settles what kind of failure this is.

A floor under a run count counts the texts with at most $r$ runs and takes the logarithm: a structure whose size is a function of $r$ has to give a different bit string to every one of them, so it needs $\log_2 N(n,\sigma,r)$ bits. That argument is about what any such structure must spend, and it says nothing about what this one does spend.

The two are different claims and it is easy to read the first as excusing the second. The floor says a run-based representation cannot be arbitrarily small; the measurement here says a particular run-based sampling is, on a particular text, larger than the array it replaces. Neither implies the other, and the gap between them on short texts is enormous — a floor of 7.27 bits against a measured 142 at twelve characters, as that essay reports.

What the floor does supply is the shape of the excuse that is not available. A structure sized by $r$ cannot be rescued on non-repetitive text by a better encoding of the same information, because the information itself is $\Theta(n)$ when $r$ is $\Theta(n)$. The failure is in choosing the measure, not in coding it.

The same failure at one copy #

The condition bites on collections as well as on texts, and the sweep this strand is built on contains its own counterexample at the left-hand end.

At one copy — a single 512-character English text — the r-index is 10,974 bits and the run-length index with a regular sampling at one value in thirty-two is 3,939. Nearly three times larger. The two structures hold the same transform, represented identically, and the entire difference is the sampling: 7,324 bits against 289.

That point is on every sweep plate in this strand and it is the first point of each of them. It is not hidden, and it is also not what a reader looking at a falling line takes away, which is why it gets an essay rather than a footnote. The index that stores the runs made the same shape of claim about the transform and drew the negative half on the same axes for the same reason.

What a rate can do that a measure cannot #

There is a defence of the run-boundary sampling that has to be dealt with, because it is correct and it is not enough.

The comparison above is at a fixed rate of one in thirty-two, and a rate is a choice. Faced with four-symbol text an implementer would not use one in thirty-two; they would use one in 128, or one in 1,024, and the sampling would be 5,397 bits or 674, and the structure would be far smaller than the r-index still.

That is exactly right, and it is the point. A rate can be turned down and a measure cannot. The cost of turning it down is on the other axis — one value in 1,024 walks up to a thousand LF steps per occurrence — and the choice belongs to whoever knows how often locates happen.

So the correct statement of the trade is not that one policy is better. It is that a rate offers a curve and the run count offers a point, and on a repetitive collection the point is off the good end of the curve while on ordinary text it is off the bad end. Every occurrence at the same price draws the good case; this is the same picture with the axes’ meaning unchanged and the text changed.

The measure was not chosen to be small #

It is tempting to treat this as a design flaw, and it is worth resisting because the same property is what makes the good case work.

$r$ is not an approximation to anything. It is a count of runs in a particular permutation of the text, and its value on a text with no repeats is a fact about that text rather than a failure of the structure. What the structure does is make its own size a function of that count — faithfully, in both directions.

That faithfulness is what repetition is not entropy has been arguing since the measure was introduced. An entropy cannot see a copy: two copies of a text have the symbol distribution of one, so $nH_k$ doubles when nothing new arrives. $r$ can see a copy and does not move. The price of a measure that can see one thing is that it is blind to another, and here the blindness is that $r$ has no idea whether $n$ is large.

Where the crossing actually sits #

The threshold $r/n < 1/2s$ has a rate in it, so “where does the r-index win” is not a single number. It is a curve in two variables, and a reader deciding between structures wants it stated in the direction they will use.

Fix the locate cost instead. At one predecessor query per occurrence the r-index costs $2r$ values plus its predecessor structure; the only regular rate that matches is one value in one, which costs $n$ values. So at equal speed the r-index wins whenever $2r < n$ — that is, whenever the transform has fewer than half a run per character.

Measured against that threshold, the five texts read: 0.017, 0.045, 0.029, 0.292 and 0.753. Four of the five are under a half and the four-symbol text is over it. At equal locate cost the structure wins on ordinary English too, by 1.25 times, and loses on four-symbol text by 2.07.

That is a different and more useful statement than the one the fixed-rate plate makes, and it is the reason this essay carries both.

The term that grew, one strand later #

This is the second time in this strand that a structure’s dominant part has turned out to be the one it is not named after, and the two are worth reading together because they point in opposite directions.

What is still proportional to n found a run-length index whose transform-sized parts grew 1.45 times across a collection while its sampling grew 18.3 times, until half the structure was the part that had nothing to do with runs. The repair was to make the sampling a function of $r$ as well.

This essay is the repair’s own failure case: once every part is a function of $r$, a text where $r$ is $\Theta(n)$ makes all of them proportional to the text, and there is no longer a small part to point at. The structure is uniformly bad rather than lopsided.

That is a better failure and worth saying so. A lopsided structure hides its cost in a term described as negligible; a uniform one is exactly as large as its measure says it is, and its measure is a number anybody can print in one pass. The earlier defect needed a plate with the parts separated to see; this one needs a division.

Three ways to be wrong about a structure sized by a measure #

The general form is worth extracting, because this collection has now hit it three times in three fields and each time it looked like a different mistake.

Quoting the size on the collection the structure is for. Every published size for a run-length structure is on a repetitive corpus, correctly, and every one of them is an upper bound of the form $O(r\log(n/r))$ that is silent about what $r$ is on anything else. The bound is true; it becomes a claim about a structure only after $r$ is measured.

Assuming the measure is bounded. $r$ is at most $n$ and its worst case is reached, near enough, by a random text over a small alphabet. A structure whose size is $\Theta(r)$ has a worst case of $\Theta(n\log n)$ bits, which is a suffix array.

Comparing at fixed size instead of at fixed speed. Two structures that answer a question at different prices per answer cannot be ranked by their sizes, and the fixed-rate comparison in this strand’s first essay reads as a near-tie exactly because it makes that mistake deliberately, so that the essay after it can correct it.

The check that must fail #

The gate for this claim is written as a rejection rather than as a measurement, and the direction matters.

It requires that on English and on four-symbol text the run-boundary sampling is larger than a regular sampling at one value in thirty-two. If it ever stops being larger, something has changed that the rest of the strand’s plates would not notice — a sampling that quietly stopped storing run ends, say, which halves the size and breaks only the locate.

The companion check requires the opposite on a repetitive collection, and the pair is what makes either one worth running. A check that only demanded the win would pass on a structure that had stopped measuring the text at all; a check that only demanded the loss would pass on a structure with no sampling in it.

An index is allowed to be larger than its text #

One more comparison belongs here, because a reader who has followed the field from its first essay will already be holding it.

An index larger than what it indexes opened this field with the observation that a suffix array plus its text is about five times the file on ordinary English, and that the phrase “smaller than the text” names four different numbers depending on which size of the text is meant. The r-index on four-symbol text is 325,218 bits over 8,193 characters — nearly forty bits a character, against a packed text’s two.

So the structure being larger than its input is not by itself a scandal; every index in this field except the compressed ones is. What makes this one a finding is that it is larger than the structure it was derived from, on a text where the derivation’s premise is false, while carrying the machinery that only pays off where the premise holds.

The text that does not have to be kept is the essay that makes the size comparison meaningful at all, by establishing what “self-indexing” has to mean before a size can be quoted. Every structure in this strand is measured under that seal, including this one in its failure.

What a practitioner should take from this #

Three sentences, and none of them is “it depends”.

Measure $r/n$ on the actual corpus before choosing the structure — it costs one transform and one pass, and it decides the question. If it is under about 0.02, the run-boundary sampling is smaller than any rate that matches its speed and the decision is made. If it is over a half, the structure will be larger than the suffix array it replaces and the question is which regular rate to use.

The measurement is cheap because $r$ is not an asymptotic quantity, and it is the kind of number a limit is not a prediction says to take rather than to reason about. It is a number a program prints, on the corpus in hand, before any structure is built — which is the whole argument of fitting a class to measurements applied to a size rather than to a running time.

The equal-speed comparison holds at exactly one rate #

At equal locate cost the structure wins on ordinary English too is the most favourable sentence on this page, and it is worth checking which rate makes it true, because the answer is one.

The condition is $r/n < 1/2s$. English is at 0.292, so it clears the threshold only when $1/2s > 0.292$ — that is, when $s < 1.7$, which for an integer rate means $s = 1$. At $s = 2$ the threshold is 0.25 and English is already over it; at the strand’s usual thirty-two it is over by nineteen times.

And $s = 1$ is not a sampling. It is the whole suffix array, kept. So the equal-speed comparison is the r-index against an uncompressed array — the one case where the r-index is 1.25 times smaller and, per occurrence, one predecessor query slower than an array read.

Which puts the sentence’s own footing in question, in the way this page is otherwise careful about. Calling those two costs equal converts a predecessor query into an array read at par, and a predecessor query is a binary search over the samples or a rank on a sparse vector — several array reads, on the same accounting that prices a succinct range-minimum query at nine or ten. The comparison that flatters the structure most is the one that sums unlike units, which is the habit this collection refuses everywhere else.

Redo it at an honest rate. If a predecessor query is worth about ten array reads, the matching regular sampling is the one whose mean walk is ten LF steps — a rate of about twenty — and the threshold becomes $r/n < 0.025$. Measured against that: the thirty-two-copy collection at 0.017 clears it, the internally repetitive text at 0.029 is just over, and English at 0.292 misses by a factor of twelve.

So the strand’s original fixed-rate statement was closer to right than the reframing that replaced it. The r-index is smaller at matched speed on repetitive collections and on nothing else, and the threshold is near 0.02 rather than near 0.5 — within a small factor of the 0.0156 the one-in-thirty-two plate uses, rather than an order of magnitude away from it.

That does not weaken every occurrence at the same price’s result, which is about the locate being flat per answer rather than about the size. It narrows this page’s own most generous claim back to the band the sampling that follows the runs measured in, and it removes the one line here that a reader could take as licence to build the structure over ordinary prose.

The honest limit #

Four of the five texts here are generated rather than collected, and the generators are this collection’s own: an English-like source, a four-symbol source, a periodic one and a uniform one. Their run counts are plausible and they are not measurements of any real corpus, so the ordering is the claim and the exact ratios are properties of these sources.

The other limit is the length. At eight thousand characters, $\lceil\log_2 n\rceil$ is thirteen and the predecessor structure’s low parts are small; both grow slowly with the collection, and a sweep over four doublings cannot separate a term in $\log n$ from one in $\log^2 n$. The crossing condition itself has no such problem — it is a comparison of counts of values, and the widths cancel.

What is missing is a corpus where $r/n$ sits near the threshold rather than an order of magnitude either side of it. Everything measured here is decisively on one side or the other, and the behaviour of both structures in the middle is an interpolation nobody has run.