...

パッケージ suffixarray

import "index/suffixarray"
概要
目次

概要 ▾

suffixarray パッケージは,インメモリの接尾辞配列を使って,対数時間の部分文字列検索を実装します。

使用例:

// あるデータの索引を作成する
index := suffixarray.New(data)

// バイトスライス s を検索する
offsets1 := index.Lookup(s, -1) // データ中に s が出現するすべてのインデックスのリスト
offsets2 := index.Lookup(s, 3)  // データ中に s が出現する最大 3 つのインデックスのリスト

type Index

Index は,速い部分文字列検索である接尾辞配列を実装します。

type Index struct {
    // エクスポートされていないフィールドがあります
}

func New

func New(data []byte) *Index

New は,データに対して新たな Index を作成します。 Index の作成時間は N = len(data) として, O(N) です。

func (*Index) Bytes

func (x *Index) Bytes() []byte

Bytes は,索引が作成された元となったデータを返します。 このデータは修正してはいけません。

func (*Index) FindAllIndex

func (x *Index) FindAllIndex(r *regexp.Regexp, n int) (result [][]int)

FindAllIndex は,正規表現 r に重ならずにマッチするソートされたマッチリストを返します。 マッチとは,x.Bytes() のスライスにマッチしたインデックスのペアを意味します。 n < 0 の場合,順に並んだすべてのマッチが返ります。 それ以外の場合,最大 n マッチが返り,それらは 順に並んではいないかもしれません。 n == 0 の場合,あるいはマッチがない場合,結果は nil となります。

func (*Index) Lookup

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

Lookup は,データ中に出現するバイト文字列 s の最大 n 個のインデックス(ソートはされていない)を返します。 n < 0 の場合,すべての出現箇所を返します。 s が空文字の場合,s が見つからなかった場合,そして n == 0 の場合は nil が返ります。 検索時間は,N をデータサイズとして, O(log(N)*len(s) + len(result)) です。

コード:

index := suffixarray.New([]byte("banana"))
offsets := index.Lookup([]byte("ana"), -1)
for _, off := range offsets {
    fmt.Println(off)
}

出力:

1
3

func (*Index) Read

func (x *Index) Read(r io.Reader) error

Read は,r から索引(index)を読み込んで x に設定します。x は nil であってはなりません。

func (*Index) Write

func (x *Index) Write(w io.Writer) error

Write は,索引(index) x を w に書き込みます。