Computing Inverse ST in Linear Complexity

Ge Nong; Sen Zhang; Wai Hong Chan

doi:10.1007/978-3-540-69068-9_18

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 proceeding › Conference proceeding › peer-review

8 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Combinatorial Pattern Matching
Subtitle of host publication	19th Annual Symposium, CPM 2008 Pisa, Italy, June 18-20, 2008, Proceedings
Editors	Paolo Ferragina, Gad M. Landau
Publisher	Springer Berlin
Pages	178-190
Number of pages	13
Edition	1st
ISBN (Electronic)	9783540690689
ISBN (Print)	3540690662, 9783540690665
DOIs	https://doi.org/10.1007/978-3-540-69068-9_18
Publication status	Published - 3 Jun 2008
Externally published	Yes
Event	19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008 - Pisa, Italy Duration: 18 Jun 2008 → 20 Jun 2008 https://link.springer.com/book/10.1007/978-3-540-69068-9 (Conference proceedings)

Publication series

Name	Theoretical Computer Science and General Issues
Publisher	Springer
Volume	5029
ISSN (Print)	2512-2010
ISSN (Electronic)	2512-2029

Conference

Conference	19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008
Country/Territory	Italy
City	Pisa
Period	18/06/08 → 20/06/08
Internet address	https://link.springer.com/book/10.1007/978-3-540-69068-9 (Conference proceedings)

Scopus Subject Areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-69068-9_18

Cite this

Nong, G., Zhang, S., & Chan, W. H. (2008). Computing Inverse ST in Linear Complexity. In P. Ferragina, & G. M. Landau (Eds.), Combinatorial Pattern Matching: 19th Annual Symposium, CPM 2008 Pisa, Italy, June 18-20, 2008, Proceedings (1st ed., pp. 178-190). (Theoretical Computer Science and General Issues; Vol. 5029). Springer Berlin. https://doi.org/10.1007/978-3-540-69068-9_18

@inproceedings{0fe0bced1ab04aadb9f0d9c138f83199,

title = "Computing Inverse ST in Linear Complexity",

abstract = "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.",

author = "Ge Nong and Sen Zhang and Chan, {Wai Hong}",

note = "Publisher copyright: {\textcopyright} 2008 Springer-Verlag Berlin Heidelberg; 19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008 ; Conference date: 18-06-2008 Through 20-06-2008",

year = "2008",

month = jun,

day = "3",

doi = "10.1007/978-3-540-69068-9_18",

language = "English",

isbn = "3540690662",

series = "Theoretical Computer Science and General Issues",

publisher = "Springer Berlin",

pages = "178--190",

editor = "Paolo Ferragina and Landau, {Gad M.}",

booktitle = "Combinatorial Pattern Matching",

address = "Germany",

edition = "1st",

url = "https://link.springer.com/book/10.1007/978-3-540-69068-9",

}

Nong, G, Zhang, S & Chan, WH 2008, Computing Inverse ST in Linear Complexity. in P Ferragina & GM Landau (eds), Combinatorial Pattern Matching: 19th Annual Symposium, CPM 2008 Pisa, Italy, June 18-20, 2008, Proceedings. 1st edn, Theoretical Computer Science and General Issues, vol. 5029, Springer Berlin, pp. 178-190, 19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008, Pisa, Italy, 18/06/08. https://doi.org/10.1007/978-3-540-69068-9_18

Computing Inverse ST in Linear Complexity. / Nong, Ge; Zhang, Sen; Chan, Wai Hong.
Combinatorial Pattern Matching: 19th Annual Symposium, CPM 2008 Pisa, Italy, June 18-20, 2008, Proceedings. ed. / Paolo Ferragina; Gad M. Landau. 1st. ed. Springer Berlin, 2008. p. 178-190 (Theoretical Computer Science and General Issues; Vol. 5029).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Computing Inverse ST in Linear Complexity

AU - Nong, Ge

AU - Zhang, Sen

AU - Chan, Wai Hong

PY - 2008/6/3

Y1 - 2008/6/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=45849125009&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-69068-9_18

DO - 10.1007/978-3-540-69068-9_18

M3 - Conference proceeding

AN - SCOPUS:45849125009

SN - 3540690662

SN - 9783540690665

T3 - Theoretical Computer Science and General Issues

SP - 178

EP - 190

BT - Combinatorial Pattern Matching

A2 - Ferragina, Paolo

A2 - Landau, Gad M.

PB - Springer Berlin

T2 - 19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008

Y2 - 18 June 2008 through 20 June 2008

ER -

Computing Inverse ST in Linear Complexity

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this