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

From: Zed A. Shaw <zedshaw@zedshaw.com>
Date: Apr 28, 2005, 03:41 UTC
Message-ID: <1114659700.5910.10.camel@thamachine>
In-Reply-To: <Pine.LNX.4.21.0504271854240.30848-100000@iabervon.org>

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