How to sort array suffixes in block sorting

Question

I'm reading the block sort algorithm from the Burrows and Wheeler paper. This a step of the algorithm:

Suppose S= abracadabra

Initialize an array W of N words W[0, ... , N - 1], such that W[i] contains the characters S'[i, ... , i + k - 1] arranged so that integer comparisons on the words agree with lexicographic comparisons on the k-character strings. Packing characters into words has two benefits: It allows two prefixes to be compared k bytes at a time using aligned memory accesses, and it allows many slow cases to be eliminated

(Note: S' is the original S with k EOF characters appended to it, k being the number of characters that fit in a machine word (I'm in a 32 bits machine, so k=4)

EOF = '$'

Correct me if I'm wrong:

S'= abracadabra$$$$  
W= abra brac raca acad cada adab dabr abra bra$ ra$$ a$$$

Then, the algorithm says you have to sort the suffix array of S (named V), by indexing into the array W.

I don't fully understand how can you sort suffixes by indexing into W. For example: at some point of the sorting, suppose you get two suffixes, i and j, and you have to compare them. Since you are indexing into W, you are checking 4 characters at the time.
Suppose they have both the same first 4 characters. Then, you would have to check, for each suffix their next 4 characters, and you do it by accessing from the 4th position of each suffix in W. Is this right? Does this "packing characters into words" really speed things up?

Ouster

Are you sure that this (abra brac raca...) is the type of packing the authors intended? Could it be abra cada...? Can you provide a little more context for the quote? – Vikiviking

Answer 1

The way you describe it in the question is entirely accurate. And yes, it speeds things up because, like you said, it compares four characters at a time.

There are two remarks to be made, though:

1. When you compare suffixes i and j, like in your example, you compare entries W[i] and W[j] indeed. The result of this is the same as if you had lexicographically compared the quadruple of characters S[i..i+3] and S[j..j+3], so you have saved computing time equivalent to three character comparisons. And yes, if the result indicates that the two quadruples are identical, you have to continue comparing W[i+1] and W[j+1], however: You don't do it right away. The way their algorithm works is that of a radix sort. That is, you put the suffixes into buckets right after the initial comparison (possibly both into the same bucket), and then internally sort the buckets, recursively.
2. The algorithm described in the original paper by Burrows and Wheeler (from which you cite; there is a copy here for example), which is from 1994, is not the optimal suffix array construction algorithm. Firstly, in 2003 several O(N), direct construction methods were discovered; secondly, since then, many further improvements to the implementation were made. The core of the 1994 paper is the idea of using the Burrows-Wheeler transform as basis for string compression, not the exact way the transform itself is generated.

Delitescence

Answer 2

The array V is not a suffix array, but an array of indices into W. Once the sorting is complete, V should hold indices into W such that if

V[i] <= V[j]

then

 W[V[i]] <= W[V[j]].

I hope I said that right :) Having them EXACTLY match is not an issue and either order is fine. The point is that when you apply the reverse transformation you need to be able to recover W in order to recover the original string, and identical elements of W are not going to cause an problem with that.

Instructive