Computing the inverse sort transform in linear time

Ge NONG, Sen ZHANG, Wai Hong CHAN

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

The Sort Transform (ST) can significantly speed up the block sorting phase of the Burrows-Wheeler Transform (BWT) by sorting the limited order contexts. However, the best result obtained so far for the inverse ST has a time complexity O(N log k) and a space complexity O(N), where N and k are the text size and the context order of the transform, respectively. In this article, we present a novel algorithm that can compute the inverse ST for any k-order contexts in an O(N) time and space complexity, a linear result independent of k. The main idea behind the design of this linear algorithm is a set of cycle properties of k-order contexts that we explore for this work. These newly discovered cycle properties allow us to quickly compute the Longest Common Prefix (LCP) between any pair of adjacent k-order contexts that may belong to two different cycles, which eventually leads to the proposed linear-time solution. Copyright © 2011 ACM.
Original languageEnglish
Article number27
JournalACM Transactions on Algorithms
Volume7
Issue number2
DOIs
Publication statusPublished - Mar 2011

Citation

Nong, G., Zhang, S., & Chan, W. H. (2011). Computing the inverse sort transform in linear time. ACM Transactions on Algorithms, 7(2). Retrieved from https://doi.org/10.1145/1921659.1921673

Keywords

  • Burrows-wheeler transform
  • Inverse transform
  • Limited order context
  • Linear time

Fingerprint Dive into the research topics of 'Computing the inverse sort transform in linear time'. Together they form a unique fingerprint.