The order the column cannot see

The deepening the sort was already doing tried to save the Burrows–Wheeler transform some of its reading. The transform sorts every rotation of a text completely, reading as many characters of each as it takes to tell it from its neighbours, and its output is the last column of that sorted list: the character before each rotation. A cheaper sort orders rotations by their first $k$ characters only and leaves rotations that agree on those $k$ in the order of their positions. The page deepened that cheaper sort only inside ranges whose contexts repeat at twice the depth, and it recovered the transform’s bits on every stream. It read more characters than the transform to do it, 74.5 a symbol against 69.4 on technical writing, because a comparison sort of rotations already reads deep only where rotations agree. The transform was the adaptive sort.

Its closing section changed the question. A sort that must stop somewhere, because its reading is capped or because it runs a fixed number of passes, has a budget, and the question is where to spend it. The transform spends wherever rotations agree, whether or not their order changes the output. But a range of rotations all preceded by the same character writes the same run into the last column whatever order it is in, and reading through it buys nothing. The proposal compared two ways of spending a budget on the ranges a sort by four characters leaves. One takes the ranges whose rotations agree longest, as the transform would. The other takes the ranges whose rotations are preceded by the most different characters, which is what the output’s bits depend on. It predicted that on technical writing the second would reach within a hundredth of a bit of the transform at two thirds of the transform’s reading. It named one way that could fail: counting the preceding characters in a range might cost as much reading as the deepening saves.

Ranges, prices and two orders of spending #

Each stream is 8,192 characters, eight streams from a corpus of essays about algorithms and eight from a corpus of technical writing about instrumenting programs, the streams every essay on these sorts has used. Each is first sorted as rotations by their first four characters, ties broken by position. Every maximal run of two or more rotations that share those four characters is a range, about 1,400 of them a stream. Deepening a range means sorting it completely, as the transform would, reading from the fifth character on, and its price is the number of characters that sort reads. A budget is stated as a share of what the transform reads beyond the four-character sort.

Longest agreement first takes ranges in order of how many characters a rotation the transform reads in them, deepest first, and deepens each whose price still fits what is left of the budget. It is told those depths free, which is generous to it: finding out how far a range’s rotations agree is the reading. Most different first takes ranges in order of how many different characters precede their rotations, the largest first, ties by size. It never deepens a range preceded by one character, and it pays one read a rotation to count the preceding characters. That charge is the failure the proposal named.

Bits a symbol are move-to-front followed by zeroth-order entropy, the coder the transform that emits nothing introduced, so the transform’s own bits are the target and the loss is measured above them.

Two ranges, side by side #

The first range is three copies of one line of a program listing, all preceded by “m”, and the transform reads 1,168 characters to put them in an order that writes “mmm” into the last column, which is what any order writes. It is the long repeat that the repeats a context cannot see past found costing the four-character sort its bits on technical writing. A long repeat is exactly where the transform reads deepest, because its rotations agree for so long that a comparison has to go 195 characters before it finds a difference. All of that reading decides the order of three identical characters.

The second range is the other kind. Its rotations begin with “s merge” or “s measurable”, and they are preceded by “i”, “e” and “a”. Here the order matters: it decides whether the three "e"s sit together, where move-to-front codes them as small numbers, or are split by the others. This is the reading that buys bits. The proposal’s ranking says to spend on the second kind first and never on the first, and the plate shows why on one stream before any budget is set.

The prediction’s price, and the curve #

The four-character sort alone reads 52.8 characters a symbol on technical writing, 76% of the transform’s 69.3, so the prediction’s price of two thirds of the transform’s reading could not be met by any spending. The proposal priced the deep reading as if it were most of the transform’s work. It is a quarter of it. A comparison sort of 8,193 rotations makes about 96,000 comparisons, every one reads at least one character of each rotation, and most read a few. The first four characters of each comparison are three quarters of all the reading. The order inside a tie found a four-character sort reading 63% of the transform’s characters on its streams and coding slightly better than the transform. The deep reading this page is about is the remainder.

