What the locating apparatus becomes

A self-index answers three questions and only two of them need the sampling.

How many is a backward search: m ranks on the wavelet tree, no sampling involved. What does the text say is an extraction: LF steps from row zero, no sampling involved. Where is a locate, and a locate is the whole reason the sampled positions and the mark vector exist.

So the locating apparatus is separable, and its share of the structure is a number a system can look at and decide about.

The share, plainly represented #

On sixteen thousand characters of English-like text:

One in four: 49.1% of the index. The apparatus is nearly half the structure. One in eight: 36.9%. One in sixteen: 28.3%. One in thirty-two: 23.0%. One in sixty-four: 20.1%. One in a hundred and twenty-eight: 18.5%.

The curve falls steeply and then flattens. Between one in four and one in thirty-two it halves; between one in thirty-two and one in a hundred and twenty-eight it falls by a fifth.

What is left at the flat end is the marks: 16,385 bits of an apparatus totalling 18,320. Eighty-nine per cent of the flat part is one array.

The share, sparsely represented #

Replace the marks with an Elias–Fano array and the same sweep gives:

One in four: 49.4%. Slightly worse, because at that density the sparse representation costs a couple of bits more than the plain vector and the index it is a share of is a couple of bits smaller. One in eight: 34.2%. One in sixteen: 21.6%. One in thirty-two: 12.7%. One in sixty-four: 7.1%. One in a hundred and twenty-eight: 3.8%.

No flattening. The curve keeps falling because both parts of the apparatus now shrink with the rate.

The one thing worth staring at in that pair of lists is the sign change at the dense end. At one in four the sparse representation makes the apparatus’s share slightly larger while making its bits slightly smaller — 77,842 against 77,840, a difference of two bits in the wrong direction on the apparatus, and a smaller index for the share to be of.

Two bits. That is not a measurement of anything except that the two representations cost the same at that density, which is exactly what where the sparse representation loses predicts: the crossing is at about one row in 3.5, and one in four is just past it.

It is worth reporting rather than rounding away because a share that moves the wrong way is the sort of thing that reads as an error when it is the crossing being crossed.

What the index costs #

The shares are one way to read it and the totals are the other, and the totals are what a system pays.

At one in thirty-two the index goes from 104,720 bits to 89,150 — a saving of 15,570, or 14.9% of the whole structure.

At one in a hundred and twenty-eight: 98,960 to 80,743, 18.4%.

At one in four: 158,480 to 157,696, 0.5%.

So the saving spans nothing to nearly a fifth across the dial, and which end a system is on decides whether the change is worth making at all.

Why the dense end saves nothing #

At one in four the sampled positions are 61,455 bits and the marks are 16,385 — the values dominate four to one, so shrinking the marks by five moves the apparatus by a fifth of a quarter.

The crossing between the two parts is at s = ⌈log₂ n⌉, which at this size is fifteen. Below it the values dominate and this strand’s work is nearly irrelevant; above it the marks dominate and it is most of the apparatus.

That is a clean statement and it is the reason the array that says where is twice the samples leads with the ratio rather than with the sizes.

There is a way of putting the flat end that makes the whole strand’s motivation clear in one sentence. At one row in a hundred and twenty-eight, an index keeps a hundred and twenty-nine suffix-array values and spends sixteen thousand three hundred and eighty-five bits saying which rows they belong to.

A hundred and twenty-nine numbers, and their index is a hundred and twenty-seven times their count in bits. Written that way it is obviously wrong, and written as “n bits of marks, which is o(n) relative to the wavelet tree” it is not.

What the apparatus is a share of #

Every number above is a share of a whole index — wavelet tree, directories, C table, marks and sampled positions — and it is worth saying what that base is, because a share of a differently-defined base is a different number.

On this collection at one in thirty-two the parts are: wavelet tree payload 66,724, rank directories 13,626, marks 16,385, sampled positions 7,695, C table 290. Total 104,720.

The apparatus is the last two but one: 24,080 of 104,720, or 23.0%.

A base excluding the directories would give 24.5%. A base including a stored copy of the text — which a non-self-index would have — would give about 15%. And a base of only the wavelet tree’s payload, which is the number sometimes quoted as “the index”, would give 36%.

