import "index/suffixarray"

メモリ上で接尾辞配列(suffix array)を使い、対数時間内で部分文字列検索を行います。

使用例:

// データのインデックスを作成
index := suffixarray.New(data)

// バイトスライスsを検索
offsets1 := index.Lookup(s, -1) // data内で見つかったsの全インデックス
offsets2 := index.Lookup(s, 3)  // data内で見つかったsのインデックス、最大3個

パッケージファイル

suffixarray.go

Index型

Indexは、高速部分文字列検索用の接尾辞配列を実装しています。

type Index struct {
    // contains unexported fields
}

New関数

func New(data []byte) *Index

Newは、dataのインデックスを新たに作成します。Indexの作成時間は、N = len(data)として、ほぼO(N*log(N))です。

(*Index) Lookup関数

func (x *Index) Lookup(s []byte, n int) []int

Lookupは、インデックス付られたデータ内で、バイト文字列sが現れた位置の最大n個のインデックスから成る、ソートされていないリストを返します。n < 0のとき、該当するすべてのインデックスが返されます。sが空であるか、sが見つからないか、n == 0ときは、nilが返されます。検索時間は、インデックス付られたデータのサイズをNとして、O((log(N) + len(result))*len(s))です。

バグ

かなり長く(仮に100000個)、同一バイトが連続している巨大なデータ(10MB)に対するインデックスの作成時間は、とても遅いです。