Revised : 202/07/25
Since : 2006/05/01
元のデータを回転させ、同じ記号が並びやすくする方法である。
データサイズは、少しだけ大きくなる。Burrows Wheeler Transform(BWT)とも呼ばれる。
| 元のデータ | 回転させる | 並替 | 変換後のデータ |
| banana | 0:banana 1:ananab 2:nanaba 3:anaban 4:nabana 5:abanan |
5:abanan 3:anaban 1:ananab 0:banana 4:nabana 2:nanaba |
3nnbaaa |
| 一文字回転 | 昇順に並べる | 元のデータの位置 最後の文字を並べる |
| 変換後の データ |
並替 | 前後入替 | 連結する | 連結順番の解説 |
| 3nnbaaa | 0:n -> a 1:n -> a 2:b -> a 3:a -> b 4:a -> n 5:a -> n |
0:a xxxx n 1:a xxxx n 2:a xxxx b 3:b xxxx a 4:n xxxx a 5:n xxxx a |
3:b 2:a 5:n 1:a 4:n 0:a |
3
が元のデータだから最初は「ｂ」 回転させ「b」が最後に来るのは 2 2 は3番目の「a」だから回転後は 5 5 は2番目の「n」だから回転後は 1 1 は2番目の「a」だから回転後は 4 4 は1番目の｢n｣だから回転後は 0 |
| 昇順に 並べる |
符号化手順 並替と同形 「x」は まだ不明 |
上から順に banana |
パズルのように組み合わせる |
接尾辞配列(Suffix Array)を用いて、高速にブロックソートを行うことができる。
接尾辞配列の構築アルゴリズムとしてDivSufSortやSAIS(Suffix Array - Induced Sorting)等がある。
