Computing Inverse ST in Linear Complexity

Ge Nong*, Sen Zhang, Wai Hong Chan

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

8 Citations (Scopus)


The Sort Transform (ST) can significantly speed up the block sorting phase of the Burrows-Wheeler transform (BWT) by sorting only limited order contexts. However, the best result obtained so far for the inverse ST has a time complexity O(Nlogk) and a space complexity O(N), where N and k are the text size and the context order of the transform, respectively. In this paper, we present a novel algorithm that can compute the inverse ST in an O(N) time/space complexity, a linear result independent of k. The main idea behind the design of the linear algorithm is a set of cycle properties of k-order contexts we explored 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, leading to the proposed linear inverse ST algorithm.
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching
Subtitle of host publication19th Annual Symposium, CPM 2008 Pisa, Italy, June 18-20, 2008, Proceedings
EditorsPaolo Ferragina, Gad M. Landau
PublisherSpringer Berlin
Number of pages13
ISBN (Electronic)9783540690689
ISBN (Print)3540690662, 9783540690665
Publication statusPublished - 3 Jun 2008
Externally publishedYes
Event19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008 - Pisa, Italy
Duration: 18 Jun 200820 Jun 2008 (Conference proceedings)

Publication series

NameTheoretical Computer Science and General Issues
ISSN (Print)2512-2010
ISSN (Electronic)2512-2029


Conference19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008
Internet address

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Computing Inverse ST in Linear Complexity'. Together they form a unique fingerprint.

Cite this