Click here to Skip to main content
15,867,453 members
Articles / Programming Languages / C++

Minimum Difference

Rate me:
Please Sign up or sign in to vote.
5.00/5 (3 votes)
22 Apr 2002CPOL3 min read 107.9K   772   35   16
Identifying the minimum difference between two data sets.

Introduction

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.

Algorithm

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.

Implementation

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:

C++
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:

C++
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:

C++
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:

C++
compare_t compare(&compare_data1, &compare_data2);

And finally we can call process()

C++
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.

Contact

Website:http://homepage.virgin.net/cdm.henderson
e-mail:cdm.henderson@virgin.net

License

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


Written By
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.

Comments and Discussions

 
GeneralVC++ how to compare constant char with a char Pin
Oriocat16-Jul-04 7:22
Oriocat16-Jul-04 7:22 
GeneralCool Pin
alex.barylski16-May-04 3:54
alex.barylski16-May-04 3:54 
Generalfile compare using perl Pin
Graham Bright18-Jun-03 4:11
Graham Bright18-Jun-03 4:11 
GeneralComparison of text files Pin
Philippe Lhoste2-May-02 2:12
Philippe Lhoste2-May-02 2:12 
GeneralRe: Comparison of text files Pin
Craig Henderson3-May-02 5:24
Craig Henderson3-May-02 5:24 
GeneralRe: Comparison of text files Pin
Philippe Lhoste3-May-02 6:05
Philippe Lhoste3-May-02 6:05 
GeneralRe: Comparison of text files Pin
Craig Henderson3-May-02 9:00
Craig Henderson3-May-02 9:00 
GeneralRe: Comparison of text files Pin
Philippe Lhoste29-May-02 2:13
Philippe Lhoste29-May-02 2:13 
Generalmisprint Pin
Igor Urdenko29-Apr-02 20:33
Igor Urdenko29-Apr-02 20:33 
GeneralInteresting article - thanks Pin
Neville Franks23-Apr-02 1:10
Neville Franks23-Apr-02 1:10 
Hi Craig, thanks for posting this. You references sent me on a bit of journey and I was able to glimmer some interesting information about Difference Analysis that I wasn't aware of before. I've written a Diff engine which is ED4W, so this is an area of particular interest to me.

I ran your demo on some small files and it worked fine, but when I tried it on two files of some 70K lines I got the following error:

"This application has requested the Runtime to terminate it in an unusual way. Please contact the application's support team for more information."

I assume this is a memory issue. I couldn't find this in your code so I guess that it's coming from STL.

Neville Franks, Author of ED for Windows. www.getsoft.com
GeneralRe: Interesting article - thanks Pin
Craig Henderson23-Apr-02 9:55
Craig Henderson23-Apr-02 9:55 
GeneralRe: Interesting article - thanks Pin
Craig Henderson7-Nov-02 0:33
Craig Henderson7-Nov-02 0:33 
NewsRe: Interesting article - thanks Pin
Craig Henderson8-Sep-13 22:17
Craig Henderson8-Sep-13 22:17 
GeneralFancy page Pin
Jason Hooper20-Apr-02 0:55
Jason Hooper20-Apr-02 0:55 
GeneralRe: Fancy page Pin
Craig Henderson20-Apr-02 9:08
Craig Henderson20-Apr-02 9:08 
GeneralRe: Fancy page Pin
Jason Hooper20-Apr-02 9:46
Jason Hooper20-Apr-02 9: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.