Re: More delta storage stuff...

On Wednesday, February 13, 2002, at 01:05 PM, Greg Hudson wrote:

> On Wed, 2002-02-13 at 01:06, Daniel Berlin wrote:
>> "Data differencing is the process of computing a compact and invertible
>> encoding of a "target file" given a "source file"."
>>
>> Then they go on to describe vdelta/vcdiff as doing data differencing.
>
> Maybe we missed something really big in their paper.

Nopoe
>
> Right now, if you compute a delta between <big file> and <empty file>,
> the delta will contain basically no information (no instructions, just
> an svndiff header and a window header)--certainly not enough information
> to reconstruct <big file>. As far as I know, that's just a natural
> consequence of the vdelta algorithm.

And almost any diff algorithm.

I think your definition of invertible is not what they mean, or what
other algorithms mean.

I believe invertible means that given:

text a
text c
delta b that gives you c given a.

You can:
Transform delta b so that it gives you a given c, in time O(size of the
delta).

This of course, still requires access to a and c.

Your definition would be able to do it without a and c.

In other words, the advantage of being invertible is that you can change
the direction of the delta without having to recompute the entire delta
between the two texts.
--Dan

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Sat Oct 21 14:37:07 2006