Algorithms & Data Structures
the bound is a claim, and it is checkable
Theme

The thread: A model is not a corpus

A generated collection is an instrument: one dial, moved to produce a stated degree of repetition so a structure can be measured against it. It is not a sample. Its documents are one length, its edits one rate, its alphabet 22 symbols where real text has 87 — and a finding that turns on a threshold is a finding about where the data sits.
stay 0.9, 400 pairsacgtacgt0525505225045240stay 0.5, 400 pairsacgtacgt0212202112022120cost of aligning the row letter with the column letterpseudocount 1 When the algorithm is a table

The matrix a corpus wrote

A substitution matrix is not a property of an alphabet. Fit one to four hundred pairs of sequences that rarely change and the dearest substitution costs five; fit the same model to four hundred pairs that often change and it costs two. Two hundred test pairs aligned under each matrix give different alignments in 115 cases — and a matrix fitted to eight pairs of the first kind moves 79 of them, from sampling alone.

 100100occurrences of the patternreadsmost frequent ", and " · 388 occurrencesthe scanthe chain12 documents · 144,617 characters3 of 6 won What the libraries do

What the generated collection was right about

Five strands of conclusions, drawn on collections made by one line with one dial, checked against a corpus nobody made. Most hold. One headline was a property of the generator's alphabet, and one crossing that was guessed at turns out to be met — but only with the structure the strand on range minima built.

 twelve essays — runs0.491generated, matched0.109twelve essays — phrases0.213generated, matched0.046eight source modules — runs0.461generated, matched0.122eight source modules — phrases0.210generated, matched0.050ten revisions of one file — runs0.126generated, matched0.113ten revisions of one file — phrases0.067generated, matched0.047per character24,576 characters a partdivergence 0.02 The data that is not a number

A corpus that was not generated

Every collection in five strands has been copies of a generated text with a fraction of its characters replaced — three numbers, one dial. Here is one that was not — twelve essays, eight source modules, ten revisions of one file — measured beside the model of it.

 run together867 bits a characterone separator877 bits a charactera separator each897 bits a charactergenerated, run together215 bits a characterdistinct symbolstwelve essays0.0% premium The index that replaces the text

Documents that are not the same length

A separator per document costs a whole bit per character — on a generated collection whose alphabet is 21 symbols, where adding a few crosses 32. Real prose has 87 symbols and sits 41 short of the next power of two, so the same separators cost 0.04%.

 ① prose144,617 chars12 docs · median 12,335① code106,283 chars8 docs · median 13,150① revisions75,658 chars10 docs · median 7,774② essays1,004,822 chars82 docs · median 12,335② captions549,210 chars2,214 docs · median 230② history174,282 chars14 docs · median 12,963① the first freeze · ② the second6 parts The data that is not a number

A million characters of the same thing

Every measurement this collection has published about real text was taken on twenty-four thousand characters, because the phrase count was quadratic. It is linear now, so here is the same corpus at forty times the size — and what forty times does to its own numbers.

 10⁴10⁵10⁶characters in the collectionshuffled ÷ real, phraseswhat the order is wortha million characters of prose · phrases per characterx1.37 over the sweep What is taught wrongly

The half of a fall that is the logarithm

Phrases per character on a real collection of essays fall by a factor of 2.34 as it grows. A shuffle of the same characters falls by 1.70. Nearly three quarters of the movement is arithmetic, and no definition of the measure says so.

 ① prose12,33512① code13,1508① revisions7,77410② essays12,33582② captions2302,214② history12,96314documentscharacters in a document① the first freeze · ② the secondmedian marked The index that replaces the text

Two thousand documents of two hundred characters

Every collection this field has measured has been a dozen documents of ten thousand characters. A real collection is usually the other shape, and the other shape moves every term in a document index — one of them by a factor of seventy.

 0200400200400occurrences of the patternrows read, and documents in the answerrows readdocuments in the answertwo thousand short documents · 2,214 documents1.04 occurrences a document What the libraries do

The crossing that never arrives

Output-sensitive document listing exists because a pattern can occur four thousand times in eight documents. On a real collection of two thousand short documents it occurs 1.04 times per document, and the whole apparatus buys nothing at all.

 02468101214mean 5.71depthshare of the collectionten revisionstwelve essays75,658 characters · 2,966 phrasesworst 14, mean 5.71 The data that is not a number

The shape of a real history's depth

Four essays here are about capping how far an extraction follows a chain of copies, and every number in them came from a generated collection. Here is the depth histogram of a real version history, which is a bell, and of twelve unrelated essays, which is nearly the same bell.

 05101520510revisions in the collectiondepthone revision alone: 8worst depthmean depthfourteen revisions of another9 generations added exactly one Structures

One revision, one level

The cap ladder assumed depth is generations of copying. On a real file it is exactly that — one more revision, one more level, nine times running — plus eight levels the first revision already had before any history existed.

 one text16 short documentsprosecopies of one baseprose, one textr/n 0.2996z/n 0.1273prose, many short documentsr/n 0.3053z/n 0.1301copies of one base, run togetherr/n 0.0638z/n 0.0354one copy per documentr/n 0.0768z/n 0.04188,192 characters throughoutthe outlined cell is the one that was empty The data that is not a number

The cell nobody filled

Every structure here was measured either on one long repetitive text or on prose cut into short documents. The collection that is both is a two-by-two with one empty corner, and what is in it is not the product of its margins.

 10⁴0.1charactersphrases of the parse, per charactershuffled: 1.45xthe collection: 4.71x4,111 to 65,551 charactersworth 3.24x after the control The data that is not a number

What repetition is worth once the logarithm is gone

On prose, nearly three quarters of the fall in phrases per character with size is arithmetic that any text pays. On a collection built of copies it is a fifth, and what is left is a factor of three that is genuinely the arrangement.

 ten revisions of one filecap 10worst 14 · mean 5.7fourteen revisions of anothercap 10worst 17 · mean 7.2twelve unrelated essayscap 10worst 14 · mean 4.9eight source modulescap 10worst 78 · mean 5.9a generated collectioncap 10worst 13 · mean 4.6within a twentieth of the free parsefour to eight was the model What the libraries do

The cap that would ship

The published sweep put the knee at four to eight. On four real collections it is at nine to twelve, a cap of one costs forty-eight times the free parse rather than twenty-one, and the number a system should actually set is none of those.

 1.0%10.0%0.11fraction of characters changedper characterthe real runsthe real phrasesgenerated runsgenerated phrasesten revisions of one file · 24,580 characters2.32% against 3.24% What is taught wrongly

The dial that has no setting

The generator has one parameter. The real version history's run count asks it for 2.3% and its phrase count asks for 3.2% — and the reason is not that the dial is badly calibrated. Real edits average 7.3 characters a block and generated ones average 1.04.

 one text16 short documentsprosecopies of one baseprose, one textr/n 0.2996z/n 0.1273prose, many short documentsr/n 0.3053z/n 0.1301copies of one base, run togetherr/n 0.0638z/n 0.0354one copy per documentr/n 0.0768z/n 0.04188,192 characters throughoutthe outlined cell is the one that was empty What the libraries do

A collection is a construction

The same characters, arranged as one copy per document or cut across the copies, give a different run count, a different boundary cost and a different answer about which structure to build. Which one a benchmark used is usually not recorded.

All threads