regex - 从正则表达式中提取静态字符串

Question

我正在尝试有效地提取静态字符串( 必须 匹配的字符串才能匹配给定的正则表达式)。我已经能够在最简单的情况下做到这一点，但我正在努力寻找更强大的解决方案。

给定一个正则表达式，如下所示

"fox jump(ed|ing|s)"

会给我们

"fox,jumped,jumping,jumps"

另一个例子是

"fox jump(ed|ing|s)?"

这会给我们

"fox,jump"

由于可选运算符

我现在的算法过于简单。它将从正则表达式的末尾开始并删除组或单个字符后跟这些运算符“*？”以及“爆炸”分组 OR 运算符“(|)”。这工作得很好，但没有考虑到正则表达式的完整语法。您可以将其视为正则表达式的最小集生成过程(正则表达式可以“生成/必须匹配”的最小字符串集)。

为什么？
我正在尝试将一堆文本与大量正则表达式进行匹配。如果我可以获得这些“必需”正则表达式的“关键字”列表，我可以对该关键字进行快速文本搜索以过滤我关心的正则表达式(忽略那些我保证不匹配的正则表达式，甚至跳过该文本完全有效地不在文本上运行任何正则表达式，因为我们保证在我们的正则表达式集中没有匹配项)。在我什至尝试通过有限自动机运行文本之前，我可以在有效的数据结构(二进制搜索/Trie/Aho-Corasick)中组织这组关键字来过滤正则表达式集。在尝试运行正则表达式之前，我可以将速度极快的字符串匹配算法作为过滤阶段运行。通过这个简单的过程，我已经能够将吞吐量提高很多倍。

Answer 1

如果我正确理解您的问题，您正在寻找一组单词，以便所有这些单词都是(给定的)正则表达式接受的任何单词的(不相交的)子串。

我的猜测是，这样的集合通常是空的，但仍然可以找到。

为了找到这样的集合，我提出了以下算法:

找到与您的输入正则表达式相对应的 FA。

识别起始状态 S 和接受状态 F 之间的桥( https://en.wikipedia.org/wiki/Bridge_(graph_theory ))。例如，这可以通过删除边 E 并询问在删除 E 的 FA 中是否存在从 S 到 E 的路径来完成 - 重复此操作所有边缘。

在接受运行期间，所有作为桥的边都必须被击中，并且每条边对应一个输入字母。

您现在可以通过端到端连接后续的桥边来生成所需的单词。

我认为从算法构造可以看出，FA(而不是 DFA)足以使其工作。同样，证明会很好，但我认为它应该有效:)