如何为正则表达式集合找到"最小生成集"？

Question

背景:

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

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

请注意,我的集合中的所有RE都不是完全等效的(对于任何一对RE,至少有一个匹配一个的文本字符串与另一个不匹配).

战略:

我想构建一个有向图G,其中有一个节点用于我的集合中的每个RE,并且每对RE的有向边具有排序关系(A - > B表示"匹配A意味着与B匹配"),并找到一个图的节点的"最小生成集"(节点S的最小集合,使得G中的每个节点位于源自S的有向路径上).

简单的部分:

有很多免费的算法可用于定向非循环图.因此,一旦为我的RE集合构建了图形G(这是不同的,应该保证G是非循环的),我不希望找到一个合适的算法来寻找G的最小生成集.

在哪里我需要帮助:

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

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

有没有人知道现有的实现(用于比较RE),这些实现是合理有效的,可免费获得的,并且(理想情况下)是用一种流行的脚本语言或C/C++实现的？

Answer 1

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