gpt4 book ai didi

c++ - 在不知道最后一个字符的情况下反向 BWT

转载 作者:行者123 更新时间:2023-11-30 05:28:32 25 4
gpt4 key购买 nike

通常在 Burrows-Wheeler 变换算法中,$ 字符用于表示字符串的结尾,但在很多情况下,这个 $ 被省略。

我想知道如何在不知道最后一个字符的位置的情况下反转它?

例如,我有这个 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.

关于c++ - 在不知道最后一个字符的情况下反向 BWT,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36798538/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com