Four bases, four numbers, one structure. A sixth of what, exactly is the essay this collection wrote about exactly that, and the convention it settled on is that a share names its base — which is why every figure here says “of the index” and the parts are listed.

What a system actually chooses #

The dial is a time-space trade and the apparatus’s share is one half of it, so it is worth putting the other half beside these numbers.

A locate walks s/2 rows on average. At one in four that is two LF steps; at one in a hundred and twenty-eight it is sixty-four. Each LF step is a rank and an access on the wavelet tree — several bit-vector operations — so a locate at the sparse end costs a few hundred operations against the dense end’s ten.

A query returning ten thousand occurrences therefore spends a few million operations at one in a hundred and twenty-eight and a few hundred thousand at one in four.

So the choice is: an index half of which is locating machinery and a locate costing ten operations, or an index a fifth of which is machinery and a locate costing three hundred. Neither is wrong and the workload decides.

What this strand changes is the first number at the sparse end. The same locate cost at one in a hundred and twenty-eight now comes with an apparatus of 3.8% rather than 18.5%, which moves the trade — a system that had settled at one in thirty-two for size reasons can go sparser for less size than it expected.

An index that answers two of the three questions #

The separability of the apparatus has a consequence worth drawing out, because it describes a structure some systems actually want.

An index with no locating apparatus at all answers how many and what does the text say and cannot answer where. At one in thirty-two that structure is 80,640 bits against the full index’s 104,720 — 77% of it, or a saving of 23%.

That is not a hypothetical. A system counting occurrences for a ranking function, or checking membership, or extracting a known region, needs none of the sampling. And the reverse half of a bidirectional index needs none of it either, which is the structure an index that cannot locate builds.

What makes the apparatus separable in the first place is that its two arrays are read only by locate. The wavelet tree is read by everything; the C table is read by everything; the marks and the samples are read by one method. So the accounting can be split cleanly and the structure can be built without them, which is the check that the separation is real: the stripped index raises when asked to locate rather than returning something.

An object that held the arrays and promised not to read them would have the same size as one that uses them, and this collection has had to guard against that shape three times.

The other structure this changes #

The apparatus’s share matters most where somebody is trying to remove it, and there is a strand in this collection about exactly that.

A bidirectional index is two self-indexes, and the reverse one is asked for ranks and never for positions — so its locating apparatus can go entirely. An index that cannot locate is the structure and the half that is never asked where is the measurement, which put the saving at 16.7% of both halves at one in thirty-two, falling to 13.5% and flattening.

The flattening was the marks. Half of what was being dropped was one badly represented array, and with the array represented properly the saving falls to 1.8% at one in two hundred and fifty-six.

The floor was the marks is that retraction, and it is the strand’s largest result: a saving of a sixth becoming a saving of a fiftieth, on the same structure at the same rate, because one component was replaced.

Reading the two curves as a decision #

Put the two curves together and a system has three configurations rather than two, which is more useful than either curve alone.

Dense sampling, either representation. One in four, apparatus about half the index, locate in two LF steps. The representation does not matter; take the plain vector for its simpler operations.

Sparse sampling, plain marks. One in a hundred and twenty-eight, apparatus 18.5%, locate in sixty-four steps. This is the configuration a system arrives at by turning the dial until the size stops falling — and the size stops falling because of the marks, so the system has been stopped by an artefact.

Sparse sampling, sparse marks. Same locate cost, apparatus 3.8%. The configuration the second one was trying to be.

The middle one is the interesting entry. It is what a size-conscious system tuning its sampling rate would land on, because the dial stops paying past a point and there is no reason to keep turning it. With the marks represented properly the dial keeps paying, so the same tuning process lands somewhere else.

That is a nice illustration of a general thing: a flat region in a tuning curve is a place systems accumulate, and if the flatness is an artefact then so is the accumulation.

What the wavelet tree is doing meanwhile #

The apparatus’s share is a ratio and ratios have two ends, so it is worth saying what the denominator is made of as the numerator shrinks.

At one in a hundred and twenty-eight with sparse marks, the index is 80,743 bits and the apparatus is 3,095 of them. The other 77,648 is the wavelet tree’s payload, its rank directories and the C table — which is to say, the transform and the machinery for reading it.

That is the structure a self-index is supposed to be: nearly all of it is the text, compressed, and a few per cent is the ability to say where things are.

