Copyright	(c) Edward Kmett 2009-2012
License	BSD-style
Maintainer	ekmett@gmail.com
Stability	experimental
Portability	non-portable (type families)
Safe Haskell	Trustworthy
Language	Haskell98

Data.Compressed.Internal.LZ78

Contents

Lempel-Ziv 78
Encoding
Decoding (reduce)
Recoding
Unsafe (exposes internal structure)

Description

Compression algorithms are all about exploiting redundancy. When applying an expensive Reducer to a redundant source, it may be better to extract the structural redundancy that is present. LZ78 is a compression algorithm that does so, without requiring the dictionary to be populated with all of the possible values of a data type unlike its later refinement LZW, and which has fewer comparison reqirements during encoding than its earlier counterpart LZ77.

Synopsis

data Token a = Token !Int a
data LZ78 a
- = Cons !(Token a) (LZ78 a)
- | Nil
encode :: (Hashable a, Eq a) => [a] -> LZ78 a
encodeOrd :: Ord a => [a] -> LZ78 a
encodeEq :: Eq a => [a] -> LZ78 a
decode :: LZ78 a -> [a]
recode :: (Eq a, Hashable a) => LZ78 a -> LZ78 a
recodeOrd :: Ord a => LZ78 a -> LZ78 a
recodeEq :: Eq a => LZ78 a -> LZ78 a
data Entry i a = Entry !i a
entries :: LZ78 a -> LZ78 (Entry Int a)

Lempel-Ziv 78

data Token a #

Constructors

Token !Int a

Instances

Functor Token #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods fmap :: (a -> b) -> Token a -> Token b # (<$) :: a -> Token b -> Token a #
Foldable Token #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods fold :: Monoid m => Token m -> m # foldMap :: Monoid m => (a -> m) -> Token a -> m # foldr :: (a -> b -> b) -> b -> Token a -> b # foldr' :: (a -> b -> b) -> b -> Token a -> b # foldl :: (b -> a -> b) -> b -> Token a -> b # foldl' :: (b -> a -> b) -> b -> Token a -> b # foldr1 :: (a -> a -> a) -> Token a -> a # foldl1 :: (a -> a -> a) -> Token a -> a # toList :: Token a -> [a] # null :: Token a -> Bool # length :: Token a -> Int # elem :: Eq a => a -> Token a -> Bool # maximum :: Ord a => Token a -> a # minimum :: Ord a => Token a -> a # sum :: Num a => Token a -> a # product :: Num a => Token a -> a #
Traversable Token #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods traverse :: Applicative f => (a -> f b) -> Token a -> f (Token b) # sequenceA :: Applicative f => Token (f a) -> f (Token a) # mapM :: Monad m => (a -> m b) -> Token a -> m (Token b) # sequence :: Monad m => Token (m a) -> m (Token a) #
Comonad Token #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods extract :: Token a -> a # duplicate :: Token a -> Token (Token a) # extend :: (Token a -> b) -> Token a -> Token b #
Extend Token #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods duplicated :: Token a -> Token (Token a) # extended :: (Token a -> b) -> Token a -> Token b #
Eq a => Eq (Token a) #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods (==) :: Token a -> Token a -> Bool # (/=) :: Token a -> Token a -> Bool #
Ord a => Ord (Token a) #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods compare :: Token a -> Token a -> Ordering # (<) :: Token a -> Token a -> Bool # (<=) :: Token a -> Token a -> Bool # (>) :: Token a -> Token a -> Bool # (>=) :: Token a -> Token a -> Bool # max :: Token a -> Token a -> Token a # min :: Token a -> Token a -> Token a #
Hashable a => Hashable (Token a) #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods hashWithSalt :: Int -> Token a -> Int # hash :: Token a -> Int #

data LZ78 a #

An LZ78 compressed Generator.

Constructors

Cons !(Token a) (LZ78 a)
Nil

Instances

