regex - 如何为正则表达式集合找到 "minimal spanning set"？

Question

上下文:

我有一个很小(目前不到 100 个)但不断增长的正则表达式集合，我想优化确定给定文本字符串的过程，以确定我的集合中哪些 RE 与文本字符串匹配。

一些 RE 具有排序关系——例如，如果我知道字符串 $t 匹配/windows/i，那么我也知道 $t 匹配/windows.*2000/i。因此，在针对我的集合中的 RE 测试 $t 时，如果我已经针对/windows.*2000/i 测试了 $t 并找到了匹配项(尽管/windows.*2000/i 确实如此，那么我可以跳过测试/windows/i不匹配那么我当然不能跳过对/windows/i 的测试)。

请注意，我的集合中没有一个 RE 是完全等价的(对于任何一对 RE，至少有一个文本字符串与一个匹配而另一个不匹配)。

策略:

我想为我的集合中的每个 RE 构建一个有向图 G，并为每对具有排序关系的 RE 构建一个有向边(A -> B 表示“与 A 匹配意味着与 B 匹配”)，并找到一个图的节点的“最小跨越集”(最小节点集 S 使得 G 中的每个节点都位于源自 S 的有向路径上)。

最简单的部分:

有许多免费可用的算法可用于处理有向无环图。因此，一旦为我的 RE 集合构建了图 G(不同的应该保证 G 是非循环的)，我预计找到合适的算法来为 G 找到最小跨度集不会有太大困难。

我需要帮助的地方:

我想找到一种有效的方法来查找我的集合中的 RE 之间的所有排序关系——也许还可以确保集合中没有两个 RE 是等价的(我需要一种方法来自动验证这一点，因为新的 RE 是添加)。

因此，我的(基本上是随机的)网络搜索至少出现了一个合理的说法，即确实存在计算两个 RE 之间存在什么(如果有的话)排序关系的合理方法，但还没有出现对完整算法的任何描述。

有谁知道现有的实现(用于比较 RE)，它相当高效、免费提供，并且(理想情况下)用一种流行的脚本语言或 C/C++ 实现？

Answer 1

我不确定您在需要使用的正则表达式库方面是否具有灵 active ，但您可以查看 RE2谁的Set interface 可以同时匹配多个正则表达式。请注意，RE2 主要使用 DFA 方法，并且不支持其他(主要是回溯)实现所做的所有正则表达式功能。