HOW TO USE THE PREDICTOR FOR COMPRESSION

We use a standard procedure for predictive coding. With the help of a copy of $P$, an unknown file $f$ can be compressed as follows: Again, $n$ default characters are inserted at the beginning. For each character $c^f_m~(m>n)$, the predictor emits its output $P^f_m$ based on the $n$ previous characters. There will be a $k$ such that $c^f_m = z_k$. The estimate of $P(c^f_m = z_k \mid c^f_{m-n}, \ldots, c^f_{m-1})$ is given by $P^f_m(k)$. The code of $c^f_m$, $code(c^f_m)$, is generated by feeding $P^f_m(k)$ into the Huffman Coding algorithm (see below), or, alternatively, into the Arithmetic Coding algorithm (see below). $code(c^f_m)$ is written into the compressed file. The basic ideas of both coding algorithms are described next.