string - 没有 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-O-n-time-O-n-space