A sort that infers the order

The question asked at every split found that most of what the Burrows–Wheeler transform had been paying to read was the price of one way of computing it. The transform sorts the rotations of a text and writes out the character before each one. Counted with a comparison sort, that costs about sixty-five characters of the text read for every symbol, three quarters of them re-reads of the first few characters, made again in every comparison. A three-way radix quicksort, which reads a rotation’s character at each depth once for each split it passes through, cut that to sixteen to twenty. Asking at every split whether a group’s rotations are all preceded by one character, and dropping the group if they are, cut it to about fourteen on every stream, whatever its repetition.

Its closing section looked past both. Suffix sorting has a family of algorithms that do not find most of the order by reading at all. Induced sorting sorts a small chosen set of suffixes and derives the place 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 one position to its right. It predicted that such a sort would read about three characters a symbol on every stream. It also predicted that the quicksort’s question would save it nothing, because an induced sort derives the order of a whole bucket at once.

The second prediction holds, for a reason that turns out to be the whole point of the measurement. The first is off by a factor of two.

A third of the suffixes, and the rest by induction #

The algorithm here is SA-IS, the induced sort of Nong, Zhang and Chan, run on the same sixteen streams with the same unique end marker. Every rotation of a text ending in a marker smaller than every character is ordered exactly as the text’s suffixes are, so a suffix array of the text is the rotation order the transform needs.

SA-IS first classifies every suffix as smaller or larger than the suffix one position to its right. One right-to-left pass does it, reading each character once and keeping the character after it in a register. A smaller suffix that follows a larger one is called leftmost-smaller, LMS for short, and on these streams they are a third of all suffixes. The algorithm sorts only those. It puts each LMS suffix at the end of the bucket for its first character, and then induces. A left-to-right pass over the partly filled array places every larger suffix, because a larger suffix sorts after the suffix to its right and its bucket is fixed by its first character. A right-to-left pass places every smaller one the same way from the other end. One round of that sorts the LMS substrings, the stretches from one LMS position to the next. If two LMS substrings are equal, their suffixes are not yet ordered, so each substring gets a name, the string of names is sorted by the same algorithm recursively, and the result places the LMS suffixes in their true order. A last round of the two passes then places everything.

Every read of the text at the top level is counted, by the step that makes it: the classification, the two placings of the LMS suffixes, the two rounds of induction, and the naming, which compares each sorted LMS substring with the one before it two characters a position until they differ. The recursion’s reads are counted separately, because they read names, not characters. The order SA-IS returns is checked against the comparison sort’s on every stream, rotation by rotation, and the column it implies against the transform’s.

Six characters a symbol, on every stream #

Induced sorting reads 6.19 characters of the text a symbol on technical writing and 6.13 on the essays, against the stopped quicksort’s 13.9 and 14.0, and the sixteen streams lie between 6.11 and 6.25. Counting the recursion’s reads of its reduced strings as well, it reads 8.77 and 8.46. Either way it is the cheapest sort of the rotations measured in this strand, by more than a factor of two over the best before it and by a factor of ten over the comparison sort.

The prediction said three. The measured count is twice that, and it is the flatness that is the stronger result. On the quicksorts the stream with the longest repeats was the expensive one: 31.1 characters a symbol without the test, 15.3 with it, against fifteen or sixteen for the flattest essay. For induced sorting that stream costs 6.23, a tenth of a character more than the cheapest. A sort that reads in order to find the order pays for every position two rotations share, and repetition is a measure of how many positions rotations share. A sort that infers the order pays per suffix, and a suffix is a suffix whatever text it ends.

The comparison that is not one comparison found that a comparison of two strings is a walk along both, and that most of a comparison sort’s cost of sorting strings is the length of those walks. The radix quicksort walks each rotation once, at the cost of one read for every depth it is still grouped at. Induced sorting does not walk at all. Its passes read the first character of each suffix they place and nothing further into it, and the order beyond the first character arrives from the suffix to the right, which was placed earlier in the same pass.

Where the six characters go #

Of the 6.19 characters a symbol induced sorting reads on technical writing, the classification reads exactly one, the two rounds of induction exactly two, the placing of the LMS suffixes 0.69, and naming the LMS substrings 2.50, the largest single step. The first three are fixed by the algorithm. One right-to-left pass reads every character. Each round of induction places every suffix once and reads one character to place it. Placing the LMS suffixes reads one character for each, twice, and the LMS suffixes are a third of the text, a share that depends on the text’s alphabet and order but that varies here only from 0.33 to 0.36.

