git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Daniel Barkalow <barkalow@iabervon.org>
Date
Apr 28, 2005, 04:30 UTC
Message-ID
<Pine.LNX.4.21.0504280016000.30848-100000@iabervon.org>
In-Reply-To
<1114659700.5910.10.camel@thamachine>
On Wed, 27 Apr 2005, Zed A. Shaw wrote:
Show 11 quoted lines
> On Wed, 2005-04-27 at 19:32 -0400, Daniel Barkalow 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'm not too surprised; but can you hope to merge or compare PDFs anyway? I'd think that you'd just screw up alignment or something. (Note that we aren't using deltas for history storage, so we're not interested in the "compressing multiple versions" aspect of diffs.) I think I want to punt anything too binary-like and try to find an unambiguous history-based difference (i.e., there was some commit in the past that replaced one of the versions with the other; therefore, we want the replacing one).

I'm thinking of line-based compressed suffix trees, with the obvious delta algorithm: make the trees, find the longest prefix of the file, find the longest prefix of the rest of the file, add an insertion for a line that doesn't match, repeat. I probably need a few extra things to stabilize the process (prefer that the next chunk come from the same file, prefer that it come from next in the file, ignore copied lines without enough content).

I haven't actually started yet; I'm waiting for a weekend when I'm feeling inspired and not too fried.

	-Daniel
*This .sig left intentionally blank*
Previous: Zed A. Shaw
Message 9 of 9 in “The criss-cross merge case”
  1. Bram CohenApr 27, 2005
  2. Daniel BarkalowApr 27, 2005
  3. Tupshin HarperApr 28, 2005
  4. Daniel BarkalowApr 28, 2005
  5. Benedikt SchmidtApr 28, 2005
  6. Daniel BarkalowApr 28, 2005
  7. David RoundyApr 28, 2005
  8. suffix array/tree deltas (Was: The criss-cross merge case)Zed A. Shaw, Apr 28, 2005
  9. Daniel BarkalowApr 28, 2005

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.