Copyright | (c) Edward Kmett 2009-2012 |
---|---|

License | BSD-style |

Maintainer | ekmett@gmail.com |

Stability | experimental |

Portability | non-portable (type families) |

Safe Haskell | Trustworthy |

Language | Haskell98 |

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`

.

Monad LZ78 Source # | |

Functor LZ78 Source # | |

Applicative LZ78 Source # | |

Foldable LZ78 Source # | |

MonadZip LZ78 Source # | |

Zip LZ78 Source # | |

Indexable LZ78 Source # | |

Lookup LZ78 Source # | |

Adjustable LZ78 Source # | |

FoldableWithKey LZ78 Source # | |

Pointed LZ78 Source # | |

Eq a => Eq (LZ78 a) Source # | |

Ord a => Ord (LZ78 a) Source # | |

(Read a, Hashable a, Eq a) => Read (LZ78 a) Source # | |

Show a => Show (LZ78 a) Source # | |

Generator (LZ78 a) Source # | |

type Key LZ78 Source # | |

type Elem (LZ78 a) Source # | |

# Encoding

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

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

using a `HashMap`

internally.

encodeOrd :: Ord a => [a] -> LZ78 a Source #

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

using a `Map`

internally.

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

*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)

Entry !i a |