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


That's not quite right.  I suspect you've taken an imprecise, non-technical, handwavy statement from Wikipedia and interpreted too much into it.  They're trying to summarize some underlying theory in an informal way, but such summaries are inevitably incomplete.  Instead, you'd be better off reading and understanding the underlying theory.

There is a sense in which that statement is correct if we make certain assumptions -- e.g., that the source is memoryless (each character is independent of all past ones, with no history), and that we interpret it in an asymptotic, average-case kind of way -- but for many real-world sources of  data, those assumptions don't apply.