sais

Documentation

Index

• func MakeSuffixArray(str []byte, keyBound int) []uint32
• func MakeSuffixArrayInt(str []uint32, keyBound int) []uint32
• func MakeSuffixArrayIntInto(str []uint32, keyBound int, sa []uint32) []uint32
• func MakeSuffixArraySourceInto[S Uint32Source](str S, keyBound int, sa []uint32) []uint32
• func MakeSuffixArraySourceIntoWithWorkspace[S Uint32Source](str S, keyBound int, sa []uint32, workspace *Workspace) []uint32
• func SuffixLowerBound(sa []uint32, str1 []byte, query []byte) int
• func SuffixLowerBoundLazy(sa []uint32, oldProj []uint32, q QueryAt, queryLo, queryEnd int) int
• func SuffixLowerBoundSource[H, Q Uint32Source](sa []uint32, old H, query Q, queryLo, queryEnd int) int
• func SuffixLowerBoundUint32(sa []uint32, oldProj []uint32, newProj []uint32, dstOffset int) int
• type ProjectionSource
  • func NewProjectionSource(image []byte, refStart, refCover []uint64, refRank, refProj []uint32) *ProjectionSource
  • func (s *ProjectionSource) QueryAt(i int) uint32
  • func (s *ProjectionSource) Size() int
• type QueryAt
• type Uint32Source
• type Workspace

Functions

func MakeSuffixArray

func MakeSuffixArray(str []byte, keyBound int) []uint32

MakeSuffixArray computes the suffix array for input byte slice str, where characters are in range [0, keyBound).

func MakeSuffixArrayInt

func MakeSuffixArrayInt(str []uint32, keyBound int) []uint32

MakeSuffixArrayInt computes the suffix array for a slice of uint32 tokens.

func MakeSuffixArrayIntInto

func MakeSuffixArrayIntInto(str []uint32, keyBound int, sa []uint32) []uint32

MakeSuffixArrayIntInto is MakeSuffixArrayInt but writes into sa when it has enough capacity, avoiding a fresh len(str)*4 byte allocation. sa's contents are fully overwritten. Callers that reuse a buffer across calls save a transient peak of one whole suffix array.

func MakeSuffixArraySourceInto

func MakeSuffixArraySourceInto[S Uint32Source](str S, keyBound int, sa []uint32) []uint32

MakeSuffixArraySourceInto computes the suffix array of a random-access source. It reuses sa when possible and never materializes the source.

func MakeSuffixArraySourceIntoWithWorkspace

func MakeSuffixArraySourceIntoWithWorkspace[S Uint32Source](str S, keyBound int, sa []uint32, workspace *Workspace) []uint32

MakeSuffixArraySourceIntoWithWorkspace is MakeSuffixArraySourceInto with reusable temporary storage. The returned suffix array never aliases the workspace.

func SuffixLowerBound

func SuffixLowerBound(sa []uint32, str1 []byte, query []byte) int

SuffixLowerBound performs binary search in suffix array sa of str1 for target query.

func SuffixLowerBoundLazy

func SuffixLowerBoundLazy(sa []uint32, oldProj []uint32, q QueryAt, queryLo, queryEnd int) int

SuffixLowerBoundLazy is SuffixLowerBoundUint32 with the query drawn lazily from q over [queryLo, queryEnd). The haystack oldProj stays materialized, since it is also the suffix-sorted string; only the query is computed on demand. Comparisons stop at the first mismatch, so the number of QueryAt calls is small relative to a full projection array.

func SuffixLowerBoundSource

func SuffixLowerBoundSource[H, Q Uint32Source](sa []uint32, old H, query Q, queryLo, queryEnd int) int

SuffixLowerBoundSource finds the lower bound of query[queryLo:queryEnd] in the suffix array of old. Both strings remain in their compact source form.

func SuffixLowerBoundUint32

func SuffixLowerBoundUint32(sa []uint32, oldProj []uint32, newProj []uint32, dstOffset int) int

SuffixLowerBoundUint32 performs binary search in suffix array sa of oldProj for newProj[dstOffset:].

Types

type ProjectionSource

type ProjectionSource struct {
	// contains filtered or unexported fields
}

ProjectionSource is the compact, random-access representation used by an executable-aware suffix sort. Raw bytes stay in image; only references need the auxiliary bitsets, rank table, and projected values.

func NewProjectionSource

func NewProjectionSource(image []byte, refStart, refCover []uint64, refRank, refProj []uint32) *ProjectionSource

func (*ProjectionSource) QueryAt

func (s *ProjectionSource) QueryAt(i int) uint32

func (*ProjectionSource) Size

func (s *ProjectionSource) Size() int

type QueryAt

type QueryAt interface {
	QueryAt(i int) uint32
}

QueryAt supplies query characters by absolute position, letting SuffixLowerBoundLazy run without a materialized query string.

type Uint32Source

type Uint32Source interface {
	Size() int
	QueryAt(i int) uint32
}

Uint32Source is a random-access string of uint32 symbols. Keeping the source abstract lets callers suffix-sort compact or computed views without first materializing four bytes per input symbol.

type Workspace

type Workspace struct {
	// contains filtered or unexported fields
}

Workspace retains SA-IS temporary storage across calls. A Workspace is not safe for concurrent use; callers should keep one per active suffix sort.