The occurrences a join invents

Every repetitive collection in this field has been one string. The entropy that cannot see a copy built it — a base text, repeated, with an optional substitution rate — and five essays since have measured run counts, phrase counts, index sizes and search costs on it.

Three of those essays end with the same sentence, and it has been the oldest thing on this collection’s list of what it has not built:

What is missing is a collection with document boundaries. A parse crossing from the end of one document into the start of the next produces phrases that are artefacts of the concatenation, and every measurement in this strand pays that cost silently.

This is what that cost is.

What a join invents #

Eight documents of two hundred and fifty-six characters, run together into a single string of 2,048.

A window of $m$ characters starting in one document and finishing in the next spans a join. There are exactly $(m-1)(d-1)$ of them for $d$ documents — seven joins, $m-1$ starting positions each. At eight characters that is forty-nine.

Of those forty-nine, twenty-three are strings that occur in no document at all. They are not corrupt or malformed — they are perfectly ordinary eight-character strings, made of the last few characters of one document followed by the first few of the next, and there is nothing about any of them that an index could notice. The other twenty-six happen to also appear somewhere legitimately, because the documents are near-copies of one another and short strings recur.

So the concatenation contains twenty-three eight-character strings the collection does not contain. An index over it will find them, count them, and report their positions.

How the count grows #

Twenty-one spanning windows at four characters, thirty-five at six, forty-nine at eight, seventy-seven at twelve — and five, thirteen, twenty-three and forty-four of them invented.

The formula is $(m-1)(d-1)$ for the spanning count, so it is linear in both the pattern length and the number of documents, and independent of how long the documents are.

That last part is the one worth carrying. A corpus of a thousand short documents has a thousand joins and a thousand times the artefacts of a corpus of one long one, at the same total size. The measurement here is on eight documents of 256 characters; a version-controlled repository with ten thousand files has 9,999 joins, and at an eight-character query that is nearly seventy thousand invented strings.

The share of the whole collection is small — 1.1% of the windows at $m = 8$ here — and the share is the wrong statistic, in the same way an average is the wrong statistic for a defect concentrated in one place. What matters is that the artefacts are concentrated at the joins, and a query landing on one gets a wrong answer rather than a slightly noisy one.

What the artefacts do to a search #

A count is wrong by however many of the artefacts match. A locate returns positions that belong to no document. And a document listing — the query a collection exists to support — returns a document that does not contain the pattern, or worse, two.

The last of those is the sharpest. An occurrence spanning the join between documents three and four is in neither: its first characters are in three and its last are in four. Whatever a listing does with it is wrong, and both plausible answers — report three, report both — are wrong differently.

That is why the artefacts are not a rounding error on a collection with a question. They are a correctness failure on the only question a collection has that a text does not, which is a list of documents is not a list of occurrences and is what this ladder is for.

The fix, and what it costs #

One character between the documents that no document contains.

A pattern drawn from a document cannot contain that character, so no window spanning a join can match any pattern — the artefacts still exist as strings in the concatenation, and they become unmatchable. Measured: 24 invented strings at $m = 8$ with a shared separator, and zero of them matchable.

The count of invented strings does not fall. It rises slightly, because the separator itself creates new windows. What falls to zero is the number that a search can ever return, which is the quantity that matters and is a different quantity from the one an artefact count reports.

That distinction is why the check for this has two halves. A check counting invented strings would report the separator as making things worse; a check counting matchable artefacts reports it as making them zero, and it also requires the run-together case to have some, so that the fix is measured against a problem rather than against nothing.

Why the artefacts were invisible for five essays #

Nothing about them shows up in any measurement the earlier strand took, and it is worth listing what would have had to be measured for one to appear.

Not the sizes. A handful of extra phrases and runs is under one per cent of either measure, well inside the variation between corpora.

Not the search costs. Every pattern in the parse strand is drawn from inside the collection at a fixed offset, so it lands inside a document and its occurrences are genuine. A pattern drawn across a join would have found an artefact, and no plate drew one.

Not the correctness checks. Those compare the index’s occurrences against exhaustive search over the same string — which contains the artefacts, so both sides agree. An index over a concatenation reports the concatenation’s occurrences correctly.

