6

よく知られているバロウズ・ウィーラー変換を線形時間で実行する必要があります。サフィックスソートとEOF文字を使用した解決策を見つけましたが、EOFを追加すると変換が変更されます。例: 文字列bcababa と 2 つの回転を 考えてみましょう

  • s1 =abababc
  • s2 =ababcab

s1 < s2 であることは明らかです。EOF 文字を使用すると、次のようになります。

  • s1 = アババ#bc
  • s2 = アバ#bcab

そして今、s2 < s1。そして、結果として生じる変換は異なります。EOF なしで BWT を実行するにはどうすればよいですか?

4

3 に答える 3

4

それ自体と連結された文字列のサフィックス配列を計算することにより、EOF 文字なしで線形時間と空間で変換を実行できます。次に、サフィックス配列を反復処理します。現在の接尾辞配列の値が より小さい場合n、出力配列に、接尾辞配列の現在の値で示される位置から始まる回転の最後の文字を追加します。ただし、このアプローチでは、EOF 文字が存在するかのように文字列のローテーションがソートされないため、BWT 変換の結果が少し異なります。

より完全な説明はここにあります: 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

BWT が機能するには、文字列に EOF 文字が含まれている必要があります。そうしないと、元の文字列を取得するために逆変換を実行できないためです。EOF がない場合、文字列 "ba" と "ab" は両方とも同じ変換バージョン ("ba") になります。EOF では、変換が異なります

ab        ba

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

つまり、ab は "|ab" に変換され、ba は "b|a" に変換されます。

EOF は、文字サイクルが開始するポイントをマークするため、BWT に必要です。

Re: ウィキペディアによると、EOF 文字なしで実行すると、

入力文字列の回転は同じ変換文字列につながるため、入力に「EOF」マーカーを追加するか、インデックスなどの情報で出力を補強しない限り、BWT を反転することはできません。すべてのローテーションのクラスからの入力文字列。

transform には全単射バージョンがあり、変換された文字列が元の文字列を一意に識別します。このバージョンでは、すべての文字列に同じ長さの一意の逆数があります。

全単射変換は、最初に入力をリンドン単語の非増加シーケンスに因数分解することによって計算されます。このような因数分解は、Chen–Fox–Lyndon の定理によって存在し、線形時間で見つけることができます。次に、アルゴリズムは、これらすべての単語のすべてのローテーションをまとめて並べ替えます。通常の Burrows-Wheeler 変換と同様に、これは n 個の文字列の並べ替えられたシーケンスを生成します。変換された文字列は、この並べ替えられたリスト内の各文字列の最後の文字を選択することによって取得されます。

于 2012-05-10T05:23:21.707 に答える
0

このスレッドがかなり古いことは知っていますが、同じ問題があり、次の解決策を思いつきました。

  • 辞書式の最小文字列回転を見つけて、オフセットを保存します (逆にする必要があります) (私は lydon 因数分解を使用します)
  • 回転された文字列に対して通常の bwt アルゴリズムを使用します (すべてのアルゴリズムは、文字列の後に辞書的に最小の文字が続くと想定しているため、これにより正しい出力が生成されます)。
  • 逆に: インデックス 0 から始まる後方検索などを使用して unbwt し、対応する文字を保存されたオフセットに書き込みます。
于 2015-07-18T13:25:08.567 に答える