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/konferenshandlingKonferensbidragVetenskapligPeer 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åkengelska
Titel på värdpublikation32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021
RedaktörerPawel Gawrychowski, Tatiana Starikovskaya
FörlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Utgivningsdatum1 juli 2021
Artikelnummer7
ISBN (elektroniskt)9783959771863
DOI
StatusPublicerad - 1 juli 2021
MoE-publikationstypA4 Artikel i en konferenspublikation
EvenemangAnnual Symposium on Combinatorial Pattern Matching - Wroclaw, Polen
Varaktighet: 5 juli 20217 juli 2021
Konferensnummer: 32

Publikationsserier

NamnLeibniz International Proceedings in Informatics, LIPIcs
Volym191
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

Citera det här