Compressed Suffix Arrayの解説(2) -SAの計算量-

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

Suffix Arrayの計算量について解説。

計算量には空間計算量、時間計算量の2種類がある。
空間計算量とは、あるデータ構造を保持するのに必要となるメモリ、ディスクの大きさを表す。
時間計算量とは、あるアルゴリズムがデータを処理するのにかかる時間を表す。

計算量はデータ数などの関数として表現され、たとえばデータ数がNのとき

O(N)
O(NlogN)
O(N^2)

などと表される。動かすマシンの性能ではなく、単純にデータ数が非常に大ききなった場合のデータ構造、アルゴリズムの性能を検討する際に計算量の考え方が用いられる。

まずは空間計算量の話から。

たとえば1文字1byte(8bit)とした場合、N文字のテキストを保持するのに必要なbit数は8Nbit。

ちょっと書き換えると文字種として256種類を取りうる文字を1文字保持するのに必要なbit数は2を底として

log256bit = log(2^8) = 8bit

一般化して、取りうる文字の集合をΣとすると文字の種類は|Σ|なので

log|Σ| bit

必要ということ。
従って、N文字のテキストを保持するのに必要な空間計算量はO(Nlog|Σ|)となる。

一方、Suffix Arrayのインデックスについて、各インデックスは、それぞれの部分文字列の出現位置なのでテキストのサイズがNならインデックスとして取りうる値は1からNの整数。つまり文字の種類は|Σ|=N種類となる。従って空間計算量は

O(NlogN)

となる。

よってSuffix Arrayを用いたキー検索をする場合

O(Nlog|Σ|) + O(NlogN)

だけメモリが必要となる。

ちなみにCompressed Suffix Arrayはインデックスに対する空間計算量O(NlogN)を圧縮し、大雑把に言ってO(Nlog(logN))でインデックスを保持できるようになっている。

最後に時間計算量についてだが、これはN個要素をもつインデックスを単純に二分探索しているだけなので

O(logN)

となる。

ということで今回はここまで。
次回はCSAの解説に入る。