The question asked at every split

The order the column cannot see found a fact about the Burrows–Wheeler transform that made a budget for its reading unnecessary. The transform sorts the rotations of a text and outputs the character before each one. A range of rotations that are all preceded by the same character writes the same run of that character into the output, whatever order the range is in. So a sort that orders rotations by their first four characters, and then sorts completely only the ranges preceded by more than one character, writes the transform’s column exactly. It read 11% less than the transform on technical writing and 6% less on the essays, on all sixteen streams.

It asked the question once, of the ranges four characters leave. The closing section noticed that a range that is deepened becomes smaller ranges at every further character, and each of those can be asked the same question. A sort that partitions on one character at a time, a three-way radix quicksort, could ask at every partition whether the characters before its rotations are all one, and stop the moment they are. It predicted that sort would read 20% less than the transform on technical writing and 12% less on the essays, because every deep range preceded by several characters still contains sub-ranges preceded by one, and those sub-ranges hold most of its deep reading. And it named the way the prediction could fail. A multikey sort reads each character once per partition rather than once per comparison, and if its reading on the shallow ranges were greater than the comparison sort’s, the stopped sub-ranges might only pay for the change of sort.

The prediction’s direction was right, and so was the size of the question’s own saving. Its account of what the change of sort costs was backwards.

Three sorts that write one column #

The streams are the earlier essay’s: eight of 8,192 characters from each corpus, with a unique end marker so every rotation is distinct. Three sorts of their rotations are compared, and every one is counted in characters of the text read.

The first is the comparison sort the transform essays have counted from the start, a merge sort of rotations whose every comparison reads two characters at each position until the rotations differ. The second is the three-way radix quicksort. It takes a group of rotations known to agree on their first $d$ characters, reads the character at position $d$ of each, picks the middle one’s as a pivot, and splits the group into those below, equal to and above it. The below and above parts are split again at the same position, and the equal part moves on to position $d + 1$. Each split reads one character from each rotation in the group. The third is the same quicksort with the question. Before sorting, it reads each rotation’s preceding character once, $n$ reads in all, and carries it along with the rotation. Then, before splitting any group, it checks whether the carried characters all agree, and drops the group if they do.

The carried check reads no text, so it is not charged as reading. How many checks it makes is reported: about 1.6 for every symbol of the stream. Every last column the two quicksorts write is checked against the transform’s before any count is reported, and both match on every stream, so the bits are the transform’s bits throughout. Move-to-front and entropy coding, the measure the transform that emits nothing settled on, see the same column from all three.

Four fifths less, and where it comes from #

The quicksort that asks the question at every split reads 13.9 characters a symbol on technical writing and 14.0 on the essays, against 69.3 and 64.0 for the comparison sort: four fifths less, where the prediction said a fifth and an eighth. It writes the transform’s column on every stream. The plate’s third bar is the one that changes how to read that. Without any question at all, the quicksort reads 19.6 and 16.2 characters a symbol. The change of sort saves 72% of the transform’s reading on technical writing and 75% on the essays. The question then saves 29% and 14% of what is left.

Those last two figures are close to what the prediction named, 20% and 12%, and they rank the corpora the same way. The question does what the closing section expected of it. What the section did not expect was that the sort underneath would be a quarter of the transform’s price before the question was asked. Its named risk, that partitioning one character at a time might read more than comparing, was the opposite of the truth by a factor of four.

The comparison that is not one comparison found the reason long before any transform was built. A comparison of two strings is not one operation but a walk along both until they differ, and a comparison sort starts every walk at the first character. Of the transform’s 69.3 characters a symbol, 23.5 are reads of the very first character, made again in each of the twenty-odd comparisons a rotation takes part in during a merge sort of 8,193 of them. A radix quicksort reads the first character of each rotation about four times, once for each split it passes through at that position, and never again once the rotation has moved deeper. A radix sort is the sort that reads a key one digit at a time, the trade the digit a pass chooses for itself priced in passes over integer keys. A three-way quicksort is that idea for keys with no fixed length, where a digit is a character and the depth is however far two keys agree.

The change of sort saves at the top, the question saves deep #

On technical writing the comparison sort reads 53.6 characters a symbol in the first four positions and the quicksort 11.5; from the fifth position on, the quicksort reads 8.1 and the question cuts that to 2.0. The two savings live in different places. The change of sort removes the repeated reading at shallow depth, where the comparison sort spends three quarters of its total. The question removes the deep reading, where the rotations agree for many characters and a quicksort pays a read for each of them.

Beyond 32 characters the plate is the earlier essays’ long repeats. Technical writing repeats whole identifiers and lines, so its rotations agree deep, and the quicksort still reads 1.9 characters a symbol there, nearly the comparison sort’s 2.3, because a radix sort pays one read for every position two rotations share. The repeats a context cannot see past found this corpus needs about ten characters of context where the others need four or five, for the same reason. The question reduces that deep reading to 0.1. A long repeat is a long run of rotations that agree, and the character before such a repeat is usually the same in every copy, because a repeat is usually part of a larger copied stretch. So a group that is deep is almost always a group the question can drop, and the deeper the agreement the sooner it is dropped relative to where the reading would have stopped.

On the essays the quicksort reads 4.8 characters a symbol from the fifth position on, and the question cuts it to 2.1. The essays have almost no deep agreement. Nothing past 32 characters, a fifth of a character a symbol between 16 and 31. The question saves less here because there is less deep reading to save, and what it saves comes from the middle depths, four to fifteen characters, where English words and short phrases recur.

The two profiles explain why the prediction ranked the corpora correctly. The question’s saving is a share of the deep reading, and deep reading is what repetition costs. The deepening the sort was already doing found that the transform already reads deep only where contexts repeat. The question now removes most of that reading wherever the repeat’s preceding characters agree, which is nearly everywhere a repeat is long.

Where the question stops #

The question drops 58% of all rotations on technical writing and 53% on the essays, and half of all rotations are dropped after only two to seven characters of agreement. That is earlier than the earlier essay’s question could reach. A sort by four characters could not ask anything of a range until it had read four characters of every rotation in it. The quicksort asks at every split, and 29% of the rotations on technical writing are in groups dropped after two or three characters, groups the four-character sort would have gone on reading.

The groups are small. Groups of two to eight rotations hold 39% of all rotations on technical writing, and groups of more than 64 hold 2%. This is the arithmetic of English text, which where a context stops naming the letter before counted directly: after a few characters of context the letter before is usually decided, because inside a word the letters that can precede a given pair or triple are few. In a group of a handful of rotations they are often all one letter, the group is a run in the output, and the quicksort finds it as soon as the next character has separated the group from its neighbours.

The question reads the answer #

The character the question carries is not a hint about the output. It is the output. The transform’s last column is, rotation by rotation, the character before each rotation, so reading every preceding character once reads the whole column, in text order, before a single rotation has been sorted. What the sort adds is the order of that column, and only the order. What a reordering costs to undo measured the other side of this: sorting a text’s characters clusters them perfectly and costs, to undo, almost exactly the bits the clustering saved. The transform’s value lies entirely in which arrangement of a fixed set of characters it writes.

Seen that way, a dropped group is a part of the column that is already finished. Its characters are known, they are all one character, and the group’s place in the column is fixed by the splits that formed it. The quicksort with the question writes the column in pieces as it goes. Half the rotations reach their final piece of output after two to seven characters of agreement, and the sort never reads further into them. The rest are the rotations whose preceding characters still disagree, and only those need the sort to go on.

This is also why the question costs nothing in bits. The order inside a tie found that a sort stopped at four characters wrote a slightly different column, which happened to compress a little better and could be undone at no cost. A result the size of its own noise then showed the difference was within the spread of sixteen streams. The question does not stop anywhere that could change the column, so there is no difference in bits to argue about, on any stream.

