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

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

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Abstrakti

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.

Alkuperäiskielienglanti
Otsikko32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021
ToimittajatPawel Gawrychowski, Tatiana Starikovskaya
KustantajaSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Julkaisupäivä1 heinäk. 2021
Artikkeli no7
ISBN (elektroninen)9783959771863
DOI - pysyväislinkit
TilaJulkaistu - 1 heinäk. 2021
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaAnnual Symposium on Combinatorial Pattern Matching - Wroclaw, Puola
Kesto: 5 heinäk. 20217 heinäk. 2021
Konferenssinumero: 32

Julkaisusarja

NimiLeibniz International Proceedings in Informatics, LIPIcs
Vuosikerta191
ISSN (painettu)1868-8969

Lisätietoja

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

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä