Three Way Merge Algorithms for Text

algorithm merge diff revision
icco picture icco · Jul 30, 2009 · Viewed 13.2k times · Source

So I've been working on a wiki type site. What I'm trying to decide on is what the best algorithm for merging an article that is simultaneously being edited by two users.

So far I'm considering using Wikipedia's method of merging the documents if two unrelated areas are edited, but throwing away the older change if two commits conflict.

My question is as follows: If I have the original article, and two changes to it, what are the best algorithms to merge them and then deal with conflicts as they arise?

Answer

Kyle Wiens picture Kyle Wiens · Jul 30, 2009

Bill Ritcher's excellent paper "A Trustworthy 3-Way Merge" talks about some of the common gotchas with three way merging and clever solutions to them that commercial SCM packages have used.

The 3-way merge will automatically apply all the changes (which are not overlapping) from each version. The trick is to automatically handle as many almost overlapping regions as possible.

Related questions

Understanding the Recursion of mergesort

Most of the mergesort implementations I see are similar to this. intro to algorithms book along with online implentations I search for. My recursion chops don't go much further than messing with Fibonacci generation (which was simple enough) so maybe …

Read More
How to merge two BST's efficiently?

How to merge two binary search trees maintaining the property of BST? If we decide to take each element from a tree and insert it into the other, the complexity of this method would be O(n1 * log(n2)), where …

Read More
Number of Comparisons in Merge-Sort

I was studying the merge-sort subject that I ran into this concept that the number of comparisons in merge-sort (in the worst-case, and according to Wikipedia) equals (n ⌈lg n⌉ - 2⌈lg n⌉ + 1); in fact it's between (n lg n …

Read More