## 3 Conditional Compression
### A simple experiment  
It is not easy to determine the behavior of a source by looking at a finite, small number of consecutive messages. In real life we often update our personal computers with new versions of existing software products: internet browsers, word processors, anti-viruses, messengers, _etc._ Generally the new software distribution includes large parts of the previous one. If we identify these repeated parts we can avoid their re-transmission when both the encoder and the decoder maintain a copy of the old distribution. To study the amount of shared knowledge that is retained by successive software distributions, we can extend the logical operator eor to compute the differences between two binary files. We indicate with \(\oplus\) this difference operator: if A and B are two binary files of equal length then: \(\mathrm{C=A\oplus B}\), where C will be a new binary file such that C[i], _i.e._, the i-th bit of C, will be one if and only if the i-th bits of A and B are not equal. Therefore, given that the operator is associative and commutative:  
\[\mathrm{A\oplus B\oplus A=B\ and\ A\oplus B\oplus B=A.\ Mover\ A\oplus A=000 \ldots 0}.\]  
Suppose that M and N are two large and strictly correlated files (for example they are two subsequent distribution versions of the same software) and that we compute M \(\oplus\) N. If we can identify and remove from N the sequences of bits that are unchanged with respect to its old version M the resulting, smaller, file will be hopefully easier to compress. In a simple experiment (see [3]) we consider two consecutive distribution versions of the Internet browser Netscape for Mac:  
1. MacNS6 FullInstaller.sea.bin (about 17.7 Mb),
2. MacNS6 FullInstaller2.sea.bin (about 17.7 Mb),  
These two files are self-extracting files that are already partially compressed. Part of the correlation between the files is therefore probably lost. We compress (by using the standard Unix utility gzip) the first file, then we split the files into consecutive segments of 2,000 bytes each and compare the compressed size of the first file with the size of the compressed Net(i) files, where each Net(i) of the second file is obtained from the first file by operating a bitwise eor difference in the first i segments. The intuition is that, when considering two consecutive distribution versions of the same software, we might expect to see the parts of the files that are similar at the beginning of the files after which the two files will probably differentiate. Figure 1 (from [3]) shows the results of this approach for MacNS6 FullInstaller.sea.bin. We have plotted on the x-axis the number of 2,000 bytes segments on which we apply the difference operator (between this file and MacNS6 FullInstaller2.sea.bin) and on the y-axis the size of the compressed file. For convenience we have also reported the size of the gzip compressed version of MacNS6 FullInstaller.sea.bin (the straight line). We see in the figure that the first part of the first file and the first part of the second file (up to about the first two hundreds 2,000 bytes segments) are strictly correlated. By operating a difference between the actual distribution of the software and the previous version we have used previous knowledge of the source (or the knowledge of a source that is correlated to the one we want to compress) to exploit the compression process. The savings we have obtained are limited because of the original nature and correlation of the files we are experimenting, but it is significant that even with this type of data and at least in this case, this approach works. In the experiment we have used a segmentation of the two files in fixed size segments. This implies a sort of alignment of the two files we are comparing.