At the other end of the dial it is not. At one in four the index is 157,696 bits of which 77,842 is the apparatus, so half the structure is machinery for locating and half is the text. A reader told that a self-index is “the text in n·H₀ bits plus o(n)” and shown that configuration would reasonably ask which part is the o(n).

The answer is that the apparatus is not o(n) at any fixed sampling rate. It is (n/s)log n + n, both linear in n, and it becomes o(n) only in the limit where s grows with the collection — which no implementation does, because a locate would then take unbounded time.

An index larger than what it indexes is this collection’s first essay on a size that was not what its account said, and this is the same observation about a smaller component of a better structure.

What is left in the apparatus #

At one in a hundred and twenty-eight with sparse marks, the apparatus is 3,095 bits: 1,935 of sampled positions and 1,160 of marks.

The positions are n/s values of ⌈log₂ n⌉ bits, and there is nothing obviously compressible about them — they are suffix-array values at scattered rows, which is to say arbitrary numbers.

The marks are already at their information content plus about half a bit an element.

So the apparatus is close to what it has to be, and the remaining question is not representation but policy: whether to sample by row at all. A function with r pieces is the alternative — sampling at run boundaries, which is 2r values and no marks whatsoever — and on a repetitive collection it is a different structure with a different bound.

That is the honest end of this strand. The apparatus can be made small by representing it well, and it can be removed by changing what is sampled, and the second is a bigger change with a narrower range of applicability.

What the numbers look like as a text grows #

Everything above is at sixteen thousand characters and the shares move with n, so it is worth saying which way.

The wavelet tree’s payload is n·H₀ — linear in n with a constant that is the entropy.

The sampled positions are (n/s)⌈log₂ n⌉ — linear in n times a logarithm, so they grow slightly faster than the payload.

The plain marks are n — linear, constant one.

The Elias–Fano marks are (n/s)(2 + log₂ s) — linear times a constant that depends on s and not on n.

So as the collection grows, the sampled positions become a larger share (the logarithm) and the marks become a constant share either way. The apparatus’s share therefore rises slowly with n, at a fixed sampling rate, and the crossing between the two parts moves right by one for each doubling.

That is a mild effect and it means the numbers above are stable enough to use: a million-character index at one in thirty-two has an apparatus of about 26% plainly and 14% sparsely, against the 23% and 12.7% measured here.

The one thing that does change is that the saving grows, because the marks’ share is constant and the sampled positions’ logarithm makes the base larger. A larger collection gets slightly more from this substitution, which is the convenient direction.

The general point about a component’s share #

Two things this measurement makes available that a total does not.

Where to spend effort. A component at 23% of a structure is worth improving; one at 2% is not. That is obvious and the measurement is what turns it from a guess into a decision — and the answer here depends on the sampling rate by a factor of forty.

Whether a curve that flattens has a term worth attacking. The apparatus’s plain curve flattens at 18.5% and the flat part is 89% one array. A curve that flattens is a curve with a constant in it, and the constant is where the next result is.

That second is the reusable one and it is the reason this strand exists. Two earlier essays drew the flattening curve and both named the marks as its cause, correctly, in their prose. Neither priced the alternative, because a named cause reads as an explanation rather than as a target.

There is a third thing and it is smaller and worth having. A component’s share is a function of a dial, and the dial has to be on the plate. The apparatus is 49% of this index and 18% of it and 3.8% of it, all true, all of the same structure, differing only in a setting. A sentence saying “the locating apparatus is about a fifth of a self-index” is a sentence about one configuration, and it has been written in this collection more than once.

The convention that follows is the one every plate in this strand carries: a figure about the apparatus has the sampling rate on its axis, and a number quoted from one has the rate beside it. That is not a style rule; it is the difference between a measurement and a number.

It is worth stating what that convention costs, because a rule that costs nothing is usually a rule nobody obeys. Putting the rate on the axis turns a bar chart into a sweep, which is a wider plate, more work to build and more work to read. The number it produces is also less quotable: a curve cannot be pasted into a summary the way a percentage can. So the convention is paid for in the currency this collection is short of, which is the reader’s attention — and it is still the right trade, because the alternative is a quotable number that is true of one configuration and read as true of the structure.

The same argument decides how this strand reports its saving. A share that moves with a dial has a range, and the range belongs beside the figure rather than in a sentence somewhere behind it.