Click here to Skip to main content
13,290,556 members (64,980 online)
Click here to Skip to main content
Add your own
alternative version


35 bookmarked
Posted 18 Apr 2002

Minimum Difference

, 22 Apr 2002
Rate this:
Please Sign up or sign in to vote.
Identifying the minimum difference between two data sets.


Calculating the minimum difference between two sets of data is a common requirement. The compare<> class can be used to identify the minimum difference between two sets of arbitrary types. It is a template class that uses a generic data source class interface to supply data to it. This means that the algorithm is entirely independent of the data, and the representation of the data.


To calculate the minimum difference between two data sets is to reverse the problem and calculate the Longest Common Subsequence and use the result of this to determine the differences. The LCS problem is well documented on the Internet and in research papers. I have implemented the Iterative LCS algorithm described by Professor David Eppstein at the University of California. The LCS will identify the longest groups of elements common between the two sources. By definition, extracting these groups from the original will identify the minimum non-common elements between the two.


The algorithm is encapsulated entirely within one class, compare<> which is implemented within the cmp namespace. cmp::compare<> is a template class that is instantiated with a data source class to supply its data. I have included two data sources for demonstration purposes. The first is another template class called cmp::data_source<>. This can be used for any basic data type, for example to compare to text strings. The second is cmp::data_source_text_file. used to compare two text files

cmp::data_source<> example

To make life a little easier, we can typedef the cumbersome template classes:

typedef cmp::data_source<const char>        compare_data_source_t;
typedef cmp::compare<compare_data_source_t> compare_t;

Here's the data to compare:

const char str1[] = "little jack horner";
const char str2[] = "sat in a corner";

So we simply instantiate two data sources, and give them the data:

compare_data_source_t compare_data1(str1, strlen(str1));
compare_data_source_t compare_data2(str2, strlen(str2));

Now we can instantiate the cmp::compare<> class:

compare_t compare(&compare_data1, &compare_data2);

And finally we can call process()

compare_t::result_set seq;
int lcs = compare.process(&seq);

process() returns an integer which is the length of the Longest Common Subsequence. This isn't really very useful to us when trying to determine the difference, but the return value can give two useful pieces of information. A return value of -1 indicates an error, and 0 (zero) indicates that the two data sets are identical.

The seq parameter will, on successful return, contain the result sequence. This contains a list of records from the two data sets, along with information about their relationship to the second dataset. Each record will be marked as KEEP, REMOVE, or INSERT. These are descriptive of creating the second data set from the first, thus:

  • KEEP - records in both data sources
  • REMOVE - records in the first, but not the second data set
  • INSERT - records not in the first, but in the second data set

Memory requirements

The LCS implementation is heavy on memory allocation. It requires n*m*sizeof(short) bytes of storage where n and m are the number of records in each of the data sets. For example, to compare two 1KB datasets requires 1MB of storage!

To overcome this overhead, we compare larger blocks of data and subdivide differing blocks and perform a separate LCS process on those. For example, the cmp::data_source_text_file class compares text files line by line to yield a result similar to that of a version control system, identifying which lines in the two files are different. To identify character changes in a text file, each line that is different could be passed through a cmp::data_source<char> as in the first example.




This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Craig Henderson
Technical Lead
United Kingdom United Kingdom
Craig graduated with a B.SC. Honours in Computing for Real Time Systems from the University of the West of England, Bristol in 1995 after completing an HND in Computing in 1993.

You may also be interested in...


Comments and Discussions

GeneralVC++ how to compare constant char with a char Pin
Oriocat16-Jul-04 8:22
memberOriocat16-Jul-04 8:22 
GeneralCool Pin
Hockey16-May-04 4:54
memberHockey16-May-04 4:54 
Generalfile compare using perl Pin
Graham Bright18-Jun-03 5:11
sussGraham Bright18-Jun-03 5:11 
GeneralComparison of text files Pin
Philippe Lhoste2-May-02 3:12
memberPhilippe Lhoste2-May-02 3:12 
GeneralRe: Comparison of text files Pin
Craig Henderson3-May-02 6:24
memberCraig Henderson3-May-02 6:24 
GeneralRe: Comparison of text files Pin
Philippe Lhoste3-May-02 7:05
memberPhilippe Lhoste3-May-02 7:05 
GeneralRe: Comparison of text files Pin
Craig Henderson3-May-02 10:00
memberCraig Henderson3-May-02 10:00 
GeneralRe: Comparison of text files Pin
Philippe Lhoste29-May-02 3:13
memberPhilippe Lhoste29-May-02 3:13 
Generalmisprint Pin
Igor29-Apr-02 21:33
memberIgor29-Apr-02 21:33 
GeneralInteresting article - thanks Pin
Neville Franks23-Apr-02 2:10
memberNeville Franks23-Apr-02 2:10 
GeneralRe: Interesting article - thanks Pin
Craig Henderson23-Apr-02 10:55
memberCraig Henderson23-Apr-02 10:55 
GeneralRe: Interesting article - thanks Pin
Craig Henderson7-Nov-02 1:33
memberCraig Henderson7-Nov-02 1:33 
NewsRe: Interesting article - thanks Pin
Craig Henderson8-Sep-13 23:17
memberCraig Henderson8-Sep-13 23:17 
GeneralFancy page Pin
Jason Hooper20-Apr-02 1:55
memberJason Hooper20-Apr-02 1:55 
GeneralRe: Fancy page Pin
Craig Henderson20-Apr-02 10:08
memberCraig Henderson20-Apr-02 10:08 
GeneralRe: Fancy page Pin
Jason Hooper20-Apr-02 10:46
memberJason Hooper20-Apr-02 10:46 

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.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.171207.1 | Last Updated 23 Apr 2002
Article Copyright 2002 by Craig Henderson
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid