License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2020.21
URN: urn:nbn:de:0030-drops-121463
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12146/
Go to the corresponding LIPIcs Volume Portal

Köppl, Dominik ; Hashimoto, Daiki ; Hendrian, Diptarama ; Shinohara, Ayumi

In-Place Bijective Burrows-Wheeler Transforms

pdf-format:
LIPIcs-CPM-2020-21.pdf (1 MB)

Abstract

One of the most well-known variants of the Burrows-Wheeler transform (BWT) [Burrows and Wheeler, 1994] is the bijective BWT (BBWT) [Gil and Scott, arXiv 2012], which applies the extended BWT (EBWT) [Mantaci et al., TCS 2007] to the multiset of Lyndon factors of a given text. Since the EBWT is invertible, the BBWT is a bijective transform in the sense that the inverse image of the EBWT restores this multiset of Lyndon factors such that the original text can be obtained by sorting these factors in non-increasing order.
In this paper, we present algorithms constructing or inverting the BBWT in-place using quadratic time. We also present conversions from the BBWT to the BWT, or vice versa, either (a) in-place using quadratic time, or (b) in the run-length compressed setting using ?(n lg r / lg lg r) time with ?(r lg n) bits of words, where r is the sum of character runs in the BWT and the BBWT.

BibTeX - Entry

@InProceedings{kppl_et_al:LIPIcs:2020:12146,
  author =	{Dominik K{\"o}ppl and Daiki Hashimoto and Diptarama Hendrian and Ayumi Shinohara},
  title =	{{In-Place Bijective Burrows-Wheeler Transforms}},
  booktitle =	{31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-149-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{161},
  editor =	{Inge Li G{\o}rtz and Oren Weimann},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12146},
  URN =		{urn:nbn:de:0030-drops-121463},
  doi =		{10.4230/LIPIcs.CPM.2020.21},
  annote =	{Keywords: In-Place Algorithms, Burrows-Wheeler transform, Lyndon words}
}

Keywords: In-Place Algorithms, Burrows-Wheeler transform, Lyndon words
Collection: 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)
Issue Date: 2020
Date of publication: 09.06.2020
Supplementary Material: At https://github.com/daikihashimoto/BWT_to_BBWT, we have some preliminary implementations available giving empirical evidence of our conversions.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI