Copyright | (c) Matthew Mosior 2022 |
---|---|
License | BSD-style |
Maintainer | mattm.github@gmail.com |
Portability | portable |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
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.
Synopsis
- data Suffix a = Suffix {
- suffixindex :: Int
- suffixstartpos :: Int
- suffix :: Maybe (Seq a)
- type SuffixArray a = Seq (Suffix a)
- type BWT a = Seq (Maybe a)
- type BWTMatrix = Array BN Ix1 String
- saToBWT :: SuffixArray a -> Seq a -> BWT a
- createSuffixArray :: Ord a => Seq a -> SuffixArray a
- sortTB :: (Ord a1, Ord a2) => (a1, a2) -> (a1, a2) -> Ordering
- type BWTSeq a = Seq a
- type STBWTSeq s a = STRef s (BWTSeq a)
- pushSTBWTSeq :: STBWTSeq s a -> a -> ST s ()
- emptySTBWTSeq :: ST s (STBWTSeq s a)
- type STBWTCounter s a = STRef s Int
- updateSTBWTCounter :: STBWTCounter s Int -> Int -> ST s ()
- emptySTBWTCounter :: ST s (STBWTCounter s Int)
- magicInverseBWT :: Seq (Maybe a, Int) -> ST s (BWTSeq a)
- createBWTMatrix :: String -> BWTMatrix
Documentation
Basic suffix data type. Used to describe
the core data inside of the SuffixArray
data type.
Suffix | |
|
Instances
Generic (Suffix a) Source # | |
Read a => Read (Suffix a) Source # | |
Show a => Show (Suffix a) Source # | |
Eq a => Eq (Suffix a) Source # | |
Ord a => Ord (Suffix a) Source # | |
Defined in Data.BWT.Internal | |
type Rep (Suffix a) Source # | |
Defined in Data.BWT.Internal type Rep (Suffix a) = D1 ('MetaData "Suffix" "Data.BWT.Internal" "text-compression-0.1.0.6-8iHiPfKbF8N8A2iiyksdsV" '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 (Maybe (Seq a)))))) |
type SuffixArray a = Seq (Suffix a) Source #
The SuffixArray data type. Uses sequence internally.
type BWTMatrix = Array BN Ix1 String Source #
The BWTMatrix data type. Uses a massiv array internally.
saToBWT :: SuffixArray a -> Seq a -> BWT a Source #
Computes the Burrows-Wheeler Transform (BWT) using the suffix array and the original string (represented as a sequence for performance).
createSuffixArray :: Ord a => Seq a -> SuffixArray a Source #
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 Source #
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 STBWTSeq s a = STRef s (BWTSeq a) Source #
Abstract data type representing a BWTSeq in the (strict) ST monad.
pushSTBWTSeq :: STBWTSeq s a -> a -> ST s () Source #
State function to push BWTString data into stack.
emptySTBWTSeq :: ST s (STBWTSeq s a) Source #
State function to create empty STBWTString type.
type STBWTCounter s a = STRef s Int Source #
Abstract BWTCounter and associated state type.
updateSTBWTCounter :: STBWTCounter s Int -> Int -> ST s () Source #
State function to update BWTCounter.
emptySTBWTCounter :: ST s (STBWTCounter s Int) Source #
State function to create empty STBWTCounter type.
createBWTMatrix :: String -> BWTMatrix Source #
Simple yet efficient implementation of converting a given string into a BWT Matrix (the BWTMatrix type is a massiv array).