monoids-0.1.20: Monoids, specialized containers and a general map/reduce frameworkSource codeContentsIndex
Data.Monoid.Generator.LZ78
Portabilityportable
Stabilityexperimental
Maintainerekmett@gmail.com
Contents
Lempel-Ziv 78
Decoding
Encoding
QuickCheck Properties
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. Since we aren't storing these as a bitstream the LZSS refinement of only encoding pointers once you cross the break-even point is a net loss.
Synopsis
module Data.Monoid.Generator
data LZ78 a
decode :: LZ78 a -> [a]
encode :: Ord a => [a] -> LZ78 a
encodeEq :: Eq a => [a] -> LZ78 a
prop_decode_encode :: Ord a => [a] -> Bool
prop_decode_encodeEq :: Eq a => [a] -> Bool
Documentation
module Data.Monoid.Generator
Lempel-Ziv 78
data LZ78 a Source
show/hide Instances
Decoding
decode :: LZ78 a -> [a]Source
a type-constrained reduce operation
Encoding
encode :: Ord a => [a] -> LZ78 aSource
contruct an LZ78-compressed Generator using a Map internally, requires an instance of Ord.
encodeEq :: Eq a => [a] -> LZ78 aSource
contruct an LZ78-compressed Generator using a list internally, requires an instance of Eq.
QuickCheck Properties
prop_decode_encode :: Ord a => [a] -> BoolSource
QuickCheck property: decode . encode = id
prop_decode_encodeEq :: Eq a => [a] -> BoolSource
QuickCheck property: decode . encodeEq = id
Produced by Haddock version 2.4.1