确定给定输入集匹配集的算法

Question

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

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

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

1. 如果RM的所有元素与RT中的对应元素相同，则进行匹配。(字符串完全匹配被视为相同)。如果RM中的元素为null，则不检查RT是否匹配。
2. 只有一个匹配是可能的。如果识别出多个匹配项，则认为RM最长的匹配是正确的。这里可以忽略具有相同长度的多个RM的情况。我们只挑出第一个识别出来的。

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

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

这将在.NET中进行编码，并且非常感谢用于.NET的任何现有代码或库。

谢谢,

凯末尔

备注：

1. 这不是家庭作业。我大约20年前毕业:)
2. 正则表达式均方根是这个问题的一个变体。但是对于当前版本来说，具有简单的字符串等价性的匹配就足够了。
3. 以下是一些例子：

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

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

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

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

Answer 1

解决方案应该涉及某种匹配树。目标是遍历每个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表中尽可能快地结束遍历树。