The deepening the sort was already doing

The repeats a context cannot see past followed a sort of rotations that stops after the first k characters, leaving rotations that agree on those k in the order of their positions. On streams of ordinary prose that sort stops losing to the full Burrows–Wheeler transform at four or five characters. On a corpus of technical writing it keeps losing until about ten. What predicted the loss, stream by stream, was repetition. The share of positions inside a sixteen-character string that recurs in the stream tracked the technical corpus’s loss with a correlation of 0.98. A sort by k characters cannot separate two rotations that agree for longer than k, and a text that repeats long strings is full of them.

Its closing section proposed a sort between the two. Sort by k characters, then look at each range of rotations that share those k characters. Where two of them share twice as many, sort that range again by twice as many, and repeat until no range repeats. Everything else stays at k. The prediction was that this would match the full transform’s bits on every stream while comparing far fewer characters: nearly the sort by k where few strings repeat, paying only for the repeats where many do. It named one way it could fail. Deepening one range might reorder its neighbours, so that the ranges could not be deepened independently.

Three sorts and what each is charged #

Every sort here is the same bottom-up merge sort over the rotations of a stream, with a sentinel closing the text, as the earlier pages used. A comparison reads characters from the two rotations in step until they differ or the depth limit is reached, and every character read is counted, two for each step. The sort by k stops at k characters and breaks ties by position. The full transform has no limit: each comparison reads until the rotations differ. The deepened sort first sorts by k. Then, for each range of rotations sharing k characters, it reads the next k characters of every rotation in the range, looking for two that match. If it finds a match, it sorts the range again by those next k characters, since the first k are known equal and need not be read again. Then it looks at each resulting sub-range at twice the depth, and so on. A range with no match stays in position order. The test’s reading is counted with the sort’s.

The failure the proposal named cannot happen, and this is a matter of construction rather than measurement. Sorting by k characters puts rotations with different k-character prefixes into different ranges, in the right order relative to each other, and deepening only reorders rotations inside one range. No rotation ever crosses a range boundary. The deepened sort’s output is the sort by k with some of its ranges refined, and every refinement is local.

Each sort’s output is coded as the earlier pages coded it: a move-to-front pass, then the zeroth-order entropy of the result, in bits a symbol. The model is the compressor is why that number, and not a real coder’s output, is the one compared: it is the floor any coder of that move-to-front stream works against. Streams are 8,192 characters, eight from the essays and eight from the technical corpus, the same slices the earlier page used.

The bits come back, and the reading goes up #

Deepened where contexts repeat, the sort by four characters codes the technical streams to 2.793 bits a symbol against the full transform’s 2.792. It reads 74.5 characters a symbol to get there, where the transform reads 69.4. Half of the prediction holds, and precisely. Starting from two, four or eight characters, the deepened sort lands within a thousandth of a bit of the transform. The other half fails. The deepened sort reads 7% more than the transform, from every starting depth, and far more than the sort by k whose bits it repairs.

On the essays the picture is the same at smaller scale. The deepened sort codes to 2.891 bits a symbol from four characters against the transform’s 2.894, and reads 66.3 characters a symbol against 64.0. Nothing about the proposal’s idea of where to spend the reading was wrong. It was simply not new.

A comparison sort already reads deep only where the text repeats #

A comparison between two rotations stops at their first difference, so the full transform’s sort reads past k characters only in comparisons between rotations that agree for more than k. Those are exactly the rotations inside the repeats. On an essay stream a third of the comparisons end at the first character, and 89% of all the characters the sort reads are read by comparisons that end within eight. Hardly any run past sixteen, because in ordinary prose a sixteen-character string rarely recurs. On a technical stream that repeats whole lines, the distribution has a long tail, the same repeats that the dictionary that builds itself turns into copies: 40% of the characters are read past the eighth, and 120 comparisons run past 128 characters, each reading a repeated line to its end.

So the full transform is already the sort the proposal described. It spends its reading in proportion to how far rotations agree, which is how much the text repeats around them, and it spends nothing extra anywhere else. There is no range test, because it does not need one: every comparison is its own test, and one that finds a difference at the first character has spent two characters finding it. The deepened sort does the same deep reading inside the same ranges, and adds two things the transform does without.

What the deepened sort pays that the transform does not #

The test costs 7 to 10 characters a symbol, and that is the whole of the difference. From four characters the deepened sort re-sorts 1,258 ranges a technical stream and 788 an essay stream, counting each depth separately, and it tests every range of two or more rotations whether it turns out to repeat or not. Starting from four characters, the deepened sort reads 52.9 characters a symbol in its first sort and 12.3 sorting the repeating ranges deeper, 65.2 in all, which is a little less than the transform’s 69.4. Its first sort and its deeper sorts together do almost exactly the transform’s work, split into stages. The test adds 9.4. To find out whether a range holds two rotations that agree for another k characters, it reads the next k characters of every rotation in the range until it finds a match. The transform learns the same thing inside its comparisons, at no extra charge.

Splitting the work into stages does not itself cost extra. On both corpora the first sort and the deeper sorts together read slightly less than the transform, 61.0 characters a symbol against 64.0 on the essays. Which pairs a merge sort happens to compare, and so how far it reads, depends on the order the rotations arrive in each merge, and the staged sorts arrive in a different order. The difference is a few characters a symbol, and the test swallows it twice over.

A version that tested for repeats as a side effect of sorting — noting, at each depth, which adjacent rotations compared equal all the way — would lose the test’s cost and be the transform computed by prefix doubling. Deepening every range of two or more, with no test, gives exactly the transform’s output, and reads 68.5 characters a symbol on the technical streams, 1% fewer than the merge sort. That is the most any depth-staged sort can save here, and it saves it by computing the transform, not by stopping short of it.

Why the reading looked like it could be saved #

The expectation that a deepened sort would read far less came from an earlier measurement. The order inside a tie found that sorting rotations by their first four characters used 63% of the full transform’s character reads and clustered its output about as well. Read one way, that says 37% of the transform’s reading buys nothing, which is what the sort by four characters did without. If that 37% were spread across all the rotations, a sort that did the deep reading only in the few ranges where it changes the output would keep nearly all of the saving.

The depth histogram says the 37% is not spread. It sits in the comparisons between rotations that agree past four characters, and those are the rotations inside repeated strings. On the essays there are few of them, and the 37% is mostly the fifth to eighth characters of ordinary words, read once in comparisons that end there. On the technical corpus there are many, and a large share of the reading is a handful of comparisons walking through repeated lines. In both cases the transform’s reading past four characters is already confined to the ranges where rotations agree past four. There was never a large amount of deep reading outside the repeats for a test to save.

So the earlier measurement’s 63% was not a saving waiting to be kept. It was the price of the repeats, read off from the other side. The sort by four characters paid 63% and lost the repeats’ bits; the transform paid 100% and kept them. The transform that emits nothing found that the transform changes only the order of the characters, and that everything it gains comes from what the order lets move-to-front see. What the deep reading buys is the order inside the repeats, and there is no way to get that order without reading the repeats.

Stream by stream, the bits are recovered where they were lost #

Sorted by four characters, the sixteen streams code between 0.002 and 0.129 bits a symbol above the transform, and deepened every one is within 0.006. The most repetitive stream, whose next sixteen characters recur at 28% of its positions, loses 0.129 bits a symbol sorted by four and 0.001 deepened. The deepening finds its repeats and sorts through them as far as they go: some ranges to 128 characters, where lines of the technical text recur whole.

