読者です 読者をやめる 読者になる 読者になる

$shibayu36->blog;

プログラミングの話や自分の考えを色々と書いています。

suffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6)

tech algorithm

文字列アルゴリズムを学んでいると、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ステップで実装できる。この考え方だと、まずソートが{\mathcal{O} ( n \log n ) }の計算量である。またソートのための文字列比較がn文字分ありえるのでその計算量が{\mathcal{O} ( n ) }である。これらから、全体の計算量は{\mathcal{O} ( n^2 \log 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とすると、{\mathcal{O} ( m \log n ) }となる。

また、さらに検索を高速化するには、最長共通接頭辞(LCP, Longest Common Prefix)というものを構築しておくと良いらしい。これを使うと{\mathcal{O} ( m + \log n ) }で検索ができるようだった。

ということで、次回はLCPを構築するのをやってみたい。