Compressed Suffix Arrayの解説(1) -Suffix Array-

================================================

最近(でもないか)話題のCompressed Suffix Array(CSA)について解説してみる。

CSAとはSuffix Array(SA)のインデックスを圧縮して小さくしたもの。大規模テキストデータに対する検索インデックスを作る場合など少しでもインデックスを小さくしたい場合に使われる。

CSAを知るにはSAから！ということで今回はSAの解説を。

Suffix Array(SA)とはデータ構造の一種で事前に(サイズがNの)テキストに対してインデックスを作っておくことでキーとなる文字列を入力として与えるとテキストに含まれるキーの位置をO(logN)で探索できる、というもの。

たとえば、テキスト

abracadabra

に対してインデックスを作っておくと、キー

abra

が与えられたときに

1,8

とキーの出現位置を返してくれる。(先頭を1とした場合)

利用例としては、SAを使ってwebからクロールしてきた文書にインデックスを作っておけば検索クエリに対して、そのクエリの出現する文書と出現位置を取得することができるので、検索エンジンとして使うことが考えられる。

================================================

以下、SAのインデックスの作り方について解説。

まず、テキストのそれぞれの位置についてその位置から末尾までの部分文字列を並べる。各部分文字列の右側の数値は元テキストでの開始位置。

 1 abracadabra
 2 bracadabra
 3 racadabra
 4 acadabra
 5 cadabra
 6 adabra
 7 dabra
 8 abra
 9 bra
10 ra
11 a

次に、この部分文字列をアルファベット順にソートする。

11 a
 8 abra
 1 abracadabra
 4 acadabra
 6 adabra
 9 bra
 2 bracadabra
 5 cadabra
 7 dabra
10 ra
 3 racadabra

最後に、ソート後の開始位置の並びをインデックスとして保持しておく。

11 8 1 4 6 9 2 5 7 10 3

このインデックスと元のテキストを使ってキーの出現位置を高速に見つけだす。

具体的には以下のように二分探索を行う。キーとしてabraが与えられたとする。

まずはインデックスの真ん中の値である9を取り出す。

11 8 1 4 6 [9] 2 5 7 10 3

テキストabracadabraの9番目の位置から始まる部分文字列はbraなのでキーabraのほうがアルファベット順では小さい。

よって次の探索範囲は

11 8 [1] 4 6

なので真ん中の値1を取り出す。テキストabracadabraの1番目の位置から始まる
部分文字列abracadabraの先頭部分がキーabraと同じなのでインデックス1を出力する。

インデックスは部分文字列のアルファベット順でソートされているのでインデックス1の前後でキーabraと先頭部分が一致するものを、すべて出力する。

11 a
 8 abra
 1 abracadabra
 4 acadabra

なので1以外に8もキーabraと先頭部分が(今回はたまたまイコールになったが)一致する。よってインデックス8を出力する。

従って最終的な出力は

1,8

となる。

ということで今回はここまで。
次回はSAの計算量の話。

================================================< ---- < | > Compressed Suffix Arrayの解説(2) -SAの計算量- >