Within that remainder, the ranking is right on average. At half of the deep reading, spending it on the ranges preceded by the most different characters leaves the output 0.0062 bits a symbol above the transform on technical writing. Spending it on the longest agreements leaves it 0.0216 above, three and a half times as much, and a hundredth of a bit is not reached until four fifths of the budget is spent. On the essays, where repeats are fewer and shorter, the two policies are closer, 0.0041 against 0.0067, because there is less long agreement for the transform’s order to waste its reading on. A gap of 0.0026 bits a symbol between two means of eight streams is small beside the spread a result the size of its own noise found between streams of this kind, a standard deviation of 0.011 in one sort’s lead over another, so on the essays the ranking is suggested rather than shown. On technical writing the gap is six times larger.

The most-different policy also stops spending. Past two thirds of the deep reading it has deepened every range preceded by more than one character and has nothing left to buy. It reaches the transform’s bits at 62.0 characters a symbol on technical writing and stays there. The failure the proposal named did not happen: counting the preceding characters costs 0.9 characters a symbol, about a ninth of what skipping saves.

Stream by stream the ranking is a lean rather than a law: at half the deep reading, most different first loses less on five of eight technical streams and five of eight essay streams. Its lead in the means comes from three technical streams with long repeats, where longest first spends its whole budget ordering the repeats: on the second stream it is 0.093 bits a symbol above the transform against 0.0075. On the streams without long repeats, the two policies trade places by a few thousandths of a bit. On two essay streams the half-deepened sort even codes a little better than the transform, the effect the order inside a tie found when a sort by four characters beat it: an order that is not the transform’s can cluster the column slightly better by chance, and averages hide it.

What the longest-first policy bought with its first third #

The longest-agreement policy is what a sort does when it treats depth as the measure of difficulty, and the plates show what that buys. With a third of the deep reading to spend on technical writing, it deepens the ranges the transform reads deepest, and 55% of what it spends goes on ranges preceded by one character, whose order the output never sees. On the essays the share is 42%. Its curve stays flat at first for exactly that reason: the first characters it buys are the most expensive in the stream and the least useful, three copies of a line of code ordered among themselves.

The most-different policy spends its first third only on ranges whose order can change the column, starting with those preceded by the most different characters, where there are the most arrangements for the order to choose among. Its curve drops fastest there. Whether a range preceded by six characters is really worth more bits a read than one preceded by two was not measured separately; the ranking needs only that a range preceded by one is worth nothing, and that part is exact.

Neither policy is told anything the sort could not find cheaply. The preceding characters of a range are known the moment the range is: they are the characters at one position before each rotation, read once. The depth of a range’s agreement is not known until it has been read. A sort with a budget can rank by the first for less than a character a rotation, and it cannot rank by the second at all without spending the budget it was trying to allocate.

Skipping is exact, not approximate #

The curve reaches the transform’s bits, and that is not a coincidence of averages. A range whose rotations are all preceded by the same character contributes one run of that character to the last column, of the range’s length, at the range’s position, whatever order its rotations are put in. The four-character sort has already put the range in the right place among the other ranges, because ranges are separated by their first four characters. So sorting such a range changes nothing the transform outputs. A sort that deepens every range preceded by two or more characters, and leaves every range preceded by one in position order, writes the transform’s last column character for character. On all sixteen streams it does.

What a reordering costs to undo found that a reordering is only worth its clustering if undoing it is free, and the order inside a tie found that whether a cheaper sort is free to undo depends on how it orders its ties. The skipping sort sidesteps both questions. Its column is the transform’s character for character, so the transform’s own inverse reconstructs the text from it, and nothing about its ties has to be undone. The rotations inside a skipped range are out of order, but no character of the output can tell.

Where the transform’s deep reading goes #

Ranges preceded by one character take 48% of the transform’s reading past the fourth character on technical writing and 40% on the essays, and the share is nearly the same at every depth. The proposal’s account said the waste would sit in the long repeats, where rotations agree for dozens of characters and are mostly preceded by one character. It is there, 53% of the reading in ranges read more than thirty-two characters deep, but it is just as much in ranges read two to four characters deep. Half the ranges of every depth are preceded by a single character.

