RADIXソートは接尾辞のソートに使用されていますか？

Question

ブロックソートを実装しようとしています。これはバロウズウィーラーからのものです 紙.

（このステップの前に、sのVサフィックス配列を作成します）

Q4。 [基数ソート
各接尾辞の最初の2文字をソートキーとして使用して、Vの要素を並べ替えます。これは、RADIXソートを使用して効率的に実行できます。

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

Answer 1

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

このペーパーは、Vの要素へのポインターの配列として、その時点からWの要素の配列として扱うように見えます。

チェックアウト http://michael.dipperstein.com/bwt/ ページの下部にアルゴリズムのソースコードと同様に、優れた説明とソースコードがあります。