fmindex

README

FM-index

A FM-index using Wavelet Tree's to store the Burrows–Wheeler transform. A Prefix Tree using BitVector and a Sampled Suffix Array, for storing the offsets.

The Prefix Tree can be shared across FM-indexs to reduce storage needs.

index, err := NewFMIndex("The quick brown fox jumps over the lazy dog", WithCompression(2))

Operation

Count

count := index.Count("jumps")
fmt.Println(count) // 1

Locate

matches := index.Locate("jumps")
fmt.Println(matches) // []int{20}

Extract

text := index.Extract(matches[0], 5)
fmt.Println(text) // "jumps"

Documentation

Index

• type FMIndex
  • func NewFMIndex(text string, opts ...FMIndexOption) (*FMIndex, error)
  • func (s *FMIndex) CaseInsensitive() bool
  • func (s *FMIndex) Compression() int
  • func (s *FMIndex) Count(pattern string) int
  • func (s *FMIndex) Extract(offset, length int) string
  • func (s *FMIndex) Locate(pattern string) []int
  • func (s *FMIndex) PrefixTree() *prefixtree.Prefix
• type FMIndexOption
  • func WithCaseInsensitive(caseinsensitive bool) FMIndexOption
  • func WithCompression(compression int) FMIndexOption
  • func WithPrefixTree(prefix prefixtree.Prefix) FMIndexOption

Types

type FMIndex

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

func NewFMIndex

func NewFMIndex(text string, opts ...FMIndexOption) (*FMIndex, error)

func (*FMIndex) CaseInsensitive

func (s *FMIndex) CaseInsensitive() bool

func (*FMIndex) Compression

func (s *FMIndex) Compression() int

func (*FMIndex) Count

func (s *FMIndex) Count(pattern string) int

func (*FMIndex) Extract

func (s *FMIndex) Extract(offset, length int) string

func (*FMIndex) Locate

func (s *FMIndex) Locate(pattern string) []int

func (*FMIndex) PrefixTree

func (s *FMIndex) PrefixTree() *prefixtree.Prefix

type FMIndexOption

type FMIndexOption func(f *FMIndex)

func WithCaseInsensitive

func WithCaseInsensitive(caseinsensitive bool) FMIndexOption

func WithCompression

func WithCompression(compression int) FMIndexOption

func WithPrefixTree

func WithPrefixTree(prefix prefixtree.Prefix) FMIndexOption