The deeper the stream, the more the question saves #

On the stream with the longest repeats the question removes 51% of the quicksort’s reading, from 31.1 characters a symbol to 15.3; on the flattest essay it removes 10%. The sixteen points lie close to one rising line. A stream that makes the quicksort read deep is a stream with long repeats, and the question removes most of whatever reading the repeats add, leaving every stream at 13.3 to 15.3 characters a symbol. With the question asked at every split, the reading barely depends on how repetitive the stream is.

That flattening is the result the closing section was really asking about. Its question was how much of the transform’s reading is spent on order its output cannot see, once the question is asked everywhere. Of the transform’s reading, most is spent re-reading the first characters, which the output can see, but which a better sort reads once. Of what is left once that is fixed, the order the output cannot see is between a tenth and a half, and it is exactly the part that grows with repetition.

The question’s own price is small and fixed: one read of the text a rotation for the preceding character, and about 1.6 carried checks a symbol. On the flattest stream the question still saves 1.6 characters a symbol after paying its one, and on none of the sixteen does it cost more than it saves.

What the prediction got right, and what it had backwards #

The closing section predicted 20% less reading than the transform on technical writing and 12% less on the essays. The quicksort with the question reads 80% and 78% less. The question’s own contribution, measured against the same sort without it, is 29% and 14%, the size and the ranking the prediction named.

It named a failure: that a sort partitioning on one character at a time might read more than the comparison sort on the shallow ranges, so that the question’s savings would only pay for the change of sort. The shallow ranges are where the change of sort saved most. In the first four positions the quicksort reads 11.5 characters a symbol against the comparison sort’s 53.6. The prediction treated the comparison sort’s reading as the natural price of ordering rotations and the question as a discount on it. The comparison sort’s reading was mostly the price of restarting every comparison from the beginning.

That has a consequence for every essay in this strand. Each measured the transform’s reading with a comparison sort, and each saving was stated against it. The skip of the earlier essay saved 11% of a reading of which three quarters was avoidable another way. The savings were real, but the base they were measured from was not the cost of the transform. It was the cost of one way of computing it.

What the counts assume #

Characters, not time. Every count is characters of the text read. A radix quicksort also moves rotations between partitions, and the carried preceding character doubles what it moves. A comparison sort moves less and compares more. Nothing was timed.

One kind of quicksort. The pivot is the middle rotation’s character at each split. A different pivot rule changes how many splits a rotation passes through at each position, and so the shallow reading; no other rule was run. The deep reading, and the question’s share of it, depend mostly on how far rotations agree, which is a property of the text.

The streams of the strand. Sixteen streams of 8,192 characters. Longer streams have longer repeats, which would raise the quicksort’s deep reading and the question’s share of it, as the stream with the longest repeats already shows.

Still open: a sort that induces the order instead of reading it #

The quicksort with the question reads about fourteen characters a symbol on every stream, whatever its repetition. Suffix sorting has a family of algorithms that read fewer still, by not reading most of the order at all. Induced sorting sorts a small set of chosen suffixes and derives the order of every other suffix from them in two linear passes, because a suffix’s place follows from its first character and the place of the suffix after it. It reads each character a constant number of times.

The measurement that follows counts the characters an induced suffix sort reads on the same sixteen streams, against the quicksort with the question. It also asks whether the question can be asked inside it, by stopping the induction of a bucket whose suffixes are all preceded by one character. The prediction is that induced sorting reads about three characters a symbol on every stream, under the quicksort’s fourteen. It also predicts that the question saves it nothing, because an induced sort’s passes derive the order of a whole bucket at once and gain nothing from leaving part of it unordered. The question is whether the order the output cannot see is a cost only for sorts that find order by reading, and costs nothing for a sort that infers it.