Portability | non-portable (type families) |
---|---|

Stability | experimental |

Maintainer | ekmett@gmail.com |

Safe Haskell | Safe-Inferred |

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.

# Lempel-Ziv 78

An LZ78 compressed `Generator`

.

# Encoding

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

*O(n)* Construct an LZ78-compressed `Generator`

using a `HashMap`

internally.

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

*O(n log n)* Contruct an LZ78-compressed `Generator`

using a `Map`

internally.

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

*O(n^2)* Contruct an LZ78-compressed `Generator`

using a list internally, requires an instance of Eq,
less efficient than encode.