suffix array/tree deltas (Was: The criss-cross merge case)

["Zed A. Shaw" <zedshaw@zedshaw.com>]

On Wed, 2005-04-27 at 19:32 -0400, Daniel Barkalow wrote:
> On Wed, 27 Apr 2005, Bram Cohen wrote:
> 

> My plan is to implement multi-file diff and merge with a suffix tree-based
> algorithm, and then revisit the history stuff once we have a merger that
> can do sensible things with this information.

Hey, that's neat.  I've already implemented two versions of this very
thing with FastCST.  The original used suffix trees, but I found that
there were plenty of pathological cases which chewed memory and
processor.  Most of these cases were large (>1MB) PDF files.  Don't ask
me why PDF drove suffix tree algorithms insane, but they just did.

I recently switched to a suffix array based algorithm which actually
ends up being faster than the suffix tree alternative.  I'm not using
the most recent fastest algorithm and it still compares favorably with
xdelta.

There's tons of weird things about doing a delta based on suffix
arrays/trees, so feel free to pick my brain or the FastCST code if you
attempt it.  The difficult parts turn out to be making the suffix array
and searching for the matching/non-matching regions.  Once you do that
the actual delta algorithm is a simple while loop that keeps doing the
match/non-match detection.

Zed