高效地搜索正则表达式集合

Question

如果我有一些未知数量的正则表达式（零个或更多，希望少于几千个）搜索与给定字符串匹配的正则表达式的有效方法是什么？

我应该使用什么样的容器、算法and/or数据结构？如果我想找到唯一匹配的正则表达式与我想找到所有正则表达式匹配，这有什么不同吗？这些与只想知道有多少匹配项不同吗？

让我换一种说法，假设我有一个用户输入任意字符串并且我有一些正则表达式容器。我可以按照自己选择的方式设计容器，也可以按照自己选择的方式设计搜索。如果我想要一个与该集合中的用户输入相匹配的所有正则表达式的列表，我该怎么办？如果我只想知道存在多少匹配项怎么办？如果我只是想确保匹配的唯一性怎么办？

Answer 1

一个PHP例子：

<?php
$regex_array = array(
  "/regex_1/" => 0,
  "/regex_2/" => 0,
  "/regex_3/" => 0    // and so on and so forth
);

$strings_array = array(
  "input_string_1",
  "input_string_2",
  "input_string_3"    // and so on and so forth
);

foreach ($regex_array as $key => $value)
  foreach ($strings_array as $current_string)
    if (preg_match($key, $current_string))
      $regex_array[$key]++;
?>

Here是运行代码。

Answer 2

我不会把自己的答案标记为答案，除非几天内没有人打败它。

到目前为止，我唯一有价值的想法是在添加容器时将正则表达式放入容器内的两堆之一。

每个正则表达式都带有一些通配符、字符 class 或任何其他使其偏离常规字符串的内容。我将其称为 RegexPile.

另一堆是所有正则表达式，它们是字符串或可以简单地转换为字符串。因为字符串很容易匹配并且算法很好理解，所以我可以说这堆将是有序的容器并且将被排序，并且通过二进制搜索在其中查找字符串是微不足道的。我将其称为 SortedStringArray.

天真地，我可以线性搜索 RegexPile 并在 SortedStringArray 上进行二进制搜索。这至少让我可以跳过一些比较，并且在时间或 space 方面花费很少，但也没有太多真正的优化。

它在计算上是相似的，但如果我做这样的事情，我想我会为 RegexPile 中的每个正则表达式（或每个小组的正则表达式）启动一个线程。我的想法是，任何给定的正则表达式都可以使用无限量，因为正则表达式可以做到这一点。然后，如果任何线程花费的时间太长，我可能会因超时而失败并过早终止所有线程。我还认为大多数人会在第一个字符上失败，这意味着一旦检查了第一个字符，大多数线程就会消失。现在大多数系统都提供廉价的写时复制线程，这个线程生成应该足够便宜，以至于在我完成所有线程生成之前许多线程将关闭，并且只有非常相似的线程会一直存在。然后我在另一个线程中为 SortedStringArray.

执行二进制文件

Answer 3

如果您可以在尝试将字符串与它们匹配之前对正则表达式进行一些预计算，那么您可以将所有这些的并集转换为 DFA，它可以同时将一个字符串与所有这些进行匹配.

参见：https://en.wikipedia.org/wiki/Deterministic_finite_automaton

这种方法经常用于解析器和编译器中的词法分析（标记化）。 DFA 的好处是无论您放入多少正则表达式或它们有多复杂，它的速度都是一样的（快）。

这不是那么容易，但周围有工具。如果您在 Java 工作，那么我有一个您可以使用的开源项目：http://mtimmerm.github.io/dfalex/。要回答您的其他问题，您可以根据需要从中获取所有匹配正则表达式的集合。

如果您对如何自己动手感兴趣，该过程通常包括将您的正则表达式转换为 NFA (https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton) using Thompson's construction (https://en.wikipedia.org/wiki/Thompson%27s_construction), and then converting the NFA into a DFA using subset construction (https://en.wikipedia.org/wiki/Powerset_construction), and then usually minimizing the DFA with Hopcroft's algorithm (https://en.wikipedia.org/wiki/DFA_minimization)

有很大的优化和技巧空间。

祝你好运！

P.S。我应该注意几件事：1) 你通常不能从具有反向引用的正则表达式中创建 DFA。 2) 理论上 DFA 有可能呈指数级增长。这几乎不会是偶然发生的，但是如果您的正则表达式被潜在的恶意人员输入，那么您将不得不对这种可能性采取一些措施。

高效地搜索正则表达式集合

Searching a Collection of Regexes Efficiently

regex

language-agnostic

algorithm

containers