Copyright	(c) Matthew Mosior 2022
License	BSD-style
Maintainer	mattm.github@gmail.com
Portability	portable
Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.BWT

Description

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.

Synopsis

toBWT :: Ord a => [a] -> BWT a
fromBWT :: Ord a => BWT a -> [a]

Documentation

toBWT :: Ord a => [a] -> BWT a Source #

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

fromBWT :: Ord a => BWT a -> [a] Source #

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 (Nothing,_) entry.