The reason is that most of a text’s four-character contexts are followed by one of a handful of characters and preceded by one of a handful too, and in a stream of 8,192 characters a context that occurs only two or three times is often preceded by the same character every time: " the" after a space, “tion” after “a”. Those ranges are shallow and numerous. A long repeat is a range of the same kind in which the agreement simply goes on longer. The transform cannot tell them apart before reading, because it does not look at the characters before its rotations at all until it writes them.

Where a context stops naming the letter before counted, in one pass and with no sorting, the share of positions whose $k$ characters fail to decide the character before them. That count was a measurement of exactly these ranges, from the other side. A range whose preceding characters are all one is a context that has already named the letter before it, and no deeper sort of it can change a bit.

Stream by stream #

On every one of the sixteen streams the skipping sort writes the transform’s column and reads less: 5% to 8% less on the essays, 6% to 19% less on technical writing, the most on the stream with the longest repeats, where the transform reads 89.5 characters a symbol and the skipping sort 72.4. That stream is the one the first plate’s two ranges came from, where a line of a program occurs three times over, and its repeats are the deepest reading in the study. A repeated line is preceded each time by whatever came before it, and when the repeat is long the thing before it is usually repeated too.

The saving tracks repetition, as the earlier page’s loss did. Where the four-character sort lost most to the transform, the transform read most past the fourth character, and the skipping sort saves most of that reading. Where text barely repeats, as in the essays, the transform’s deep reading is small to begin with, and skipping half of it saves a twentieth of the whole.

What a budget was for #

The proposal treated a budget as the constraint and the ranking as the answer. The measurement found the ranking more useful than the budget. With the ranking alone, the budget question for half the ranges is settled before any reading: preceded by one character, spend nothing. For the other half the budget question remains, and there the ordering by preceding diversity still helps, as the curve’s first half shows. But a sort with no budget at all gets the transform’s column for 89% of its reading on technical writing and 94% on the essays, and needs no knob.

That is the shape of several results about this transform. The deepening the sort was already doing found that a cleverer stopping rule could not beat the comparison sort, because the comparison sort’s own reading already adapted to the text. This page finds that the comparison sort adapts to the wrong thing. It reads until it can tell two rotations apart, which is a question about the rotations, while the output only asks a question about the characters before them. A sort that asks the output’s question once per range reads less and writes the same.

Three things the counts assume #

Reading as the cost. Every number here is characters compared, which is the cost model of a comparison sort over rotations. The transform is usually computed from a suffix array, the structure an index larger than what it indexes priced at nearly four times its text, built by doubling or by induced sorting, whose costs are passes over the text rather than comparisons. A doubling construction could skip a range preceded by one character at any round, which would save rounds rather than reads. That was not built.

One depth for the test. The preceding characters are counted once, at four characters. A range preceded by three different characters that is deepened splits into sub-ranges, and many of those will be preceded by one character each. A sort that applied the test again at every split would skip more. The measurement applied it only at the top.

Move-to-front and entropy. The column is identical to the transform’s, so its bits under any coder are identical too; the exactness does not depend on the coder. The budgeted curves do, since a column that differs from the transform’s in a few places can cost more or less under another second stage.

Still open: the test applied at every split #

The skipping sort asks its question once, of the ranges a four-character sort leaves, and then sorts every remaining range completely. But a range that is deepened becomes a set of smaller ranges at each further character, and each of those can be asked the same question. A range of twelve rotations preceded by “e”, “e”, “e”, “i” and eight "s"s splits at the fifth character into, perhaps, a sub-range of eight all preceded by “s” and a few others, and the eight need no further reading. A multikey sort that partitions on one character at a time could ask at every partition whether the characters before its rotations are all one, and stop the moment they are.

The measurement that follows builds that sort, a three-way partition on one character at a time that drops any partition whose preceding characters agree, and counts its reading against the transform’s and against the skipping sort’s on the same sixteen streams. The prediction is that it reads 20% less than the transform on technical writing and 12% less on the essays. Every deep range that is not preceded by one character at the top still contains sub-ranges that are, and those sub-ranges hold most of its deep reading. It could fail on the partitioning itself. A multikey sort reads each character once per partition rather than once per comparison, and if its reading on the shallow ranges is greater than the comparison sort’s, the stopped sub-ranges may only pay for the change of sort. The question is how much of the transform’s reading is spent on order that its output cannot see, once the question is asked everywhere rather than once.