Monad LZ78 #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods (>>=) :: LZ78 a -> (a -> LZ78 b) -> LZ78 b # (>>) :: LZ78 a -> LZ78 b -> LZ78 b # return :: a -> LZ78 a # fail :: String -> LZ78 a #
Functor LZ78 #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods fmap :: (a -> b) -> LZ78 a -> LZ78 b # (<$) :: a -> LZ78 b -> LZ78 a #
Applicative LZ78 #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods pure :: a -> LZ78 a # (<>) :: LZ78 (a -> b) -> LZ78 a -> LZ78 b # liftA2 :: (a -> b -> c) -> LZ78 a -> LZ78 b -> LZ78 c # (>) :: LZ78 a -> LZ78 b -> LZ78 b # (<*) :: LZ78 a -> LZ78 b -> LZ78 a #
Foldable LZ78 #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods fold :: Monoid m => LZ78 m -> m # foldMap :: Monoid m => (a -> m) -> LZ78 a -> m # foldr :: (a -> b -> b) -> b -> LZ78 a -> b # foldr' :: (a -> b -> b) -> b -> LZ78 a -> b # foldl :: (b -> a -> b) -> b -> LZ78 a -> b # foldl' :: (b -> a -> b) -> b -> LZ78 a -> b # foldr1 :: (a -> a -> a) -> LZ78 a -> a # foldl1 :: (a -> a -> a) -> LZ78 a -> a # toList :: LZ78 a -> [a] # null :: LZ78 a -> Bool # length :: LZ78 a -> Int # elem :: Eq a => a -> LZ78 a -> Bool # maximum :: Ord a => LZ78 a -> a # minimum :: Ord a => LZ78 a -> a # sum :: Num a => LZ78 a -> a # product :: Num a => LZ78 a -> a #
MonadZip LZ78 #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods mzip :: LZ78 a -> LZ78 b -> LZ78 (a, b) # mzipWith :: (a -> b -> c) -> LZ78 a -> LZ78 b -> LZ78 c # munzip :: LZ78 (a, b) -> (LZ78 a, LZ78 b) #
Zip LZ78 #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods zipWith :: (a -> b -> c) -> LZ78 a -> LZ78 b -> LZ78 c # zip :: LZ78 a -> LZ78 b -> LZ78 (a, b) # zap :: LZ78 (a -> b) -> LZ78 a -> LZ78 b #
Indexable LZ78 #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods index :: LZ78 a -> Key LZ78 -> a #
Lookup LZ78 #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods lookup :: Key LZ78 -> LZ78 a -> Maybe a #
Adjustable LZ78 #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods adjust :: (a -> a) -> Key LZ78 -> LZ78 a -> LZ78 a # replace :: Key LZ78 -> a -> LZ78 a -> LZ78 a #
FoldableWithKey LZ78 #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods toKeyedList :: LZ78 a -> [(Key LZ78, a)] # foldMapWithKey :: Monoid m => (Key LZ78 -> a -> m) -> LZ78 a -> m # foldrWithKey :: (Key LZ78 -> a -> b -> b) -> b -> LZ78 a -> b # foldlWithKey :: (b -> Key LZ78 -> a -> b) -> b -> LZ78 a -> b #
Pointed LZ78 #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods point :: a -> LZ78 a #
Eq a => Eq (LZ78 a) #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods (==) :: LZ78 a -> LZ78 a -> Bool # (/=) :: LZ78 a -> LZ78 a -> Bool #
Ord a => Ord (LZ78 a) #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods compare :: LZ78 a -> LZ78 a -> Ordering # (<) :: LZ78 a -> LZ78 a -> Bool # (<=) :: LZ78 a -> LZ78 a -> Bool # (>) :: LZ78 a -> LZ78 a -> Bool # (>=) :: LZ78 a -> LZ78 a -> Bool # max :: LZ78 a -> LZ78 a -> LZ78 a # min :: LZ78 a -> LZ78 a -> LZ78 a #
(Read a, Hashable a, Eq a) => Read (LZ78 a) #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods readsPrec :: Int -> ReadS (LZ78 a) # readList :: ReadS [LZ78 a] # readPrec :: ReadPrec (LZ78 a) # readListPrec :: ReadPrec [LZ78 a] #
Show a => Show (LZ78 a) #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods showsPrec :: Int -> LZ78 a -> ShowS # show :: LZ78 a -> String # showList :: [LZ78 a] -> ShowS #
Generator (LZ78 a) #
Instance details Defined in Data.Compressed.Internal.LZ78 Associated Types type Elem (LZ78 a) :: * # Methods mapReduce :: (Reducer e m, Monoid m) => (Elem (LZ78 a) -> e) -> LZ78 a -> m # mapTo :: (Reducer e m, Monoid m) => (Elem (LZ78 a) -> e) -> m -> LZ78 a -> m # mapFrom :: (Reducer e m, Monoid m) => (Elem (LZ78 a) -> e) -> LZ78 a -> m -> m #
type Key LZ78 #
Instance details Defined in Data.Compressed.Internal.LZ78 type Key LZ78 = Int
type Elem (LZ78 a) #
Instance details Defined in Data.Compressed.Internal.LZ78 type Elem (LZ78 a) = a

