最後の文字を知らない逆BWT

Question

通常、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]禁止[2]バナナ[3]バンド[4]包帯[12]ビン[14：ケースでは、元の文字列が何であるかを迷っています]バインド[15]バインディング

Answer 1

あなたはできません（しかし試してみてください;-)。 最初のbwtシンボルは元の文字列 'S'の最後です。 元の文字列をLFマッピングを介して逆方向に展開する必要があります。 実際にはbin [sym] + rank（sym、i）+ 1で始まり、i = 0で始まります。 bin []配列を出現から簡単に取得できます。 問題は、 'i'が大きくなると '$'が省略され、この最後の '1'は追加しないでください。文字列を壊して物事が厄介になります。 sa []を再構築してすでに設定されているインデックスを上書きすると、エラーを検出できます。だから、任意の$ positionを '0'に設定して回復しようとすると、失敗すると正しく再構築されるまで1に設定されます。これを最適化できるかどうかはわかりません。

乾杯、

D.