monoids-0.1.31: Monoids, specialized containers and a general map/reduce framework Source code Contents Index

Data.Generator.Compressive.LZ78 Portability portable Stability experimental Maintainer ekmett@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.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.Generator

Lempel-Ziv 78

data LZ78 a Source

Instances Functor LZ78 Foldable LZ78 Eq a => Eq (LZ78 a) Ord a => Ord (LZ78 a) Show a => Show (LZ78 a) Generator (LZ78 a)

Decoding

decode :: LZ78 a -> [a] Source

a type-constrained reduce operation

Encoding

encode :: Ord a => [a] -> LZ78 a Source

contruct an LZ78-compressed Generator using a Map internally, requires an instance of Ord.

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

contruct an LZ78-compressed Generator using a list internally, requires an instance of Eq.

QuickCheck Properties

prop_decode_encode :: Ord a => [a] -> Bool Source

QuickCheck property: decode . encode = id

prop_decode_encodeEq :: Eq a => [a] -> Bool Source

QuickCheck property: decode . encodeEq = id

Produced by Haddock version 2.4.2