Naming is where the text’s content enters. Two neighbouring LMS substrings in sorted order are compared character by character until they differ or one ends, so the cost is the length the neighbours share. In a text where the same short stretches recur, neighbouring LMS substrings are often identical, and identical substrings are read to their end. Technical writing names at 2.50 against the essays’ 2.46, a difference of under two per cent, because LMS substrings are short, about three characters on these streams, and a shared stretch longer than one LMS substring is not read by the naming at all. It is passed to the recursion as a repeated name.

A plain change to the naming removes an eighth of it. An LMS substring’s length is known from its position and the next LMS position, and two substrings of different lengths cannot be equal, so comparing lengths before characters names them apart without reading them. On technical writing that cuts naming from 2.50 to 2.19 characters a symbol and the whole sort from 6.19 to 5.89. The recursion falls with it, from 2.58 to 2.29, because the same check applies to the reduced strings.

The prediction’s three was the count of the passes, classification and two inductions, and the passes do read three characters a symbol. What it left out was the work of sorting the chosen third. Placing them, comparing their substrings and recursing on the names costs more than the induction it makes possible.

A third a level #

Each level of the recursion sorts a string about a third the length of the one above it, 33% to 36% of the text at the first level, and stops once every name is distinct, after two to four levels. Technical writing goes deeper. Three of its eight streams need a fourth level and none of the essays do, because the first reduced string of a text that repeats whole lines and identifiers contains repeated runs of names, and those runs need another level to separate.

A third a level is why the recursion’s reads are a bounded share of the total. The reduced strings shrink geometrically, so the reading summed over all of them is about two fifths of the top level’s reading over again, and a text that repeats more adds a level a twenty-seventh or an eighty-first of its length, not a pass over the whole text. That is the opposite of what repetition did to the quicksort, where a long repeat meant every rotation inside it was read again at every depth the repeat covered.

Flat at every length #

From 1,024 characters of technical writing to 32,768, the quicksort with the test rises from 11.7 characters a symbol to 16.3, and induced sorting moves from 5.75 to 6.28. The quicksort’s reading grows because a longer stream holds longer repeats. Its rotations agree further, and every further position they agree on is a position it reads. The test removes most of the growth, since a long repeat is usually preceded by one character throughout, but not all of it: the radix quicksort alone goes from 12.1 to 22.9, and its stopped version rises by four and a half characters a symbol over a factor of thirty-two in length.

On the essays the stopped quicksort rises from 12.0 characters a symbol to 16.1 and induced sorting from 5.79 to 6.23. At the longest length the radix quicksort reads 22.9 characters a symbol on technical writing and 18.7 on the essays; induced sorting reads 6.28 and 6.23. The little growth it has is all in the naming, which reads 2.09 characters a symbol at 1,024 characters of technical writing and 2.60 at 32,768, while the classification, the placing and the induction stay at exactly what they were. A longer text holds more copies of each short stretch, so a sorted LMS substring is more often identical to its neighbour and read to its end, and its recursion goes a level deeper, at 8,192 characters on technical writing and at 16,384 on the essays. That is growth in how many copies of each short stretch a text has, not in how long its repeats are, and over a factor of thirty-two in length it is half a character a symbol.

The repeats a context cannot see past found that technical writing needs about ten characters of context where the essays need four or five, and every reading sort in this strand has paid for those extra characters. Induced sorting does not see them. Its cost is set by the number of suffixes and by the short-range structure the classification finds, larger or smaller than the next suffix, which both corpora have in the same proportion.

The question reads the answer, twice #

The quicksort’s question cost it one read of the text a rotation: before sorting, it read each rotation’s preceding character and carried it. Those $n$ reads are the transform’s column, in text order, and what the sort then supplied was only the column’s order.

Induced sorting reads the same $n$ characters without being asked. Its last round of induction scans the array from left to right and right to left, and for each suffix already placed it reads the character before it, to put the suffix one position to the left into its bucket. The character before each suffix is its preceding character, which is the transform’s output for that suffix. So the final induction reads the transform’s column once in full, and it reads it in sorted order, because it walks the array that is being sorted. The sort’s last pass is the transform. In an induced sort the question is not a test placed in front of the work. It is the work.

