「高速文字列解析の世界」忘備録

「高速文字列解析の世界」(岡野原大輔 著)を勉強中です。

で、その忘備録というか、自分なりのまとめというか…。
適当な理解なので間違っているかもしれないですが、そこはご容赦ください。

今日(今日で終わりかもしれませんが)は、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 $
接尾辞配列とBWT配列
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$