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 - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.htmlReceived on Thu Apr 28 13:41:49 2005
This archive was generated by hypermail 2.1.8 : 2005-04-28 13:41:50 EST