在不知道最后一个字符的情况下反向 BWT
Reverse BWT without knowing last character
通常在Burrows-Wheeler Transform算法中，$字符用于表示字符串结束，但在很多情况下，这个$被省略了。
不知道最后一个字符的位置如何反转？
例如，我有这个 BWT：
[[[[[1[[11endgnad1234245ndbnbbb]]]]]]]nnnngnabbbdiaaaiaaii
按照该算法，我可以轻松构建 BWT 矩阵的第一列，我选择以压缩方式表示，如下所示：
Character : Occurrences
1 : 4
2 : 2
3 : 1
4 : 2
5 : 1
[ : 7
] : 7
a : 7
b : 7
d : 4
e : 1
g : 2
i : 4
n : 9
在不知道原始字符串中最后一个字符的情况下，我看不出如何重建原始字符串。
非常感谢任何帮助。
唐
P/S：如果您想知道原始字符串是什么：
[1]ban[2]banana[3]band[4]bandage[12]bin[14]bind[15]binding
你不能（但你可以试试 ;-)。
您的第一个 bwt 符号是原始字符串中的最后一个 'S'。
现在您应该通过 LF 映射向后展开原始字符串。
它实际上是 bin[sym] + rank(sym, i) + 1，你从 i = 0 开始。
您可以轻松地从事件中获取 bin[] 数组。
问题是，一旦你的 'i' 更大然后省略了 '$' 你不应该添加最后一个 '1' 这样你就破坏了字符串并且事情变得讨厌。
如果您还重建 sa[] 并覆盖已设置的索引，则可以检测到错误。因此，您可以将任意 $ position 设置为“0”并尝试恢复，如果失败则将其设置为 1...直到您正确重建。不知道这个能不能优化。
干杯，
D.
通常在Burrows-Wheeler Transform算法中，$字符用于表示字符串结束，但在很多情况下，这个$被省略了。
不知道最后一个字符的位置如何反转？
例如，我有这个 BWT：
[[[[[1[[11endgnad1234245ndbnbbb]]]]]]]nnnngnabbbdiaaaiaaii
按照该算法，我可以轻松构建 BWT 矩阵的第一列，我选择以压缩方式表示，如下所示：
Character : Occurrences
1 : 4
2 : 2
3 : 1
4 : 2
5 : 1
[ : 7
] : 7
a : 7
b : 7
d : 4
e : 1
g : 2
i : 4
n : 9
在不知道原始字符串中最后一个字符的情况下，我看不出如何重建原始字符串。
非常感谢任何帮助。 唐
P/S：如果您想知道原始字符串是什么：
[1]ban[2]banana[3]band[4]bandage[12]bin[14]bind[15]binding
你不能（但你可以试试 ;-)。 您的第一个 bwt 符号是原始字符串中的最后一个 'S'。 现在您应该通过 LF 映射向后展开原始字符串。 它实际上是 bin[sym] + rank(sym, i) + 1，你从 i = 0 开始。 您可以轻松地从事件中获取 bin[] 数组。 问题是，一旦你的 'i' 更大然后省略了 '$' 你不应该添加最后一个 '1' 这样你就破坏了字符串并且事情变得讨厌。 如果您还重建 sa[] 并覆盖已设置的索引，则可以检测到错误。因此，您可以将任意 $ position 设置为“0”并尝试恢复，如果失败则将其设置为 1...直到您正确重建。不知道这个能不能优化。
干杯，
D.