Encoding

encode :: (Hashable a, Eq a) => [a] -> LZ78 a #

O(n) Construct an LZ78-compressed Generator using a HashMap internally.

encodeOrd :: Ord a => [a] -> LZ78 a #

O(n log n) Contruct an LZ78-compressed Generator using a Map internally.

encodeEq :: Eq a => [a] -> LZ78 a #

O(n^2) Contruct an LZ78-compressed Generator using a list internally, requires an instance of Eq, less efficient than encode.

Decoding (reduce)

decode :: LZ78 a -> [a] #

A type-constrained reduce operation

Recoding

recode :: (Eq a, Hashable a) => LZ78 a -> LZ78 a #

O(n). Recompress with Hashable

recodeOrd :: Ord a => LZ78 a -> LZ78 a #

O(n log n). Recompress with Ord

recodeEq :: Eq a => LZ78 a -> LZ78 a #

O(n^2). Recompress with Eq

Unsafe (exposes internal structure)

data Entry i a #

Constructors

Entry !i a

Instances

Functor (Entry i) #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods fmap :: (a -> b) -> Entry i a -> Entry i b # (<$) :: a -> Entry i b -> Entry i a #
Comonad (Entry i) #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods extract :: Entry i a -> a # duplicate :: Entry i a -> Entry i (Entry i a) # extend :: (Entry i a -> b) -> Entry i a -> Entry i b #
Extend (Entry i) #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods duplicated :: Entry i a -> Entry i (Entry i a) # extended :: (Entry i a -> b) -> Entry i a -> Entry i b #
Eq i => Eq (Entry i a) #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods (==) :: Entry i a -> Entry i a -> Bool # (/=) :: Entry i a -> Entry i a -> Bool #
Ord i => Ord (Entry i a) #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods compare :: Entry i a -> Entry i a -> Ordering # (<) :: Entry i a -> Entry i a -> Bool # (<=) :: Entry i a -> Entry i a -> Bool # (>) :: Entry i a -> Entry i a -> Bool # (>=) :: Entry i a -> Entry i a -> Bool # max :: Entry i a -> Entry i a -> Entry i a # min :: Entry i a -> Entry i a -> Entry i a #
(Read i, Read a) => Read (Entry i a) #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods readsPrec :: Int -> ReadS (Entry i a) # readList :: ReadS [Entry i a] # readPrec :: ReadPrec (Entry i a) # readListPrec :: ReadPrec [Entry i a] #
(Show i, Show a) => Show (Entry i a) #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods showsPrec :: Int -> Entry i a -> ShowS # show :: Entry i a -> String # showList :: [Entry i a] -> ShowS #
Hashable i => Hashable (Entry i a) #
Instance details Defined in Data.Compressed.Internal.LZ78 Methods hashWithSalt :: Int -> Entry i a -> Int # hash :: Entry i a -> Int #

entries :: LZ78 a -> LZ78 (Entry Int a) #

exposes internal structure