没有EOF特征的Burrows-Wheeler变换

Question

我需要在线性时间内执行着名的Burrows-Wheeler变换.我找到了一个带后缀排序和EOF字符的解决方案,但附加EOF会改变转换.例如:考虑字符串bcababa 和两个旋转

• s1 = abababc
• s2 = ababcab

很明显,s1 <s2.现在有了EOF字符:

• s1 = ababa #bc
• s2 = aba #bcab

现在s2 <s1.由此产生的转变将是不同的.如何在没有EOF的情况下执行BWT？

Answer 1

通过计算字符串与其自身连接的后缀数组，可以在没有 EOF 字符的情况下在线性时间和空间中执行转换。然后迭代后缀数组。如果当前后缀数组值小于n，则将从后缀数组中当前值表示的位置开始的旋转的最后一个字符添加到输出数组中。但是，此方法将产生略有不同的 BWT 转换结果，因为字符串旋转不会像存在 EOF 字符那样进行排序。

更全面的描述可以在这里找到：http://www.quora.com/Algorithms/How-I-can-optimize-burrows-wheeler-transform-and-inverse-transform-to-work-in-On-time -太空中

Answer 2

您需要在字符串中包含 EOF 字符才能使 BWT 工作，否则您将无法执行逆变换来恢复原始字符串。如果没有 EOF，字符串“ba”和“ab”都具有相同的转换版本（“ba”）。对于 EOF，变换是不同的

\n\n

ab        ba\n\na b |     a | b\nb | a     b a |\n| a b     | b a\n

\n\n

即 ab 转换为“|ab”，ba 转换为“b|a”。

\n\n

BWT 需要 EOF，因为它标记字符循环的开始点。

\n\n

回复：根据维基百科，在没有 EOF 字符的情况下执行此操作，

\n\n

\n

由于输入字符串的任何旋转都会导致相同的\n 转换后的字符串，因此如果不向输入添加 \'EOF\'\n 标记，或者使用索引等信息增强输出，则无法反转 BWT ，这使得可以从输入字符串的所有旋转类别中识别输入字符串。

\n\n

有一个双射版本的变换双射版本，\n 变换后的字符串唯一标识原始字符串。在此版本中，每个字符串都有一个相同长度的唯一反转。

\n\n

双射变换的计算方法是首先将输入分解为 Lyndon 词的非递增序列；根据 Chen\xe2\x80\x93Fox\xe2\x80\x93Lyndon 定理，这样的分解存在，并且可以在线性时间内找到。\n 然后，算法将所有这些单词的所有旋转排序在一起；与通常的 Burrows\xe2\x80\x93Wheeler 变换一样，这会生成 n 个字符串的排序序列。然后通过选择此排序列表中每个字符串的最后一个字符来获得转换后的字符串。

\n

\n