Трехсторонние алгоритмы слияния для текста - PullRequest
27 голосов
/ 30 июля 2009

Итак, я работал над сайтом типа вики. Что я пытаюсь решить, так это лучший алгоритм объединения статьи, которая редактируется одновременно двумя пользователями.

Пока что я рассматриваю использование метода слияния документов Википедии, если редактируются две несвязанные области, но отбрасываю более старые изменения, если конфликт двух коммитов.

У меня следующий вопрос: если у меня есть оригинальная статья и два изменения к ней, каковы наилучшие алгоритмы их объединения, а затем устранения конфликтов по мере их возникновения?

Ответы [ 3 ]

31 голосов
/ 30 июля 2009

Отличная статья Билла Ритчера " Надежное трехстороннее слияние " рассказывает о некоторых распространенных проблемах с трехсторонним объединением и умных решениях для них, которые использовались коммерческими пакетами SCM.

Трехстороннее объединение автоматически применяет все изменения (не перекрывающиеся) для каждой версии. Хитрость заключается в том, чтобы автоматически обрабатывать как можно больше практически перекрывающихся областей.

10 голосов
/ 22 ноября 2012

В этой статье приведен формальный анализ алгоритма diff3 с псевдокодом: http://www.cis.upenn.edu/~bcpierce/papers/diff3-short.pdf

Она называется «Формальное расследование Diff3» и написана Сандживом Ханной, Кешавом Куналом и Бенджамином С. Пирсом из Yahoo.

2 голосов
/ 30 июля 2009

Честно говоря, я бы положился на diff3. Он есть практически в каждом дистрибутиве Unix, и вы всегда можете собрать и собрать .EXE для Windows, чтобы убедиться, что он существует для ваших целей.

...