On Bijective Variants of the Burrows-Wheeler Transform
On Bijective Variants of the Burrows-Wheeler Transform
复制标题
关于 Burrows-Wheeler 变换的双射变体
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Manfred Kufleitner
中科院分区：
文献类型：
--
作者：
Manfred Kufleitner
排序转换（ST）是洞穴 - 轮毂变换（BWT）的修改。两种转换将长度为n的任意单词映射到由长度为n和1和n之间的索引组成的一对。 BWT分类输入单词的所有旋转缀合物，而s的sT仅使用第一个k个字母来对所有此类共轭物进行排序。如果两个结合物以相同的长度K的前缀开头，则使用旋转的索引进行抢七。两者都会转换排序列表的最后一个字母的顺序和排序列表中输入的索引。在本文中，我们讨论了BWT（由于Scott）的一种族裔变体，证明了其与Gessel和Reutenauer（1993）以及Crochemore，Desarmenien和Perrin（2005）所致的其他结果的正确性和关系。此外，我们提出了ST的一种新型的BEATEVITE变体。
The sort transform (ST) is a modification of the Burrows-Wheeler transform (BWT). Both transformations map an arbitrary word of length n to a pair consisting of a word of length n and an index between 1 and n. The BWT sorts all rotation conjugates of the input word, whereas the ST of order k only uses the first k letters for sorting all such conjugates. If two conjugates start with the same prefix of length k, then the indices of the rotations are used for tie-breaking. Both transforms output the sequence of the last letters of the sorted list and the index of the input within the sorted list. In this paper, we discuss a bijective variant of the BWT (due to Scott), proving its correctness and relations to other results due to Gessel and Reutenauer (1993) and Crochemore, Desarmenien, and Perrin (2005). Further, we present a novel bijective variant of the ST.