Text comparison algorithm

We have a requirement in the project that we have to compare two texts (update1, update2) and come up with an algorithm to define how many words and how many sentences have changed. Are there any algorithms that I can use? I am not even looking for code. If I know the algorithm, I can code it in Java.

529 5 5 silver badges 17 17 bronze badges asked Jan 30, 2012 at 14:38 java_mouse java_mouse 2,099 4 4 gold badges 21 21 silver badges 30 30 bronze badges Commented Jan 30, 2012 at 14:41 Commented Jan 30, 2012 at 14:42

7 Answers 7

Typically this is accomplished by finding the Longest Common Subsequence (commonly called the LCS problem). This is how tools like diff work. Of course, diff is a line-oriented tool, and it sounds like your needs are somewhat different. However, I'm assuming that you've already constructed some way to compare words and sentences.

answered Jan 30, 2012 at 14:40 FatalError FatalError 54.2k 16 16 gold badges 103 103 silver badges 118 118 bronze badges There is a frontend to diff(1) called wdiff(1), which works on a word-by-word basis. Commented Jun 1, 2018 at 16:13

For your information, there are implementations with various programming languages by myself in following page of github.

answered Jan 31, 2012 at 11:05 cubicdaiya cubicdaiya 368 1 1 silver badge 6 6 bronze badges

Some kind of diff variant might be helpful, eg wdiff

If you decide to devise your own algorithm, you're going to have to address the situation where a sentence has been inserted. For example for the following two documents:

The men are bad. I hate the men

The men are bad. John likes the men. I hate the men

Your tool should be able to look ahead to recognise that in the second, I hate the men has not been replaced by John likes the men but instead is untouched, and a new sentence inserted before it. i.e. it should report the insertion of a sentence, not the changing of four words followed by a new sentence.

answered Jan 30, 2012 at 14:44 3,885 1 1 gold badge 16 16 silver badges 12 12 bronze badges

The specific algorithm used by diff and most other comparison utilities is Eugene Myer's An O(ND) Difference Algorithm and Its Variations. There's a Java implementation of it available in the java-diff-utils package.

answered Jan 30, 2012 at 15:37 Zoë Peterson Zoë Peterson 13.2k 2 2 gold badges 46 46 silver badges 65 65 bronze badges here's a pdf of eugene myer's paper: https://neil.fraser.name/writing/diff/myers.pdf Commented Jul 17 at 20:03

Here are two papers that describe other text comparison algorithms that should generally output 'better' (e.g. smaller, more meaningful) differences:

Tichy, Walter F., "The String-to-String Correction Problem with Block Moves" (1983). Computer Science Technical Reports. Paper 378.
Paul Heckel, "A Technique for Isolating Differences Between Files", Communications of the ACM, April 1978, Volume 21, Number 4

The first paper cites the second and mentions this about its algorithm:

Heckel[3] pointed out similar problems with LCS techniques and proposed a linear-lime algorithm to detect block moves. The algorithm performs adequately if there are few duplicate symbols in the strings. However, the algorithm gives poor results otherwise. For example, given the two strings aabb and bbaa, Heckel's algorithm fails to discover any common substring.

The first paper was mentioned in this answer and the second in this answer, both to the similar SO question: