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

Question

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

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

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

Answer 1

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

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

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

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

如果您对如何自己做感兴趣，这个过程通常包括使用 Thompson 的构造 (https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton) 将您的正则表达式转换为 NFA (https://en.wikipedia.org/wiki/Thompson%27s_construction)，然后使用子集构造 (https://en.wikipedia.org/wiki/Powerset_construction)，然后通常使用 Hopcroft 算法最小化 DFA (https://en.wikipedia.org/wiki/DFA_minimization)

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

祝你好运!

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