[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gnu-arch-users] FW: 3 way merge algorithm
From: |
Rob Weir |
Subject: |
[Gnu-arch-users] FW: 3 way merge algorithm |
Date: |
Thu, 29 Apr 2004 22:46:14 +1000 |
User-agent: |
Mutt/1.5.5.1+cvs20040105i |
Just saw this on the svn-dev list, perhaps it's a useful algorithm for
us, too?
----- Forwarded message from Torsten Rueger <address@hidden> -----
From: Torsten Rueger <address@hidden>
To: address@hidden
Subject: 3 way merge algorithm
Date: Wed, 28 Apr 2004 14:19:36 +0300
Moi,
at the university I work, we have found a more efficient algorithm for
3 way merging. It's works better than diff3 especially in that it
handles moves. So it can merge cases where one person moves a piece of
text, while the other edits a subset of it. It also handles XML merges
surprisingly well.
Unfortunately I can not release code (which is ruby anyway), but I can
describe the algorithm, which is quite simple, and help anyone who
wants to implement it.
I would suggest it could be used for cases where diff3 fails, so as not
to rock the boat too much initially.
I'd really like to hear if anyone is interested in this, even quite
separate from wanting to implement it.
Below is a minimal description of the algorithm using a small xml
example,
Torsten
Original: <html><body>Stuff</body><head>Merge Example</head></html>
1 2 3 4 5 6 7 8 9
One: <html><head>Merge Example</head><body>Stuff</body></html>
1 <--5 6 7 8 <--2 3 4 <--9
Two: <html><body>Algorithm</body><head>Example</head></html>
1 2 <--10 <--4 5 <-- 7 8 9
Merge: <html><head>Example</head><body>Algorithm</body></html>
1 5 7 8 2 10 4 9
Matching phase: Find the string in One and Two to map to the original.
Add added strings
One: 1 5-8 2-4 9
Two 1 5 7,8 2 add:10 4 9
Merging phase: go backwards through original following the change
pattern:
Start with 9 in either
Go to 4, because of change in One
Go to 10 because of change in Two
Go to 2 because of change in Two
Go to 8 because of change in One
Go to 7 because no change in original order
Go to 5 because of change in Two
Go to 1 because of change in One
Output in reverse order and get Merge!
While going through the original matches of the matching phase, one has
to recognise the "changes" inside the matches. It's either that or
splitting all matches into the non overlapping pieces that are the
numbers. This second option has proven to be more complicated.
Matching is done al la xdelta, by splitting files into chunks,
calculating hashes for each chunk. Then looking for equal hashes and
expanding the match as far as possible. At the end one can add the
strings in the "gaps" that have not been matched.
---------------------------------------------------------------------
To unsubscribe, e-mail: address@hidden
For additional commands, e-mail: address@hidden
----- End forwarded message -----
--
Rob Weir <address@hidden> | address@hidden | Do I look like I want a CC?
Words of the day: Vince Foster MD4 UNSCOM Legion of Doom threat digicash
signature.asc
Description: Digital signature
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Gnu-arch-users] FW: 3 way merge algorithm,
Rob Weir <=