An O(ND) Difference Algorithm for C#
Here you can find an C# implementation of the famous algorithm that finds the best diff of 2 inputs. You can use it for text documents and compare the complete lines, for a text lines and compare the characters or just to compare 2 arrays of numbers. This algorithm is used by many applications that need to find the best way to describe the difference e.g. to extract it as a patch.
This implementation is based on the algorithm published in "An O(ND) Difference Algorithm and its Variations" by Eugene Myers Algorithmica Vol. 1 No. 2, 1986, p 251.
The source code that you can find in the download implements a small class with a simple to use API that just does this job. You should have it in the bag of your algorithms.
The core algorithm is comparing 2 arrays of numbers so when you like to find differences in text files you need a small converter that is also included in the implementation because this is the most used purpose.
Documentation and source code:
This is a detailed documentation for the Diff class that explains some of the backgrounds, concepts and the API.
This is a step by step sample how to use the Diff class for comparing 2 strings on a character basis.
Sample diff results using the older and actual versions of the Diff source code:
These links use the difference algorithm for comparing files and formatting the result as HTML. You can follow the evolution of it since 2002. There was no need for a bug fixing since February 2003:
- Diff v1->v2
- Diff v2->v3
- Diff v3->v4
- Diff v4->v5
- Diff v5->v6
License agreement changed to a BSD style license.
- Diff v6->v7
Optimization of some typical text file sequences added.
- Diff v7->v8
After refactoring the 2 vector creations the algorithm seems ok on big files: 2MB files are crunched in a few seconds thanks to Jan Stoklasa.
- Diff v8->v9
Fixing a test case and adding a new test case from Chris.