6

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

  • s1 =abababc
  • s2 =ababcab

很明显 s1 < s2。现在使用 EOF 字符：

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

现在 s2 < s1。并且由此产生的转变会有所不同。如何在没有 EOF 的情况下执行 BWT？

4

3 回答 3

4

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

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

于 2012-12-21T01:21:43.700 回答
1

您需要在字符串中包含 EOF 字符才能使 BWT 工作，否则您将无法执行逆变换以获取原始字符串。如果没有 EOF，字符串 "ba" 和 "ab" 具有相同的转换版本 ("ba")。使用 EOF，变换是不同的

ab        ba

a b |     a | b
b | a     b a |
| a b     | b a

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

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

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

由于输入字符串的任何旋转都将导致相同的转换字符串，因此如果不向输入添加“EOF”标记或使用诸如索引之类的信息来增加输出，则无法反转 BWT，从而可以识别从其所有旋转的类中输入字符串。

有一个双射版本的变换，转换后的字符串唯一地标识原始版本。在这个版本中，每个字符串都有一个相同长度的唯一倒数。

双射变换是通过首先将输入分解为林登词的非递增序列来计算的；Chen-Fox-Lyndon 定理存在这样的因式分解，并且可以在线性时间内找到。然后，算法将所有这些单词的所有旋转排序在一起；就像在通常的 Burrows-Wheeler 变换中一样，这会产生 n 个字符串的排序序列。然后通过在这个排序列表中选择每个字符串的最后一个字符来获得转换后的字符串。

于 2012-05-10T05:23:21.707 回答
0

我知道这个线程很老，但我遇到了同样的问题并提出了以下解决方案：

  • 找到字典顺序的最小字符串旋转并保存偏移量（需要反转）（我使用lydon分解）
  • 在旋转的字符串上使用正常的 bwt 算法（这会产生正确的输出，因为所有算法都假定字符串后面跟着字典最小的字符）
  • 反转：unbwt 使用例如从索引 0 开始的向后搜索并将对应的字符写入保存的偏移量
于 2015-07-18T13:25:08.567 回答