bwt

README

bwt

Burrows-Wheeler Transform and FM-index in golang

Install

This package is "go-gettable", just:

go get -u github.com/shenwei356/bwt

Licence

Copyright (c) 2015-2021, Wei Shen (shenwei356@gmail.com)

MIT License

Documentation

Index

• Variables
• func FromSuffixArray(s []byte, sa []int, es byte) ([]byte, error)
• func InverseTransform(t []byte, es byte) []byte
• func SuffixArray(s []byte) []int
• func Transform(s []byte, es byte) ([]byte, error)
• type SliceOfByteSlice
  • func (s SliceOfByteSlice) Len() int
  • func (s SliceOfByteSlice) Less(i, j int) bool
  • func (s SliceOfByteSlice) Swap(i, j int)

Variables

var CheckEndSymbol = true

CheckEndSymbol is a global variable for checking end symbol before Burrows–Wheeler transform

var ErrEmptySeq = errors.New("bwt: empty sequence")

ErrEmptySeq means a empty sequence is given

var ErrEndSymbolExisted = errors.New("bwt: end-symbol existed in string")

ErrEndSymbolExisted means you should choose another EndSymbol

var ErrInvalidSuffixArray = errors.New("bwt: invalid suffix array")

ErrInvalidSuffixArray means length of sa is not equal to 1+len(s)

Functions

func FromSuffixArray

func FromSuffixArray(s []byte, sa []int, es byte) ([]byte, error)

FromSuffixArray compute BWT from sa

func InverseTransform

func InverseTransform(t []byte, es byte) []byte

InverseTransform reverses the bwt to original byte slice. Not optimized yet.

func SuffixArray

func SuffixArray(s []byte) []int

SuffixArray returns the suffix array of s. This function is the performance bottleneck of bwt and bwt/fmi package, with O(nlogn).

func Transform

func Transform(s []byte, es byte) ([]byte, error)

Transform returns Burrows–Wheeler transform of a byte slice. See https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform

Types

type SliceOfByteSlice

type SliceOfByteSlice [][]byte

SliceOfByteSlice is [][]byte

func (SliceOfByteSlice) Len

func (s SliceOfByteSlice) Len() int

func (SliceOfByteSlice) Less

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

func (SliceOfByteSlice) Swap

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