1

ブロックソートを実装しようとしています。これはBurrowsWheelerの論文からのものです。

（この手順の前に、SのV接尾辞配列を作成します）

Q4。[基数ソート]
各サフィックスの最初の2文字をソートキーとして使用して、Vの要素をソートします。これは、基数ソートを使用して効率的に実行できます。

基数ソートでサフィックスをソートしているとのことですが。
これはどのようにアレイVを更新することになっていますか？基数ソートが終了して初めて、接尾辞のソートされた位置を知ることができます。4番目のサフィックスがソート後の最初のサフィックスになるとします。したがって、V [0]=iです。この場合、（私があなたに言ったので）i = 4であることがわかります。しかし、アルゴリズムは、それらの位置を追跡していないので、どのようにしてそれを知るのでしょうか。サフィックスとそのサフィックス番号の両方を含むクラスを作成する必要がありますか？

4

1 に答える 1

2

簡単に読んだ後; Burrows-Wheelerにはエラーがあり、配列Vを使用してWの要素を並べ替え、Wの要素の最終的な位置を追跡およびマッピングすることを意味していると思います。Wは変更されず、Vにはソートされたインデックスのリストが含まれます。

この論文は、Vをその時点からWの要素へのポインタの配列として扱っているように見えます。

http://michael.dipperstein.com/bwt/をチェックして ください。ページの下部に、アルゴリズムの優れた説明とソースコードがあります。

于 2011-06-15T04:09:43.827 に答える