wt

README

WT

wt is a basic implementation of wavelet trees.

It uses a standard binary tree shape with the bitvector at each node compressed with rrr.

TODO

• Extend to support larger alphabets?

References

• Gonzalo Navarro: Wavelet trees for all

Documentation

Index

• type WT
  • func New(s []byte) (*WT, error)
  • func NewFromSerialized(buf []byte) (wt *WT, wtBytes int, err error)
  • func (w *WT) Access(i uint64) byte
  • func (w *WT) BitmapSize() int
  • func (w *WT) InverseSelect(i uint64) (c byte, rank uint64)
  • func (w *WT) Rank(c byte, i uint64) uint64
  • func (w *WT) WriteTo(writer io.Writer) (err error)

Types

type WT

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

WT is a static wavelet tree

func New

func New(s []byte) (*WT, error)

New builds a wavelet tree representation of the sequence s

func NewFromSerialized

func NewFromSerialized(buf []byte) (wt *WT, wtBytes int, err error)

NewFromSerialized returns a new wavelet tree for the serialized representation

func (*WT) Access

func (w *WT) Access(i uint64) byte

Access returns the ith byte in the sequence

func (*WT) BitmapSize

func (w *WT) BitmapSize() int

BitmapSize is the size of the compressed bitmap

func (*WT) InverseSelect

func (w *WT) InverseSelect(i uint64) (c byte, rank uint64)

InverseSelect returns the symbol and rank of the symbol at position i

func (*WT) Rank

func (w *WT) Rank(c byte, i uint64) uint64

Rank returns the rank of the symbole c at position i

func (*WT) WriteTo

func (w *WT) WriteTo(writer io.Writer) (err error)

WriteTo writes a serialized version of the wavelet tree to writer