haskus-system-0.6.0.0: Haskus system programming framework

Safe HaskellNone
LanguageHaskell2010

Haskus.Format.Compression.Algorithms.Huffman

Contents

Description

Implement Huffman coding

Synopsis

Huffman Tree

data Tree a Source #

A binary tree

Constructors

Node (Tree a) (Tree a) 
Leaf a 
Empty 

Instances

Functor Tree Source # 

Methods

fmap :: (a -> b) -> Tree a -> Tree b #

(<$) :: a -> Tree b -> Tree a #

Eq a => Eq (Tree a) Source # 

Methods

(==) :: Tree a -> Tree a -> Bool #

(/=) :: Tree a -> Tree a -> Bool #

Show a => Show (Tree a) Source # 

Methods

showsPrec :: Int -> Tree a -> ShowS #

show :: Tree a -> String #

showList :: [Tree a] -> ShowS #

computeHuffmanTreeFromFoldable :: (Foldable m, Ord a) => m a -> Tree a Source #

Create a Huffman tree

computeHuffmanTreeFromPriorityQueue :: PriorityQueue a -> Tree a Source #

Build the Huffman tree

computeHuffmanTreeFromCodes :: Show a => [(Code, a)] -> Tree a Source #

Build a tree from a set of codes

Coding table

data Encoder a Source #

Huffman tree encoder

Constructors

Encoder 

Fields

inverseEncoder :: Encoder a -> Encoder a Source #

Inverse left and right in the given encoder

stringEncoder :: Encoder String Source #

String encoder ("0" and "1" chars)

textEncoder :: Encoder Text Source #

Text encoder ("0" and "1" chars)

binaryEncoder :: Encoder Code Source #

Binary encoder

buildCodingTable :: Ord a => Encoder b -> Tree a -> Map a b Source #

Build a coding table for a Huffman tree

Huffman Code

data Code Source #

Huffman binary code

Length of the code is limited to 64

Constructors

Code 

Fields

Instances

Eq Code Source # 

Methods

(==) :: Code -> Code -> Bool #

(/=) :: Code -> Code -> Bool #

Ord Code Source # 

Methods

compare :: Code -> Code -> Ordering #

(<) :: Code -> Code -> Bool #

(<=) :: Code -> Code -> Bool #

(>) :: Code -> Code -> Bool #

(>=) :: Code -> Code -> Bool #

max :: Code -> Code -> Code #

min :: Code -> Code -> Code #

Show Code Source # 

Methods

showsPrec :: Int -> Code -> ShowS #

show :: Code -> String #

showList :: [Code] -> ShowS #

emptyCode :: Code Source #

Empty code

codeAdd :: Word64 -> Code -> Code Source #

Add a value to a code

codeShiftL :: Word -> Code -> Code Source #

Increase code length

codeShiftR :: Word -> Code -> Code Source #

Decrease code length

codeTestBit :: Code -> Int -> Bool Source #

Test a bit in the code (no check if out of bounds)

codeReverseBits :: Code -> Code Source #

Reverse bits in a code

codeAppend :: Code -> Code -> Code Source #

Append two codes into a single one

Encoding

makeBitGet :: Bool -> Tree a -> BitGet (Maybe a) Source #

Create a binary parser that reads a single encoded element. Use the given Tree to decode it.

You can specify which tree side (left or right) is 0

toBinary :: (Foldable m, Ord a) => Map a Code -> m a -> Buffer Source #

Convert a sequence into a compressed binary

fromBinary :: Bool -> Tree a -> Buffer -> [a] Source #

Convert a binary sequence into a token sequence

fromBinaryLen :: Bool -> Tree a -> Int -> Buffer -> [a] Source #

Convert a binary sequence into a delimited token sequence

Helpers

computePriorityTable :: (Foldable m, Ord a) => m a -> PriorityTable a Source #

Compute a priority table (i.e. number of occurences for each element)

computePriorityQueue :: PriorityTable a -> PriorityQueue a Source #

Build min priority queue (priority is number of occurences)