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?
A suffix array can be constructed from Suffix tree by doing a DFS traversal of the suffix tree. In fact Suffix array and suffix tree both can be constructed from each other in linear time. A simple method to construct suffix array is to make an array of all suffixes and then sort the array.
The suffix array data structure can be used as a full-text index, allowing arbitrary substring search in time O(logn) in the size of the text. The next section discusses suffix arrays in more detail. The major disadvantage of suffix arrays is their size: They require roughly one pointer per character in the text.
In computer science, a suffix array is a sorted array of all suffixes of a string. It is a data structure used in, among others, full-text indices, data-compression algorithms, and the field of bibliometrics.
Suffix array construction means simply sorting the set of all suffixes. • Using standard sorting or string sorting the time complexity is Ω(DP(T[0..n] )). • Another possibility is to first construct the suffix tree and then traverse it from left to right to collect the suffixes in lexicographical order.
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:
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With