version: 1.10

package suffixarray

import "index/suffixarray"


Package suffixarray implements substring search in logarithmic time using an
in-memory suffix array.

Example use:

  1. // create index for some data
  2. index := suffixarray.New(data)
  3. // lookup byte slice s
  4. offsets1 := index.Lookup(s, -1) // the list of all indices where s occurs in data
  5. offsets2 := index.Lookup(s, 3) // the list of at most 3 indices where s occurs in data



Package files

qsufsort.go suffixarray.go

type Index

  1. type Index struct {
  2. // contains filtered or unexported fields
  3. }

Index implements a suffix array for fast substring search.

func New

  1. func New(data []byte) *Index

New creates a new Index for data. Index creation time is O(N*log(N)) for N =

func (*Index) Bytes

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

Bytes returns the data over which the index was created. It must not be

func (*Index) FindAllIndex

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

FindAllIndex returns a sorted list of non-overlapping matches of the regular
expression r, where a match is a pair of indices specifying the matched slice of
x.Bytes(). If n < 0, all matches are returned in successive order. Otherwise, at
most n matches are returned and they may not be successive. The result is nil if
there are no matches, or if n == 0.

func (*Index) Lookup

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

Lookup returns an unsorted list of at most n indices where the byte string s
occurs in the indexed data. If n < 0, all occurrences are returned. The result
is nil if s is empty, s is not found, or n == 0. Lookup time is O(log(N)*len(s)

  • len(result)) where N is the size of the indexed data.


  1. index := suffixarray.New([]byte("banana"))
  2. offsets := index.Lookup([]byte("ana"), -1)
  3. for _, off := range offsets {
  4. fmt.Println(off)
  5. }
  6. // Unordered output:
  7. // 1
  8. // 3

func (*Index) Read

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

Read reads the index from r into x; x must not be nil.

func (*Index) Write

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

Write writes the index x to w.