Ответ 1
На самом деле нет такой вещи, как "алгоритм дифференциала". Существует множество различных алгоритмов дифференцирования, и в действительности используемые алгоритмы дифференцирования в некоторых случаях считаются бизнес-преимуществом конкретного инструмента сравнения.
В общем, многие алгоритмы diff основаны на проблеме "Самая длинная общая подпоследовательность" (LCS).
Оригинальная программа Unix diff с 1970-х годов была написана Дугом Макиллоем и использует так называемый алгоритм Hunt-McIllroy. Почти 40 лет спустя расширения и производные этого алгоритма все еще очень распространены.
Несколько лет назад Брэм Коэн (создатель самой успешной программы обмена файлами и наименее успешная система управления версиями) создал алгоритм терпимости Diff, который предназначен для получения более удобочитаемых результатов, чем LCS. Он был первоначально реализован в VCS Bazaar, а также добавлен в Git в качестве опции.
Однако, если вы не заинтересованы в исследовании алгоритмов diff, лучшим вариантом будет, вероятно, просто использовать некоторую существующую библиотеку diff, например Davide Libenzi LibXDiff, который, например, используется Git. Я не был бы слишком удивлен, если бы уже было добавлено расширение PHP. Хорошей альтернативой является библиотека Google Diff-Match-Patch, которая используется, например, в Bespin или WhiteRoom и доступна для многих языков. Он использует алгоритм Meyers Diff Algorithm плюс некоторую предварительную и пост-обработку для дополнительных ускорений.
Совершенно другой подход, если вы больше заинтересованы в слиянии, чем в разной степени, называется Операционными преобразованиями. Идея OT заключается в том, что вместо выяснения различий между двумя документами вы пытаетесь "перепроектировать" операции, которые привели к этим различиям. Это позволяет значительно лучше слить, потому что вы можете "повторить" эти операции. Они наиболее полезны для коллективных редакторов в режиме реального времени, таких как EtherPad, Google Wave или SubEthaEdit.