Как работают алгоритмы работы с документами?

Ответ 1

Самое оптимальное решение lcs O (ND) Myer алгоритм, и вот алгоритмический подход, который я использовал для реализации diff Office 2007. Ссылка на бумагу алгоритма

Ответ 2

Ну, вообще говоря, diff 'ing обычно решается Самая длинная общая проблема подпоследовательности. Также см. Раздел Алгоритм статьи Википедии о Diff:

Работа дифференциала основана на решение самой длинной общей подпоследовательности проблема.

В этой проблеме у вас есть два последовательности элементов:

   a b c d f g h j q z

   a b c d e f g i j k r x y z

и вы хотите найти самый длинный последовательность элементов, присутствующих в обе исходные последовательности в том же заказ. То есть вы хотите найти новую последовательность, которая может быть получена из первая последовательность, удалив некоторые элементов, а из второй последовательности - удаление других элементов. Вы также хотите эта последовательность должна быть такой же, как и возможное. В этом случае это

   a b c d f g j z

Из самой длинной общей подпоследовательности это лишь небольшой шаг, чтобы получить diff-like output:

   e   h i   q   k r x y 
   +   - +   -   + + + +

Тем не менее, все это прекрасно работает с текстовыми документами. Поскольку Word Documents эффективно работают в двоичном формате и содержат множество информации и данных форматирования, это будет намного сложнее. В идеале вы могли бы изучить автоматизацию самого Word, поскольку он имеет возможность "различать" между документами, как описано здесь:

Совет Microsoft Word: сравнение двух документов для различий

Ответ 3

Разница по существу представляет собой просто решение для самого длинного общего подкаталога, проблема последовательности.

Оптимальное решение требует знания динамического программирования чтобы решить довольно сложную задачу.

Однако это также можно сделать, построив суффикс-дерево. Оба алгоритма выделены здесь.

Ответ 4

См. Алгоритм разности O (ND) для С#.

Ответ 5

Как указал Бен С, проблема разграничения может быть решена в основном путем решения самой длинной общей проблемы подпоследовательности. Более конкретно, алгоритм Hunt-McIlroy является одним из классических алгоритмов, которые были применены к проблеме (например, при реализации Unix diff).