# Numerical example of theoretical diff file size using Kullback Leibler?

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.

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...

• What do you mean by "the theoretical size"? Where did you come to that understanding? Did you read that somewhere, and if so, where? I think you need to explain the claim more carefully, as I don't think it's true in the broad form you laid out. There might be a narrower claim that is true but it needs more care to state correctly. For one thing, the K-L divergence can only be applied to two distributions, not to two files or two samples from two distributions. Can you edit the question to provide more context?
– D.W.
Dec 13, 2016 at 17:41
• @D.W. the theoretical patch file size via KL is as Shannon entropy is to the minimum compressed file size. The two distributions are the byte value probabilities of the original and target files. Dec 13, 2016 at 22:47