文字列アルゴリズムを学んでいると、suffix array(接尾辞配列)という配列が出てくる。これは文字列の接尾辞の集合を辞書順にソートし、その順でそれぞれの接尾辞の文字列中の開始位置のindexを格納した配列のことである。以下が参考になる。
例えばbananaの場合、接尾辞は
- banana (position=0) - anana (position=1) - nana (position=2) - ana (position=3) - na (position=4) - a (position=5)
となり、これを辞書順にソートしたものは
- a (position=5) - ana (position=3) - anana (position=1) - banana (position=0) - na (position=4) - nana (position=2)
となるので、suffix arrayはこのpositionの配列である [5, 3, 1, 0, 4, 2]となる。
このsuffix arrayは文字列探索や全文検索にも使われる構造らしい。今度全文検索エンジンを試しに実装してみようと思っていたので、ひとまず一番簡単なアルゴリズムで実装してみた。Javaで実装した。
考え方
一番簡単なアルゴリズムの考え方は単純である。
- 前方から一文字ずつ削っていって部分文字列集合とpositionの組を作る
- 部分文字列を辞書順ソートする
- 最後にその順でpositionの配列を作る
の3ステップで実装できる。この考え方だと、まずソートがの計算量である。またソートのための文字列比較がn文字分ありえるのでその計算量が
である。これらから、全体の計算量は
となる。大分遅いけど、ひとまず理解するためにこれで実装してみる。
Javaでの実装
以下のようになった。単純。
import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.stream.Collectors; public class SuffixArray { public static List<Integer> make(String string) { // 部分文字列とindexの集合を作る List<SuffixArrayItem> items = new ArrayList<>(); for (int position = 0; position < string.length(); position++) { items.add(new SuffixArrayItem(position, string.substring(position))); } // 部分文字列でsortする items.sort( Comparator.comparing(SuffixArrayItem::getString) ); // indexにmapして返す return items.stream().map(x -> x.getPosition()).collect(Collectors.toList()); } } class SuffixArrayItem { private int position; private String string; public SuffixArrayItem(int position, String string) { this.position = position; this.string = string; } public int getPosition() { return this.position; } public String getString() { return this.string; } }
テストも書いておいた。
import org.junit.Test; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import static org.assertj.core.api.Assertions.*; public class SuffixArrayTest { @Test public void make() throws Exception { List<Integer> suffixArray; suffixArray = SuffixArray.make(""); assertThat(suffixArray).isEqualTo(new ArrayList<>()); suffixArray = SuffixArray.make("abc"); assertThat(suffixArray).isEqualTo(Arrays.asList(0, 1, 2)); suffixArray = SuffixArray.make("banana"); assertThat(suffixArray).isEqualTo(Arrays.asList(5, 3, 1, 0, 4, 2)); } }
今回学んだこと
今回の実装をするにあたって、Javaとしても学ぶことがあったので書いておく。
モダンなソート書き方
Java8になってから、モダンなソートの書き方は変わったらしい。やってみたけどたしかに簡単だった。
例えば文字列の辞書順に並べるには、Collections.sortを使って以下のように書ける。
items.sort( Comparator.comparing(SuffixArrayItem::getString) );
逆順であれば以下のように書ける。
items.sort( Comparator.comparing(SuffixArrayItem::getString).reversed() );
他にもいろいろ書き方はあるみたい。このあたり詳しくは以下を参照。
JUnitのアサーションではなくてassertjを使う
JUnitを使ってアサーションを書いていたけど、なんか配列の比較とかが普通にだるくてよくわからなかったので、assertjを使ってみた。gradleを使っていたら、dependenciesに以下を追加すると利用できる。
testCompile 'org.assertj:assertj-core:3.6.1'
あとは上記のテストで書いたみたいに、assertThatで書いていく。
List<Integer> suffixArray = SuffixArray.make("banana"); assertThat(suffixArray).isEqualTo(Arrays.asList(5, 3, 1, 0, 4, 2));
他にもcontainsとかいろんなメソッドで比較できるので便利。詳しくは以下を参照。
まとめ
今回は全文検索などに利用されるsuffix arrayという構造をJavaで実装してみた。
suffix arrayは辞書順の並びなので、この時点で二分探索を利用して検索をすることもできる。この時の検索のオーダーは検索文字列の長さをm、文字列の長さをnとすると、となる。
また、さらに検索を高速化するには、最長共通接頭辞（LCP, Longest Common Prefix）というものを構築しておくと良いらしい。これを使うとで検索ができるようだった。
ということで、次回はLCPを構築するのをやってみたい。
![プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～](https://m.media-amazon.com/images/I/41bHxtpurqL._SL500_.jpg "プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～")
