The last array in the apparatus

Three arrays were needed to answer the question which documents contain this pattern at a cost proportional to the answer rather than to the occurrences.

D, the document array: for each row of the suffix array, which document that row’s suffix belongs to. C, the previous-occurrence chain: for each row, the previous row holding the same document, or minus one. And a range minimum over C, so that the smallest chain value in a range can be found without scanning it.

Muthukrishnan’s observation is that inside the rows for a pattern, the first row belonging to each document is exactly the row whose chain entry falls outside the range. So the distinct documents are the positions where C is less than the range’s start, and finding all of them is a range minimum, a report and two recursions.

Two of those three arrays have since gone, and the two that went were the two that were machinery.

What went, and why each one could #

The chain went because the answer knew. The array the walk never reads is Sadakane’s substitution: the test C[at] < lo asks is this the first row of this document in the range, and a walk that visits the left subrange before the right has already reported every document whose first row lies to the left. So the answer-so-far can answer the question the array existed for, and the array — n⌈log₂ n⌉ bits, exactly the width of the suffix array — goes, replaced by one bit per document.

The replacement is not free and the essay measuring it says so: the bitmap has to be cleared between queries, and clearing it by walking it costs d per query, which on two thousand documents answering a query whose answer is three is worse than the array was. A document already in the answer is where that trap is written out.

The range minimum shrank because it did not need values. The apparatus that is smaller than its index replaced a segment tree with a succinct structure — a Cartesian tree in 2n + o(n) bits — and gained a factor of 3.19 on that part alone. It did not go; it got smaller.

D stayed, because nothing else in the collection knows which document a row belongs to. It is the only one of the three whose contents cannot be derived from anything else present.

Machinery against information #

That distinction is the reason this essay exists rather than being a summary.

C is computable from D in one pass: walk the rows in order, remember the last row seen for each document, write it down. So C holds no information D does not; it is a precomputed answer to a question about D, kept because answering that question at query time was thought to be expensive. It turned out not to be, and the array went.

The range minimum holds no information at all. It is an index over C, and C is an index over D. Two levels of machinery over one array.

D is different. Given the text and the suffix array, D requires knowing where the documents begin — and that is an input, supplied by whoever built the collection. It is not derivable, it is not compressible to nothing, and its size is a real quantity: n⌈log₂ d⌉ bits, which on sixty-four documents over sixteen thousand characters is ninety-eight thousand bits, or twelve kilobytes for a two-kilobyte collection.

There is a third category worth naming because the bitmap that replaced the chain falls into it: state. One bit per document, cleared between queries, holding nothing between them. It is neither information about the collection nor machinery derived from it; it is scratch space whose size is a function of the collection and whose contents are a function of the query.

That is a different accounting problem, and this collection has met it once before in a different field. A structure’s size at rest and its working memory during a query are separate bills, and a structure whose size is o(n) and whose query holds d bits has a term nothing in its own accounting mentions. The listing bitmap is d bits, which on two thousand documents is small; the phrase index’s visited set is proportional to the answer, which is not.

What the apparatus costs now #

On sixty-four documents of two hundred and fifty-six characters, the published apparatus — D, C and a segment tree — is 838,797 bits beyond the suffix array and the text.

Removing C and making the range minimum succinct brings it to 285,460, a factor of 2.9.

Putting D in a wavelet tree, which is where the rest of this strand goes, brings it to 119,972 — 14.3% of where the strand started, and 42.0% of where the previous removal left it.

That last step does two things at once and they are worth separating. It makes D smaller, by the amount its symbol distribution allows. And it makes the range minimum unnecessary, because the distinct symbols of an interval are what a wavelet tree enumerates. The tree answers the question is that argument; this essay is about what is left to answer it about.

What “beyond the suffix array” is hiding #

Every share quoted above is a share of an apparatus, and the apparatus sits on a base that is much larger than any of it. That base deserves a paragraph because it decides whether any of this matters.

On sixty-four documents of two hundred and fifty-six characters the suffix array is n⌈log₂ n⌉ bits and the text is n⌈log₂ σ⌉, and together they are 328,000 bits. The published apparatus was 838,797 — two and a half times the thing it sits on. That is the number the apparatus that is smaller than its index was named after, and it is why the strand kept going: an apparatus larger than its index is not an optimisation, it is a second index.

At 119,972 it is 36.5% of the base, which is a share a reader can consider paying. The whole arc of the strand is a structure going from two and a half times its base to a third of it, and none of the steps changed what the structure computes.

The share also explains why the removals came in the order they did. The chain was the single largest part — n⌈log₂ n⌉ bits, the same width as the suffix array — so removing it was worth more than everything else together. The range minimum was next. D was last because it was smallest, and it is only now the largest part because everything above it has gone.

The shape of the sequence #

D is not an arbitrary sequence and its structure is the whole of what the rest of the strand is about.

Each document appears in D exactly as many times as it contributed characters. So D’s symbol distribution is the collection’s length distribution, exactly — not approximately, not statistically, but by construction. A collection of equal-length documents gives D a uniform distribution and an entropy of exactly log₂ d. A collection where one document holds four fifths of the text gives D an entropy near the binary entropy of four fifths.

That is a strong statement and it makes the compression question answerable in advance. The array is the length distribution is the measurement, and it comes out with a null result on the collection everybody pictures.

The distribution is also the reason a compression result here needs its collection stated, and it is worth being blunt about how strong the effect is. On equal-length documents the entropy of D is log₂ d to three decimal places — the ceiling — so no coding of any kind saves anything. That is not a weak result about a particular coder; it is a statement that the sequence has no redundancy of the zeroth-order kind at all.

