Antisequential suffix sorting for BWT-based data compression

doi:10.1109/TC.2005.56

Antisequential suffix sorting for BWT-based data compression

2005-04-01

14

PRE

AI

DOI：10.1109/TC.2005.56

Original

Original request for help

Save

Abstract

En 中文

Suffix sorting requires ordering all suffixes of all symbols in an input sequence and has applications in running queries on large texts and in universal lossless data compression based on the Burrows Wheeler transform (BWT). We propose a new suffix lists data structure that leads to three fast, antisequential, and memory-efficient algorithms for suffix sorting. For a length-N input over a size-\X\ alphabet, the worst-case complexities of these algorithms are Theta(N-2), O(\chi\ N log(N/\chi\)) and O(Nroot\chi\log(N/\chi\)), respectively. Furthermore, simulation results indicate performance that is competitive with other suffix sorting methods. In contrast, the suffix sorting methods that are fastest on standard test corpora have poor worst-case performance. Therefore, in comparison with other suffix sorting methods, suffix lists offer a useful trade off between practical performance and worst-case behavior. Another distinguishing feature of suffix lists is that these algorithms are simple; some of them can be implemented in VLSI. This could accelerate suffix sorting by at least an order of magnitude and enable high-speed BWT-based compression systems.

Keywords:

Burrows Wheeler transform

data compression

source coding

suffix sorting

VLSI

Antisequential suffix sorting for BWT-based data compression

Abstract

Journal

Organization