Click here to Skip to main content
15,745,574 members
Articles / Programming Languages / C#
Posted 6 Mar 2006


139 bookmarked

An O(ND) Difference Algorithm for C#

Rate me:
Please Sign up or sign in to vote.
4.87/5 (34 votes)
14 Mar 20067 min read
This article is about comparing text files, and the best and most famous algorithm to identify the differences between them.


This article is about comparing text files, and the best and most famous algorithm to identify the differences between them. The source code that you can find in the download implements a small class with a simple to use API that does this job. You must have this in your collection of algorithms.

Besides the class that implements the algorithm, there is also a sample web application that compares two files and generates an HTML output with a combined and colored document.

The algorithm was first published 20 years ago under the title "An O(ND) Difference Algorithm and its Variations" by Eugene Myers, Algorithmica Vol. 1 No. 2, 1986, p 251. You can find a copy if it here. In this article, you can find an abstract recursive definition of the algorithm, using some pseudo-code that needs to be transferred to an existing programming language.

There are many C, Java, and Lisp implementations publicly available of this algorithm out there on the internet. Before I wrote the C# version, I discovered that almost all these implementations came from the same source (GNU diffutils) that is available under the (unfree) GNU public license and therefore cannot be reused as a source code for commercial or redistributable application, without being trapped by the GNU license.

There are very old C implementations that use other (worse) heuristic algorithms. Microsoft also published the source code of a diff-tool (WinDiff) that uses some tree structures. Also, a direct transfer from a C source to C# is not easy because there is a lot of pointer arithmetic in the typical C solutions, and I wanted a managed solution. I tried a lot of sources, but found no usable solution written for the .NET platform.

These are the reasons why I implemented the original published algorithm from scratch, and made it available without the GNU license limitations, under a Creative Commons Attribution 2.0 Germany License. The history of this implementation traces back to 2002 when I published a Visual Studio add-in that also compares files, see Visual Studio 2005 Add-in that adds diff tools, an explore command, subversion support, and web project reporting. I couldn't find any bugs in the last 3 years, so I think the code is pretty stable.

I didn't need a high performance diff tool. I will do some performance tweaking as and when needed, so please let me know. I have also dropped some hints in the source code on that topic.

How it works (briefly)

You can find an online working version of the download files here.

  • Comparing the characters of two huge text files is not easy to implement and tends to be slow. Comparing numbers is much easier, so the first step is to compute unique numbers for all the text lines. If the text lines are identical then identical numbers are computed.
  • There are some options that need to be considered before computing these numbers, which are normally useful for some kind of text: stripping off space characters and comparing case insensitive.
  • The core algorithm itself will compare two arrays of numbers, and the preparation is done in the private DiffCodes method and by using a Hashtable.
  • The methods are DiffText and DiffInts.
  • The core of the algorithm is built using two methods:
    • LCS: This is the divide-and-conquer implementation of the longest-common-subsequence algorithm.
    • SMS: This method finds the Shortest Middle Snake.
  • To get some usable performance, I did some changes to the original algorithm. The original algorithm was described using a recursive approach, and compares zero indexed sequences, and passes parts of these sequences as parameters. Extracting sub-arrays and rejoining them is very CPU and memory intensive. To avoid copying these sequences as arrays around, the used arrays together with the lower and upper bounds are passed while the sequences are not copied around all the time. This circumstance makes the LCS and SMS functions more complicate.
  • I added some code to the LCS function to get a fast response on sub-arrays that are identical, completely deleted, or inserted instead of recursively analyzing them down to the single number case.
  • The result is stored in two arrays that flag for modified (deleted or inserted) lines in the two data arrays. These bits are then analyzed to produce an array of objects that describe the found differences.
  • Read the original article if you want to understand more.


To use this functionality, you only have to call one of the DiffText methods. They all get a pair of strings, and return an array of items that describe the inserts and deletes between the two strings. There are no "changes" reported. Instead, you can find an "insert" and "deleted" pair.

DiffText(string TextA, string TextB)

Finds the difference between two texts, comparing by text lines without any conversion. An array of items containing the differences is returned.

DiffText(string TextA, string TextB, bool trimSpace, bool ignoreSpace, bool ignoreCase)

Finds the difference between two texts, comparing by text lines with some optional conversions. An array of items containing the differences is returned.

Diff(int[] ArrayA, int[] ArrayB)

Finds the difference between two arrays of integers. An array of items containing the differences is returned.

A sample application for the algorithm

The sample is a small web application that calculates the difference between two text files and displays the result using HTML.

To setup the sample, you have to create a web-project and copy all the files found in the zip file into the directory. The implementation of the algorithm is given inside the "diff.cs" class.

Further possible optimizations (if you really need speed)

(First rule: don't do it; second: don't do it yet.)

The arrays DataA and DataB are passed as parameters, but are never changed after the creation, so they can be used as members of the class to avoid parameter overhead. In the SMS, there is a lot of boundary arithmetic in the for-D and for-k loops that can be done by incrementing and decrementing the local variables. The DownVector and UpVector arrays are always created and destroyed each time the SMS gets called. It is possible to reuse them when transferring them to members of the class.

