文章基本信息

标题：In-Place Bijective Burrows-Wheeler Transforms
本地全文：下载
作者：Dominik K{"o}ppl ; Daiki Hashimoto ; Diptarama Hendrian 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：161
页码：21:1-21:15
DOI：10.4230/LIPIcs.CPM.2020.21
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：In-Place Algorithms; Burrows-Wheeler transform; Lyndon words