Nine of the sixteen streams come out slightly below the transform, by up to 0.006 bits a symbol. Where a range does not repeat at twice the depth, the deepened sort leaves it in position order rather than sorting it fully. The order inside a tie found that position order inside a tie sometimes clusters the output better than the transform’s order does, because rotations from nearby positions tend to share their preceding character. A result the size of its own noise then found that advantage no larger than the spread between streams. The same small effect appears here, on both sides of zero, and no conclusion should be drawn from its sign.

What stopping at k characters buys #

A sort by eight characters reads 2.5 characters a symbol fewer than the transform on the essays and loses no bits; on the technical corpus it reads 8.1 fewer and loses 0.010 bits a symbol. Every character the sort by k saves is one the transform would have read inside a repeat longer than k, and every bit it loses is a repeat it failed to sort through. The two are the same repeats seen in two currencies. On the essays, repeats past eight characters are so rare that stopping there costs almost nothing in either currency. On the technical corpus they are common enough that stopping at eight saves an eighth of the reading and loses a hundredth of a bit.

That is the trade the deepened sort was meant to escape, and there is no escape from it by testing. To code a repeat as the transform does, a sort must read through the repeat; the transform reads through it once, inside the comparisons that meet it. Where a context stops naming the letter before counted, in one pass, the positions whose context fails to name the character before them. That count prices the bits. The comparison depths price the reading, and on these streams both are set by the same repeats.

The limits of the measurement #

Characters read, not time. A sort’s cost here is the characters its comparisons and tests read, counted exactly, which counting instead of timing explains as this collection’s rule. A real implementation of the transform uses a suffix-array construction that reads each character a bounded number of times whatever the text repeats, and a real context sort uses radix passes. Neither is a merge sort of rotations. The comparison between staged and unlimited sorting holds for comparison sorts. It says nothing about a construction built on different principles.

Prefix doubling is the clearest of those. It sorts by one character, gives every rotation the rank of its one-character prefix, and then sorts by two characters by comparing pairs of ranks, by four by comparing pairs of two-character ranks, and so on, stopping when every rank is distinct. It reads the text once, in the first pass, and every later pass compares numbers. In that design depth costs passes rather than characters, and a repeat of 128 characters costs seven passes over the rotations still tied rather than 128 characters a comparison. The deepened sort here is prefix doubling that re-reads the text at each depth instead of using ranks, and the test is the one step prefix doubling does not need, since a tie that survives a pass is its own evidence of a repeat. Whether a ranked version that stopped early in non-repeating ranges saves passes on these corpora is the same question in a different currency, and it was not measured.

Two corpora, eight streams each, one length. Streams are 8,192 characters. On longer streams a repeated line recurs more often, the long comparisons are a larger share of the transform’s reading, and the absolute characters saved by stopping at k grow. The shape — the deepened sort’s reading at or above the transform’s — should not change, since the test’s cost grows with the ranges it examines.

One test. The test looks for two rotations in a range that agree on the next k characters. A test that sampled a few rotations, or that stopped at the first match without reading the rest, would cost less and would sometimes miss a repeat. It was not tried.

Still open: a sort whose depth is priced before it is paid #

The deepened sort failed because it paid twice to find what the transform finds once. A sort that must stop somewhere, because its reading is capped or because it runs in a fixed number of radix passes, faces a different question. At a fixed budget of characters, which ranges should get the deep reading? The transform spends its reading wherever rotations agree, whether or not the agreement changes the character before them. A repeat whose rotations are all preceded by the same character codes the same whether it is sorted through or left in position order, and reading through it buys nothing.

The measurement that follows gives a sort a budget of characters a symbol, below what the transform reads, and compares two ways of spending it on the ranges left by a sort by four characters. One deepens the ranges whose rotations agree longest, as the transform would. The other deepens the ranges whose rotations are preceded by the most different characters, which is what the output’s bits depend on. The prediction is that on the technical corpus the second reaches within a hundredth of a bit of the transform on two thirds of its reading, because most long repeats are preceded by one character and need no sorting. It could fail if counting the preceding characters in a range costs as much reading as the deepening it saves.