Two thousand documents of two hundred characters

Every collection this field has measured here has had the same shape: eight or twelve documents, ten or twelve thousand characters each, joined into one string.

That is what a version history of one file looks like, and it is the case a compressed index is built for. It is not what a document collection usually is.

Here is the other shape, measured: 2,214 documents with a median of 230 characters, the shortest 80 and the longest 594. It is every figure caption in this collection, one document each, and it is real prose written to one form by one hand — which makes it the kind of collection a search box actually sits in front of.

Nothing about it is exotic. Every term in a document index changes anyway, and one of them changes by a factor of seventy.

The term that knows how many documents there are #

A document index is four things beyond the text: a suffix array, an array saying which document each row belongs to, a chain of previous occurrences, and a range structure over the chain. A list of documents is not a list of occurrences is what they are all for.

Only one of them knows the document count. The document array is n⌈log₂ d⌉ bits — one document number per row of the index — and d is inside the logarithm.

On 82 documents that is 7 bits a row. On 2,214 it is 12. The same collection, the same characters, the same suffix array — and the document array goes from 917,791 bits to 1,585,992, which is 67% of the suffix array beside it rather than 39%.

That is the whole of the difference between the two rows on the plate, and it is a number that appears in no size formula quoted in this field, because the formula is usually written O(n log d) and read as though d were small.

What the separators cost when there are two thousand of them #

The second term is the one one separator or one for each priced, and its arithmetic was exactly right and its example was too small to show it.

A construction that needs every suffix comparable — a suffix array over a collection, a wavelet tree over its symbols — needs the documents separated by characters that occur nowhere else. One shared separator costs one symbol. A separator per document costs d symbols, and the alphabet is inside a logarithm in every size here.

On twelve documents the alphabet goes from 96 symbols to 97, ⌈log₂ σ⌉ stays at 7, and distinct separators cost nothing at all. That is the measurement this collection published, and it is exact.

On 82 documents the alphabet goes from 115 to 183, crosses 128, and the packed collection gets 14.3% larger.

On 2,214 documents the alphabet goes from 115 to 2,321, crosses 128 and 256 and 512 and 1,024 and 2,048, and seven bits a character becomes twelve. The packed collection gets 71% larger, for punctuation nobody reads.

The prediction was nothing at all until σ + d crosses a power of two, and then a whole bit per character. It crosses five times here. A claim that was true and looked like a rounding note turns into the largest single line in the size table, and the only thing that changed is the shape of the collection.

The artefacts, per character rather than in total #

The third term is the strings a concatenation invents. The occurrences a join invents counted them: exactly (m − 1)(d − 1) windows span a join, and each of them is a string the index will report and no document holds.

That count follows the document count and not the size of the collection, which is a sentence that means very little at twelve documents and a great deal at two thousand.

The same 131,072 characters produce 405 spanning windows at six characters when they are 82 documents and 11,065 when they are 2,214. Per thousand characters that is 3.09 against 85.15 — a factor of twenty-eight, from cutting the same text into more pieces.

And they are almost all real artefacts rather than accidental strings: 97.0% of them occur in no document at all on the essays, 96.5% on the captions, and 100% on a version history whose documents are near-copies. At twelve characters the share is 100% everywhere, because a twelve-character string that straddles a boundary is essentially never a string the collection contains for another reason.

So the fix — a separator — is not optional on this shape, and the fix is the thing the previous section priced at 71%. That is the trade in one sentence: on many short documents either the separators are paid for or the wrong query is answered eighty-five times per thousand characters.

Why nobody measured this shape #

It is worth asking why every collection in this field arrived as a dozen long documents, because the answer is not carelessness and it decides how much of the earlier work travels.

The first reason is that the compressed-index literature is largely about repetitive collections, and the canonical repetitive collection is a version history: successive revisions of one thing, each nearly identical to the last. That is genuinely a dozen documents of ten thousand characters, and it is the case where a self-index is worth building, because a structure proportional to the number of phrases in a parse is small exactly when the documents are near-copies of each other.

The second reason is that a generated collection makes the wrong shape easy. The model here — a base text, k copies, a fraction of the characters replaced — produces documents of exactly one length by construction, and the parameter that would make them many and short is the same parameter that makes each of them too short to hold a planted pattern several times. The dial that has no setting is about the model failing to reproduce a real history’s repetition; this is the same model failing to reproduce a real collection’s shape, one axis further out.

The third reason is that the earlier numbers were not wrong. A document array at 4 bits a row, a free separator, half a spanning window per thousand characters — those are the correct numbers for a dozen documents, and there was nothing in any of them to suggest that one of the three would grow by a factor of seventy on a collection that is no larger.

What makes it findable at all is having a real collection of the other shape lying around. This one is 2,214 captions written over the life of an essay collection: nobody made it to be a corpus, which is exactly what makes it worth measuring.

Which structures notice and which do not #

Worth being precise about, because “everything gets worse” is not a measurement.

The suffix array does not notice. It is n⌈log₂ n⌉ bits whatever the collection is cut into, and n barely moves — 2,213 separator characters on 546,997 is 0.4%.

The text does not notice, unless the separators are distinct, in which case it is the 71% above.

The chain of previous occurrences does not notice. It is n⌈log₂ n⌉ bits: one row number per row, independent of how many documents those rows belong to.

The range structure does not notice, for the same reason — it is a structure over the chain’s shape.

The document array notices, at ⌈log₂ d⌉ bits a row.

And a reported bitmap, if a listing uses one, notices least of all: d bits in total, which is 2,214 bits against the 1.5 million the range structure costs. The array the walk never reads is what makes that substitution available, and this is the shape on which it is worth the most.

What a real short document is like #

The other half of “many short documents” is that they are short and uneven, and the unevenness is not decoration.

The lengths here run from 80 characters to 594, a spread of 7.4 — and documents that are not the same length is the essay about what that does to a listing’s cost model, which assumes nothing about lengths and is quietly measured on collections that have only one.

A collection trimmed to a common length is a different object. Cutting all 2,214 documents to the mean of 59 characters at the size these plates are drawn at would drop 1,226 of them below their own length and throw away 15.6% of the collection — and it would make every plate on this page look tidier and mean less.

That is the same discipline as keeping the alphabet real. A model that hands back documents of exactly 256 characters is answering a question about a collection that does not exist, and the answer will be right — it is the same arithmetic — and its constants will be somebody’s choice.

The one thing that gets easier #

Not everything about many short documents is worse, and the exception is instructive.

A pattern occurring in a short document occurs in it once. On this collection the most frequent six-character string occurs 543 times across 522 documents, which is 1.04 occurrences a document — so the answer to “which documents” is nearly the same size as the list of occurrences, and every structure that exists to make the answer cheaper than the occurrences has nothing to do.

The crossing that never arrives is that result taken seriously. It is a negative one, and it is the most useful thing on this page for anybody choosing a structure: the apparatus that makes document listing output-sensitive costs bits proportional to the index and buys nothing at all on a collection whose documents are short.

The shape parameter, as an axis #

The tidy way to hold all of this is to stop treating the document count as a property of a collection and start treating it as an axis, exactly as the character count is.

Fix the characters and sweep the documents. Every term then sorts itself into one of three behaviours, and the sorting is mechanical rather than a matter of judgement: the terms that do not contain d at all — the suffix array, the chain, the range structure, the text under a shared separator — are flat lines. The term that contains ⌈log₂ d⌉ is a staircase, rising by one bit a row each time d crosses a power of two. The term that contains d itself is the bitmap, which is d bits in total and is invisible at every point on the axis.

Drawn that way the plate stops being a comparison of two collections and becomes a statement about a family, and it says something a comparison cannot: the crossing point where the apparatus stops being smaller than the index it sits on is at about two thousand documents for this amount of text, and it moves with n because the flat terms grow with n and the staircase does not.

That is why the size plate on this page sweeps rather than tabulates. Two rows would have shown that many short documents cost more; the sweep shows which term costs more, that it is a staircase rather than a slope, and where the crossing is — which is the number somebody choosing a structure actually needs.

The other axis, the one this page holds fixed, is how long the documents are relative to the patterns being searched. That one decides whether the listing apparatus is worth having at all, and it has a page of its own.

The crossing is a step, and it is at a document length #

Treating the document count as an axis pays off further than the section above takes it, because once every term is sorted into flat, staircase or invisible, the crossing can be solved for rather than read off a plate.

