## 4 Interactive Compression
### An interactive communication protocol  
An efficient communication protocol that allows a Sender and a Receiver to communicate via dictionaries that are built independently from previous (and may be discordant) examples of communication messages that each of the two sides has available is presented by [PERSON] in [8]. This communication protocol results in an improvement in compression paid with a negligible or almost null possibility of communication errors. Consider an information source \(U\) that emits words over a certain alphabet and for which it is possible to partition the words emitted by the source into two sets: one \(D\) of cardinality \(m\) that has probability \(P(D)=1-\alpha\) and another \(D_{comp}\) with probability \(P(D_{comp})=\alpha\), where \(\alpha<<1/2\), and the words \(w\in D\) have probability \(p_{w}\) such that \(|(1-\alpha)/m-p_{w}|<\varepsilon\) for an appropriately chosen \(\varepsilon\). The set \(D\) might be viewed as the ideal \"Dictionary\" for the source. It is possible to recognize this property in many real life situations. As an example consider a source that outputs programs. For this source an ideal set \(D\) might include all the keywords and reserved words of the programming language and the set of the most common identifiers. Consider now a situation in which Sender and Receiver have access to different corpora of the same language: for example different sets of books and/or web pages and/or newspapers, _etc._ They can use these different corpora to independently construct their own dictionaries. If the Sender and the Receiver have both knowledge of the source in the form of a large number of messages that are recorded in two files of length approximately \(n\), if \(n\) is big enough and \(n_{w}\) is the number of occurrences of \(w\) in the file and \(\delta\) is an opportunely chosen number in [0, 1/2], then we have that for each word \(w\), (\(P|n_{w}/n^{-}p_{w}|<\varepsilon\)) \(>(1-\delta)\). The S  
Receiver have a wrong estimate of \(\mathrm{p_{w}}\). Therefore, if n is big enough the probability of a word w in \(\mathrm{D_{S}}\) but not in \(\mathrm{D_{R}}\) is: P(w belongs to \(\mathrm{D_{S}}\) but does not belong to \(\mathrm{D_{R}}\)) \(<2\delta-\delta^{2}\). In a practical situation the Sender has to transmit to the Receiver a message that comes from a source whose behavior is well known by both Sender and Receiver: they have available a large number of messages from the source, but not necessarily the same messages. Based on the messages each of them knows, Sender and Receiver independently construct dictionaries \(\mathrm{D_{S}}\) and \(\mathrm{D_{R}}\) by including in the dictionaries what they assume are the m most common words of the source. The Sender transmits the compressed message to the Receiver by using dictionary \(\mathrm{D_{S}}\) and the Receiver decodes the message by using dictionary \(\mathrm{D_{R}}\). The communication line between Sender and Receiver is a bidirectional line: the Receiver has the possibility of sending acknowledgment messages to the Sender, participating actively to the compression/ transmission process. The Sender will send dictionary words by using [PERSON] and [PERSON]'s fingerprints (see [9]) to improve the compression by allowing a small possibility of communication errors. If the current input word is in the Sender's dictionary than the Sender either sends a previously assigned codeword (if Sender and Receiver have already agreed on that word) or it sends a fingerprint of the current word. In this second case the Receiver either acknowledges its understanding of the dictionary word (if the Receiver has a single word that matches that fingerprint in its dictionary), or it tells the Sender that there is more than one word in its dictionary for that fingerprint and then invites the Sender to send another, different, fingerprint for the same word, or finally it communicates to the Sender that it does not recognize the word and that the word has to be sent explicitly through a standard compression method.