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 Boxed vectors, Vector
, and Unboxed vectors, Vector
,
provided by the vector.
The internal BWTMatrix
data type relies upon the massiv package.
Synopsis
- data Suffix a = Suffix {
- suffixindex :: Int
- suffixstartpos :: Int
- suffix :: Maybe (Vector a)
- type SuffixArray a = Vector (Suffix a)
- newtype BWT a = BWT (Vector (Maybe a))
- type BWTMatrix = Array BN Ix1 String
- saToBWT :: Unbox a => SuffixArray a -> Vector a -> BWT a
- tailsV :: Unbox a => Vector a -> [Vector a]
- sortVecSA :: Ord a => Vector (Int, a) -> Vector (Int, a)
- sortVecBWT :: Ord a => Vector (a, Int) -> Vector (a, Int)
- createSuffixArray :: (Unbox a, Ord a) => Vector a -> SuffixArray a
- sortTB :: (Ord a1, Ord a2) => (a1, a2) -> (a1, a2) -> Ordering
- type BWTVec a = Vector a
- type STBWTVec s a = STRef s (BWTVec a)
- pushSTBWTVec :: STBWTVec s a -> a -> ST s ()
- emptySTBWTVec :: ST s (STBWTVec s a)
- type STBWTCounter s a = STRef s Int
- updateSTBWTCounter :: STBWTCounter s Int -> Int -> ST s ()
- emptySTBWTCounter :: ST s (STBWTCounter s Int)
- magicInverseBWT :: Vector (Maybe a, Int) -> ST s (BWTVec 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, Unbox a) => Read (Suffix a) Source # | |
(Show a, Unbox a) => Show (Suffix a) Source # | |
(Unbox a, Eq a) => Eq (Suffix a) Source # | |
(Unbox a, 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.8-70lkJCzZpdjEuFzWx0Few9" '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 (Vector a)))))) |
The BWT data type.
Uses Vector
internally.
type BWTMatrix = Array BN Ix1 String Source #
The BWTMatrix data type. Uses a massiv array internally.
saToBWT :: Unbox a => SuffixArray a -> Vector a -> BWT a Source #
Computes the Burrows-Wheeler Transform (BWT) using the suffix array
and the original string (represented as a Vector
for performance).
tailsV :: Unbox a => Vector a -> [Vector a] Source #
Vector
based implementation of the
well-known tails function in the List library.
sortVecSA :: Ord a => Vector (Int, a) -> Vector (Int, a) Source #
Custom sort function for Vector
s
used in the createSuffixArray
function.
sortVecBWT :: Ord a => Vector (a, Int) -> Vector (a, Int) Source #
Custom sort function for Vector
s
used in the fromBWT function.
createSuffixArray :: (Unbox a, Ord a) => Vector 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 STBWTVec s a = STRef s (BWTVec a) Source #
Abstract data type representing a BWTVec
in the (strict) ST monad.
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).