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?
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: