With the help of a copy of , an unknown file can be compressed as follows: Again, default characters are inserted at the beginning. For each character , the predictor emits its output based on the previous characters. There will be a such that . The estimate of is given by . The code of , the bitstring , is generated by feeding the probability estimates of the predictor into the Arithmetic Coding algorithm (see e.g. [41]). is written into the compressed file.
The information in the compressed file is sufficient for reconstructing the original file. This is done with the ``uncompress'' algorithm, which works as follows: Again, for each character , the predictor (sequentially) emits its output based on the previous characters, where the with were gained sequentially by feeding the approximations of the probabilities into the inverse Arithmetic Coding procedure ( e.g. [41]). The latter is able to correctly decode from . In other words, to correctly decode some character, we first need to decode all previous characters.