Three ways to merge algorithms for text

Question

So, I worked on a site like wiki. What I'm trying to solve is the best algorithm for merging an article that is simultaneously edited by two users.

So far, I am considering using the Wikipedia method to merge documents if two unrelated areas are edited, but throws an older change if two commits conflict.

My question is this: if I have an original article and its two changes, what are the best algorithms for merging them, and then handle conflicts as they arise?

Answer 1

Bill Ritcher's excellent article, Reliable Three-Way Merge, talks about some common mistakes with three ways to merge and smart solutions for them that used commercial SCM packages.

Three-way merge automatically applies all changes (which do not overlap) from each version. The trick is to automatically process as many nearly overlapping areas as possible.

Answer 2

There is a formal analysis of the diff3 algorithm with pseudo-code in this article: http://www.cis.upenn.edu/~bcpierce/papers/diff3-short.pdf

It is called the “Diff3 Formal Investigation” and was written by Sanjeev Khan, Keshav Kunal and Benjamin Pierce from Yahoo.

Answer 3

Honestly, I would rely on diff3. This is on almost all Unix distributions, and you can always create and build .EXE for Windows to make sure it exists for your purposes.