Data.BWT

Burrows-Wheeler Transform (BWT)

The two functions that most users will utilize are toBWT and fromBWT. There are auxilary function(s) inside of Data.BWT.Internal.

Data.BWT.Internal also has the function createBWTMatrix, which can be useful as well, although not used by either toBWT or fromBWT.

Documentation

toBWT :: String -> BWT

Takes a String and returns the Burrows-Wheeler Transform (BWT). Implemented via a SuffixArray.

Works with alphanumeric characters (A-Za-z0-9), as well as special characters `~?!@#%^&*()_+<>';:[]{}/|"-., Does NOT work with an input containing the $ character.

Appends the $ character to the input automatically.

fromBWT :: BWT -> String

Takes a BWT data type (please see Data.BWT.Internal) and inverts it back to the original string.

This function utilizes the state monad (strict) in order to implement the Magic Inverse BWT algorithm by backtracking indices starting with the $ character.