3

我有一组输入集，每个元素最多包含 50 个字符。想象一个带有 varchar(50) 列的数据库表，每一行都是一个输入集。列数通常在 5-8 范围内。行数通常约为 2-3 百万，但最多可达到 1.5 亿。每列必须有一个非空值。让我们称这个表为 T，它的每一行 RT

我有第二组输入，表示匹配模式。就像原始输入一样，它也可以被视为具有相同固定列数的数据库表（加上匹配目标的元数据，但该部分不相关）。然而，这一次，只有一列必须有一个值，但其中任何一个都可以为空。让我们将此表称为 M，并将其每一行称为 RM。此表的典型大小为 4000 - 5000 行，但最多可达到 40 000。

这里的任务是针对每个 RT，我们必须找到匹配的 RM。以下是给定 RT 的匹配规则：

  1. 如果 RM 的所有元素与 RT 中的相应元素相同，则进行匹配。（字符串完全匹配被认为是相同的）。如果 RM 中的元素为 null，则不检查 RT 是否匹配。

  2. 只有一场比赛是可能的。如果识别出多个匹配，则认为具有最长 RM 的匹配是正确的。这里可以忽略多个 RM 长度相同的情况。我们只选择第一个确定的。

该代码将在具有 4 GB RAM 的典型 Windows 客户端上运行。因此，MT 可以保存在内存中，但 T 不能。

我正在寻找一种减少比较次数的技术。更具体地说，您是否知道可以针对给定 RT 检查整个 MT 的技术。如果不是，那么处理这个问题的最有效方法是什么？

这将在 .NET 中编码，非常感谢任何现有的 .NET 代码或库。

谢谢，

凯末尔

笔记：

  1. 这不是家庭作业。我大约20年前毕业:)

  2. 正则表达式 RM 存在这个问题的变体。但是对于当前版本，具有简单字符串等价的匹配就足够了。

  3. 下面是一些例子：

RT = { A、B、C、D、E}

RM1 = { A,,,, } RM2 = { A, B,,, } RM3 = {A,,,D, E}

对于这个 RT，所有这些都匹配。但由于规则 2，我们选择 RM3 作为匹配项。希望这个例子能澄清

  1. T 数据实际上并未保存在数据库中。它有多种格式，包括 excel、文本、xml 和一些统计软件原生数据文件。我们有一个数据管道结构，可以动态地从它们的本机格式中读取数据并保留一个游标。RT 是该光标的一部分，只是一个字符串数组
4

1 回答 1

0

解决方案应该涉及某种匹配树。目标是遍历每个 RT 的树，直到到达叶节点，此时您可能有多个匹配项，但其中一个是最好的。树中的节点是匹配的（可能是部分匹配，例如{A,,,D,}），如果满足或不满足节点匹配，算法就会落入一个分支或另一个分支。

实现这一点的方法不止一种，要选择一种方法，您首先需要确定多快对您来说足够快。需要考虑的一件事是空间局部性，因为对于大型非优化树算法将像发狂的兔子一样在内存中跳跃，完全无视内存缓存的好处。

让我们假设二叉树已经足够好了。如果匹配满足则算法遵循左分支，否则遵循右分支。因此，对于您的情况，根节点是 match {A,,,,}，完整的树如下（每个节点尝试匹配某些内容，y>如果找到匹配则有一个分支，如果n>没有匹配则有一个分支：

{A,,,,}
 y> {,B,,,}
  y> out, matching {A,B,,,}
  n> {,,,D,E}
   y> out, matching {A,,,D,E}
   n> out, matching {A,,,,}
 n> out, no match

从 M 表编译这个匹配树本身就是一个问题。您应该考虑 T 表中项目的统计出现，以便对于大多数 RT 而言，遍历树尽快结束。

于 2013-09-10T10:20:17.560 回答