See TODO: hints.

Security issues with the web application

  • Using this web-site implementation enables clients to view all the source code of your website. Just be sure that you do not use it as-it-is on a public server.
  • You should implement a check of the parameters, and allow only a diff output on the files that can be displayed (text based files).


This work is licensed under Creative Commons Attribution 2.0 Germany License.

Built-in self-test

The class now has a built-in self-test, that works without changing the code. If you compile the diff and debug class files together, you get an EXE file that tests some simple diff-scenarios that were used to discover the bugs in versions 1 and 2 (OutOfArrayBounds typically).

The compile command is:

csc /target:exe /out:diffTest.exe /debug /d:SELFTEST Diff.cs Debug.cs

Thanks for your feedback and the two reported cases that did not diff correctly. (It was always my fault, not a problem of the algorithm).


This work was first published here.

  • 2002.09.20
    • There was a "hang" in some situations.
    • Now, I understand a little bit more of the SMS algorithm.
    • There have been overlapping boxes; those where analyzed differently. One return-point is enough.
    • An assertion was added in CreateDiffs when in debug-mode, that counts the number of equal (not modified) lines in both arrays. They must be identical.
  • 2003.02.07
    • Out of bounds error in the Up/Down vector arrays in some situations.
    • The two vectors are now accessed using different offsets that are adjusted using the start k-Line.
    • A test case is added.
  • 2003.04.09
    • Another test that threw an exception was found, but that seems to be fixed by the 2002.09.20 work.
  • 2006.03.10
    • Refactored the API to static methods on the diff class to make the usage simpler.
    • The self test is now using the standard debug class.


This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Written By
Architect Deutsche Bank AG
Germany Germany

Comments and Discussions

Questiondebug Pin
Member 157237261-Aug-22 0:20
Member 157237261-Aug-22 0:20 
GeneralMy vote of 5 Pin
Member 96680539-Jun-13 22:56
Member 96680539-Jun-13 22:56 
QuestionWinForm or WPF version Pin
Member 78411351-Oct-12 11:13
Member 78411351-Oct-12 11:13 
AnswerRe: WinForm or WPF version Pin
Member 46358743-Dec-13 2:26
Member 46358743-Dec-13 2:26 
QuestionFormating the results Pin
Member 78411351-Oct-12 11:09
Member 78411351-Oct-12 11:09 
AnswerRe: Formating the results Pin
Matthias Hertel2-Oct-12 10:17
professionalMatthias Hertel2-Oct-12 10:17 
GeneralReverting text to a previous state Pin
jsoldi1-Mar-11 8:12
jsoldi1-Mar-11 8:12 
GeneraldiffItem results are not consistent Pin
cmschick4-Dec-09 18:30
cmschick4-Dec-09 18:30 
QuestionDiffWord? Pin
keeara26-Jan-09 20:43
keeara26-Jan-09 20:43 
Generaltext diff Pin
m-khansari22-Dec-08 21:15
m-khansari22-Dec-08 21:15 
GeneralRe: text diff Pin
Matthias Hertel26-Dec-08 0:06
professionalMatthias Hertel26-Dec-08 0:06 
QuestionUnfree? Pin
Brianary30-Oct-07 14:40
Brianary30-Oct-07 14:40 
QuestionProblem with your code... :( [modified] Pin
Célio16-Jul-07 2:48
Célio16-Jul-07 2:48 
AnswerRe: Problem with your code... :( Pin
Matthias Hertel16-Jul-07 8:02
professionalMatthias Hertel16-Jul-07 8:02 
GeneralRe: Problem with your code... :( Pin
Célio16-Jul-07 22:52
Célio16-Jul-07 22:52 
GeneralRe: Problem with your code... :( Pin
Morder VonAllem6-Sep-07 11:25
Morder VonAllem6-Sep-07 11:25 
AnswerRe: Problem with your code... :( Pin
Célio6-Sep-07 22:49
Célio6-Sep-07 22:49 
GeneralLicense/Attribution Pin
chiphnc20-May-07 15:22
chiphnc20-May-07 15:22 
AnswerRe: License/Attribution Pin
Matthias Hertel21-May-07 9:01
professionalMatthias Hertel21-May-07 9:01 
QuestionAny chance of a winforms sample app? Pin
tonyk14-May-07 15:29
tonyk14-May-07 15:29 
AnswerRe: Any chance of a winforms sample app? Pin
Matthias Hertel5-May-07 2:32
professionalMatthias Hertel5-May-07 2:32 
QuestionRe: Any chance of a winforms sample app? Pin
tonyk16-May-07 17:02
tonyk16-May-07 17:02 
QuestionRe: Any chance of a winforms sample app? Pin
Matthias Hertel7-May-07 9:24
professionalMatthias Hertel7-May-07 9:24 
Questionhow can modify it to support chinese?? Pin
P.Dragon24-Mar-07 17:00
P.Dragon24-Mar-07 17:00 
AnswerRe: how can modify it to support chinese?? Pin
Matthias Hertel1-Apr-07 23:40
professionalMatthias Hertel1-Apr-07 23:40 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.