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

Data.BWT

Contents

To BWT functions
From BWT functions

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.

The helper functions for ByteString, bytestringToBWT, bytestringFromWord8BWT, bytestringFromByteStringBWT and Text, textToBWT and textFromBWT should help for common use cases.

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
bytestringToBWT :: ByteString -> BWT Word8
newtype TextBWT = TextBWT (BWT Word8)
textToBWT :: Text -> TextBWT
fromBWT :: Ord a => BWT a -> [a]
bytestringFromWord8BWT :: BWT Word8 -> ByteString
bytestringFromByteStringBWT :: BWT ByteString -> ByteString
textFromBWT :: TextBWT -> Text

To BWT functions

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

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

bytestringToBWT :: ByteString -> BWT Word8 Source #

Helper function for converting a ByteString to a BWT Word8.

newtype TextBWT Source #

A newtype to ensure you only uncompress a BWT created from textToBWT, since [Word8] -> Text is partial.

Constructors

TextBWT (BWT Word8)

Instances

Instances details

Generic TextBWT Source #
Instance details Defined in Data.BWT Associated Types type Rep TextBWT :: Type -> Type # Methods from :: TextBWT -> Rep TextBWT x # to :: Rep TextBWT x -> TextBWT #
Read TextBWT Source #
Instance details Defined in Data.BWT Methods readsPrec :: Int -> ReadS TextBWT # readList :: ReadS [TextBWT] # readPrec :: ReadPrec TextBWT # readListPrec :: ReadPrec [TextBWT] #
Show TextBWT Source #
Instance details Defined in Data.BWT Methods showsPrec :: Int -> TextBWT -> ShowS # show :: TextBWT -> String # showList :: [TextBWT] -> ShowS #
Eq TextBWT Source #
Instance details Defined in Data.BWT Methods (==) :: TextBWT -> TextBWT -> Bool # (/=) :: TextBWT -> TextBWT -> Bool #
Ord TextBWT Source #
Instance details Defined in Data.BWT Methods compare :: TextBWT -> TextBWT -> Ordering # (<) :: TextBWT -> TextBWT -> Bool # (<=) :: TextBWT -> TextBWT -> Bool # (>) :: TextBWT -> TextBWT -> Bool # (>=) :: TextBWT -> TextBWT -> Bool # max :: TextBWT -> TextBWT -> TextBWT # min :: TextBWT -> TextBWT -> TextBWT #
type Rep TextBWT Source #
Instance details Defined in Data.BWT type Rep TextBWT = D1 ('MetaData "TextBWT" "Data.BWT" "text-compression-0.1.0.16-EGmAxK0JgwH3t6C21JNSfQ" 'True) (C1 ('MetaCons "TextBWT" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (BWT Word8))))

textToBWT :: Text -> TextBWT Source #

Helper function for converting Text to a TextBWT.

From BWT functions

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.

bytestringFromWord8BWT :: BWT Word8 -> ByteString Source #

Helper function for converting a BWT of Word8s to a ByteString.

bytestringFromByteStringBWT :: BWT ByteString -> ByteString Source #

Helper function for converting a BWT ByteStrings to a ByteString.

textFromBWT :: TextBWT -> Text Source #

Helper function for converting TextBWT to a Text