2

我正在构建一个电子邮件过滤器，我需要一种有效地将单个电子邮件与大量过滤器/规则匹配的方法。可以在以下任何字段中匹配电子邮件：

  • 来自名字
  • 从地址
  • 发件人名称
  • 发件人地址
  • 学科
  • 邮件正文

目前有超过 5000 个过滤器（并且还在增长），它们都定义在我们的 PostgreSQL (9.1) 数据库的一个表中。每个过滤器可能有 1 个或多个上述字段填充了 Python 正则表达式。

当前进行过滤的方式是选择所有过滤器并将它们加载到内存中。然后，我们对每封电子邮件进行迭代，直到在所有非空白字段上找到正匹配。不幸的是，这意味着对于任何一封电子邮件，都可能有多达 30,000 (5000 x 6) 次 re.match 操作。显然，随着添加更多过滤器，这不会扩展（实际上它已经没有）。

有一个更好的方法吗？

到目前为止我考虑过的选项：

  1. 将保存的 python 正则表达式转换为 POSIX 样式的，以利用 PostgreSQL 的 SIMILAR TO 表达式。这真的会更快吗？在我看来，它只是将负载转移到其他地方。

  2. 基于每个用户定义过滤器。虽然这并不实际，因为我们的系统用户实际上受益于大量预定义的过滤器。

  3. 切换到基于文档的搜索引擎，例如弹性搜索，其中将要过滤的第一封电子邮件保存为规范表示。通过找到类似的电子邮件，我们可以缩小到特定的功能集进行测试并获得肯定的匹配。

  4. 切换到贝叶斯过滤器，这也将给我们一些机器学习能力来检测类似的电子邮件或对现有电子邮件的更改，这些邮件仍然具有足够高的概率来猜测它们是同一件事情。这听起来很酷，但我也不确定它是否会扩展得特别好。

是否有其他选择或方法需要考虑？

4

2 回答 2

3

PostgreSQL 9.1 版中的三元组支持可能会给您想要的。

http://www.postgresql.org/docs/9.1/interactive/pgtrgm.html

它几乎肯定会在 9.2（计划于 2012 年夏天发布）中成为一个可行的解决方案，因为新版本知道如何使用三元索引来快速匹配正则表达式。在我们的商店中，我们发现三元索引的速度非常好。

此外，如果您想要进行“最近邻”搜索，您可以根据与搜索参数的相似性找到 K 个最佳匹配项，那么三元索引非常棒——它实际上从索引扫描中返回按“距离”顺序排列的行”。搜索 KNN-GiST 以获取文章。

于 2012-04-18T17:42:06.600 回答
0

这些正则表达式有多复杂？如果它们真的是正则表达式（没有所有疯狂的 python 扩展），那么您可以将它们全部组合成一个正则表达式（作为替代方案），然后使用一个简单的（即内存中的）正则表达式匹配器。

我不确定这是否可行，但我怀疑您会惊喜地发现正则表达式编译成一个小得多的状态机，因为它将合并常见状态。

另外，对于快速的正则表达式引擎，可以考虑使用nrgrep来快速扫描。当从一个标题跳到下一个标题时，这应该可以加快您的速度（我自己没有使用它，但他们是朋友的朋友，当我阅读时，论文看起来很整洁）。

于 2012-04-18T19:19:10.453 回答