A column the induction writes as it goes
The Burrows–Wheeler transform of a text is one character for each rotation, the character before it, written in the rotations’ sorted order. The transform that emits nothing introduced it to this strand as a permutation of the text, and what a reordering costs to undo priced the inverse that makes it usable. Everything an FM-index or a compressor built on it needs is that column; the order inside a tie measured how well a column clusters by compressing it alone. The usual way to compute it is to compute the suffix array — every suffix’s starting position, in sorted order, four bytes a rotation on a text of a few billion characters — and then read the column off it. A sort that infers the order counted the reads of the cheapest such sort the strand has measured, SA-IS, the induced sort of Nong, Zhang and Chan, and found it reads about six characters a symbol at its top level on every stream, whatever the text’s repetition.
That essay’s closing section noticed something about the sort’s last step. Induced sorting places most suffixes by induction: a suffix’s place in the order follows from its first character and the place of the suffix one position to its right. To place the suffix that starts at , the induction reads the character at — which is precisely the column’s character for the row holding suffix . The last round of induction therefore reads the column in sorted order, one character a row, while it is filling the suffix array the column was supposed to be read from. A transform could be written directly by that round, and the array could keep a position only while the round still needs it to place a suffix further left.
The prediction was that the reads would not change, since the last round reads the same characters, and that the most the array holds would fall to about half the text, because a larger suffix that has been placed and has induced its neighbour need not be kept. The named risk was the second pass: the right-to-left pass induces from every suffix it passes, including suffixes it placed itself, so it might be unable to drop anything until it had gone by, and the array would hold nearly everything to the end.
The round, and what a slot is for
SA-IS classifies every suffix as smaller (S-type) or larger (L-type) than the suffix to its right. A smaller suffix whose left neighbour is larger is leftmost-smaller, LMS; on these streams a third of all suffixes are. The sort finds the order of the LMS suffixes first, through a round of induction, a naming and a recursion on the names. Its last round then starts from that order: it puts each LMS suffix at the end of its first character’s bucket, runs a left-to-right pass that places every L-type suffix, and runs a right-to-left pass that places every S-type suffix, the LMS ones included, in their final rows.
The measurement replays exactly that round on the strand’s sixteen streams, eight of English prose and eight of program text, 8,193 symbols each, and counts the slots of the array that are live: holding a position that some later step will read. A slot becomes live when a suffix is placed in it. When the left-to-right pass scans it and the suffix to its left is L-type, the pass reads that character, writes it into the column for this row, and induces the neighbour; the slot will never be read as a position again, so it is freed and holds only the character. When the suffix to its left is S-type, the slot must wait for the right-to-left pass, which scans every slot still live, writes its character, induces the neighbour if it is S-type, and frees it. The column produced is checked against the transform on every stream.
The ordinary sort ends this round holding all positions, the whole suffix array. The question is how far under the written round stays at its worst moment.
A third, from the first slot to the last
Written as it goes, the last round never holds more positions than it starts with: 33.2% of the text on prose and 33.6% on code, the LMS suffixes it places first — not the half predicted, and nothing like the whole array the ordinary sort ends with. The live count is flat through the whole left-to-right pass and falls steadily through the right-to-left pass to nothing. Its peak is its starting value.
The prediction expected the left pass to accumulate and the right pass to drain. Neither happens in the shape it pictured. The left pass trades: every slot it frees, it frees by inducing a neighbour into a fresh slot, so the count stays where it was. The right pass frees every slot it reads and fills at most one, so the count can only fall. The highest point of the round is therefore its beginning, the moment the LMS suffixes have been placed and nothing else.
The prediction’s “half” was counting the S-type suffixes, about half the text, on the reasoning that those are the slots the right pass needs. The slots it needs at the turn are fewer: an L-type suffix whose left neighbour is S-type, and there is exactly one such boundary for each LMS suffix, since the types alternate in runs and every run of S-types begins at an LMS position.
The same share on every stream
On every one of the sixteen streams the round’s peak is its share of LMS suffixes to the slot — 33.1% to 35.7% of the text — while the S-type suffixes the prediction’s half was counting run 49% to 52%. Every stream is reported, not a mean, because a result the size of its own noise found that one stream of a source can mislead by more than an effect; here the peaks spread over half a point on prose and two on code. The program-text streams sit a little higher because code has more short alternations of rising and falling characters, which make more LMS positions, but the rule is the same on all of them.
The equality is not a coincidence of these texts. It is what the argument of the last plate says must happen: the round’s peak is its starting count, and its starting count is the number of LMS suffixes. That number is at most half the text for any input, since an LMS position needs an L-type position before it, and on text with no special structure it sits near a third, because a position is LMS when a character is smaller than the one before it and no larger than the one after, which random text satisfies about a third of the time.
So the risk the proposal named is not merely absent on these streams; it cannot occur. The right-to-left pass does induce from slots it filled itself, but each of those slots was filled by freeing another, so holding them to the end costs nothing beyond what was held at the start.
Why the count cannot rise
No step of the round adds a live slot without freeing one: placing the LMS suffixes is the only gain, 33.2% of the text on this stream; every induction frees the slot it reads as it fills another, and the right-to-left pass frees everything it scans, which is why the risk that it would hold its own placements never arrives. The plate is the proof drawn as bookkeeping. There are four kinds of step and only one has a positive sign.
What makes this possible is that induction is one-in, one-out. A slot is read exactly when its suffix is used to place another, and after that it is used for nothing but its character. An ordinary implementation keeps the position anyway because the suffix array is its output. Once the output is the column instead, the position’s last use is the induction it feeds, and the slot can give up the position at that moment.
There is one subtlety the bookkeeping has to respect. The right-to-left pass places S-type suffixes at the ends of their buckets, and those bucket ends are where the LMS suffixes were put at the start of the round, temporarily. The left pass has already scanned those temporary slots and written a character into them. When the right pass reuses a slot, the character there belongs to the wrong row and must be discarded. The written round handles that by clearing a slot’s character whenever it places a suffix in it, and the check against the transform on every stream is what confirms it.
Flat at every length
The share does not move with length: from 1,024 to 32,768 symbols the written round holds 33.0%–33.3% of a prose text and 32.9%–34.1% of a code text, the LMS share each time. A peak that is a fixed fraction of the text is still linear in the text, so this is not a sublinear construction. It is a constant-factor saving, and the constant is a third.
The length plate is also the reason to state the saving as a share and not as a number of bytes. On a text of a billion characters the ordinary last round holds four gigabytes of positions; the written one holds about 1.3, plus the column itself at a byte a row. The column was always going to be written somewhere; what is saved is the two thirds of the position array the transform never needed.
The program texts drift upward a little with length, from 33% to 34%, because longer generated code has more short rising-and-falling patterns in identifiers and operators. The drift is in the LMS share, and the peak follows it exactly.
The peak moves down a level
With the last round holding a third, the construction’s peak moves into the recursion: the level below the top sorts a reduced string of 33%–36% of the text and needs that many positions again for its own order, about two thirds in all. The last round was the construction’s largest step only because it held the whole array. Written as it goes, it is no longer the largest, and the step that is becomes visible.
Before the last round can run, the sort must know the LMS suffixes’ true order. It gets it by naming the LMS substrings and sorting the string of names recursively, and that string is as long as there are LMS suffixes. The recursion holds the string and computes a suffix array for it, so at the level below the top it holds about two positions for every LMS suffix, two thirds of the text. Classic SA-IS fits both inside the one array of slots it was going to fill anyway, which is why the cost never showed; once the top level stops needing all slots, the recursion’s two thirds is the high-water mark.
The first round at the top level, which sorts the LMS substrings before naming, is an induction of the same shape and obeys the same bookkeeping, so it can be held to a third as well. The recursion is the step the bookkeeping does not reach, because its output must be a full order of its own input.
What the column costs in reads
Writing the column is not free in reads: the ordinary round reads 1.33 characters a symbol on prose, and the written one reads 0.33 more, because an LMS suffix’s character was read at the temporary slot the left pass found it in and must be read again where the right pass finally puts it. The prediction said the reads would not change. They change by exactly the LMS share, a quarter of the round’s own reads.
The reason is the same reuse of bucket ends the steps plate described. An LMS suffix is placed twice in the round, once at a bucket end to seed the left pass and once by the right pass in its final row. The left pass reads its left neighbour’s character at the first place, and that character is the column’s for the wrong row. The right pass, arriving at the final row, must read it again. The ordinary round never notices, because it does not care what character a row has; it only reads characters to induce.
Against the whole construction the extra third of a character is modest. A sort that infers the order counted 6.1 characters a symbol at the top level; the written round makes it about 6.4, five per cent more, for two thirds less of the largest array the top level holds. That is a trade a construction for very long texts makes gladly, and it is the trade the strand’s reads-only accounting would have missed.
Positions as a scaffold
The finding reads most clearly against the transform that emits nothing, which began this strand’s counting: the transform is a permutation of the text’s characters, and every structure built on the way to it is scaffolding. Induced sorting’s scaffolding is the suffix array, and the measurement shows how little of it is load-bearing at any one time. A position is needed from the moment its suffix is placed until the moment it places its neighbour, and in the last round those two moments are close together for most suffixes.
The general rule is a familiar one in streaming computation: hold an item only between its arrival and its last use. What makes it work here is that induction’s uses are strictly ordered by the passes. The left pass uses each slot once, in array order; the right pass uses each remaining slot once, in reverse order. No slot is ever needed by a step that cannot be predicted from its type bits, and the type bits are a bit a symbol, already held.
The question asked at every split cut the transform’s reads by asking whether a group’s order matters to the output, after the deepening the sort was already doing and the order the column cannot see had found most of a comparison sort’s reads spent on order the column never shows. This essay asks the same question of the array instead of the reads, and the answer is the same in kind: most of what the sort computes, it computes for itself. The output needs a third of the positions at any moment, and none at the end.
What the replay assumes
The last round only. The peak is measured over the top level’s last round. The first round, which sorts the LMS substrings, is the same induction and is argued to obey the same bound, but it was not replayed; the recursion is measured only by the length of its reduced strings.
Positions, not bits. A live slot is counted as one position whatever its width. The column’s characters, a byte a row, are written whatever happens and are not counted against the array.
Type bits held. The written round reads a suffix’s type to decide whether to free its slot, as the ordinary round does to decide whether to induce. The type array is a bit a symbol and is held throughout, in both.
One implementation of SA-IS. The round is the published one: LMS suffixes placed at bucket ends, then the two passes. Variants that place the LMS suffixes in their final rows directly would not read their characters twice.
Still open: a recursion held to its own third
The written round moves the construction’s peak to the recursion: the reduced string of names, a third of the text, and its own suffix array, another third. The recursion is SA-IS again on a shorter input, so its own last round can be written the same way — except that its output is not a column but the order of the LMS suffixes, which the top level’s last round needs in full. What it needs, though, is that order consumed once, in sequence, to place the LMS suffixes at their bucket ends.
The measurement that follows runs the recursion so that its last round hands the LMS suffixes to the top level as it places them, in the order the top level consumes them, and counts the positions held at every level at every step. The prediction is that the construction’s peak falls from about two thirds of the text to about four ninths — the reduced string, a third, plus its own LMS share, a third of that — on every stream. It could fail on the order of consumption: the top level places LMS suffixes from the largest to the smallest, at bucket ends, while the recursion’s right-to-left pass produces them in another order, so the order may have to be held whole before it can be used. The question is whether a recursive sort can stream its answer upward, or whether every level must finish its order before the level above can begin to use it.
Named alongside this one
Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.
- A function with r pieces burrows-wheeler transform · suffix array
- A search that runs backwards burrows-wheeler transform · suffix array
- Every substring, in fewer states than substrings auxiliary space · suffix array
- In place is a claim, and it is usually wrong about quicksort auxiliary space · in place
- Measuring what an algorithm keeps auxiliary space · in place
- The alignment that fits in one line auxiliary space · recursion
The objects this essay names
Each one links to every other essay that touches it.
Auxiliary spaceBurrows-wheeler transformIn placeRecursionSpace accountingSuffix array