7

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

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

"fox jump(ed|ing|s)"

会给我们

"fox,jumped,jumping,jumps"

另一个例子是

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

这会给我们

"fox,jump"

因为可选运算符

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

为什么？ 我正在尝试将一堆文本与大量正则表达式进行匹配。如果我可以获得这些“必需”的正则表达式的“关键字”列表，我可以对该关键字进行快速文本搜索以过滤我关心的正则表达式（忽略那些我保证不匹配甚至跳过该文本完全有效地不在文本上运行任何正则表达式，因为我们保证在我们的正则表达式集中没有匹配项）。我可以在一个有效的数据结构（Binary Search/Trie/Aho-Corasick）中组织这组关键字，以在我尝试通过有限自动机运行文本之前过滤这组正则表达式。在尝试运行正则表达式之前，我可以将一些非常快速的字符串匹配算法作为过滤阶段运行。我'

4

2 回答 2

0

如果我正确理解了您的问题，那么您正在寻找一组单词，使得所有这些单词都是（给定的）正则表达式接受的任何单词的（不相交的）子字符串。

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

为了找到这样一个集合，我提出了以下算法：

  1. 找到与您的输入正则表达式对应的 FA。
  2. 识别起始状态 S 和接受状态 F 之间的桥梁 ( https://en.wikipedia.org/wiki/Bridge_(graph_theory ) )。例如，这可以通过删除边 E 并询问是否存在来自 S 的路径来完成删除 E 的 FA 中的 E - 对所有边缘重复此操作。
  3. 在接受运行期间，所有作为桥梁的边都必须被击中，并且每条边对应于一个输入字母。
  4. 您现在可以通过端到端连接后续桥边来生成所需的单词。

我认为从算法构造来看，FA（而不是 DFA）足以使其工作。再一次，证明会很好，但我认为它应该有效:)

于 2013-01-04T23:21:31.253 回答
0

请参阅给定正则表达式的库Xeger将为您提供所有可能匹配的字符串。

您似乎只想保留这些字符串的公共前缀（您说要忽略可选运算符的部分），但如果您这样做，您可能会捕获具有该公共前缀但没有您想要的结尾的字符串（例如“跳跃”在你的例子中）。如果这不是问题，那么只需找到 Xeger 给出的最短字符串，假设可选运算符仅出现在正则表达式的末尾。

于 2014-11-15T10:44:55.597 回答