I understand that the theoretical size of a diff patch between two similar files can be calculated using Kullback Leibler (KL) as described @ Wikipedia. Can anyone point me to a numerical example of this calculation? I can only find general theory and formulae. I'd like to check my work. So this is what I have so far...
This is a graph of the individual divergences for each byte probability between two files, say P and Q. They are calculated according to the standard log formula for divergence. The byte values (0-255) are along the bottom. You can see that the divergences are both positive and negative.
I am unsure as to what the units of the y axis are, but following on from Shannon entropy, they must be bits per byte. And they're small values. The sum of all the divergences, keeping sign, is 0.019 bits /byte. Both file sizes are approximately 20KByte, so can I say that the theoretical patch size going from P to Q is 20,000 * 0.019 = 380 bits or 48 bytes?
This feels wrong. If the graph represents the patch size somehow, then I cannot see how the information contained in this complex shaped graph can be encoded in just 48 bytes. There are no examples anywhere on the Interweb that I can find. Err
One further thing. The above is for two similar files. If P or Q should be totally random (from a random number generator), the KL divergence calculation = approx. 0.5. This at least makes some semblance of sense if you think about all of the bits from P to Q being on average 50% different due to the randomness. Perhaps 48 bytes is correct. Err, um...
