SA-IS（Suffix Array - Induced Sorting）アルゴリズム
『高速文字列解析の世界』を読んでいたら、Suffix Arrayを線形時間で構築するアルゴリズムとしてInduced Sorting（IS）を用いたものが紹介されていた。文章で読んだだけでは、いまいち十分に理解できた気分にならなかったので、自分で実装してみた。これはそのSA-ISアルゴリズムの解説である。
ソースコードは https://github.com/hkurokawa/bwt-java にあるので、適宜参照してほしい。
接尾辞配列（SA; Suffix Array）については既知とする。
SAを構築するナイーブな方法は、すべての接尾辞（元の文字列の長さをnとすると、n個ある）をソートするものである。ソート自体は \(O(n \log n)\) でできるが、接尾辞同士の比較に \(O(n)\) かかるので、全体としては \(O(n^2 \log n)\) になってしまう。
これを改善して、のみならず、 \(O(n)\) でやってしまうのがInduced Sorting（IS）を利用したアルゴリズムである。なおメモリ空間使用量も \(O(n)\) で収まる。
Induced Sorting (IS)とは
“induced”は日本語で「誘起された」と訳されることが多い。このアルゴリズムが提案された元論文Two Efficient Algorithms for Linear Time Suffix Array Construction, G Nong, et.al.をざっと眺めた感じだと、貪欲に表を埋めていったときに自然とソート状態が達成される操作を”induced sorting”と呼んでいるように感じる。この呼び方が接尾辞配列以外でも使う一般的なものなのかは知らない。なにかご存知の方がいれば、教えていただきたい。
大まかな手順
最初に、大まかなアルゴリズムを説明する。目的は与えられた文字列から接尾辞配列を作ること。ここでは簡単のために文字列は英小文字から成り立ち、文字列の最後尾にどの文字よりも小さい番兵（sentinel）文字$があるとする。
基本的にはバケットソートを行う。たとえば与えられた文字列の文字がすべて相異なるなら、バケットソートを1回行うだけで接尾辞配列が得られる。一方、同じ文字が複数回登場するなら、各バケット内で接尾辞同士をソートしなければならない。これをなんとか\(O(n)\)で実行したい。
ここで接尾辞をつぎの2種類に分けて考える。
- S-type: \(S_i \lt S_{i+1}\)となる接尾辞もしくは番兵文字（
$） - L-type: \(S_i \gt S_{i+1}\)となる接尾辞
すると、同じバケット内ではL-typeの接尾辞がS-typeの接尾辞よりも前に位置することが保証される。
これを厳密ではないが直感的な方法で説明する。同じバケット内ということはどちらも同じ文字から始まっており、ここではその文字を”b”としよう。すなわち、S-typeは”bc…“や”bbc…“のような最初に現れる”b”以外の文字が”b”より大きい文字列である。一方、L-typeは”ba…“もしくは”bba…“のような最初に現れる”b”以外の文字が”b”より小さい文字列である。この2つの接尾辞を比較すると、L-typeの方が常にS-typeのものより小さくなる。
実際に”abracadabra”という文字列の接尾辞配列はつぎのようになり、同じバケット内でL-typeがS-typeより前に位置することが分かるだろう。
| index | pos | suffix | bucket | type |
|---|---|---|---|---|
| 0 | 11 | $ | $ | S |
| 1 | 10 | a$ | a | L |
| 2 | 7 | abra$ | a | S |
| 3 | 0 | abracadabra$ | a | S |
| 4 | 3 | acadabra$ | a | S |
| 5 | 5 | adabra$ | a | S |
| 6 | 8 | bra$ | b | S |
| 7 | 1 | bracadabra$ | b | S |
| 8 | 4 | cadabra$ | c | L |
| 9 | 6 | dabra$ | d | L |
| 10 | 9 | ra$ | r | L |
| 11 | 2 | racadabra$ | r | L |
さらに興味深いことに、S-typeの接尾辞がすでに表に埋められている場合、以下の手順で自然にバケット内のL-type同士がソートされた状態が実現できる（詳細は後述）。
- 表の先頭を見る
- すでに\(S_i\)が埋まっていたら\(S_{i-1}\)がL-typeか調べる
- L-typeだったら、\(S_{i-1}\)を該当するバケット内の空いている先頭に入れる
- その行が空もしくは\(S_{i-1}\)がS-typeだったら何もしないでつぎの行に移る
- #2-#4を表の最後に達するまで行う
したがって、まずはS-typeの接尾辞をソート済みの状態で表に入れることを目指す。実はこのとき、すべてのS-typeの接尾辞が表に埋まっている必要はない。「\(S_{i-1}\)がL-typeであるようなS-typeの\(S_i\)」だけ表に埋まっていればよい。このようなS-typeの接尾辞は連続するS-type接尾辞の左端でもあるのでLMS (Leftmost S-type)と呼ぶ（『高速文字列解析の世界』では\(S^*\)と表記）。このLMSはL-typeを埋めるために必要なので、とりあえずLMS同士がソートされていればよい（どうやってLMS同士をソートするかは後述）。
このLMSだけ埋められた表にL-typeの接尾辞を埋め、そのあとLMSはいったん表から削除する。そしてL-typeの接尾辞だけ埋められた表にS-typeの接尾辞を埋めていく。そうすると表全体すなわち接尾辞配列が完成する。
全体の流れはつぎのようになる。
- 接尾辞をS-type、L-typeに分類
- S-typeの接尾辞のうちLMSのものを取り出してソートする
- 表にLMSを埋める
- そのLMSを使って表にL-typeの接尾辞を埋める
- LMSを表から削除する
- 表に埋められたL-type接尾辞を使ってS-type接尾辞を埋める
アルゴリズムの詳細
ここでは、さきほど述べたアルゴリズムの詳細を述べる。分かりやすさを優先して、実際の実行順とは異なり、つぎの順番で説明する。
- 表にLMSが埋められた状態でL-typeの接尾辞を埋める（前節の#4）
- 表にL-typeの接尾辞が埋められた状態でS-typeの接尾辞を埋める（前節の#6）
- LMSをソートする（前節の#2）
L-typeの接尾辞を埋める
“abracadabra”の例だと、LMSだけ埋めた状態はつぎのようになる（LMSのtypeはS*と表記）。先ほどの表と見比べれば分かるが、接尾辞の位置は最終的な位置と若干異なる。たとえば\(S_7\)の位置はここではindex 3になっているが、最終的な接尾辞配列ではindex 2にいるべきだ。
| index | pos | suffix | bucket | type |
|---|---|---|---|---|
| 0 | 11 | $ | $ | S* |
| 1 | a | |||
| 2 | a | |||
| 3 | 7 | abra$ | a | S* |
| 4 | 3 | acadabra$ | a | S* |
| 5 | 5 | adabra$ | a | S* |
| 6 | b | |||
| 7 | b | |||
| 8 | c | |||
| 9 | d | |||
| 10 | r | |||
| 11 | r |
ここから、L-typeの接尾辞を埋めていく。
まず表の一番上、index 0を見る。index 0には\(S_{11}\)が埋まっているので、その1つ前の接尾辞\(S_{10}\)のtypeを調べるとL-typeなので表に入れる。\(S_{10}\)はすなわち”a$”である。これをバケット”a”の空いている箇所のうち一番先頭、つまり、表のindex 1に入れる。
つぎに表のindex 1を見ると、先ほど入れた\(S_{10}\)が入っている。この1つ前の接尾辞\(S_9\)はL-typeで”ra$”なのでバケット”r”の先頭、index 10に入る。
そのつぎのindex 2は埋まっていないので飛ばしてindex 3をみると\(S_7\)である。この1つ前の接尾辞\(S_6\)はL-typeで”dabra$”である。バケット”d”はindex 9に1つしか枠がないので、そこに入れる。
index 4およびindex 5についても同様にして\(S_2\)と\(S_4\)を表に埋める。ここまでで表はつぎのようになる。
| index | pos | suffix | bucket | type |
|---|---|---|---|---|
| 0 | 11 | $ | $ | S* |
| 1 | 10 | a$ | a | L |
| 2 | a | |||
| 3 | 7 | abra$ | a | S* |
| 4 | 3 | acadabra$ | a | S* |
| 5 | 5 | adabra$ | a | S* |
| 6 | b | |||
| 7 | b | |||
| 8 | 4 | cadabra$ | c | L |
| 9 | 6 | dabra$ | d | L |
| 10 | 9 | ra$ | r | L |
| 11 | 2 | racadabra$ | r | L |
このあとはindex 6および7は埋まっていないので飛ばして、8から11に関してはそれぞれの1つ前の接尾辞はL-typeでないので何もしない。以上でL-typeはすべて埋まった。
この手順でL-type接尾辞がソート済みの状態で表に埋まることが不思議に思えるかもしれない。それについて説明する。
まず、すべてのL-type接尾辞\(S_i\)について\(S_i \gt S_{i+1}\)が成り立つ。この\(S_{i+1}\)はL-typeかLMSかのどちらかである。いいかえると\(S_i\)がL-typeなら、\(S_{i+1}\)は表中で\(S_i\)よりも上側に位置してすでに埋まっているはずである。以上のことから、表を上から下まで見ていくさきほどの手順では、かならず新しく埋められるL-typeの接尾辞はいま見ているところよりも後ろに位置し、すべてのL-typeが網羅されることが保証される。
S-typeの接尾辞を埋める
さて、L-typeの接尾辞が埋まったので、LMSはいったん削除し、表はつぎのようになる。
| index | pos | suffix | bucket | type |
|---|---|---|---|---|
| 0 | $ | |||
| 1 | 10 | a$ | a | L |
| 2 | a | |||
| 3 | a | |||
| 4 | a | |||
| 5 | a | |||
| 6 | b | |||
| 7 | b | |||
| 8 | 4 | cadabra$ | c | L |
| 9 | 6 | dabra$ | d | L |
| 10 | 9 | ra$ | r | L |
| 11 | 2 | racadabra$ | r | L |
ここからS-type接尾辞を埋めていく。手順はさきほどの逆を行えばよい。すなわち表を下から上に見ていって、いま見ている接尾辞\(S_i\)の1つ前の\(S_{i-1}\)がS-typeなら、その接尾辞をバケットの空いている後ろから詰めていく。
実際に見てみよう。最初はindex 11からスタートする。この接尾辞\(S_2\)の1つ前の接尾辞\(S_1\)は”bracadabra$”なのでバケット”b”の最後尾index 7に入れる。index 10の接尾辞\(S_9\)の1つ前\(S_8\)は”bra$”なので、バケット”b”の空いている最後尾index 6に入れる。
| index | pos | suffix | bucket | type |
|---|---|---|---|---|
| 0 | $ | |||
| 1 | 10 | a$ | a | L |
| 2 | a | |||
| 3 | a | |||
| 4 | a | |||
| 5 | a | |||
| 6 | 8 | bra$ | b | S |
| 7 | 1 | bracadabra$ | b | S |
| 8 | 4 | cadabra$ | c | L |
| 9 | 6 | dabra$ | d | L |
| 10 | 9 | ra$ | r | L |
| 11 | 2 | racadabra$ | r | L |
これを繰り返していくと、接尾辞”$”、ここでは\(S_{11}\)以外のS-type接尾辞が埋まる。”$”については常にindex 0に入ることが分かっているので、最後にindex 0に\(S_{11}\)を入れると、求める接尾辞配列が得られる。
LMSのソート
ここまでで、「LMSのソート」以外はすべて説明した。残るはLMSのソートだけである。
まず「LMS-substring」という概念（『高速文字列解析の世界』では「\(S^*\)部分文字列」と呼んでいる）を導入する。これは元の文字列においてLMSになる接尾辞間の部分文字列を表す。”abracadabra”の場合、LMSは\(S_3\)、\(S_5\)、\(S_7\)、\(S_{11}\)の4つになる。したがってLMS-substringは3-5間の”aca”、5-7間の”ada”、7-11間の”abra$”になる。さらに”$”も便宜的にLMS-substringとして付け加えて、4つがLMS-substringになる。
これをソートして0始まりで数字を振る。もし同じLMS-substringがある場合は同じ数字を振る必要がある。
- 0: $
- 1: abra$
- 2: aca
- 3: ada
これを出現順に並べて、その接尾辞配列を計算する。この例の場合、”2310”の接尾辞配列なので、つぎのようになる。
| index | pos | suffix | LMS-substring | LMS |
|---|---|---|---|---|
| 0 | 3 | 0 | $ | \(S_{11}\) |
| 1 | 2 | 10 | abra$$ | \(S_7\) |
| 2 | 0 | 2310 | acaadaabra$$ | \(S_3\) |
| 3 | 1 | 310 | adaabra$$ | \(S_5\) |
これを見るとわかるが、この接尾辞配列に対応するLMSの並びがソート済みのLMSになっている。実際、LMS-substringの大小関係とこの数字の大小関係は一致しているため、この結果は当然といえる。
ここまでで、LMS-substringをソートさえすれば、LMSのソートができることがわかった。残るはLMS-substringのソートである。
LMS-substringのソート
ここでLMSを接尾辞配列の表に入れるときにきちんとソートせずに入れて、それからinduced sortingしたらどうなるか考えてみよう。具体的には、LMSを各バケットの下側に入れるが、その入れる順序は適当に行う。たとえば接尾辞配列の表はつぎのようになる。
| index | pos | suffix | bucket | type |
|---|---|---|---|---|
| 0 | 11 | $ | $ | S* |
| 1 | a | |||
| 2 | a | |||
| 3 | 7 | abra$ | a | S* |
| 4 | 5 | adabra$ | a | S* |
| 5 | 3 | acadabra$ | a | S* |
| 6 | b | |||
| 7 | b | |||
| 8 | c | |||
| 9 | d | |||
| 10 | r | |||
| 11 | r |
ここで、index 3、4、5のLMSの並びはソートされていない。またバケットソートによって1文字目はソートされているので、それを表すために1文字目だけ太字にしてある。
この状態でL-typeおよびS-typeの接尾辞をinduced sortingで表に入れてみよう。結果はつぎのようになる。同じようにソートされている文字は太字にしてある。
| index | pos | suffix | bucket | type |
|---|---|---|---|---|
| 0 | 11 | $ | $ | S* |
| 1 | 10 | a$ | a | L |
| 2 | 7 | abra$ | a | S* |
| 3 | 0 | abracadabra$ | a | S |
| 4 | 3 | acadabra$ | a | S* |
| 5 | 5 | adabra$ | a | S* |
| 6 | 8 | bra$ | b | S |
| 7 | 1 | bracadabra$ | b | S |
| 8 | 4 | cadabra$ | c | L |
| 9 | 6 | dabra$ | d | L |
| 10 | 9 | ra$ | r | L |
| 11 | 2 | racadabra$ | r | L |
LMSのあとにL-typeの接尾辞を入れたときにソート済みの部分が伸び、さらにS-typeの接尾辞を入れるときに伸びる。LMSのみに注目すると、ちょうどLMS-substringに相当する部分、つまり”$”、”abra$”、”aca”、”ada”が太字になっている。このことから、LMSをバケットの後ろに入れたあとにinduced sortingしてLMSに注目すると、ソート済みのLMS-substringが得られることがわかる。
以上をまとめると、LMSをソートするためにはつぎのようにすればよい。
- 接尾辞配列の表にLMSを入れる。このとき、LMSはソートされていなくてよい。
- induced sortingをしてL-typeとS-typeを表に埋める
- 表におけるLMSの順序に応じてLMS-substringに数字を振っていく。同じ部分文字列には同じ数字を振ること。
- 元の文字列におけるLMSの出現順に対応する数字を並べかえて、その数字を連結した文字列の接尾辞配列を求める
- 接尾辞配列の各要素に対応するLMSの並びがソート済みLMSになる
この#3で、LMS-substring同士の比較が発生するが、比較する文字の最大合計数は\(n\)なので、ぜんたいで\(O(n)\)で実行できる。また、#4で再起が発生するが、このときの接尾辞配列のサイズは半分になっている。したがって、全体のアルゴリズムの実行時間が\(O(n)\)なら、再起を含めても\(O(n) + O(n/2) + O(n/4) + \cdots O(1) = O(n)\)で収まる。
実装上の注意点
いくつか実装上で注意しておくとよいこと。
文字は置換してよい
与えられた文字列内における文字の大小関係が維持されていれば、好きな文字に置換してしまってよい。たとえば”fox”を”abc”に置換してよい。もっといえば、整数配列の[1, 2, 3]に置換してしまった方がよいだろう。こうすると、LMSのソートでLMS番号の接尾辞配列を求めるときに同じ関数が使える。
また、この置換のときに番兵文字を考慮しておけば、番兵文字が実際の文字と被ることもなくて便利である。
LMS-substringを保持する必要はない
アルゴリズムを見ればわかるが、LMS-substringそれ自体を覚えておく必要はない。最終的に、対応するLMSの接尾辞配列内における順番が分かればよい。ただし、ソートされたLMS-substringに番号を振るときに隣りあうLMS-substringが一致するか調べる必要はある。
（おまけ）LMS-substringが重複するときのLMSソート
この記事で利用した”abracadabra”はよくあるサンプルであるが、LMS-substringは相異なるので、すこし分かりづらい。実際、LMSソート用の接尾辞配列をつくると、それが実は最終的に求める接尾辞配列になっているので、なんでこんなややこしいことをしないといけないのかよく分からなくなる。
そこで”babababb”という文字列を考えよう。これのLMS-substringは”aba”, “aba”, “abb$”, “$”の4つ、3種類になる（”aba”が2つあることに注意）。LMS-substringのソートをするための接尾辞配列はつぎのようになる。
| index | pos | suffix | bucket | type |
|---|---|---|---|---|
| 0 | 8 | $ | $ | S* |
| 1 | 3 | ababb$ | a | S* |
| 2 | 1 | abababb$ | a | S* |
| 3 | 5 | abb$ | a | S* |
| 4 | 7 | b$ | b | L |
| 5 | 4 | babb$ | b | L |
| 6 | 2 | bababb$ | b | L |
| 7 | 0 | babababb$ | b | L |
| 8 | 6 | bb$ | b | L |
見てわかるように、index 1とindex 2は位置が逆だし、最終形の接尾辞配列とは異なっている。しかし、LMS-substringのソートという観点では、\(S_8\)、\(S_3\)、\(S_1\)、\(S_5\)と期待する並びになっている。
したがってLMS-substringそれぞれに0、1、2と番号を振ると、出現順は”1120”になり、これの接尾辞配列は["0", "1120", "120", "20"]なので、LMSの並び順は\(S_8\)、\(S_1\)、\(S_3\)、\(S_5\)と期待どおりになる。