Edited at

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 の返り値が含まれる記事番号を取得しています。