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

Question

Я хочу, чтобы документ Word отличался, какие алгоритмы он требует для реализации?

Answer 1

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

Операция 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

Из самой длинной общей подпоследовательности это всего лишь маленький шаг, чтобы получить дифференцированный вывод:

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

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

Совет Microsoft Word. Как сравнить два документа на предмет различий

Answer 2

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

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

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

Answer 3

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

Answer 4

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

Answer 5

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