Data.BWT.Internal

WARNING

This module is considered internal.

The Package Versioning Policy does not apply.

The contents of this module may change in any way whatsoever and without any warning between minor versions of this package.

Authors importing this library are expected to track development closely.

All credit goes to the author(s)/maintainer(s) of the containers library for the above warning text.

Description

Various data structures and custom data types to describe the Burrows-Wheeler Transform (BWT) and the Inverse BWT.

The implementation of the BWT relies upon sequence provided by the containers.

The internal BWTMatrix data type relies upon the massiv package.

Documentation

data Suffix

Basic suffix data type. Used to describe the core data inside of the SuffixArray data type.

Constructors

Suffix

Fields

• suffixindex :: Int
• suffixstartpos :: Int
• suffix :: Seq Char

Instances

Generic Suffix

Defined in Data.BWT.Internal

Associated Types

type Rep Suffix :: Type -> Type

Methods

from :: Suffix -> Rep Suffix x

to :: Rep Suffix x -> Suffix

Read Suffix

Defined in Data.BWT.Internal

Methods

readsPrec :: Int -> ReadS Suffix

readList :: ReadS [Suffix]

readPrec :: ReadPrec Suffix

readListPrec :: ReadPrec [Suffix]

Show Suffix

Defined in Data.BWT.Internal

Methods

showsPrec :: Int -> Suffix -> ShowS

show :: Suffix -> String

showList :: [Suffix] -> ShowS

Eq Suffix

Defined in Data.BWT.Internal

Methods

(==) :: Suffix -> Suffix -> Bool

(/=) :: Suffix -> Suffix -> Bool

Ord Suffix

Defined in Data.BWT.Internal

Methods

compare :: Suffix -> Suffix -> Ordering

(<) :: Suffix -> Suffix -> Bool

(<=) :: Suffix -> Suffix -> Bool

(>) :: Suffix -> Suffix -> Bool

(>=) :: Suffix -> Suffix -> Bool

max :: Suffix -> Suffix -> Suffix

min :: Suffix -> Suffix -> Suffix

type Rep Suffix

Defined in Data.BWT.Internal

type Rep Suffix = D1 ('MetaData "Suffix" "Data.BWT.Internal" "text-compression-0.1.0.3-3MpNIRMRQ1O4EHOgYUmLSc" 'False) (C1 ('MetaCons "Suffix" 'PrefixI 'True) (S1 ('MetaSel ('Just "suffixindex") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedStrict) (Rec0 Int) :*: (S1 ('MetaSel ('Just "suffixstartpos") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedStrict) (Rec0 Int) :*: S1 ('MetaSel ('Just "suffix") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedStrict) (Rec0 (Seq Char)))))

type SuffixArray = Seq Suffix

The SuffixArray data type. Uses sequence internally.

type BWT = Seq Char

The BWT data type. Uses sequence internally.

type BWTMatrix = Array BN Ix1 String

The BWTMatrix data type. Uses a massiv array internally.

saToBWT :: SuffixArray -> Seq Char -> BWT

Computes the Burrows-Wheeler Transform (BWT) using the suffix array and the original string (represented as a sequence for performance).

createSuffixArray :: Seq Char -> SuffixArray

Computes the corresponding SuffixArray of a given string. Please see suffix array for more information.

sortTB :: (Ord a1, Ord a2) => (a1, a2) -> (a1, a2) -> Ordering

Hierarchical sorting scheme that compares fst first then snd. Necessary for the setting up the BWT in order to correctly invert it using the Magic algorithm.

type BWTSeq a = Seq Char

Abstract BWTSeq type utilizing a sequence.

type STBWTSeq s a = STRef s (BWTSeq Char)

Abstract data type representing a BWTSeq in the (strict) ST monad.

pushSTBWTSeq :: STBWTSeq s Char -> Char -> ST s ()

State function to push BWTString data into stack.

emptySTBWTSeq :: ST s (STBWTSeq s Char)

State function to create empty STBWTString type.

type STBWTCounter s a = STRef s Int

Abstract BWTCounter and associated state type.

updateSTBWTCounter :: STBWTCounter s Int -> Int -> ST s ()

State function to update BWTCounter.

emptySTBWTCounter :: ST s (STBWTCounter s Int)

State function to create empty STBWTCounter type.

magicInverseBWT :: Seq (Char, Int) -> ST s (BWTSeq Char)

Magic Inverse BWT function.

grabHeadChunks :: Seq (Seq Char) -> (Seq Char, Seq Char)

Easy way to grab the first two elements of a sequence.

createBWTMatrix :: String -> BWTMatrix

Simple yet efficient implementation of converting a given string into a BWT Matrix (the BWTMatrix type is a massiv array).