## 2 Compression, Entropy and Dictionaries  
Data and information today are digital. We need data compression to deal with digital data: without compression we cannot store and/or transmit the huge amount of data we treat every day. The theoretical background of data compression techniques is strong and well established. It dates back to the seminal work of [PERSON] (see [1]). In the late 1940s, he gave a formal definition of the notion of information content or randomness of a source, which he called entropy. This theoretical background gives precise limits on the performance of a compression algorithm. Any process that generates information can be viewed as a source that emits a sequence of symbols from a finite alphabet. The source output can be seen as a sequence of words: _i.e._, finite length sequences of [PERSON] symbols. From the practical point of view to divide the source outputs into words might involve a semantic analysis that depends on the source and that it is possible only if the output of the source is interpreted in a determinate context. For example, a word of a source that emits English sentences can be a sequence of one or more common English words, including blanks, punctuation marks, _etc._ If we consider a first-order source S, in which successive symbols are statistically independent, [PERSON] and [PERSON] in [1] showed that, given the set of probabilities P = {p\({}_{1}\), p\({}_{2}\),..., p\({}_{n}\)} for the source symbols, the optimal expected number of code bits is:  
\[\sum_{{}_{i=1}}^{n}\ -p_{i}\ log_{2}\ (p_{i}\ )\]  
a quantity which they called the Entropy of the source S, usually denoted by H(S). Conditional entropy H(S\({}_{1}\)|S\({}_{2}\)) is the natural analogue of the entropy H(S) but it is based on the conditional probability. It can be shown that: H(S\({}_{1}\)|S\({}_{2}\)) \(\leq\) H(S\({}_{1}\)). Entropy is a measure of uncertainty about an event: it has a zero value if and only if there is absolute certainty and it is maximal when all the events are equiprobable: _i.e._, there is absolute uncertainty. The \"fundamental source-coding theorem\" can be stated as in Storer [2]: \"Let S be a first-order source over an alphabet \(\Sigma\) and let \(\Gamma\) be an alphabet of r \(>\) 1 characters. Then encoding the characters of S with characters of \(\Gamma\) requires an average of H\({}_{\text{r}}\)(s) characters of \(\Gamma\) per character of \(\Sigma\). Furthermore, for any real number \(\varepsilon>0\) there exists a coding scheme that uses an average of H\({}_{\text{r}}\)(s) + \(\varepsilon\) characters of \(\Gamma\) per character of \(\mathcal{I}\)\". Because of the fundamental source coding theorem entropy is a limit to the length of the string that we can use to lossless code a message. Today lossless compressors are very efficient. While it is not possible to prove that they always achieve the theoretical limit, the performances of the state of the art compressors for specific types of data, like natural language text, are certainly very close to this theoretical limit. Current research on lossless compression focuses on developing compressors for new types of digital data or on improving, often only by small amounts, existing compressors for a specific class of data. Even a small improvement is an important achievement, given the economical impact it can have on data transmission and storage. Many data compression methods are based on the notion of \"dictionary\". In this paper we will primarily consider dictionary based compression methods. Dictionaries can be static, _i.e._, built at the beginning of the compression/communication process and never updated and in this case the compression method is called static dictionary method. Otherwise, if the dictionaries are consistently and independently built, maintained, and updated by both compressor and decompressor, then the compression method is called dynamic dictionary method. We can use static dictionary methods when the source is known in advance.