The deepest text is punctuation

Ten revisions of one file reach depth 14. Fourteen revisions of another reach 19. Twelve unrelated essays reach 15.

Eight source modules — no version history, no generations, no copying between them beyond the fact that one person wrote them all — reach depth 78.

And the tail is flat. Not decaying: flat. The same number of characters at depth 20 as at depth 40 as at depth 70, all the way to the end.

A flat tail is not a thing a distribution produces. It is what one object produces when its positions are spread one per level, and that is exactly what has happened.

What a run does to a parse #

The mechanism is in the definition of a phrase and is easy to miss.

A phrase copies from a source that starts earlier. It does not have to end earlier — the source region may overlap the phrase itself, which is what lets a run of a thousand identical characters be two phrases rather than five hundred: a literal, then one phrase of length 999 copying from the position one before it. The phrases a text copies from itself is where that is established, and a run is a property of the input is where runs get their own treatment.

Now follow the depths. The literal is depth 0. The next character copies from it: depth 1. The next copies from that one: depth 2. Along a run of length L the depths are 0, 1, 2, …, L − 1, one level per character, because each position’s source is the position immediately before it.

So a run of 73 characters single-handedly populates every depth from 0 to 72, one character each.

The object #

The longest run in eight modules of source code is 73 dashes, and there are 24 of them. There are another 24 of length 70. Those are the rules inside comment banners — the line of dashes that separates one section of a file from the next — and they are the deepest text in the collection by a factor of four.

That accounts for the flat tail exactly. Twenty-four runs of 73 and twenty-four of 70 put 48 characters at each depth from 0 to 69 and 24 at each depth from 70 to 72, which is what the histogram shows: 48 at every level from 20 to 69, then a short step down.

Every position deeper than 20 in this collection is inside a run. Not most: all of them, 2,685 of 2,685.

Why this is in the taught-wrongly field #

Because the natural reading of a depth histogram is wrong, and it is wrong in the direction that makes somebody set a parameter badly.

The reading is: depth measures how many times something has been copied, so a deep tail means passages that have been copied through many generations, and a cap will cut them. Everything in that sentence is a reasonable inference from the definition and all of it fails here. The tail is not copied passages. It is punctuation, and it is one kind of punctuation.

The consequence is quantitative. Somebody looking at this histogram would see a worst depth of 78 and conclude that an extraction on this collection can cost 78 chained lookups, which is true, and that capping the depth is therefore expensive, which is false.

A cap of 24 on the source code costs 1.1% of the phrase count. A cap of 16 costs 2.0%. The tail that reaches 78 is 2,685 characters out of 106,283 — two and a half per cent of the collection — and truncating it costs a phrase or two per run, because a capped run just becomes a few more phrases.

Meanwhile a cap of 8 on a real version history, whose worst depth is half the source code’s, costs 68% more phrases. The collection with the deeper histogram is the cheaper one to cap, and the histogram alone says the opposite.

What the cap actually buys on a run #

Worth following through, because the guarantee a cap gives is about extraction and a run is the case where extraction is worst.

Producing the last character of a 73-character run means following 72 copies, each a single-character hop. That is genuinely the worst extraction in the collection and it is genuinely what the cap is for. Capping at 8 turns the run into nine phrases instead of two — eight characters copied, then a fresh literal, and so on — and the extraction cost of any position in it falls to at most 8.

So the cap does exactly what it promises, and what it costs on this object is seven extra phrases per run times 48 runs, which is 336 phrases in a collection of 15,408. That is the 1.1%.

The general shape: a cap is cheap where the deep positions are concentrated in few, long, self-overlapping structures, and expensive where the deep positions are the bulk of the collection. Those are opposite ends of the histogram, and only the second is what a version history looks like.

Three ways a chain of copies can be long #

Once the run case is separated out, it is worth having the whole taxonomy, because the three causes want different responses and only one of them is what the cap strand was written about.

