Rounding — where it appears
Named by 5 essays across 3 fields — each of them below, with the objects they name alongside it.
The ties a rounded matrix makes
Measure how far each optimal alignment is from a tie — the smallest change to any one cost that makes another alignment win — and it predicts which alignments a refitted substitution matrix will move. A resample of the same corpus moves 30 of the 63 test alignments that sit on a tie and 3 of the other 137. A matrix fitted to a different divergence moves alignments far from a tie as well, and the prediction weakens to a chance of 0.62. And a third of the alignments were on a tie only because the matrix was rounded to whole bits — fitted without rounding, 15 of 200 are, and every prediction improves.
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.
The grain a corpus chooses for itself
A fitted substitution matrix can choose its own rounding lattice: the coarsest grain that keeps all six of its costs apart. On eight resamples of the same 400-pair corpus that grain comes out anywhere from an eighth of a bit to a forty-seventh, because it is set by whichever two costs happen to land closest, and those two differ by less than a tenth of their own standard error. Asked instead which costs it can actually tell apart, the corpus pools six into the generator's two and chooses an alignment the generator agrees with for every one of 200 test pairs on every resample.
A saving quoted without its collection
A check asking whether a compressed document array is smaller than the plain one passes on the rounding whenever the document count is not a power of two. It would report a saving of nothing as sixteen per cent, on a collection that has no redundancy at all.
The 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.
Named alongside it
The objects these essays reach for when they reach for this one.
CorpusAlignmentCost modelEstimatorFittingHonest limitParameter choiceSensitivity analysisSubstitution matrixDocument arrayDocument collectionEntropy