Safe Haskell | None |
---|---|

Language | Haskell2010 |

Implement DEFLATE (de)compression algorithm

http://www.ietf.org/rfc/rfc1951.txt

TODO: use BufferBuilder instead of Seq Word8!

TODO: the function `putFixedCode`

is currently exported to avoid a compiler
warning. We should implement the whole compression algorithms and export a
"compress" method instead.

# Documentation

makeHuffmanCodes :: (Show b, Show a, Ord a, Ord b, Num b) => [(a, b)] -> [(Code, a)] Source #

Compute Huffman codes from a list of code lengths with given (unchecked) properties.

Deflate algorithm uses Huffman coding with some additional rules: For two symbols a and b: 1) if codelength(a) == codelength(b) then if code(a) < code(b) then a < b else a > b

2) if codelength(a) < codelength(b) then code(a) < code(b)

where: * code(x) is the value of the coding of x * codelength(x) is the length of the coding of x (i.e. the number of bits)

These properties allow the Huffman encoding to be provided with only a sequence of code lengths. A null code length indicates an element that cannot be encoded.

makeBitGetFromCodes :: (Show a, Show b, Ord a, Ord b, Num b) => [(a, b)] -> BitGet a Source #

Create a Huffman code getter from a list of codes

# Internal functions

putFixedCode :: Word -> BitPut () Source #

Put the token code with the fixed Huffman compression