给定一组输入，查找匹配集的算法

Question

3

我有一组输入集，每个元素由最多50个字符组成。可以将其视为一个具有varchar（50）列的数据库表格，每行表示一个输入集。列数通常在5-8范围内。行数通常约为200-300万，但可能高达1.5亿。每个列必须具有非空值。让我们称此表为T，每行为RT。

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

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

1.如果RM的所有元素与RT中的相应元素相同，则会进行匹配（字符串完全匹配被视为相同）。如果RM中的元素为空，则不检查RT是否匹配。 2.只有一个匹配是可能的。如果识别出多个匹配，则最长的RM被认为是正确的。多个RM长度相同的情况可以忽略。我们只选择识别的第一个。

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

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

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

谢谢，

Kemal

注意：

1.这不是作业。我毕业已经20年了 :)

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

3.以下是一些示例：

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

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

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

实际上，T数据并没有存储在数据库中。它以多种格式存在，包括Excel、文本、XML和一些统计软件原生数据文件。我们有一个数据管道结构，可以动态读取其原始格式的数据并保持游标。RT是该游标的一部分，仅仅是一个字符串数组。

- Kemal Erdogan

这听起来像是一道作业练习，所以：你目前尝试了什么？[SO]会帮助回答问题，但我们更希望您自己尝试并寻求帮助来进步。 - Richard

1

我们需要完整的匹配规则，以使M中的项目遵循。RM是正则表达式还是其他什么东西？ - Dialecticus

我认为你应该给出一些RM和RT的示例，以及它们如何匹配。 - Daniel Hilgarth

2

只是为了澄清一下：您没有包含数据的数据库，提到表只是为了解释，对吗？ - Christian Severin

@ChristianSeverin 的问题很好：你的实际数据结构是什么？ - Daniel Hilgarth

@Christian：是的，数据不在数据库中。它实际上以多种格式存在，包括Excel、文本、XML和一些统计软件原生数据文件。 - Kemal Erdogan

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dialecticus · Answer 1

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

有多种实现方法可供选择，要选择一种方法，首先需要确定您需要多快才够快。需要考虑的一件事是空间局部性，因为对于一个大型未经优化的树，算法将像疯狂的兔子一样在内存中跳来跳去，并完全忽略内存缓存的好处。

假设二叉树已经足够好了。如果满足匹配，则算法遵循左分支，否则遵循右分支。因此，对于您的情况，根节点是匹配项{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，遍历树尽快结束。