sa

README

---

BWT construction by inducing SA

var text []byte
// fill data in buffer text
...

// transform text to BWT, cnt is length of original text
cnt, bwt, _ := BWT(text)

Please note, this implementation is different from others in following:

1. sentinel starts from the beginning of the text, ie, LMS is actually RMS.
2. only supports UTF-8 encoded text input
3. Multi strings use byte value (1) as divider

References

This implementation has referenced the following papers and code

• Inducing enhanced suffix arrays for string collections F. A. Louza, S. Gog and G. P. Telles
• Two Efficient Algorithms for Linear Time Suffix Array Construction Ge Nong, Sen Zhang, Wai Hong Chan
• sais-lite Yuta Mori

Documentation

Index

• type Aux
  • func BWT(t []byte) (int, []byte, *Aux)

Types

type Aux

type Aux struct {
	// Len length
	Len uint

	// Eob End of Bucket
	Eob [][]uint

	// Dist distribution
	Dist []uint

	// Hist histogram
	Hist []uint

	// dictionary, [0] -> 0, [1] -> 1, [2] -> can be any char
	Dict []byte
}

Aux Auxiliary for merge

func BWT

func BWT(t []byte) (int, []byte, *Aux)

BWT transforms t into BWT, returns the length of BWT, BWT and auxiliary data structure can be used to merge BWTs