博士

やあ、ロボ子！今日はBurrows-Wheeler変換（BWT）について話すのじゃ！データ圧縮とか配列アラインメントに使われてるすごいヤツなのじゃぞ！

ロボ子

BWTですか、博士。`bzip2`や`bowtie`、`bwa`といったツールで使われているんですね。具体的にどのような変換をするのでしょうか？

博士

BWTは文字列を並べ替えて、同じ文字がまとまるようにするのじゃ。例えば、`coconut`をBWTにかけると`tooccun`になるのじゃ！

ロボ子

なるほど、`coconut`の文字が並び替えられて、`o`や`c`がまとまっているんですね。でも、それってどうやって元の文字列に戻すんですか？

博士

そこがミソなのじゃ！BWTは可逆的な変換なのじゃ。元の文字列をちゃんと復元できるのじゃぞ！

ロボ子

すごい！具体的にはどんなアルゴリズムなんですか？

博士

まず、文字列のすべての回転をリストにするのじゃ。例えば`banana`なら、`banana`, `anaban`, `nabana`, `abanan`, `nanaba`, `anaban`って感じじゃな。それを辞書順にソートして、ソートされた回転の最後の文字を抽出するのじゃ！

ロボ子

なるほど、回転させて辞書順に並べるんですね。`$`記号が出てきましたが、これは何ですか？

博士

`$`は文字列の終端を示す特別な記号なのじゃ。これがないとBWTが可逆じゃなくなっちゃうのじゃ！

ロボ子

BWTは配列アラインメントにも使えるんですね。小さな文字列を大きな文字列から検索するのに役立つとのことですが、どうしてですか？

博士

BWTには「最終列から最初の列へのマッピング（Last-to-first Mapping）」という性質があるのじゃ。これを使うと、文字列検索が効率的にできるのじゃ！

ロボ子

最終列から最初の列へのマッピング…ですか。BWT文字列のデコードも、`$`記号を基点に最終列と最初の列を反復することで行うと。

博士

その通り！でも、BWT変換は非効率な場合もあるのじゃ。そんな時はSuffix Arrayというデータ構造を使うと効率化できるのじゃぞ！

ロボ子

Suffix Arrayですか。さらに検索を高速化するにはFM Indexというものが使えるんですね。

博士

そうそう！BWTは同じ文字をまとめる傾向があるから、圧縮にも役立つのじゃ！

ロボ子

BWT、奥が深いですね！データ圧縮から配列アラインメントまで、色々な応用があるなんて知りませんでした。

博士

じゃろ？ところでロボ子、BWTで圧縮されたデータを見てると、なんだか私の部屋みたいだと思うのは私だけかのじゃ？

ロボ子

え？どういうことですか？

博士

だって、同じものがゴチャっとまとまってる感じが…！