CODEWITHSUNDEEP
textcomparisondiffcompare
java_mouse
java_mouse

Reputation: 2109

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.

Upvotes: 42

Views: 57996

Answers (7)

ozanmut
ozanmut

Reputation: 3234

The most famous algorithm is O(ND) Difference Algorithm, also used in Notepad++ compare plugin (written in C++) and GNU diff(1). You can find a C# implementation here: http://www.mathertel.de/Diff/default.aspx

Upvotes: 0

Kenny Evitt
Kenny Evitt

Reputation: 9801

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

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:

Upvotes: 8

becke.ch
becke.ch

Reputation: 27

The difficulty comes when comparing large files efficiently and with good performance. I therefore implemented a variation of Myers O(ND) diff algorithm - which performs quite well and accurate (and supports filtering based on regular expression):

Algorithm can be tested out here: becke.ch compare tool web application

And a little bit more information on the home page: becke.ch compare tool

Upvotes: 1

cubicdaiya
cubicdaiya

Reputation: 368

An O(NP) Sequence Comparison Algorithm is used by subversion's diff engine.

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

https://github.com/cubicdaiya/onp

Upvotes: 19

Zoë Peterson
Zoë Peterson

Reputation: 13322

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.

Upvotes: 9

Howard
Howard

Reputation: 3895

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

and

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.

Upvotes: 12

FatalError
FatalError

Reputation: 54611

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.

Upvotes: 26

Related Questions