An algorithm for computing Burrows-Wheeler transform using q-grams - Cabunducan, Gerard Salvilla (Quezon City College of Engineering, University of the Philippines Diliman, 2013)
We have conducted an exploration on the role of q-grams in suffix array construction and Burrows-Wheeler transformation and its effect on minimizing the required amount of workspace. As one of the existing lightweight suffix array construction algorithms, we have studied Seward's algorithm and adapted it to perform the Burrows-Wheeler transform on sequence T of length n. Since Seward's algorithm considers depth-2 buckets and 1-groups only, we have generalized the algorithm to support depth-2 buckets, 1 ≤ q ≤ n, and (q - i)-groups, q - i > 0; and then getting the idea from the generalized algorithm, we have formulated alternative algorithms based on q-gram occurences. We compare these algorithms against the original and the generalized Seward's algorithm. When comparing the algorithms in terms of the total workspace usage, we have employed a different perspective on the complexity analysis through the relationship between q-grams and subword complexity. Our results show that the formulated algorithms can be as good as Seward's algorithm, or even better, in obtaining the Burrows-Wheeler transform of an input sequence derived from a small alphabet ∑, with |∑| є O(1), and using q < log|∑| n. Moreover, the formulated algorithms exhibit decreasing trend in their complexities when the value of q increases, q < log|∑| n, which is opposite to the trend of complexity in Seward's algorithm and its generalization. One particular formulated algorithm based on multikey quicksort has improved the previously formulated algorithms even further in terms of total workspace usage, and through q-grams, it is possible to have a total workspace usage for the Burrows-Wheeler transform that is less than n.
Thesis (M.S. Computer Science)--University of the Philippines, Diliman.
Keywords: Data compression (Computer science).; Burrows-Wheeler transform