在处理数据时，经常需要比较两组数据之间的差异。本文介绍的算法旨在找出两组数据之间的最小差异。这种算法的核心是计算最长公共子序列（Longest Common Subsequence, LCS），通过这一结果来确定差异。LCS问题在互联网和学术论文中都有详细记录，本文实现了加州大学教授David Eppstein描述的迭代LCS算法。
要计算两组数据之间的最小差异，实际上是将问题反过来，计算两组数据的最长公共子序列。LCS算法能够识别两组数据中最长的共同元素组。根据定义，从原始数据中提取这些组，就可以确定两组数据之间的最小非共同元素。
算法完全封装在一个名为compare<>的类中，该类实现了在cmp命名空间内。cmp::compare<>是一个模板类，它使用一个数据源类来提供数据。这意味着算法完全独立于数据，以及数据的表示形式。
为了演示，提供了两种数据源。第一种是模板类cmp::data_source<>，它可以用于任何基本数据类型，例如比较文本字符串。第二种是cmp::data_source_text_file，用于比较两个文本文件。
为了简化代码，可以使用C++的typedef来定义这些复杂的模板类：
typedef cmp::data_source<const char> compare_data_source_t;
typedef cmp::compare<compare_data_source_t> compare_t;
以下是要比较的数据：
const char str1[] = "little jack horner";
const char str2[] = "sat in a corner";
只需实例化两个数据源，并将数据传递给它们：
compare_data_source_t compare_data1(str1, strlen(str1));
compare_data_source_t compare_data2(str2, strlen(str2));
然后可以实例化cmp::compare<>类：
compare_t compare(&compare_data1, &compare_data2);
最后，可以调用process()方法：
compare_t::result_set seq;
int lcs = compare.process(&seq);
process()方法返回一个整数，表示最长公共子序列的长度。这个返回值本身并不直接用于确定差异，但它可以提供两个有用的信息。返回值-1表示错误，0（零）表示两组数据完全相同。
如果成功返回，seq参数将包含结果序列。这个序列包含了两组数据的记录列表，以及它们与第二组数据的关系信息。每个记录将被标记为KEEP、REMOVE或INSERT。这些标记描述了如何从第一组数据创建第二组数据：
KEEP - 两组数据源中的记录REMOVE - 第一组中有，但第二组中没有的记录INSERT - 第一组中没有，但第二组中有的记录LCS实现对内存分配要求较高。它需要n*m*sizeof(short)字节的存储空间，其中n和m是每组数据中的记录数。例如，比较两个1KB的数据集需要1MB的存储空间！
为了克服这种开销，比较更大的数据块，并细分不同的块，然后对这些块执行单独的LCS过程。例如，cmp::data_source_text_file类按行比较文本文件，以产生类似于版本控制系统的结果，识别两个文件中哪些行是不同的。要识别文本文件中的字符变化，可以将不同的每一行通过cmp::data_source<char>传递，如第一个示例所示。