Real collections are not equal-length, and the departure is where the whole saving lives. A collection whose lengths fall as one over rank — which is what a real archive of documents tends to look like — gives an entropy of 4.15 against a ceiling of 5.00, and its array compresses to 83% of the plain one. A collection where one document dominates gives 1.69 and compresses to 40%.

Between the null case and the extreme is a factor of two and a half in what the last array costs, decided entirely by a property of the collection that has nothing to do with its text.

Why D is the last one #

There is a reason to expect this strand to stop here, and it is not that nobody has thought of anything.

The three arrays formed a chain of derivations: the range minimum is about C, C is about D, D is about the collection. Removing a derived structure is always available when the thing it derives can be recomputed cheaply enough at query time, and each removal in this strand found exactly that. There is nothing below D to derive it from, because the collection’s document boundaries are the input.

What is available is representation. D can be stored more cheaply — that is the entropy question — and it can be stored in a form that answers more questions, which is the wavelet tree. Neither of those removes it.

The one thing that would remove D is a different formulation of the problem. If the query were which documents, answered by a structure over documents rather than over rows — an inverted index — then D would not exist, and neither would the suffix array. That is a different design with different costs, and the comparison between the two is not made here.

There is a fourth thing that could go, and it is worth naming even though this strand does not take it: the suffix array itself. Every method here reads the rows of a pattern out of a suffix array and the suffix array is n⌈log₂ n⌉ bits, which is larger than the apparatus above it by a wide margin. An index larger than what it indexes is where that was first measured, and the index that is smaller than the text is where it was replaced with a self-index.

Replacing it changes the accounting above completely: the base against which the apparatus is a share falls by a factor of several, so an apparatus at 36% of a suffix array plus a text is a much larger share of a self-index. That comparison is not drawn in this strand, and it is the honest limitation of every share quoted here — the denominator is the uncompressed base.

Doubling the document count raises the ceiling by a bit and moves the equal-length case exactly with it, which is what “by construction” means and is worth seeing twice. The three uneven collections move differently: the one-over-rank shape gains almost the whole bit, because doubling the documents doubles the number of small ones and the distribution’s shape is preserved; the dominated collection gains almost none, because its entropy is decided by the one large document and adding thirty-two more tiny ones changes very little.

So the saving — the gap between the entropy and the ceiling — grows with the document count on a skewed collection and stays at zero on an even one. That is the direction a reader would want, since the array is also getting wider, and it means the compression is worth more on exactly the collections where the array is largest.

The pattern across three removals #

Three arrays, three removals, and the three had different reasons — which is worth noticing because it means there is no single trick being applied.

The chain went because a traversal order made its test answerable. The range minimum shrank because a representation held the same information in fewer bits. And the range minimum goes entirely, in the next essay, because a different structure over D answers the same question as a side effect of holding D.

Those are three separate techniques and only the first is specific to this problem. The second and third are general moves — represent it better, and check whether something already present answers it — and both were available from the first day.

That is the uncomfortable part of the summary. An apparatus that shrank by a factor of seven over three passes did not require any new idea about document listing. It required noticing three times that something already present was doing a job an extra array had been built for.

The habit that produced all three is worth stating, because it is the actionable part. When a structure holds an array whose entries are derived from another array it holds, ask what question the derived array answers and whether the traversal, the representation or a neighbouring structure already answers it. Three times out of three in this apparatus the answer was yes.

The corresponding warning is that each removal made the query do more. The chain’s removal added a bitmap and an order constraint; the succinct range minimum’s operations cost more than a segment tree’s per query; the wavelet tree’s descent does more work per document than a range-minimum step. The apparatus is seven times smaller and its query is not seven times cheaper — what the chain cost measured that trade for the first removal and found the work identical, which was a better outcome than expected and is not the general case.

Reading the four methods against each other #

The four rows of the method plate are worth walking once, because they are the strand’s whole history in one picture and the ordering is not what a reader would guess.

Reading every occurrence holds only D. It costs the occurrences — fifty-four operations on the query drawn — and it is proportional to the range rather than to the answer, which is the defect the whole apparatus exists to fix.

The published range-minimum method holds D, C and the tree, and costs two hundred and sixty-seven operations inside the structure for the same eight documents. That is five times what reading every occurrence cost. The asymptotics are right and the constant is not: a range-minimum query on a segment tree visits a logarithmic number of nodes and the walk performs one per reported document plus one per pruned subrange, so the constant multiplying the answer is large.

Removing the chain brings it to eighty-three, which is still above the fifty-four that reading every row cost.

The descent over a wavelet tree brings it to thirty-two, which is finally below. That is the first method in the strand’s history that is both proportional to the answer and cheaper than the naive alternative on the collection it was measured on.

That ordering says something about how the earlier essays should be read. The cost that is the size of the answer established the proportionality and drew the crossing where the constants put it. The apparatus has been shrinking ever since, and the crossing has been moving with it, and nothing in the strand had put the constant below the naive method’s until the last array became the whole apparatus.

What is measured from here #

The rest of this strand is about the last array, and it has four questions in it.

How far D compresses, which is the length distribution and has a null case. What the floor under that compression is, which is a code word being at least one bit. Whether the tree that compresses it can also answer the query, which removes the range minimum. And what the answer’s order costs, which is the one remaining trade.

None of those is about the chain, the range minimum, or the walk. The strand has moved from the machinery to the thing the machinery was reading, and that is where an apparatus ends up when its derived parts have been removed one at a time.