That third one is the instructive one. The check was right, the index was right, and the object being indexed was not the object the prose described. This collection’s usual failure is a measurement of the wrong quantity; this is a measurement of the right quantity on the wrong object, and no check comparing an implementation against a reference implementation over the same input can ever see it.

The way it eventually surfaced is the way such things do: by writing the sentence “what is missing is a collection with document boundaries” at the end of an essay, three times, and finally building one. Requiring a check to be able to fail is a discipline about implementations; there is no corresponding discipline for the object, and the nearest thing is a habit of writing down what has not been built.

The cost is charged to every character of every document #

A separator adds a symbol to the alphabet, and the alphabet sits inside a logarithm in every size this field measures: a packed text is $n\lceil\log_2\sigma\rceil$ bits, a wavelet tree is $\log\sigma$ levels deep, and a bad-character table is $\sigma$ rows.

One shared separator takes an alphabet of twenty-one to twenty-two, which on this text is five bits per character either way — free, because twenty-two is still under thirty-two.

A separator per document takes it to thirty-five at fifteen documents, which is six bits per character. Every character of every document costs an extra bit so that the boundaries can be told apart, and the whole collection is 1.2 times its packed size.

That is the subject of the next essay, — one separator, or one for each — and the reason it needs one is that the two costs — a symbol, or $d$ symbols — look identical until the alphabet crosses a power of two, and then one of them is a whole bit per character.

What it does to the measures of repetition #

The other quantity a separator disturbs, and it is small.

A separator is a character that occurs $d-1$ times in a collection where nothing else occurs so rarely. In the Burrows-Wheeler transform it ends a run; in the parse it ends a phrase. Measured across two, four, eight and fifteen documents of 512 characters, run together against a separator each: the run count goes 331 to 334 at two documents and 1,855 to 1,863 at fifteen; the phrase count moves similarly.

So the two measures this field is built on move by well under one per cent, and the movement is proportional to the number of documents rather than to their length. On a corpus of a million short documents it would not be small, which is worth saying because the corpora this field is for — versioned files, genome collections, log stanzas — are exactly the many-short-documents case.

The three joins, side by side #

The collection this ladder is built on can be joined three ways, and each is a different object rather than a setting.

Run together. No separator. The artefacts are matchable, the alphabet is unchanged, and the collection is the string the earlier strand measured. It is the right object when the documents genuinely are one text — the chapters of a book, a stream of records where a pattern spanning a boundary is a real occurrence.

One shared separator. A single character no document holds, between every pair. Artefacts unmatchable, alphabet plus one. It is the right object for a search that must not cross boundaries and a listing that only needs to name the documents.

A separator per document. Alphabet plus $d$. It is the right object when the construction needs every suffix to be strictly comparable — some suffix-array constructions and some document-retrieval structures require it — and it is the expensive one.

The three are not a quality ordering. A collection run together is the correct model for some corpora and the wrong one for others, and the choice is editorial rather than technical. What is technical is that the choice has to be made explicitly, and until this ladder it was made by default and never named.

That is the pattern the model has parameters is about, arriving at the level of the input rather than of the algorithm: a property of the data that the measurement fixed silently, drawn as a dial once somebody noticed it was one.

What was measured wrongly before, and how much #

The honest accounting for the five earlier essays that used the concatenated collection.

Their subject was sizes and search costs on a collection of copies, and both are essentially unaffected: the artefacts add a handful of phrases and runs, well under one per cent, and the patterns those essays search for were drawn from inside the documents rather than across the joins.

What was unstated is that the collection had no documents in it. Every number about a “collection of thirty-two copies” is a number about a single string that happens to have a repeating structure, and every property that depends on the parts being separate objects — a listing, a per-document count, a boundary-respecting parse — was not being measured because it did not exist.

So the correction is a scope correction rather than a numerical one. The measurements stand; what they are measurements of is one text, and the strand that begins here is about the object those essays were describing without having.

The place it bites is the language. “A collection of thirty-two copies” invites a reader to think of thirty-two documents, and a reader who then asks which of them contains a pattern is asking a question the structure could not answer and the prose implied it could. That is the cost of the omission, and it is a cost in what the essays meant rather than in what they measured.

