Measurement — where it appears
Named by 108 essays across 12 fields — each of them below, with the objects they name alongside it.
An index larger than what it indexes
A suffix array over 16,384 characters is 229,376 bits, and it cannot answer a single question without the 81,920 bits of text beside it. Nearly four times the text, to search the text. Every index on this site had been weighed at zero until somebody put one on a scale.
A search that runs backwards
Twenty-three occurrences of a six-character pattern in sixteen thousand characters, found in twelve rank queries and zero character comparisons. Not few comparisons — none. The algorithm never asks whether two symbols are equal, and it knows how many matches there are before it has located one.
The constant the notation drops
Six algorithms on this site are Θ(n log n) and their comparison counts differ by a factor of two. The class is what they have in common; the constant is what distinguishes them. It is measurable to three digits, it is the number that actually decides between them, and it is precisely the number the classification is designed to discard.
The index that is smaller than the text
The Burrows–Wheeler transform is a permutation, so it changes no symbol frequency and a plain index over it is the same size whether the text has deep structure or none — 6.29 bits a character against 6.16, on texts whose third-order entropies differ fourfold. What the transform changed was the runs, and a structure that charges one bit per bit cannot see a run.
A cost that is not one
The same eighty-one cells, filled by the same recurrence, return 6, 10, 10 and 15 — in edits, in cost, in bits and in bits again. Only the first is a count of anything, two of them are equal by arithmetic coincidence, and the alignment each one chooses is different.
The count somebody chose
Six quantities can now be measured for every sort. Ranking the ten algorithms by each of them and comparing the orders, comparisons and peak space disagree about 91% of all pairs, and memory traffic and modelled misses disagree about 7%. There is no ranking of sorting algorithms; there are six, and choosing between them is a statement about the data rather than about the algorithms.
A cell that has to know where it is
A gap of four characters is usually one event, not four. No recurrence over a single table can charge it that way, because the price of a gap character depends on how the cell above it was reached and a cell holding one number has thrown that away. The repair is three tables, and it costs exactly three times the cells.
The shift a set of patterns allows
Aho-Corasick reads every character of the text exactly once, whatever the number of patterns. Commentz-Walter reads backwards inside a window and steps over what it can, and on eight patterns of ten characters it looks at sixty-two per cent of a twenty-thousand-character text. The rule that does the skipping is not the one everybody implements.
A floor under a run count
A structure whose size is a function of the number of runs in a transform must give a different bit string to every text with that many runs, so it needs at least the logarithm of how many such texts there are. That count is walked rather than estimated — all four thousand and ninety-six of them — and the representation everybody uses turns out to have five bits of slack.
The filter that feeds the table
A self-index answers exact queries and nothing else. Approximate matching needs a table with twenty thousand columns in it. The pigeonhole joins them — cut the pattern into k+1 pieces and at least one occurs exactly, and the index that cannot answer the question decides where to ask it.
The sampling that goes the other way
An FM-index hands the text back, and the way it does it is to walk from the last character to the first. So thirty-two characters from the end cost thirty-three steps and thirty-two characters from the beginning cost eight thousand one hundred and ninety-two. The repair is a second array the same size as the first, indexed the other way round.
The clock that cannot see the burst
A stream generator asked for a burst ten times faster than its mean rate, on a clock whose resolution was the mean gap, produced a perfectly even stream — index of dispersion 0.00, for something called bursty. Nothing had gone wrong except that the instrument could not represent what it was being asked to measure.
The entropy that cannot see a copy
Two copies of a text have exactly the same symbol statistics as one, so every entropy on this site doubles when the second copy arrives and the second copy carries no information at all. The number of runs in the Burrows-Wheeler transform is 224 at two copies and 224 at thirty-two.
The index that stores the runs
A compressed self-index over thirty-two copies of a text is 30,557 bits, because its size follows an entropy that cannot see a copy. An index that stores the transform as its runs is 11,900 — and at a single copy it is the larger of the two, which is what makes the comparison a claim about repetition rather than about size.
What a window costs in bits
The approximate structure grows like the square of a logarithm and the exact one grows like the window, so the approximation wins eventually. Eventually is a window of 6,000 at a 2% tolerance — and below it the summary is larger than the thing it is summarising.
Rank is the only thing it does
Constant time and o(n) extra space — a phrase true of a rank directory costing 163% overhead and reading three words, and equally true of one costing 3% and reading eighteen. Both numbers are decided by two integers somebody typed into a header, and the phrase names neither.
Select is not rank backwards
Rank counts the ones before a position and select finds the position of the k-th one, and only the first has an obvious structure. The constant-time answer costs 1.56 bits per one, is bounded in a unit the machine does not charge for, and on a vector with one bit in fifty it inspects more positions than the binary search it replaced.
The pass that was never a parameter
One pass is the streaming model's defining restriction, and this collection has enforced it by making a second read throw. A prohibition cannot be swept. Turn it into a dial and the first thing it says is that a second pass turns eighteen candidate heavy hitters, six of them wrong, into twelve that are exactly right — for 3,680 bits carried across the boundary and no extra space at all.
The row that starts at zero
The same 1,413 cells, filled by the same recurrence in the same order, answer 148 and 0. One line of initialisation decides which question the table was asked, and only one of the two answers is about whether the pattern is there.
The summary that has to forget
Every structure in this field so far accumulates. Ask instead for the count over only the last thousand arrivals and no counter will do, because a counter has no record of which of its increments are old — and the repair is a row of buckets whose whole error is the oldest one.
The text that does not have to be kept
The index reproduces its text character for character, in 1,024 mapping steps and zero reads of anything. That is the whole justification for weighing it against the text rather than beside it — and the price is a dial that moves the structure by 3.3 times and the cost of locating one match by 72.
The sampling that follows the runs
A run-length index over thirty-two copies of one text spends 11,286 bits on its suffix-array sampling and 5,605 on the transform it was built to compress. Sample at the run boundaries instead and the sampling is 10,942 bits that stop moving — two values per run, and a function that fills in everything between them.
The bits that say when
A windowed cardinality estimator holds 4,592 bits and 2,392 of them are clocks. Every summary in this collection has reported its size from the shape of its own structure, and not one of those numbers has ever been asked what the bits were for — so the resource that half of these structures spend most of their state on has been invisible while being counted.
What a second pass buys
Exact selection of a median from thirty-two thousand values needs the whole stream in one pass — a million bits — and eleven thousand in two. By nine passes it is three hundred and twenty. The state falls as n to the power one over p, which is a law with an exponent worth fitting, and on skewed data the deterministic rule misses it by three orders of magnitude.
A function with r pieces
Computed at every one of eight thousand positions across four texts, a function defined on the whole suffix array agrees exactly with r−1 anchors and one addition. Anchor it at the successor instead of the predecessor — one character of code — and it disagrees at 506 of 800 positions while still returning plausible numbers.
The occurrence carried through the search
Backward search returns how many and not where, and every index on this site pays for the second question separately. Carrying one occurrence along with the interval costs a lookup on 75% of the steps for a two-character pattern and on 18% of them for a sixteen-character one, and it is what makes a run-boundary sampling usable at all.
The phrases a text copies from itself
Four thousand characters of English-like text hold 604 phrases in the greedy parse and 1,219 runs in the transform. Thirty-two copies of one text hold 156 phrases and 233 runs. Two measures of repetition, neither of them an entropy, and they do not agree about which text is the more repetitive.
A floor that holds if something else does
The four lower bounds on this site are proofs. This one is a chain of implications with a conjecture at the top, and neither end of it is proved. The link that can be performed is performed here — checked over 55,754 formulas, 918 of them unsatisfiable — and the link that cannot is quoted and marked as quoted.
A register that became a list
HyperLogLog replaces a key per distinct item with a five-bit register, and over a whole stream that is a saving of a hundred times. Ask it about the last four thousand arrivals instead and the same comparison against the same exact structure comes out at five. The estimator did not get worse. The exact answer got cheap.
Sized for a rate that does not hold still
A four-second window on a stream at a hundred arrivals a second holds four hundred items on average and between 105 and 2,169 when the rate moves. An allocation set at that average overflows at 47 per cent of instants while 35 per cent of it stands empty, which is the same decision failing in both directions at once.
What is still proportional to n
An index whose size is a function of the run count still has an n in it, and at thirty-two copies of a text the n is half of it. Everything that stores the transform grew by 45 per cent; the two arrays that answer "where" grew by eighteen times, and neither of them has anything to do with repetition.
An index with z in its size
Over thirty-two copies of one text, an index built on the parse is 8,892 bits, the r-index is 17,047 and the entropy-bounded index is 34,615. Over eight thousand characters of four-symbol text the same three are 7,844, 25,177 and 20,413, and the smallest of the three has changed places twice.
The occurrences that cross a boundary
One pattern, thirty-two copies of a text, thirty-two occurrences. The search finds one of them and produces the other thirty-one by arithmetic, and the count it finds is the same one at two copies, at eight and at thirty-two — the searching does not grow when the answer does.
The branches an error opens
The tree multiplies by 19.6 for the first error, 12.3 for the second, 10.3 for the third and 8.8 for the fourth. A branching factor of four on a sixteen-character pattern would predict sixty-four, and the gap between sixty-four and eight is the intervals emptying.
The table that fits inside a block
A block of six parentheses has sixty-four possible shapes and twenty-eight questions can be asked about each, so all 1,792 answers fit in a table of 9,408 bits — computed once, shared by every structure of that block length, and never counted in any of their sizes.
A floor one pass cannot get under
An exact one-pass selector must reach a different memory state for every prefix it might have read, and the pigeonhole that proves it is small enough to perform — nine hundred and twenty-four prefixes through a nine-bit state, the collision produced, the suffix that separates it, and two true medians it cannot both return. Ten bits collide on none, so the bound is exact — and a second pass walks under it by a factor of ninety.
An error measured against the answer
A quantile summary asked for the 99.9th percentile answered 9,694 where the truth was 256, and violated nothing — its promise was a rank error under one per cent of the stream and it delivered a tenth of one per cent. One per cent of the stream is a thousand per cent of the tail, and no amount of extra state changes that.
The q-grams an error cannot destroy
A pattern of twenty-four characters holds twenty-one four-grams. Two errors can destroy at most eight of them, so any occurrence with two errors still shares thirteen — and a filter that keeps only the windows sharing thirteen proposes 104 of 3,977 and computes 16,744 table cells instead of 96,000.
The search that spends a budget
A backward search narrows one interval per pattern character. Give it a budget of three errors and it narrows 39,943 of them instead, finds every occurrence the whole table finds, and reads not one character of the text — 177,046 index ranks against 60,000 table cells and zero characters examined.
The table that walks every pair
The exact shift rules cost 769,724 character comparisons to build for 128 patterns and the published ones cost 5,604. The scan they are both built for reads 41,580 characters, so one of the two constructions is eighteen times the work it is there to save.
The rule that pays on a long enough text
With two patterns, the cheap tables cost 106 steps and the scan reads 13,084 characters; the exact tables cost 594 and the scan reads 12,306. Below thirty-two thousand characters the cheap tables win the total, above it the extra skipping pays for them, and with thirty-two patterns there is no crossing at all.
A promise about the rank is not a promise about the value
A quantile summary asked for the 99th percentile of a log-normal stream returns the largest value it ever saw — 2,169 against a true 318, six times too high — and its rank error is 1.00% against a promised 2%. The guarantee held. It was never about the number.
The ceiling the shortest pattern sets
A matcher that skips is described as faster than one that reads every character, and the description leaves out what decides it. No shift can exceed the shortest pattern in the set, so adding one two-character pattern to fifteen of sixteen characters takes a run from reading fifty-eight per cent of the text to reading all of it twice.
The floor a histogram already knows
A summary of thirty-two counters settles at a smallest counter of 119, and the number can be computed from the shard's key frequencies before a single counter is allocated. The obvious way to compute it is wrong by a factor of two, and the reason is that the heavy counters carry no error at all.
The floor charged at every level
A key surviving a fold of sixty-four shards is charged 2, then 8, then 20, then 43, then 88, then 248 — the floor of whatever summary it was merged against, level by level. They sum to 409, and the damage read off the merged table is 409. The model that charged sixty-three copies of the leaf floor said 222.
The tuples a summary does not report
A Greenwald–Khanna summary at ε = 0.01 answers `tuples` with seventy-seven. Watched through the run it holds a hundred and thirty-six. The gap is the compression period, it is 1.70 to 1.93 times across every tolerance measured, and it is the number a deployment has to allocate.
The shift somebody published
The exact rules for shifting a multi-pattern window are a definition that quantifies over every pattern at every offset. The 1979 rules are two tables read off the trie's own failure links, they are computed in one pass, and on this pattern set they agree with the definition at every node.
The collection decides which index is small
Three compressed self-indexes over one text of five hundred characters measure 3,511, 7,285 and 10,974 bits. Repeat that text thirty-two times and the same three measure 34,615, 8,892 and 17,047 — the ordering has completely reversed, and nothing about any of the structures changed.
Where the exact rules pay now
With a construction as cheap as the published one, the exact shift rules pay for themselves past eight thousand characters of text at two patterns, four thousand at four, and never at thirty-two — because by thirty-two patterns the two rules make identical decisions.
The branch that cannot reach an answer
Seventy-two rank operations over the pattern remove 27,906 of the 39,957 interval extensions a bounded-error index walk performs — 70% of the tree, at a budget of three. The share grows with the budget, which is what a pruning has to do to be worth its cost.
A floor with two variables in it
Under round-robin a Space-Saving summary's floor is 0.0203·n^1.018 over a hundred-and-twenty-eight-fold range of shard size, worst residual 2.7%. Under hashing the same measurement has no exponent at all — the local slope runs from n^5.17 to n^1.19 — and a least-squares line through it reports n^1.73 at a 441% residual.
The filter that proposes everything
Seed-and-extend saves two thousand times the work at zero errors and costs more than doing nothing at four. Between them the selectivity falls through the floor, and where it falls is set by two numbers that can be computed before the filter is run — one of which does not contain the length of the text at all.
Every occurrence at the same price
A regular sampling has one dial and it moves two costs together — 1,495 bits at 63 LF steps an occurrence, 131,088 bits at none. A sampling at the run boundaries sits at 10,244 bits and one predecessor query, which is a point the curve reaches only at 69,649.
The candidates a filter cannot avoid
A phrase index answers a search by intersecting two ranges of boundaries, and it does the intersection by walking the smaller one. On a collection of thirty-two copies that is 4,355 phrase examinations to produce 32 occurrences — 136 examinations each, and rising.
A parse that will not follow a long chain
A greedy self-referential parse bounds the copy depth by nothing at all — thirty-two copies of a text give a position costing twenty-two phrase follows. Restricting every phrase to sources no deeper than D holds it at D, and the whole question is what that costs.
The number that would choose a cap
A depth histogram is one linear pass — 3.16 operations a character over thirty-two thousand of them — and it says the whole text sits at a mean depth of 3.98 with a worst of ten. Nobody prints it, and every choice of cap in this collection was made without it.
The lattice that decides the ties
Rounding a fitted substitution matrix to whole bits puts 63 of 200 alignments on a tie where the exact fit puts 15. Rounding to half bits — a finer grain, and the obvious repair — puts 79. What tracks the ties is not how fine the lattice is but how many of the six fitted costs it keeps apart: whole and half bits both leave three, an eighth of a bit leaves all six, and matches the exact fit exactly.
A distance that is not a distance
Under unit cost the edit distance obeys the triangle inequality and this site asserts that it does. Under a stated substitution matrix it need not, and on 42,840 enumerated triples it fails 2,832 times — taking with it every structure that prunes by distance, at a measured 13.22% of the bounds they rely on.
The count that outlives its arrivals
A Misra-Gries counter holding six thousand is not a record of six thousand arrivals. It is a number that has been added to and taken from, and nothing in the structure says when any of it happened — so when the key stops arriving the counter stays, and goes on reporting a key with nothing in the window as the heaviest thing in it.
The window that is even in the wrong currency
A window of four thousand arrivals in eight blocks retires a block every 5.1 seconds on a steady stream and anywhere between 0.57 and 14.8 seconds on a stream whose rate moves. The structure cannot tell, because it is counting arrivals, and the alert written against it is in seconds.
The character that costs a chain
The index over thirty-two copies is 8,892 bits and does not grow. Producing one character of the text it indexes costs 17.89 phrase-follows on average and 38 in the worst case, against 2.38 and 7 at one copy — the size stopped growing and the price of reading it did not.
What a ceiling costs in phrases
A cap of sixteen costs one phrase of a hundred and fifty-six and halves the worst chain. A cap of four costs six times the phrases. The curve between them is flat at one end and vertical at the other, and the elbow is where a structure should be built.
The errors the rest of the pattern needs
Read the pattern left to right in an index of the reversed text and count the points where the interval empties. That count is a lower bound on the errors any alignment of the prefix must contain, it costs 72 rank operations, and it removes 70% of a search tree.
The cost that is the size of the answer
Ten range-minimum queries answer the listing at every point of a sweep where the occurrences run from 30 to 790. They cost 256 to 288 node visits — and the scan they replace costs 30 to 790, so the output-sensitive method loses until about thirty occurrences per document.
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.
The counter that takes the smallest slot
Space-Saving keeps two numbers per key and they bracket the truth from both sides. On the twenty heaviest keys of a stream its mean error is a tenth of one arrival, against a hundred and ten for Misra-Gries at the same bits — and on the keys ranked past a hundred the ordering reverses.
The period that is not a promise
Greenwald–Khanna's ε appears twice — once as the rank tolerance the structure promises, and once as ⌊1/2ε⌋, the number of updates between compressions. Unhook the second from the first and sweep it across a thousand-fold range. The tuples held move by 10%, the worst rank error by 21%, the peak by ten times and the housekeeping by seventy.
Two structures that are one
Space-Saving never underestimates and Misra-Gries never overestimates, and they are taught as rival structures with opposite failure modes. Subtract one number from every Space-Saving counter and what is left is the Misra-Gries table, key for key and count for count, at all twenty thousand prefixes of a stream and at every table size tried.
The structure paid for before the first query
The two grids that make a phrase index's search proportional to its answer are 3,240 bits on an 8,892-bit index — twenty-seven per cent of the whole structure, answering nothing on their own, and 38% of them is rank directory rather than payload — the lower-order term of the published bound, measured.
The table the links already knew
The exact good-suffix rule costs 757,058 character comparisons to build from its definition at 128 patterns, and 3,824 from the trie's failure links. Same table, checked at every node — a factor of 198, and the definition was never the algorithm.
A list of documents is not a list of occurrences
A pattern occurring 790 times in eight documents has an answer of size eight. Reading every occurrence to find out costs 790 array reads; the question a collection has that a text does not is the one its index does not answer.
Where a crossing moved to
The prediction was that a succinct range minimum would move the document listing's crossing "to a handful". It moves it from 32 occurrences per document to 11 — a factor of three, not an order of magnitude — because a constant-time query is ten lookups rather than one.
The digest that promises nothing
The t-digest is the quantile structure most widely deployed and the only one with no proven bound on its rank error at any quantile. Measured, it beats the structure that does have one — and on two clusters with a gap between them it returns 431.5, where the data holds nothing at all between 40 and 800.
The term that came back
A phrase index is worth building because 8,192 characters parse into 156 phrases. Cap the copy depth at one and the same text parses into 7,351 — ninety per cent of the characters — and the structure is proportional to the text again.
An interval that grows at both ends
A backward search step is two ranks. A bidirectional step is two ranks and the width of the interval for every symbol that sorts before the one being added — 16.5 ranks on four symbols and 138.6 on twenty-six, which is a cost no account of the structure mentions.
The search that starts in the middle
The same pattern, the same six occurrences, the same index — and 830 interval extensions, or 303, according to which end the search begins at. A pattern cut into three pieces has an error-free one, and only a search with two ends can start there.
The cap an automaton cannot see
A state of a suffix automaton stands for a set of occurrences and hands back one of them. So a capped parse driven by it can ask whether the earliest occurrence is shallow enough and cannot ask whether any occurrence is — which costs up to 9.8% of the phrases, and only at the caps that bind.
The histogram that cannot see the order
A prediction accurate to one per cent on three streams is seven times out on the fourth, and the input that fails is the one every capacity plan is built from. A statistic computed from the same input says in advance which case is in hand — and misses one of the two ways it can go wrong.
A bound that has to be paid for
The pruning removes seventy per cent of a search tree for seventy-two rank operations. It also needs an FM-index of the reversed text — 17,033 bits against the forward index's 17,032 — which doubles the structure whose small size was the entire argument for walking an index.
A block, a class and an offset
Replacing each block of a bit vector by how many ones it holds and which arrangement it is takes 7.6% off the grid. On a permutation with no structure at all it takes 2.6%, so five of the seven points are the data and two of them are the encoding.
The parse in one pass of the text
The same parse, phrase for phrase, from 1,324,336 character comparisons or from 25,420 transitions and suffix-link steps. One of those numbers grows with the text and the other grows with its square, and the difference is why every measurement about a depth cap here was taken on a few thousand characters.
The boundary that hides the burst
A window whose blocks hold five hundred and twelve arrivals reports a perfectly even stream — every block the same duration to the tick — while the arrivals it is retiring have an index of dispersion of 0.57. Move the block to a hundred and twenty-five and the same stream varies by 1.8 times.
One separator, or one for each
A shared separator costs one alphabet symbol and is free. Fifteen distinct ones take the alphabet from twenty-two to thirty-five, which crosses a power of two, so every character of every document costs a sixth bit — 1.2 times the packed collection, to tell the boundaries apart.
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.
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%.
The sampler that cannot alias
A block window's boundary fires on an arrival count, and a stream whose burst repeats every sixty-four arrivals is reported as perfectly even by a block of five hundred and twelve. A quantile summary compresses on an update count, which is the same arrangement. Swept against three periodic value processes and their shuffles, it does not alias — and the reason is one line of arithmetic rather than a lucky sweep.
Two bits a value, and what undoes them
The parentheses of a range minimum over 65,536 values are 131,072 bits. Everything that makes them answerable is 651,800 more — five times the payload — and one encoding choice nobody quotes accounts for a sixth of it on its own.
A parameter that waits for another
Four merge fold shapes over thirty-two evenly loaded shards leave errors of 665, 667, 665 and 667 — a fifth of a per cent apart. Give the same four shapes shards whose loads span seventeen-fold and they leave 148, 183, 323 and 403. The parameter did nothing until a second parameter moved, and every measurement that fixed the second one saw nothing.
The structure that was supposed to halve
A bidirectional index holds the transform of the text and the transform of its reversal — 35,335 bits each, 70,670 together, exactly twice one index. The deferral that named it hoped it would stop the index doubling. It does not remove the doubling; it reuses it.
The floor a merge does not settle at
Compute a fold's level floors from the shard histograms and the prediction over-shoots by 1.73. A merged summary's floor is not the floor a summary settles at on the same arrivals — it is 0.90 of it at four shards and 0.70 at sixty-four, straight in log₂ m at a 3% residual, because merging preserves the heavy counters and never runs their eviction cascade.
The shape a range question is about
A range minimum is a question about a tree, and the tree is determined by the array. Twelve values, eleven parent links, and the answer to every one of the seventy-eight ranges is a lowest common ancestor — with the values themselves no longer needed.
A bit for every bit
A grid over 3,612 points is 43,344 bits of payload. The smallest any structure can be that distinguishes one permutation of 3,612 things from another is 37,485. There is 16% to play for, and the deferral that asked for a compressed grid assumed there was much more.
The warning that is silent for the right reason
The statistic shipped to warn that a merge prediction is about to fail reads 0.160 on a stationary stream, 0.172 on a bursty one and 0.909 on a drifting one. It was asked to be looked at again because it does not catch a burst. It does not, and the reason is that on a burst there is nothing to catch.
The runs a permutation does not leave
A run of length L costs 2⌊log₂ L⌋ + 1 bits and replaces L, so coding runs pays above a mean run of six. This grid's mean run is 2.34, chance gives 1.90, and coding its runs makes it 17.8% larger.
A sampling that costs more than the array
On four-symbol text the transform has 0.75 runs a character, so a sampling of two suffix-array values per run is one and a half values per position — 271,565 bits against the 131,088 that keeping every value costs. The structure built to remove a term proportional to the text is twice the thing it replaced.
The measure that cannot see the alphabet
Take a Fibonacci word of 4,181 characters and transform it with a before b — six runs. Transform the same word with b before a — nineteen. The parse gives eighteen phrases either way, and the gap between the two run counts grows with every word in the family.
The threshold that reaches zero
At q = 5 and four errors on a twenty-four-character pattern the filter demands zero shared q-grams, proposes all 2,977 windows, and computes 986,266 table cells where filling the whole table would have cost 96,000. The failure is arithmetic and is knowable before a character is read.
Three savings in three currencies
The same six occurrences, found four ways. The table computes 60,000 cells and reads 60,000 characters. The counting filter computes 6,251 cells and reads 13,022 characters. The seed filter computes 3,325 and reads 550. The index walk computes none, reads none, and performs 18,645 ranks.
What the approximation gives up
Compared at every one of the 3,736 decisions a search could ask about, the published shift rules and the exact ones agree at all of them on a set of 128 patterns. At two patterns they differ at five of 84, by up to four positions — and the run reads 6.3% more characters.
The operations a candidate count leaves out
The grid examines 33 candidates where the scan examines 4,355 — a factor of 132. Counted in the operations each of them performs, the same query is 2,471 against 4,355, and the factor is 1.8.
The cap that binds on one text and not another
A periodic text looks like the one made of chains and pays 1.11 times the phrases for a cap of four. A text that repeats itself pays 2.96. The guess is backwards, and the reason is that depth measures nesting rather than repetition.
The pruning that loses an occurrence
Two versions of the same lower-bound pruning, each one character away from correct. Both return only real occurrences, both return fewer of them, and no check that asks whether the answers are right can tell either from the truth.
The ratio that was an implementation
This collection published a factor of forty-two between two shift rules' preprocessing. Sixty-nine per cent of the denominator was a table the published rule never reads, and the numerator was a definition rather than a construction. The corrected ratio is 1.6.
The occurrences a join invents
Eight documents run together hold forty-nine eight-character windows that span a join, twenty-three of which occur in no document at all. Every index built over the concatenation reports them, and five essays of this collection paid that cost silently.
A schedule nobody writes down
A search scheme is valid when its searches between them cover every way the errors can fall — ten cases at two errors, enumerable in a line. A scheme missing one of them finds seven occurrences of eight, all real, at the right error counts, and reports nothing wrong.
The level where compression stops paying
Choosing the best coding for every level of the grid separately, rather than one for all twelve, saves 26 bits out of 47,668 — five hundredths of one per cent. The apparatus for choosing costs more than that to describe.
What a quadratic construction was setting
A depth cap of one costs 90% of an 8,192-character text in phrases, and 86% of a 65,536-character one. The ladder's conclusions hold at thirty-two times the size — and the number the ladder could not reach, the deepest chain a real collection produces, turns out to be fourteen.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Trade offIndex sizeHonest limitSelf-indexSpace overheadRepetitionConstant factorFM-indexState bitsPhraseAlphabetRun-length