Reputation: 529

How do document diff algorithms work?

I want to implement word document differ, what algorithms does it requires to implement?

Upvotes: 38

Answers (5)

SunnyShah

Reputation: 30507

The most optimal solution for the LCS problem is O(ND) Myer's algorithm, and here is an algorithmic approach which I used to implement to diff office 2007 documents. Link to algorithm paper

Upvotes: 2

Brandon E Taylor

Reputation: 25369

As Ben S indicated, the differencing problem can be addressed generally by solving the longest common sub-sequence problem. More specifically, The Hunt-McIlroy algorithm is one of the classic algorithms that have been applied to the problem (e.g in the implementation of Unix' diff utility).

Upvotes: 3

CraigTP

Reputation: 44939

Well, generally speaking, diff'ing is usually solved by the Longest common subsequence problem. Also see the "Algorithm" section of the Wikipedia article on Diff:

The operation of diff is based on solving the longest common subsequence problem.

In this problem, you have two sequences of items:
   a b c d f g h j q z

   a b c d e f g i j k r x y z
and you want to find the longest sequence of items that is present in both original sequences in the same order. That is, you want to find a new sequence which can be obtained from the first sequence by deleting some items, and from the second sequence by deleting other items. You also want this sequence to be as long as possible. In this case it is
   a b c d f g j z
From the longest common subsequence it's only a small step to get diff-like output:
   e   h i   q   k r x y 
   +   - +   -   + + + +

That said, this all works fine with text based documents. Since Word Documents are effectively in a binary format, and include lots of formatting information and data, this will be far more complex. Ideally, you could look into automating Word itself as it has the ability to "diff" between documents, as detailed here:

Microsoft Word Tip: How to compare two documents for differences

Upvotes: 39