「高速文字列解析の世界」（岡野原大輔 著）を勉強中です。
で、その忘備録というか、自分なりのまとめというか…。
適当な理解なので間違っているかもしれないですが、そこはご容赦ください。
今日（今日で終わりかもしれませんが）は、BWT(Burrows Wheeler Transform)配列について。
まず、BWT配列の何が嬉しいのかということですが、部分文字列の頻度などの統計量を高速で計算できたり、データ圧縮しやすい表現になるそうです。
例えば、"abracadabra$"をBWT配列に変換すると、"ard$rcaaaabb"となります。"aaaa"や"bb"の部分、同じ文字列が連続しています。これは短い文字列なので、それほどそうは思われないかもしれませんが、もっと長い文字列だと、同じ文字列が連続して多く並ぶので、ひと目で「ああ、圧縮しやすそうだなぁ」と思えます。
では、実際のBWT配列への変換です。
文字列"abracadabra$"があったとします。
で、これを配列に格納します。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| a | b | r | a | c | a | d | a | b | r | a | $ |
次に、すべての位置から始まる部分文字列を作成します。
※"$"はどの文字よりも小さな文字
| 0 | abracadabra$ |
| 1 | bracadabra$ |
| 2 | racadabra$ |
| 3 | acadabra$ |
| 4 | cadabra$ |
| 5 | adabra$ |
| 6 | dabra$ |
| 7 | abra$ |
| 8 | bra$ |
| 9 | ra$ |
| 10 | a$ |
| 11 | $ |
次に接尾辞配列というのを求めます。
「すべての位置から始まる部分文字列」を辞書式順序で小さい順にならべ、その位置を格納したのが接尾辞配列になります。
そして、BWT配列は、この接尾辞配列の値から1マイナスした値を添字として、文字列配列を参照した場合の文字の配列になります。
ただし、0番目だけは最後の文字の一つ前の文字になります。
↓
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| a | b | r | a | c | a | d | a | b | r | a | $ |
| i | 接尾辞配列 | BWT配列 | 接尾辞 |
| 0 | 11 | a | $ |
| 1 | 10 | r | a$ |
| 2 | 7 | d | abra$ |
| 3 | 0 | $ | abracadabra$ |
| 4 | 3 | r | acadabra$ |
| 5 | 5 | c | adabra$ |
| 6 | 8 | a | bra$ |
| 7 | 1 | a | bracadabra$ |
| 8 | 4 | a | cadabra$ |
| 9 | 6 | a | dabra$ |
| 10 | 9 | b | ra$ |
| 11 | 2 | b | racadabra$ |