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

Forskningsoutput: Kapitel i bok/rapport/konferenshandling › Konferensbidrag › Vetenskaplig › Peer review

Sammanfattning

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.

Originalspråk	engelska
Titel på värdpublikation	32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021
Redaktörer	Pawel Gawrychowski, Tatiana Starikovskaya
Förlag	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Utgivningsdatum	1 juli 2021
Artikelnummer	7
ISBN (elektroniskt)	978-3-95977-186-3
DOI	https://doi.org/10.4230/LIPIcs.CPM.2021.7
Status	Publicerad - 1 juli 2021
MoE-publikationstyp	A4 Artikel i en konferenspublikation
Evenemang	Annual Symposium on Combinatorial Pattern Matching - Wroclaw, Polen Varaktighet: 5 juli 2021 → 7 juli 2021 Konferensnummer: 32

Publikationsserier

Namn	Leibniz International Proceedings in Informatics, LIPIcs
Volym	191
ISSN (tryckt)	1868-8969

Bibliografisk information

Publisher Copyright:
© Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, and Marcin Piatkowski.

Vetenskapsgrenar

113 Data- och informationsvetenskap

Åtkomst av dokument

10.4230/LIPIcs.CPM.2021.7Licens: CC BY

Linear TimeSlutlig publicerad version, 843 KBLicens: CC BY

Citera det här

Bannai, H., Kärkkäinen, J., Köppl, D., & Piatkowski, M. (2021). Constructing the bijective and the extended burrows-wheeler transform in linear time. I P. Gawrychowski, & T. Starikovskaya (Red.), 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021 Artikel 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. redaktör / 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. i P Gawrychowski & T Starikovskaya (red), 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, Polen, 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. red. / Pawel Gawrychowski; Tatiana Starikovskaya. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. 7 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 191).

Forskningsoutput: Kapitel i bok/rapport/konferenshandling › Konferensbidrag › Vetenskaplig › 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. I Gawrychowski P, Starikovskaya T, redaktörer, 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