An O(ND) Difference Algorithm for C#
An C# implementation of the difference algorithm published in "An O(ND) Difference Algorithm and its Variations" by Eugene Myers Algorithmica Vol. 1 No. 2, 1986, p 251.
This article is about comparing text files and the proven, best and most famous algorythm 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 just does this job. You should have it in the bag of your algorythms.
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.