Documents that are not the same length

The document strand made four findings about collections with parts. This is what happens to each of them on documents nobody generated.

Two transfer exactly, one transfers with a different constant, and one is a property of the generator.

The finding that does not survive #

One separator, or one for each measured that giving every document its own separator costs a whole bit per character — the alphabet goes from 22 symbols to 35 at fifteen documents, which takes a packed text from five bits a character to six.

It does. On a collection whose alphabet is 22 symbols.

Real prose of this kind has 87 symbols, which needs seven bits, and seven bits reaches 128. Adding one separator makes it 88; adding one per document for twelve documents makes it 89. All three sit comfortably below 128, so all three pack at seven bits a character and the entire premium is 0.04%.

The finding was correct. It was a finding about the generator’s alphabet.

It is worth being precise about how large the correction is. The strand reported a premium of 1.2 times the packed collection at fifteen documents; the real measurement is 1.0004. That is not a difference in degree — it is the difference between a cost worth designing around and a cost that does not exist.

Why an alphabet of 22 is the special case #

A packed character costs ⌈log₂ σ⌉ bits, which is a step function. Everything about the cost of adding symbols therefore depends on where σ already sits relative to a power of two.

At 22, the next power is 32 and there are ten symbols of headroom. Fifteen documents need fourteen separators, which overruns it, and the step is paid.

At 87, the next power is 128 and there are 41 symbols of headroom. Twelve documents need eleven separators. Nothing happens.

A generated text’s alphabet is small because somebody chose a small one, and it was chosen so that the plates would be legible and the collections would build quickly. Neither reason has anything to do with documents, and both put σ in the one range where the strand’s headline is true.

What would have caught it #

Nothing in the essay was wrong and nothing in it was hedged. It stated an alphabet — 22 symbols — and a measurement, and a reader could in principle have noticed that their own text has more symbols.

What would have caught it is the habit the cap that binds on one text and not another arrived at and this one had not: a plate about a threshold draws where the data sits relative to it. The separator finding is about crossing a power of two, and the plate that would have made it safe is one showing σ and the nearest powers of two with the collection’s own value marked.

That plate now exists and it is the hero of this essay. It answers the question a reader has — will this cost me anything — in a way the original could not, because the original’s answer was a number about one alphabet.

What a real collection would have to look like #

For the separator finding to bite on real text, the alphabet would have to sit just under a power of two and the document count would have to push it over.

That is possible. A DNA collection has four symbols plus a sentinel, which is five, and five is just under eight — so three documents with their own separators cross to sixteen and the packed width goes from three bits to four, a 33% premium. A collection of two-symbol strings is worse still.

So the finding is real and its domain is small alphabets, which is where it was measured and is not where it was stated. The corrected version is not “separators are free”; it is “separators cost a step, and whether it is paid depends on where the alphabet sits”.

The finding that transfers exactly #

The occurrences a join invents measured that a concatenation of d documents holds exactly (m − 1)(d − 1) windows of length m spanning a join.

That is arithmetic about a concatenation and it holds on any documents whatever. Checked on all three parts of the real corpus at four window lengths: twelve values, twelve exact matches.

Every one is (m − 1)(d − 1) to the window. There was never any doubt, and confirming it costs one function.

The finding that transfers with a different constant #

The second half of that essay is the interesting one. Of those spanning windows, how many are strings that no document contains?

On the generated collection: 23 of 49 at m = 8. Just under half.

On twelve real essays: all of them, at every window length. 33 of 33, 55 of 55, 77 of 77, 121 of 121.

On the real version history: 18 of 27 at m = 4, rising to all of them by m = 8.

The reason is immediate once the numbers are on the table. A spanning window is half of one document’s ending and half of the next one’s beginning; whether that string occurs inside some document depends on whether the documents share their substrings.

Twelve unrelated essays share their vocabulary and not their eight-character strings, so every artefact is new. Near-copies of one file share nearly everything, so some spanning windows turn out to occur inside a document anyway.

This is the same distinction a list of documents is not a list of occurrences draws between a query’s occurrences and its answer, applied to artefacts rather than to matches. The generated collection is near-copies by construction, so it measured the second case and reported it as the general one. The corrected statement is that the share runs from about a half to one, and it is one for any collection of unrelated documents.

