Antisequential suffix sorting for BWT-based data compression

Dror Baron, Yoram Bresler

Research output: Contribution to journalArticlepeer-review

Abstract

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 ⊖(N2), O( X N log(N/ X )), and O(N √ X log (N/ X )), 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.

Original languageEnglish (US)
Pages (from-to)385-397
Number of pages13
JournalIEEE Transactions on Computers
Volume54
Issue number4
DOIs
StatePublished - Apr 2005

Keywords

  • Burrows Wheeler transform
  • Data compression
  • Source coding
  • Suffix sorting
  • VLSI

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Antisequential suffix sorting for BWT-based data compression'. Together they form a unique fingerprint.

Cite this