That is why the question saves nothing, and the closing section’s reason, that an induced sort derives the order of a bucket at once, is not quite it. The induction places one suffix at a time, reading one character to do it, and it has no step at which a group could be left unordered: the character it reads to place a suffix is the character it would need to answer the question, and the place it computes is the place the column needs.

A run’s order is needed by what comes after it #

Of technical writing’s rotations, 69% lie in runs of one preceding character, the groups the quicksort’s test would drop. For half of them, 34% of all rotations, the rotations an induced sort derives from the run are not themselves a run, so leaving the run unordered would leave part of the column unknown. The essays have 65% in runs and the same 34%.

The arithmetic behind the plate is the last-to-first map a search that runs backwards uses to count a pattern. A run of rotations all preceded by one character, say $c$, maps one step back through the text onto the rotations that begin with $c$ followed by each of them, and those form a contiguous range of the sorted order, ordered exactly as the run is. An induced sort places that range from the run, in the run’s order. If the run had been left unordered because its own column entries are all $c$, the range one step back would be unordered too, and its column entries are the characters before $c$, which for half the runs measured are not all one character. The quicksort could drop a group because nothing downstream of a group in a reading sort uses its order. In an inducing sort the order of every suffix is used to place the suffix to its left.

So the order inside a run of the column, which the order the column cannot see found and two essays since have priced, is invisible to the output and visible to an induced sort’s own steps. A run can go unordered only as far as its chain of predecessors stays runs, and for a third of the rotations that is not a single step. Where the chain does go further, there is still nothing to save, because the induction’s one read a suffix is the read the question needed.

What the prediction got right #

The closing section predicted three characters a symbol. The inductions alone do read three, one character a suffix twice over and the classification’s one, and the prediction did not count the work of sorting the third of the suffixes they start from. Placing them, naming their substrings and recursing on the names bring the top level to 6.1 and the whole to 8.6.

It predicted that the count would be the same on every stream, and it is, within 0.14 characters a symbol across corpora whose reading by quicksort differed by a factor of two. And it predicted that the question would save nothing. The reason is stronger than the one given: an induced sort reads every rotation’s preceding character in order to place it, so the column is not something it can avoid ordering but the last thing it computes, and the order the output cannot see is order the sort’s own passes need.

That closes a thread the strand has followed since the transform was first counted. Every saving measured against the comparison sort, from deepening only where contexts repeat to asking at every split, was a saving on reading spent to find order, and induced sorting does not read to find order. A million characters of the same thing found the transform’s output cheapest on the most repetitive inputs; an induced sort makes its input’s repetition free to read as well.

What the counts assume #

Characters read, not time. Induced sorting’s passes touch the suffix array at random and its type array beside it, and on a real machine those touches, not the character reads, decide its speed. A radix quicksort’s accesses are more local. The count here says how much of the text each sort has to look at, which is the question this strand set, and not which sort is faster.

The recursion counted apart. The recursion reads names, which are integers up to the number of distinct LMS substrings, not characters. They are reported beside the text’s reads and never added to the quicksort’s figures, which have no recursion. Counted together, induced sorting reads 8.5 to 9.0 symbols for each character of the text.

One implementation. SA-IS as published, with one optional change, the length check before naming. Other induced sorts sort the chosen suffixes differently, and some read the text fewer times; none were run.

Still open: a column written by the induction itself #

The last round of induction reads the transform’s column in sorted order, one character for each rotation, and writes each suffix’s position into the suffix array. A transform needs only the characters, not the positions, and the suffix array is four bytes a rotation the transform throws away. Induced sorting can be run so that its last round writes the column directly, keeping in the array only what the induction still needs to place the suffixes to their left.

The measurement that follows builds the transform that way, from the LMS order, writing each character as the final induction reads it, and counts what the array must still hold at each point of the last pass and how many characters the whole construction reads. The prediction is that the reads do not change, 6.1 characters a symbol, since the last pass reads the same characters, and that the peak the array holds falls by about half, because a larger suffix that has been placed and has induced its neighbour need not be kept. It could fail on the smaller suffixes. The right-to-left pass induces from every suffix it passes, including those placed in the same pass, so a suffix cannot be dropped until the pass has gone by it, and the array may have to hold nearly everything until the very end. The question is whether the column’s characters can replace the positions as the sort produces them, or whether an induced sort needs every position it computes in order to compute the rest.