| Portability | non-portable (type families) |
|---|---|
| Stability | experimental |
| Maintainer | ekmett@gmail.com |
| Safe Haskell | Trustworthy |
Data.Compressed.Internal.LZ78
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.
- data Token a = Token !Int a
- data LZ78 a
- encode :: (Hashable a, Eq a) => [a] -> LZ78 a
- encodeOrd :: Ord a => [a] -> LZ78 a
- encodeEq :: Eq a => [a] -> LZ78 a
- decode :: LZ78 a -> [a]
- recode :: (Eq a, Hashable a) => LZ78 a -> LZ78 a
- recodeOrd :: Ord a => LZ78 a -> LZ78 a
- recodeEq :: Eq a => LZ78 a -> LZ78 a
- data Entry i a = Entry !i a
- entries :: LZ78 a -> LZ78 (Entry Int a)
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.
Decoding (reduce)
Recoding
Unsafe (exposes internal structure)
Constructors
| Entry !i a |