Greg Hudson <ghudson@MIT.EDU> writes:
> > "Given a source string and a delta, you can't construct the inverse
> > delta"
>
> > The latter is the situation I'm in. And I know I can do it: at the
> > very worst, I could apply the delta to the source string to produce
> > the target string and then run the delta algorithm again with the
> > arguments reversed. However, I'm hoping that with fancy arithmetic
> > I could do better.
>
> I doubt it. The delta constructs the target in linear order, but has
> essentially random access to the source.
>
> There are also some special cases where you definitely have to go to
> all the work. Suppose the source is an interesting block of data but
> the target is an empty string, or something boring like a run of
> zeros. There's clearly no way you can avoid the effort of compressing
> the source data in that case.
That sounds right to me. But Josh MacDonald says he was doing it in
his XDelta Filesystem, so I wanted to provide an interface at which we
could plug things in.
But, the original question was: why do we need the text delta window
data structure? It's the general principle of trying to choose the
right representation at each level. VCDIFF is an okay representation
on disk or on the network; the text delta windows are supposed to be a
useful representation in memory. Most of the complexity of VCDIFF
comes from trying to choose a dense representation for the edit list,
a matter of no concern to code which applies or generates text deltas.
So --- I do want to keep the idea of having a nice internal
representation of text deltas. But if the window structure is not the
right thing, then let's fix it.
Received on Sat Oct 21 14:36:08 2006