Write the chainless apparatus as bits a row. It is $\lceil\log_2 d\rceil$ for the document array plus a constant for the range structure, and the index it is measured against is another constant — neither of which contains $d$ at all. Two points from the size sweep pin both: 0.58 at four documents and 1.01 at 2,214. Since $\lceil\log_2 4\rceil = 2$ and $\lceil\log_2 2214\rceil = 12$, ten bits a row are worth 0.43 of the index, so the index is 23.3 bits a row and the range structure is 11.5.

Both fall out right. The index measured elsewhere is 23.0 bits a row and the succinct range minimum is 11.3, neither of which was used to fit anything — so a two-parameter model built from two points on one sweep reproduces two numbers measured on another.

Now solve. The apparatus equals the index when $\lceil\log_2 d\rceil = 11.8$, and a ceiling cannot take that value. At $\lceil\log_2 d\rceil = 11$ the ratio is 0.97 and at 12 it is 1.01, so the crossing is not near two thousand documents — it is a step, at exactly 2,049. One document either side of a power of two moves the whole apparatus across the index it sits on.

That is the staircase this page identifies, doing the one thing a staircase does that a slope cannot: putting the interesting boundary at a place nothing about the collection chose.

And the movement with $n$ is now readable too, in the opposite direction to the intuition. Both constants are logarithms — the index is $\lceil\log_2 n\rceil + \lceil\log_2\sigma\rceil$ and the range structure is flat — so doubling $n$ adds one bit to the index and therefore one bit to the $d$ the crossing sits at, which doubles the crossing’s document count. The crossing is proportional to $n$, which means it is not a document count at all.

It is a document length, and it is about 64 characters. At the 131,072-character size these plates are drawn at, 2,048 documents is 64 characters each, and every larger collection cut the same way crosses at the same length.

Which is the sharpest available statement of what this page is about, and it explains the number the page opens with. The captions at this plate size average 59 characters a document — just under the threshold — and the apparatus measures 1.01 times its index. The collection is not merely on the wrong side of a crossing; it is five characters over the line, and a corpus of slightly longer captions would sit under it.

So the recommendation has a form nobody would guess from the document count. Do not ask how many documents there are. Divide the collection’s characters by its documents, and compare against sixty-four. Above it the listing apparatus is smaller than the index it sits beside; below it, it is not — and the array the walk never reads’s substitution is what moves the line, since removing the $\lceil\log_2 d\rceil$ term removes the only place $d$ appears and the crossing goes away entirely.

What this changes about the earlier numbers #

Nothing published here is withdrawn, and three sentences need a shape attached to them.

The listing apparatus costs about two and a half times the index it sits on — true at 2.44 on 82 documents and 2.64 on 2,214, so the shape moves it by less than a tenth. That one travels.

A separator per document is free — true on twelve documents and on no collection larger than about a hundred.

Spanning windows are a small correction — true per document and false per character, by a factor of twenty-eight between the two shapes on this page.

A last note on why this collection and not another. What the generated collection was right about drew the line between quantities a model gets right by arithmetic and quantities it gets right by a parameter, and the shape of a collection is squarely the second: documents per collection and characters per document are two numbers somebody types. Measuring them on something nobody built as a corpus is the only way to find out what they usually are.

The general lesson is the one this strand keeps producing. A collection has two shape parameters — how much text, and how it is cut — and this field has swept the first for years and held the second at a dozen.

What is still not measured #

Two things, and the first is the one that would change a recommendation.

A repetitive collection of many short documents. Everything on this page is either prose or a version history, and the two shapes are confounded with the two kinds of repetition: the long-document collections here are the repetitive ones and the short-document collection is not. A real collection of thousands of near-identical short documents exists in quantity — log lines, product records, the same form filled in by different people — and it is the case where a compressed index and many documents meet. Nothing here says what the document array costs relative to a structure whose size follows the phrase count rather than the character count, and the answer is not obvious: one term follows n and the other follows z, and on a repetitive collection those differ by an order of magnitude.

And the query distribution. Every plate here measures the collection’s own most frequent strings, because a real corpus supplies its own patterns and a planted one does not. That is the right axis for a question about the structures, and it is not what a query log looks like: real queries are words rather than six-character windows, they are wildly unequal in frequency, and the ones people repeat are not the ones the text repeats. The listing apparatus is priced here against the text’s distribution, and pricing it against a query distribution would be a different measurement with the same structures in it.