Which direction the error runs #

It is worth noticing that this correction makes the original strand’s argument stronger, not weaker.

The point of counting invented strings is that they are strings an index over the concatenation will report and a reader looking for documents cannot use. If half of them are real, half the artefacts are harmless; if all of them are new, all of them are noise.

So on the collection type the finding most matters for — many short unrelated documents, which is what a document-retrieval corpus is — the problem is twice as bad as the generated collection said.

That is the useful shape of a correction, and it is worth saying because the previous essay’s correction ran the other way. A generated collection can flatter a finding or understate it, and there is no way to know which without the real thing.

The lengths, which nothing had ever varied #

Every generated collection in this collection has documents of exactly one length. Not approximately — exactly, because the generator makes k copies of a base text and a copy has the base’s length.

Real documents do not, and a corpus that was not generated is where the three parts come from. The version history runs from 1,086 characters to 4,079, growing monotonically because a file that is edited across ten occasions mostly gets longer. The source modules vary by a factor of 3.12.

And the twelve essays vary by a factor of 1.26, which is the narrowest spread of the three and is an artefact: they come from a collection that requires every essay to sit inside a length band. Real prose corpora are not like that, and the uniformity here is a property of how these particular documents were written.

Why the essays are the tidiest documents here #

It is worth dwelling on the 1.26, because it is the one place this corpus is less real than an arbitrary one.

These twelve essays come from a collection with a length standard — every essay between two and a half and four thousand words — enforced by a check that refuses to accept an essay otherwise. So their lengths cluster by design, and a corpus of twelve arbitrary essays would spread far wider.

The version history and the source modules have no such constraint and spread by factors of 3.76 and 3.12, which are ordinary numbers for real documents.

That is worth stating rather than quietly using the wider parts, because it is exactly the kind of hidden uniformity this whole strand exists to find. A corpus assembled from a source with its own standards inherits them.

What unequal lengths change #

Less than one would expect, on the measures this strand has.

The artefact count is (m − 1)(d − 1), which does not mention lengths. The alphabet cost does not mention lengths. The listing’s query count is 2s + 1 for an answer of s documents, which does not mention lengths either.

Where lengths enter is the answer’s size distribution: a query matching a long document and a short one gets an answer of two either way, but the occurrences are distributed unevenly, and a scan’s cost follows the occurrences. So an uneven collection has a wider spread of scan costs for the same answer size, which is exactly the axis the output-sensitive method’s crossing sits on.

That is measurable and it is measured in the next essay, where the listing the cost that is the size of the answer built is swept over a real corpus’s own vocabulary rather than over a planted pattern.

The truncation that would have hidden it #

There is a preparation step almost every corpus goes through, and it removes the property this essay is about.

Cutting every document to the shortest one’s length makes a corpus tidy. It also loses 55.8% of this collection and moves both measures: runs per character from 0.126 to 0.120, phrases from 0.0668 to 0.0724 — the second in the opposite direction to the first, because cutting removes the long tails that a parse copies from and the short heads that a transform’s runs come from.

So the tidying is not neutral — it is the same shape of hidden transformation the histogram that cannot see the order records for a different measurement. It is a transformation with a measurable effect on exactly the quantities the strand is about, applied for presentational reasons, and it is kept in the checks as a case that must be rejected.

The truncation this corpus does use scales every document by the same factor, so the spread is preserved and every document is kept.

The pattern across the four findings #

Laid out, the four have a shape.

Arithmetic transfers. (m − 1)(d − 1) is a statement about a concatenation and holds for any documents.

Statements about what the documents contain do not. The share of artefacts that are new depends on whether documents share substrings, and a generated collection fixes that by construction.

Statements about thresholds depend on where the data sits. The separator cost is a step function evaluated at the generator’s own alphabet.

And statements about distributions were never tested, because a generated collection has no distribution — its documents are one length, its edits are one rate, its alphabet is one size.

That last one is the general form and it is the reason this strand exists. A generated collection is a point, and five strands of conclusions were drawn about a neighbourhood by measuring at a point.

What is checked #

The spanning-window count is (m − 1)(d − 1) on every part at every window length, asserted as an equality rather than as an approximation.

Unrelated documents invent every spanning window and a version history does not, both asserted, so that a corpus change making them agree would fail here rather than quietly collapsing this essay’s second finding.

No join crosses a power of two on a real alphabet, and the premium is under two per cent — asserted in that direction, because the interesting claim is the absence of a cost.

And the corpus is required to have uneven documents in at least one part by a factor of more than 1.5, with the matched generated collection required to have a spread of exactly one. That pair is what makes every comparison in this essay a comparison.

What a reader with a real collection should check first #

Three numbers, all of them one pass.

The alphabet, and the nearest power of two above it. That decides whether separators cost anything, what a packed copy of the text actually costs, and how deep a wavelet tree over it will be. It is one set.

The length distribution. Longest over shortest, and whether the documents grow — a version history does, a document collection generally does not. It decides nothing on its own and it is the parameter every generated collection silently fixes.

And the document count against the window lengths in question. (m − 1)(d − 1) is the number of artefacts a concatenation invents, and on a corpus of many short documents it is large: a thousand documents at m = 8 is seven thousand invented strings, whatever the documents are.

None of those needs a structure and all three are the parameters a collection’s behaviour turns on. This collection had measured none of them on real data before this strand.

The domain is a ratio, and a retrieval corpus is squarely in it #

“Its domain is small alphabets” is the correction this essay makes, and the arithmetic says the domain is better described by a ratio — which puts a real document collection back inside it, harder than the generated one ever was.

The condition is one line. Per-document separators add $d$ symbols, and the packed width steps when the total passes the next power of two, so the collection stays free exactly while

$$d \;\le\; 2^{\lceil \log_2 \sigma \rceil} - \sigma.$$

Evaluated: the generated collection at $\sigma = 22$ tolerates ten documents and was measured at fifteen, which is the step it paid. Real prose at 87 tolerates forty-one. The source part at 98 tolerates thirty. The version history at 75 tolerates fifty-three. Twelve documents is comfortably inside all three, which is the whole of why the premium came out at 0.04%.

The headroom is not a constant, it is about a third of the alphabet. For $\sigma$ falling anywhere in $(2^{k-1}, 2^k]$ the slack $2^k - \sigma$ averages $2^{k-2}$ against a mean $\sigma$ of $3 \cdot 2^{k-2}$, so a typical text tolerates roughly $\sigma/3$ documents before it steps. That is a rule a reader can apply without knowing anything about their own corpus except its symbol count, and it makes the real question not how large the alphabet is but how many documents there are relative to it.

Which is where a document-retrieval corpus lives. Twelve essays is not a retrieval collection; a thousand documents is. Prose at $\sigma = 87$ with a thousand separators is 1,087 symbols, which needs eleven bits against seven — a 57% premium on the packed text, against the 20% the generated collection reported and the 0.04% this essay measured. The step is not paid once; it is paid four times over.

And the alternative costs nothing at any scale. One shared separator gives 88 symbols and seven bits whatever $d$ is, because a single extra symbol cannot cross a power of two that 41 symbols of headroom stand in front of. So the choice the strand’s title names is genuinely a choice, its cost is bounded and small at twelve documents, and it grows without limit in $d$.

The honest correction is therefore two-sided rather than a dismissal. The strand measured a real effect, quoted a constant that belongs to one alphabet and one document count, and the second of those turned out to be the load-bearing one. At a dozen documents the effect is absent on any realistic text; at a thousand it is larger than anything the strand reported. Both statements come from the same step function evaluated in two places, which is what a threshold somebody chose is always about — the constant is not the finding, the position relative to the step is, and a plate that draws the step can be read at a parameter nobody measured.

What this leaves #

Four findings, three of them intact and one of them relocated to the generator that produced it.

The relocation is worth carrying as a shape rather than as a fact about separators: a finding that turns on a threshold is a finding about where the data sits relative to the threshold, and a collection whose parameters were chosen for legibility sits wherever those choices put it.

What the generated collection was right about is the full accounting across five strands, and this is the sharpest single item in it.