I understand that the theoretical size of a diff patch between two similar files can be calculated using Kullback Leibler (KL) as described @ [Wikipedia][1].  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...

[![KLD graph][2]][2]

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


  [1]: https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence#Data_differencing
  [2]: https://i.sstatic.net/K2sH7.png