The thread: A model is not a corpus
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.
What the libraries doWhat 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.
The data that is not a numberA 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.
The index that replaces the textDocuments 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%.
The data that is not a numberA 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.
When the algorithm is a tableThe counts only short words carry
A spelling checker capped at two edits still gives a false suggestion to many words its vocabulary lacks, and the one evidence about a writer's intention it already holds is how often each vocabulary word is used. Scored by its nearest words' counts, weighed a tenth for each edit, an answer was predicted to separate a slip from an unfamiliar word on short queries. On the streams the checker was built against, whose typos are of words drawn evenly from the list, the false suggestions go to commoner words than the corrections do, and the test gives up sixteen corrections for each false suggestion it removes. Drawn as a writer mistypes, in proportion to use, the counts separate the two at last — and still trade worse than a plain cap of one edit, except on words of four letters or fewer, where a threshold removes a ninth of the false suggestions for one correction in ninety-six.
What is taught wronglyThe 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.
The floorsWhere a context stops naming the letter before
A sort of rotations by their first k characters matters only where those k characters fail to decide the character before them, and that share of positions can be counted in one pass with no sorting. It was proposed as a replacement for sweeping k. Counted as proposed, it misses by a factor of four: on a stream of independent words 37% of positions are still ambiguous at four characters, where the sweep has already gone flat. Counted only where the context sits inside a word that goes on past it — the one place more context can still help — it lands within a step of the sweep on four sources of five.
The index that replaces the textTwo 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.
What the libraries doThe 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.
The floorsThe repeats a context cannot see past
Sorting rotations by their first k characters stops losing to the full Burrows–Wheeler transform at four or five characters on four sources and at about ten on a corpus of technical writing. The count proposed to explain the exception — how much a context spanning a word boundary says about the letter before it — cannot be read off its own estimate, which falls on words drawn independently where there is nothing to find. Measured against each text's own shuffled twin, the information the word order carries is real, but it has all arrived by four or five characters, and at eight, twelve and sixteen the two corpora are indistinguishable. What does separate them is repetition. Stream by stream, the share of positions inside a repeated sixteen-character string predicts the technical corpus's loss with a correlation of 0.98.
When the algorithm is a tableThe commonest word at the distance
A spelling checker that lists every nearest word counts a correction whenever the intended word is somewhere in the list, and on a short query that list averages three or four words. Offering only the commonest of them was predicted to keep nine in ten of the list's corrections on short words when misspellings follow use, and far fewer when they are drawn evenly from the word list. It keeps 77% on words of three or four letters, and on the even stream it keeps 48% — less than a choice that ignores the counts. Across all lengths the two streams look the same, which is how the difference stays hidden.
The data that is not a numberThe 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.
When the algorithm is a tableA list as long as the doubt
A spelling checker that offers one word is right 64% of the time on short misspellings, and one that offers three is right 80% of the time. Between them sits the obvious design: one word when the commonest nearest word's count dominates the next, more when the counts are close. The counts do know when the commonest word is right, from 36% of the time at a ratio under two to 91% over a hundred. Yet a list sized by that ratio beats a blind mix of one word and three by at most two and a half points, a plain list of two does as well, and on misspellings drawn evenly from the word list the ratio is worse than not reading it.
StructuresOne 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.
The data that is not a numberThe 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.
When the algorithm is a tableA second word judged by its own share
A spelling checker that offered its commonest nearest word alone when that word's count was many times the next, and two or three words otherwise, beat a coin's mix of one-word and three-word lists by at most two and a half points, and a plain list of two did better. The ratio measures how dominant the first word is, not how likely the second is. Judged instead by its own share of everything within two edits of the misspelling, the second word is shown only when that share is at least 0.15: on short words drawn by use the checker then sits 4.5 points over the coin's line at 1.32 words a query, nearly twice the ratio's lift and above the list of two, and the weight given a two-edit word moves the result by a tenth of a point. A second word with a share under 0.01 is never the source. On misspellings drawn evenly the share is no guide at all, and the list of two wins.
The data that is not a numberWhat 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.
What the libraries doThe 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.
When it does not fitA span the queries do not see
A rule for dividing a levelled store's range-filter memory by its levels' sizes, with a floor of half a bit a key, came within five points of the division fitted to the store's own queries at every budget from one bit up — but at half a bit the shuffled and the clustered store wanted opposite divisions of identically sized levels. A level's fences, its first and last keys, say how much of the key space it spans, and a clustered level spans little. Scaling each level's bits by that span was predicted to close the half-bit gap and change nothing above. It changes nothing at half a bit — where the floor is the whole budget, so there is nothing left to scale — and from one bit up it puts the clustered store 30 points behind the fitted division, where the floored rule was within one. A level holding one cluster spans 0.4% of the key space and meets 4.4% of the queries, because half of them start at a stored key: the fences measure the key space, and the queries are aimed at the keys.
The data that is not a numberA layout the traffic does not move
A bidirectional index whose bit vectors code each block as an arrangement or a gap code saved bits at equal work once the choice was priced where a workload's ranks land. Traffic changes, so a layout fitted once was predicted to lose most of that gain when the searches moved from one half of a text's commonest patterns to the other's, and an index that recoded its blocks every thousand searches from their own counts was predicted to keep it. Neither happened, because nothing needed to be kept. Priced on the first half's patterns and never changed, the layout does 8.24 units of in-block work a rank on the second half's, 1% above a layout refitted to them for free; recoding every thousand searches rewrites 48 of 385 blocks, 0.71 bits a character, and ends no better. The busy blocks are where the text's common substrings sort, and both halves share them: 27 of the 39 busiest blocks under one half's patterns are among the 39 busiest under the other's.
What is taught wronglyThe 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.
What the libraries doA 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.
The index that replaces the textThe collections the saving was quoted for
A document array compressed to the entropy of its own symbols saves exactly what the collection's length distribution allows, and the measurements that showed it used four constructed collections. The estimate they ended on — a directory of source files is roughly log-normal, so its array falls about a bit short of the plain one, around 17% — can be checked on a real directory. A project's 222 source files fall short by 0.66 bits and save 10.5%, a fifth of which is only the rounding of ⌈log₂ d⌉. Across six real collections the skew of the lengths is worth between nothing and 0.76 bits, and the log-normal formula overstates it wherever short documents are common.
The index that replaces the textThe shape arrived early and the bytes late
A document array coded by its documents' lengths was predicted to survive a growing collection: fitted once at a quarter of a project's files, it would lose under a tenth of a bit a symbol by the end, because the spread of the sizes is set early. The spread was set early — 0.88 at 56 files, 0.90 at 222. The fitted code loses 0.50 to 2.08 bits all the same, because the files added after the fit hold 43% of the final bytes and every one of their symbols is named through an escape. Rebuilding only the escape's subtree brings it to 0.18.
The index that replaces the textOne doubling late
A document array coded by its documents' lengths and refitted each time a growing directory's files double needs an escape for the files added in between, and the escape's right weight is the share of the characters still to come. Weighting it by the share that arrived since the previous refit was predicted to cut the mean loss below a quarter of a bit a symbol. It cuts nothing: 0.518 bits a symbol, against 0.389 for an escape that always takes half the coding space. The growth seen is the growth to come one doubling late — 71%, 50% and 27% where the doublings that followed brought 50%, 27% and 8% — because this directory's growth slowed at every doubling, and before the first refit there is no growth to read at all. A Huffman code also rounds every weight to a whole number of bits, so being right within a factor of two buys nothing. Started from half, the growth seen averages 0.356, the best a store can know, and the weight nobody can know reaches 0.183.
The index that replaces the textRefitting when the escape is wrong
A growing directory's document array, coded by a Huffman code over its files' lengths and refitted each time the files double, loses at best 0.356 bits a symbol for 5.65 final arrays of rewriting, and even an escape weighted by the growth still to come loses 0.183. A clock read off the structure — refit when the share of characters named through the escape passes twice the share its code word stands for — was predicted to refit about six times and halve the loss. It refits 25 times, eleven in the first twelve versions, and rewrites 10.6 arrays for a loss of 0.042. Held back until the characters have grown by a quarter since the last refit, it refits 11 times and loses 0.098 bits a symbol for 4.52 arrays: under every doubling schedule on both counts, including the one that reads the future. It sees anything only if the escape starts small: weighted as half the coding space, the escape's code word is one bit, nothing behind it can ever pass twice a half, and the clock never fires.
Two parametersA switch that hears the traffic stop
A landmark watch switched off by a count of the traffic's stretch ends cannot see traffic slow down, because a slowing is the events stopping, and a count of events keeps its last reading. Letting the open spacing since the last stretch end into the reading, once it is longer than the recorded ones, was predicted to turn the watch back on within four thousand queries of a slowing and cost nothing on steady traffic. It costs nothing on steady traffic, and on ten stretch ends it hears the slowing late, after three to eleven thousand queries, because the silence is averaged with nine fast spacings. On five or three it hears it in time, and the switch on five comes within two cells of the best known policy on every stream.
Two parametersA silence that overrules the count
A landmark watch switched to the corners by a count of the traffic's stretch ends heard a slowing only once the silence outweighed the fast spacings it was averaged with, about 5,900 queries on ten stretch ends. Letting an open spacing of 1,600 queries overrule the count outright was predicted to make the count's length stop mattering on the stream that slows. It hears the slowing within a thousand queries at every count from three to ten, and keeps the corners 8% of the slow half where the count kept them 65 to 75%; the counts still differ, by 3.4 cells a query, because the fast half is where a short count keeps the corners that pay. On the stream that speeds up the override is the cheapest switch at every count, and on steady traffic it is within a cell and a half of the silence.
Two parametersA gap between off and on
A landmark watch switched to the corners whenever a count of the traffic's last stretch ends read under 1,600 queries, and back on when a silence of 1,600 overruled the count. A count that only decides when traffic is fast need not use the silence's threshold, so a second, lower one was given it: keep the corners only once the count reads under 1,200. At one jump of the destination in 2,500 queries, on three stretch ends, that saves 3.5 cells a query — 117.8 against the override's 121.3 — but keeps the corners 13% of the time, not under 5%, and stays 1.4 cells above the watch rather than within one. At one jump in 1,000, where the corners are right, the gap costs 1.7 cells; on five stretch ends it saves nothing anywhere; and at slower paces, on traffic that changes pace and on drift, it changes nothing. The two jobs do want two numbers, but only one count length wants them.