Goで接尾辞配列を用いた記事検索を実装する

Goの標準ライブラリには珍しいことに接尾辞配列(index/suffixarray)があります。

これを使って，O(log(n))時間での記事検索を実装してみます。

まず，記事を文字列とします。
接尾辞配列のインデックスを作りますが，
suffixarray.New の引数は []byte なので，
すべての記事をひとつのバイト列にしなければなりません。
記事ごとの間にdelimを入れ，記事を区別できるようにします。
これは，sentinel valueでよく，ここでは，utf8.MaxRuneとしましょう。

const delim = utf8.MaxRune

記事 + delim + 記事 + delim + ...
として，一つのバイト列を作ります。
ここで，このバイト列の何番目から記事が入るかを保存するために，Indice []intをつくっておきます。
記事全体と接尾辞配列を納めた型を定義し，インデックス作成メソッドを作ります。

type ArticleIndex struct {
	Articles []string           // 複数記事
	Indice   []int              // バイト列中で，何番目のバイトから記事が始まっているか
	SAIndex  *suffixarray.Index // 接尾辞配列
}

func (ai *ArticleIndex) MakeIndex() {
	var buf bytes.Buffer
	buf.WriteRune(delim)
	for _, t := range ai.Articles {
		buf.WriteString(t)
		buf.WriteRune(delim)
		ai.Indice = append(ai.Indice, buf.Len())
	}
	ai.SAIndex = suffixarray.New(buf.Bytes())
}

これで，インデックスを作成できました。
次に，検索部分を作りましょう。最大 n 記事，s を含む記事の記事番号を返します。

func (ai *ArticleIndex) Lookup(s []byte, n int) []int {
	var ret []int
	result := ai.SAIndex.Lookup(s, n)
	for _, x := range result {
		i := sort.SearchInts(ai.Indice, x)
		if i が ret 中になければ {
			ret = append(ret, i)
		}
	}
	return ret
}

ここで，Indice に対して sort.SearchInts を使って，接尾辞配列の Lookup の返り値が含まれる記事番号を取得しています。