The floors

A column the induction writes as it goes

Induced sorting builds the Burrows–Wheeler transform by computing a whole suffix array, four bytes a rotation the transform throws away, and its last round reads every character of the column on the way. Run so that the last round writes the column as it reads it and keeps a position only while a later step still needs it, the array was predicted to fall to about half the text at its peak, for no extra reads, unless the right-to-left pass had to hold its own placements until the end. It falls to a third — exactly the share of LMS suffixes the round starts from, on all sixteen streams and at every length — because no step of the round adds a live position without freeing one. The risk never arrives. The reads do change: an LMS suffix's character is read once at the temporary slot the left pass finds it in and again where the right pass puts it, a third of a character a symbol more. And the construction's peak simply moves, into the recursion below, which holds a reduced string a third of the text long and that string's own order.

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 p−1p - 1, the induction reads the character at p−1p - 1 — which is precisely the column’s character for the row holding suffix pp. 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 nn positions, the whole suffix array. The question is how far under nn 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 withThe slots of the suffix array holding a position some later step will read, as a share of the text, through the last round of induced sorting on the first prose stream and the first code stream (8,193 symbols each): placed LMS suffixes at the start (33.2% and 33.6%), the same at the turn between the left-to-right and right-to-left passes (33.2%, 33.6%), and none at the end. The ordinary round ends holding every position, the dashed line.00.2500.5000.7501the round, from the LMS placement through both passesshare of the text held as positionsleft to rightright to leftevery positionhalf, predictedprosecodeone stream of each sourcelive slots
Fig. 1 Slots of the suffix array holding a position some later step will read, as a share of the text, through the last round of induced sorting on the first prose stream and the first code stream (8,193 symbols each). The round starts with the LMS suffixes placed, 33.2% and 33.6%; it holds exactly that at the turn between the passes, and none at the end. The ordinary round ends holding every position, the top line; the predicted half is the faint line.

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%For each stream of 8,193 symbols, the most slots the written round holds as positions, the share of LMS suffixes, and the share of S-type suffixes, all as shares of the text: prose 1: peak 33.2%, LMS 33.2%, S-type 49.7%; prose 2: peak 33.1%, LMS 33.1%, S-type 50.6%; prose 3: peak 33.6%, LMS 33.6%, S-type 49.1%; prose 4: peak 33.6%, LMS 33.6%, S-type 50.3%; prose 5: peak 33.2%, LMS 33.2%, S-type 50.2%; prose 6: peak 33.3%, LMS 33.3%, S-type 49.5%; prose 7: peak 33.2%, LMS 33.2%, S-type 50.9%; prose 8: peak 33.4%, LMS 33.4%, S-type 49.9%; code 1: peak 33.6%, LMS 33.6%, S-type 52.1%; code 2: peak 35.0%, LMS 35.0%, S-type 50.7%; code 3: peak 34.5%, LMS 34.5%, S-type 50.3%; code 4: peak 34.6%, LMS 34.6%, S-type 50.8%; code 5: peak 35.7%, LMS 35.7%, S-type 51.8%; code 6: peak 35.5%, LMS 35.5%, S-type 52.2%; code 7: peak 34.0%, LMS 34.0%, S-type 51.4%; code 8: peak 33.4%, LMS 33.4%, S-type 51.5%.peak heldS-type suffixesevery positionprose 133.2%prose 233.1%prose 333.6%prose 433.6%prose 533.2%prose 633.3%prose 733.2%prose 833.4%code 133.6%code 235.0%code 334.5%code 434.6%code 535.7%code 635.5%code 734.0%code 833.4%sixteen streams of 8,193 symbolsshare of the text
Fig. 2 For each stream of 8,193 symbols, the most slots the written round holds as positions (dark) against the share of S-type suffixes (pale), both as shares of the text. Prose: peaks of 33.1% to 33.6% against S-type shares of 49% to 51%. Code: 33.4% to 35.7% against 50% to 52%. On every stream the peak equals the share of LMS suffixes to the slot.

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 arrivesNet change in live slots, as a share of the text, by step of the last round on the first prose stream: LMS placement +33.2%; the left-to-right pass reads each live slot and, where the suffix before is L-type, frees it and places that suffix (net nought), and where the suffix before is S-type keeps the slot for the other pass (net nought); the right-to-left pass frees every slot it reads and places at most one (net −33.2% over the pass).net change in live slotsLMS placed at bucket ends+1 each · +33.2%left pass, L-type before−1 read, +1 placedleft pass, S-type beforekept for the right passright pass, any slot−1 read, ≤ +1 placed · −33.2%first prose streamshare of the text
Fig. 3 Net change in live slots by step of the last round, as a share of the text, on the first prose stream. Placing the LMS suffixes: +33.2%. Left-to-right pass, a slot whose left neighbour is L-type: read, freed, and the neighbour placed — net nought. A slot whose left neighbour is S-type: kept for the other pass — net nought. Right-to-left pass: every slot read is freed and at most one is placed — net −33.2% over the pass.

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 timeThe most slots the last round holds as positions, as a share of the text, on texts of 1024, 2048, 4096, 8192, 16384, 32768 symbols generated from each source: prose 33.3%, 33.0%, 33.2%, 33.2%, 33.2%, 33.2%; code 33.1%, 32.9%, 33.0%, 33.6%, 33.9%, 34.1%.00.2000.4000.600symbols in the textpeak held, share of the text1,0242,0484,0968,19216,38432,768prosecodehalfgenerated texts of each sourcepeak held
Fig. 4 The most slots the last round holds as positions, as a share of the text, on texts of 1,024, 2,048, 4,096, 8,192, 16,384 and 32,768 symbols generated from each source. Prose: 33.3%, 33.0%, 33.2%, 33.2%, 33.2%, 33.2%. Code: 33.1%, 32.9%, 33.0%, 33.6%, 33.9%, 34.1%. The faint line is half.

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 allFor four streams: the last round's peak, and the reduced strings' lengths at each level below the top, as shares of the text; the recursion holds its reduced string and its own suffix array, twice the first. prose 1: last round 33.2%, levels 33.2%, 11.7%, recursion 66.3%; prose 5: last round 33.2%, levels 33.2%, 11.3%, recursion 66.3%; code 1: last round 33.6%, levels 33.6%, 12.2%, 4.1%, recursion 67.1%; code 5: last round 35.7%, levels 35.7%, 12.8%, 4.4%, recursion 71.5%.last round, writtenrecursion: string and its orderprose 133.2%66.3%prose 533.2%66.3%code 133.6%67.1%code 535.7%71.5%share of the text, in positionsline: the whole array
Fig. 5 For four streams, the written last round’s peak (dark) and what the recursion below the top level holds (light): its reduced string, one name for each LMS suffix, and that string’s own suffix array, twice the first level’s length. Prose 1: 33.2% and 66.3%. Prose 5: 33.2% and 66.3%. Code 1: 33.6% and 67.1%. Code 5: 35.7% and 71.5%. The line is the whole array.

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 nn slots it was going to fill anyway, which is why the cost never showed; once the top level stops needing all nn 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 itCharacters of the text read a symbol by the last round, averaged over eight streams of each source: the reads the ordinary round makes (placing the LMS suffixes and inducing every other suffix), and the extra reads the written round makes for the LMS suffixes' rows. English prose: 1.33 and 0.33 more, against an LMS share of 0.33; program text: 1.35 and 0.35 more, against an LMS share of 0.35.the ordinary round's readsread again for the columnEnglish prose1.33 + 0.33program text1.35 + 0.3516 streamscharacters read a symbol
Fig. 6 Characters of the text read a symbol by the last round, averaged over eight streams of each source: the reads the ordinary round makes, placing the LMS suffixes and inducing every other suffix, and the extra reads the written round makes for the LMS suffixes’ rows. Prose: 1.33 and 0.33 more. Code: 1.34 and 0.34 more.

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.

The objects this essay names

Each one links to every other essay that touches it.

Auxiliary spaceBurrows-wheeler transformIn placeRecursionSpace accountingSuffix array