bwt

README

Implements FM-Index (https://en.wikipedia.org/wiki/FM-index), full-text substring index based on the Burrows-Wheeler transform.

GoDoc

Documentation

Overview

Implements FM-Index (https://en.wikipedia.org/wiki/FM-index), full-text substring index based on the Burrows-Wheeler transform. One should use "index/suffixarray" pkg

Index

• func BWT(data interface{}, maxDepth int) (bwt []rune, suffixArray []int)
• func ReverseRunes(data interface{}) (res []rune)
• type Index
  • func New(data interface{}, maxDepth int) *Index
  • func (self *Index) Lookup(data interface{}) (result []int)
  • func (self *Index) LookupMismatches(data interface{}, threshold int) (result []int)
  • func (self *Index) Set(BWTLastCol interface{})
• type RuneSlice
  • func (s RuneSlice) Len() int
  • func (s RuneSlice) Less(i, j int) bool
  • func (s RuneSlice) Swap(i, j int)

Functions

func BWT

func BWT(data interface{}, maxDepth int) (bwt []rune, suffixArray []int)

Naive string matrix sorting (via priority queue) Uses U+0003(\u0003) End-of-text (ETX) character to indicate text end and separate rotations maxDepth < 1 will sort full text, otherwise prefixes are sorted

func ReverseRunes

func ReverseRunes(data interface{}) (res []rune)

Works with string, []byte, []rune

Types

type Index

type Index struct {
	SuffixArr              []int
	LastCol                []rune
	SymbolsOccurCountByPos map[rune][]int
	FirstOccurPos          map[rune]int
}

BWT FM-index

func New

func New(data interface{}, maxDepth int) *Index

func (*Index) Lookup

func (self *Index) Lookup(data interface{}) (result []int)

Can't find deletions or insertions, only substitution Works with string, []byte, []rune

func (*Index) LookupMismatches

func (self *Index) LookupMismatches(data interface{}, threshold int) (result []int)

When threshold < 1 will reuse Index.Lookup method.

func (*Index) Set

func (self *Index) Set(BWTLastCol interface{})

Works with string, []byte, []rune Calculates SymbolsOccurCountByPos & FirstOccurPos

type RuneSlice

type RuneSlice []rune

func (RuneSlice) Len

func (s RuneSlice) Len() int

func (RuneSlice) Less

func (s RuneSlice) Less(i, j int) bool

func (RuneSlice) Swap

func (s RuneSlice) Swap(i, j int)