[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: More delta storage stuff...

From: Daniel Berlin <dan_at_dberlin.org>
Date: 2002-02-13 21:55:34 CET

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.

> 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

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.

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

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.