论文标题
现场徒洞穴 - 轮毂转换
In-Place Bijective Burrows-Wheeler Transforms
论文作者
论文摘要
Burrows-theeler转换的最著名变体之一[Burrows and Wheeler，1994年]是Bixtive BWT（BBWT）[Gil and Scott，Arxiv 2012]，它应用了扩展的BWT（EBWT）[Mantaci等人[Mantaci等，TCS 2007]由于EBWT是可逆的，因此BBWT是一种徒的变换，因为EBWT的倒数图像恢复了lyndon因子的多种元素，因此可以通过以非侵扰顺序对这些因子进行排序来获得原始文本。在本文中，我们提出使用二次时间构建或反转BBWT的算法。 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 $O(n \lg r / \lg \lg r)$ time with $O(r \lg n)$ bits of words, where $r$ is the sum of character runs in the BWT and the BBWT.
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 $O(n \lg r / \lg \lg r)$ time with $O(r \lg n)$ bits of words, where $r$ is the sum of character runs in the BWT and the BBWT.