Generations. A passage survives from one revision to the next, and each survival adds a level. This is the case the cap ladder is about, it is measured exactly in one revision, one level, and its depth is bounded by the number of revisions plus the file’s own offset. The right response is a cap set from the generation count, and the cost is small because the deepest positions are few.

Compounded repetition. A word copies from an earlier phrase which copied from an earlier one, with no generational structure anywhere — a single document does this to itself. This produces the offset, it is what gives twelve unrelated essays a mean depth of 5.17, and it has no natural bound: it depends on how the text repeats itself and on the order the greedy parse happens to take. The right response is to measure it, since no metadata predicts it.

Runs. One character repeated, producing one level per character through overlap. Unbounded in principle — a run of a million characters has depth 999,999 — concentrated in a tiny share of positions, and cheap to cap or to remove entirely.

The three are additive and they are not distinguishable in the histogram, which is the whole difficulty. A worst depth of 78 could be a 78-generation history, a document with extraordinary internal repetition, or 73 dashes. Only one measurement separates them, and it is the one-line check at the end of this page.

What the parse could do instead #

There is a version of the parse that never produces the run case, and it is worth knowing why this one does not use it.

Forbid overlap: require a phrase’s source region to end before the phrase begins. Then a run of L characters is parsed as a literal, then a phrase of length 1, then 2, then 4 — doubling, because each phrase can copy the whole prefix of the run written so far — which is about log₂ L phrases at depths 0 through log₂ L. The tail vanishes and the phrase count rises.

That is a real alternative and it is what several published parses do, because overlap complicates a decoder. What it costs here is the property that makes z the measure this field uses: with overlap, z is the number of phrases in the smallest such parse, and a run is two phrases rather than seventeen. Forbidding overlap changes the measure, and every published z in this collection would move.

So the trade is: keep overlap, get a measure worth quoting and a deep tail made of runs; forbid it, get a shallower tail and a measure that counts a run’s length in its logarithm. This collection keeps overlap and caps the depth, which gets both — and the reason the choice is visible at all is that somebody drew the histogram of a collection with runs in it.

The same trap in the size measures #

This is not the first time in this collection that a run has quietly owned an extreme, and the earlier instance is worth putting beside it because the reasoning was identical.

The transform’s run count r is a measure of repetition, and a text with long runs of one character has a small r for a reason that has nothing to do with the text repeating passages. The measure sees a run of a thousand a’s as maximally repetitive — it is one run — and that is correct by the definition and misleading as a description.

Repetition is not entropy is the theme; the specific version is that both r and z are one-number summaries of an arrangement, and a single degenerate object can dominate either. Here that object is a comment banner. In the size measures it is any long run.

What both cases show is the same discipline: when a summary statistic reaches an extreme, look at what is at the extreme before deciding what the statistic is saying. That is a paragraph of code — walk the positions past a threshold, ask whether each one’s character equals the one before — and it converted a number that looked alarming into a number that is an artefact of formatting.

What a real system would do about it #

Three options, and they are worth ranking because the answer is not “nothing”.

Cap the depth anyway. The measurement says it costs about a per cent on this collection, and it converts the extraction guarantee from 78 to whatever the cap is. That is a good trade and it is the one the ladder recommends.

Or run-length encode first. A run is exactly what run-length coding is for, and a collection whose deep tail is runs would have no deep tail at all if the runs were coded before the parse ran. That is a preprocessing step, it is cheap, and it removes the problem rather than bounding it.

Or leave it. Two and a half per cent of positions costing up to 78 hops is a real cost only if those positions are read, and nobody extracts the middle of a comment banner. This is the option that is right in practice and wrong to assume, because “nobody reads that” is a claim about a workload and the workload is not measured here.

The reason to prefer the first is not the cost. It is that a bound that can be stated is worth more than a bound that is merely believed: a guarantee is not a result, and “no extraction costs more than 24 hops” is a sentence a system can be held to.

How this was found #

Worth recording, because it was not found by reading the histogram.

The histogram was drawn, the number 78 was noticed, and the first explanation offered was the wrong one — that source files copy from each other heavily, since eight modules of one program share boilerplate. That explanation is plausible, it fits the collection’s description, and it is what the depth strand’s framing invites.

What refuted it is one line: count, among the positions deeper than 20, how many have a character equal to the one before them. The answer was all of them, and the explanation collapsed immediately.

That check is now a standing one. It runs on every build, it requires the deep positions to be runs on the collection where they are runs, and it requires the longest run to be at least as long as the depth it is supposed to explain — which is what turns “the tail is runs” from an observation into something that could be false.

Where this sits #

The shape of a real history’s depth is the histogram this page is about the tail of. One revision, one level is the same quantity against the generation count, where the increment is exactly one and the offset is a file’s own repetition. The cap that would ship is what to set, given all three.

And the reason the tail matters at all is the one the character that costs a chain established: an index built on a parse pays its depth on every character it produces, so the worst depth is a real guarantee about a real operation. It is just not, on real text, a guarantee about the thing anybody assumed it was about.

What this changes about the other collections #

Two things, and the second is a correction to a plate rather than to a sentence.

The knee on the source code is a different kind of knee. On the two version histories the phrase count falls steeply until the cap reaches the bulk of the distribution and then flattens; on the source code it flattens at a cap of about eight and then declines by a per cent at a time for another sixteen levels. Those are two different shapes on one plate, and the second is the run tail being truncated a little at a time. Reading them as the same curve at different steepnesses is the mistake this page exists to prevent.

And the worst depth is not the right summary for a collection with runs in it. For a version history, the worst depth is a meaningful number — it is the age of the oldest surviving passage, and it saturates. For a collection with runs, it is the length of the longest run, which is a formatting decision. A summary that would be robust across both is the depth below which some large share of positions sit — the 99th percentile, say — and nothing in this collection reports one.

The general lesson is small and portable. An extreme is worth looking at directly. A histogram is a summary, a worst case is a summary of a summary, and both of them will happily describe a comment banner as though it were the structure of the collection.

What a summary statistic owes its reader #

The general form of this page is small enough to state and applies past depth histograms.

A worst case is a summary of a summary. The histogram summarises the collection; the worst depth summarises the histogram; and by the time a number reaches a caption it has been through two reductions, each of which can be dominated by one object.

Here the object is a comment separator, and the reduction that hid it is “take the maximum”. Seventy-eight is a true statement about the collection and a false impression of it.

What this collection does about that, now, is a one-line check: look at what sits past a threshold, and ask whether it is the thing the histogram is supposed to be about. On the source code the answer is that every deep position is inside a run; on a version history it is that none of them are. Two collections, one measurement, opposite answers — which is what makes the measurement worth running rather than reasoning about.

The cap that would ship is where that lands as a decision, and the decision is the opposite of what the histogram alone suggests: the collection with the deepest tail is one of the cheapest to cap.

The check deserves a threshold rather than the word a threshold, because the right one falls out of the failure it catches.

A single object contributes about as many deep positions as it is long — a comment banner of eighty characters produces eighty of them, at eighty increasing depths. So compare the population past the threshold against the collection’s longest run. If the deep positions number fewer than one run, one object can account for all of them and the histogram’s tail is a fact about that object.

That is the arithmetic behind the two opposite answers here. On the source code the deep positions are fewer than one separator line, and every one of them turns out to be inside it; on the version history they outnumber any single run by far, and none is.

It also says when the check is unnecessary. A collection whose tail holds many runs’ worth of positions cannot be dominated by one object, and its worst case is a summary of the collection after all — which is the condition a parse that will not follow a long chain’s cap sweep assumes, and the cap that would ship is where the assumption is worth checking before a parameter is chosen from it.