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

我有一个小的(目前不到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++实现？