Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to sort array suffixes in block sorting

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?

like image 531
erandros Avatar asked Jun 14 '11 23:06

erandros


People also ask

How do you find the suffix of an array?

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.

What is the disadvantage of a suffix array search?

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.

What is the use of suffix array?

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.

What is suffix array construction?

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.


1 Answers

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.
like image 127
jogojapan Avatar answered Oct 19 '22 10:10

jogojapan