文本的三路合并算法

Question

所以我一直在开发一个wiki类型的网站.我想要决定的是合并同时由两个用户编辑的文章的最佳算法.

到目前为止,我正在考虑使用维基百科的合并文档的方法,如果编辑了两个不相关的区域,但如果两个提交冲突则丢弃旧的更改.

我的问题如下:如果我有原始文章,并对其进行了两处更改,那么合并它们然后在出现冲突时处理冲突的最佳算法是什么？

Answer 1

Bill Ritcher的优秀论文" 值得信赖的3-Way Merge "讨论了商业SCM软件包使用的三种合并和巧妙解决方案的常见问题.

3向合并将自动应用每个版本的所有更改(不重叠).诀窍是自动处理尽可能多的几乎重叠的区域.

Answer 2

本文对带有伪代码的diff3算法进行了正式分析:http: //www.cis.upenn.edu/~bcpierce/papers/diff3-short.pdf

它被命名为"Diff3的正式调查",由来自雅虎的Sanjeev Khanna,Keshav Kunal和Benjamin C. Pierce编写.