Constructing the bijective and the extended burrows-wheeler transform in linear time

Hideo Bannai; Juha Kärkkäinen; Dominik Köppl; Marcin Piatkowski

doi:10.4230/LIPIcs.CPM.2021.7

Constructing the bijective and the extended burrows-wheeler transform in linear time

Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, Marcin Piatkowski

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

Abstract

The Burrows-Wheeler transform (BWT) is a permutation whose applications are prevalent in data compression and text indexing. The bijective BWT (BBWT) is a bijective variant of it. Although it is known that the BWT can be constructed in linear time for integer alphabets by using a linear time suffix array construction algorithm, it was up to now only conjectured that the BBWT can also be constructed in linear time. We confirm this conjecture in the word RAM model by proposing a construction algorithm that is based on SAIS, improving the best known result of O(n lg n/ lg lg n) time to linear. Since we can reduce the problem of constructing the extended BWT to constructing the BBWT in linear time, we obtain a linear-time algorithm computing the extended BWT at the same time.

Original language	English
Title of host publication	32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021
Editors	Pawel Gawrychowski, Tatiana Starikovskaya
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date	1 Jul 2021
Article number	7
ISBN (Electronic)	9783959771863
DOIs	https://doi.org/10.4230/LIPIcs.CPM.2021.7
Publication status	Published - 1 Jul 2021
MoE publication type	A4 Article in conference proceedings
Event	Annual Symposium on Combinatorial Pattern Matching - Wroclaw, Poland Duration: 5 Jul 2021 → 7 Jul 2021 Conference number: 32

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	191
ISSN (Print)	1868-8969

Fields of Science

Burrows-Wheeler Transform
Circular Suffix Array
Lyndon words
Suffix Array Construction Algorithm
113 Computer and information sciences

Access to Document

10.4230/LIPIcs.CPM.2021.7Licence: CC BY

Linear TimeFinal published version, 843 KBLicence: CC BY

Cite this

Bannai, H., Kärkkäinen, J., Köppl, D., & Piatkowski, M. (2021). Constructing the bijective and the extended burrows-wheeler transform in linear time. In P. Gawrychowski, & T. Starikovskaya (Eds.), 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021 Article 7 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 191). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CPM.2021.7

Bannai, Hideo ; Kärkkäinen, Juha ; Köppl, Dominik et al. / Constructing the bijective and the extended burrows-wheeler transform in linear time. 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021. editor / Pawel Gawrychowski ; Tatiana Starikovskaya. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{a3f622231bcd43609e67cb76ad0356b0,

title = "Constructing the bijective and the extended burrows-wheeler transform in linear time",

abstract = "The Burrows-Wheeler transform (BWT) is a permutation whose applications are prevalent in data compression and text indexing. The bijective BWT (BBWT) is a bijective variant of it. Although it is known that the BWT can be constructed in linear time for integer alphabets by using a linear time suffix array construction algorithm, it was up to now only conjectured that the BBWT can also be constructed in linear time. We confirm this conjecture in the word RAM model by proposing a construction algorithm that is based on SAIS, improving the best known result of O(n lg n/ lg lg n) time to linear. Since we can reduce the problem of constructing the extended BWT to constructing the BBWT in linear time, we obtain a linear-time algorithm computing the extended BWT at the same time.",

keywords = "Burrows-Wheeler Transform, Circular Suffix Array, Lyndon words, Suffix Array Construction Algorithm, 113 Computer and information sciences",

author = "Hideo Bannai and Juha K{\"a}rkk{\"a}inen and Dominik K{\"o}ppl and Marcin Piatkowski",

note = "Publisher Copyright: {\textcopyright} Hideo Bannai, Juha K{\"a}rkk{\"a}inen, Dominik K{\"o}ppl, and Marcin Piatkowski.; Annual Symposium on Combinatorial Pattern Matching, CPM ; Conference date: 05-07-2021 Through 07-07-2021",

year = "2021",

month = jul,

day = "1",

doi = "10.4230/LIPIcs.CPM.2021.7",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Pawel Gawrychowski and Tatiana Starikovskaya",

booktitle = "32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021",

address = "Germany",

}

Bannai, H, Kärkkäinen, J, Köppl, D & Piatkowski, M 2021, Constructing the bijective and the extended burrows-wheeler transform in linear time. in P Gawrychowski & T Starikovskaya (eds), 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021., 7, Leibniz International Proceedings in Informatics, LIPIcs, vol. 191, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Annual Symposium on Combinatorial Pattern Matching, Wroclaw, Poland, 05/07/2021. https://doi.org/10.4230/LIPIcs.CPM.2021.7

Constructing the bijective and the extended burrows-wheeler transform in linear time. / Bannai, Hideo; Kärkkäinen, Juha; Köppl, Dominik et al.
32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021. ed. / Pawel Gawrychowski; Tatiana Starikovskaya. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. 7 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 191).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Constructing the bijective and the extended burrows-wheeler transform in linear time

AU - Bannai, Hideo

AU - Kärkkäinen, Juha

AU - Köppl, Dominik

AU - Piatkowski, Marcin

N1 - Conference code: 32

PY - 2021/7/1

Y1 - 2021/7/1

N2 - The Burrows-Wheeler transform (BWT) is a permutation whose applications are prevalent in data compression and text indexing. The bijective BWT (BBWT) is a bijective variant of it. Although it is known that the BWT can be constructed in linear time for integer alphabets by using a linear time suffix array construction algorithm, it was up to now only conjectured that the BBWT can also be constructed in linear time. We confirm this conjecture in the word RAM model by proposing a construction algorithm that is based on SAIS, improving the best known result of O(n lg n/ lg lg n) time to linear. Since we can reduce the problem of constructing the extended BWT to constructing the BBWT in linear time, we obtain a linear-time algorithm computing the extended BWT at the same time.

AB - The Burrows-Wheeler transform (BWT) is a permutation whose applications are prevalent in data compression and text indexing. The bijective BWT (BBWT) is a bijective variant of it. Although it is known that the BWT can be constructed in linear time for integer alphabets by using a linear time suffix array construction algorithm, it was up to now only conjectured that the BBWT can also be constructed in linear time. We confirm this conjecture in the word RAM model by proposing a construction algorithm that is based on SAIS, improving the best known result of O(n lg n/ lg lg n) time to linear. Since we can reduce the problem of constructing the extended BWT to constructing the BBWT in linear time, we obtain a linear-time algorithm computing the extended BWT at the same time.

KW - Burrows-Wheeler Transform

KW - Circular Suffix Array

KW - Lyndon words

KW - Suffix Array Construction Algorithm

KW - 113 Computer and information sciences

U2 - 10.4230/LIPIcs.CPM.2021.7

DO - 10.4230/LIPIcs.CPM.2021.7

M3 - Conference contribution

AN - SCOPUS:85115238259

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021

A2 - Gawrychowski, Pawel

A2 - Starikovskaya, Tatiana

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - Annual Symposium on Combinatorial Pattern Matching

Y2 - 5 July 2021 through 7 July 2021

ER -

Bannai H, Kärkkäinen J, Köppl D, Piatkowski M. Constructing the bijective and the extended burrows-wheeler transform in linear time. In Gawrychowski P, Starikovskaya T, editors, 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2021. 7. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.CPM.2021.7