最小差值

• 下载源代码和演示 - 12 KB

引言

计算两组数据之间的最小差异是一项常见要求。`compare<>`类可用于识别任意类型的两组数据之间的最小差异。它是一个模板类，使用通用数据源类接口为其提供数据。这意味着该算法完全独立于数据以及数据的表示形式。

算法

计算两个数据集之间的最小差异，就是反过来解决问题，计算*最长公共子序列*，并使用其结果来确定差异。关于LCS问题，在互联网和研究论文中有详细记录。我实现了加利福尼亚大学David Eppstein教授描述的迭代LCS算法。LCS将识别两个源之间最长的公共元素组。根据定义，从原始数据中提取这些组将识别两个源之间最小的非公共元素。

实现

该算法完全封装在一个类中，即在`cmp`命名空间中实现的`compare<>`。`cmp::compare<>`是一个模板类，使用数据源类实例化，以提供其数据。我包含了两个数据源以供演示。第一个是另一个模板类，称为`cmp::data_source<>`。这可以用于任何基本数据类型，例如比较两个文本字符串。第二个是`cmp::data_source_text_file`，用于比较两个文本文件。

cmp::data_source<> 示例

为了使生活更轻松，我们可以`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`，如第一个示例所示。

联系方式

网站	http://homepage.virgin.net/cdm.henderson
电子邮件	cdm.henderson@virgin.net