0
$\begingroup$

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

KLD graph

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Commented Dec 13, 2016 at 17:41
  • $\begingroup$ @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. $\endgroup$
    – Paul Uszak
    Commented Dec 13, 2016 at 22:47

1 Answer 1

Reset to default
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ So what about my graph? It shows the p log(p/q) calculation for every probability of byte value 0 - 255 . It sums to 380. Can I be so bold as to say that a widely acknowledged mathematical formula should actually output something real and is not at all imprecise or handwavy? Hence what does the concrete value of 380 bits represent in your mind? $\endgroup$
    – Paul Uszak
    Commented Jan 4, 2017 at 2:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.