The same failure elsewhere in this collection #

An artefact of how the input was assembled, reported by a correct algorithm, is not a new shape here.

The boundary that hides the burst is the streaming version: a window that retires a block every fixed number of arrivals is a sampler, and against a stream whose bursts share its period it reports a perfectly even stream while the arrivals are grossly bunched. The structure is right and the object it is measuring has a property the model does not contain.

A distance that is a path through a grid has the milder version: the alignment table’s borders encode an assumption about what happens at the ends of the strings, and changing the assumption changes the answer without changing a line of the algorithm.

And the space the model does not see is the accounting version: a cost that is real, is paid, and falls outside what the model counts.

The common element is that the algorithm is not where the problem is. Every one of these is fixed by changing the input’s description or the model’s scope, and none is fixed by a better implementation — which is why they are hard to find with tests and easy to find by writing down what the object is.

What a collection is, once it has parts #

Worth setting down, because the rest of this ladder depends on the definition and because it is the first time this collection has needed one.

A text is a string. It supports two questions — how many times does this occur, and where — and every structure in this field’s index strand answers those two.

A collection is a sequence of texts. It supports those two questions about the concatenation, which are usually not the questions anybody has, and it supports a third that a text cannot be asked: which of its parts contain the pattern.

The third question is the one that makes the object different, and it is the reason a collection needs machinery a text does not: a way to say where each part starts, a way to say which part a position is in, and — if the answer is to cost what the answer costs — a way to find the parts without visiting the occurrences.

Everything in this strand follows from that. The separator is how the parts are kept from bleeding into one another; the boundary vector is how a position is mapped to a part; and the chain and its range minimum are how the third question is answered at the price of its answer. Three structures, one question, and none of them is needed by a text.

The index that is the text is where this field’s answer to the first two questions is set out; this strand is what has to be added for the third.

What is being claimed #

A concatenation of $d$ documents holds $(m-1)(d-1)$ windows spanning a join, and on eight near-identical documents twenty-three of the forty-nine eight-character ones are strings no document contains.

The count is independent of document length, so it is a property of how many documents there are, and it is worst on exactly the many-short-documents corpora this field exists for.

One shared separator makes all of them unmatchable — the fix one separator, or one for each prices — and does not reduce their number, which is why a check counting artefacts and a check counting matchable artefacts give opposite readings.

It costs one alphabet symbol, which is free until the alphabet crosses a power of two.

And it disturbs both measures of repetition by under one per cent, proportionally to the number of documents rather than to the collection’s size — which is small here and would not be on a corpus of a million short files.

The alphabet effect is a step at log_σ n #

That last caption notes the artefact share moving with the alphabet and leaves it there. The threshold is computable, and it is the same one this field keeps arriving at.

A spanning window is a string of $m$ characters that nothing constructed deliberately. It is an artefact only if it occurs in no document — and a given $m$-gram occurs somewhere in $n$ characters with probability about $1 - e^{-n/\sigma^m}$. So the artefact share is roughly $e^{-n/\sigma^m}$, which is a step: nearly zero while $\sigma^m < n$, and nearly one once $\sigma^m$ passes it.

The crossing is at $m = \log_\sigma n$.

Evaluate it on the two corpora here. Four-symbol text, 2,048 characters: $\log_4 2048 = 5.5$, so four-character spanning windows are almost all legitimate — $e^{-8}$ of them are artefacts — and eight-character ones are almost all invented. Nineteen-symbol text: $\log_{19} 2048 = 2.6$, so even a four-character window is essentially always an artefact.

Which turns the alphabet observation into a rule with a number in it. A separator is unnecessary for patterns shorter than $\log_\sigma n$ and necessary above it, and on a small alphabet that threshold is high enough to cover real queries — five characters on two thousand of DNA, and nine on a million.

It is the same $\log_\sigma n$ that decides when a pruning stops finding absent substrings and how long a parse’s phrases get, arriving here as the length at which a concatenation starts inventing things. One separator, or one for each prices the fix, and a list of documents is not a list of occurrences is the question the fix protects — neither of which is worth paying for below the threshold.