next up previous
Next: WHY NOT USE A Up: HOW TO USE THE Previous: ARITHMETIC CODING

HOW TO ``UNCOMPRESS'' DATA

The information in the compressed file is sufficient to reconstruct the original file without loss of information. This is done with the ``uncompress'' algorithm, which works as follows: Again, for each character $c^f_m~(m>n)$, the predictor (sequentially) emits its output $ P^f_m$ based on the $n$ previous characters, where the $c^f_l$ with $n < l < m$ were gained sequentially by feeding the approximations $P^f_l(k)$ of the probabilities $ P(c^f_l = z_k \mid c^f_{l-n}, \ldots, c^f_{l-1})$ into the inverse Huffman Coding procedure (see e.g. [1]), or, alternatively (depending on which coding procedure was used), into the inverse Arithmetic Coding procedure ( e.g. [7]). Both variants allow for correct decoding of $c^f_l$ from $code(c^f_l)$. With both variants, to correctly decode some character, we first need to decode all previous characters. Both variants are guaranteed to restore the original file from the compressed file.



Subsections

Juergen Schmidhuber 2003-02-25