找到最简单的正则表达式，匹配所有给定的字符串。

Question

找到最简单的正则表达式，匹配所有给定的字符串。

regexstringalgorithmpattern-matchinggrammar-induction

10

是否存在一种算法可以从一组字符串中生成一个正则表达式（可能仅限于简化语法），使得匹配该正则表达式的所有可能字符串都能够产生初始的字符串集？

对于具有非常“复杂”语法（包括任意重复、断言等）的正则表达式语法，找到这样的算法可能不现实，因此让我们从一种只允许子串OR的简化版本开始：

foo(a|b|cd)bar应匹配fooabar，foobbar和foocdbar。

示例:

给定字符串集h_q1_a、h_q1_b、h_q1_c、h_p2_a、h_p2_b、h_p2_c，算法的期望输出为h_(q1|p2)_(a|b|c)。

给定字符串集h_q1_a、h_q1_b、h_p2_a，算法的期望输出为h_(q1_(a|b)|p2_a)。请注意，h_(q1|p2)_(a|b)不正确，因为它会扩展到4个字符串，包括原始字符串集中没有的h_p2_b。

用例:

我有一个很长的标签列表，它们都是通过组合子字符串生成的。我希望有一个紧凑的输出来指示列表中有哪些标签。由于完整列表是通过程序（使用一组有限的前缀和后缀）生成的，因此我期望紧凑的符号表示比初始列表要短得多。（简化后的）正则表达式应该尽可能地短，尽管我更关心实际解决方案而不是最优解。当然，微不足道的答案就是将所有字符串连接起来，例如A|B|C|D|…，但这并不是有益的。

- fuenfundachtzig

3

这意味着匹配正则表达式的所有可能字符串的评估都能够准确地再现初始字符串集合，而不是超集。 - fuenfundachtzig

假设您有一组有限的字符串，您将永远不会使用*，因此只剩下连接和选择。您可以尝试使用前缀树进行操作，这就是算法sowrov链接将为您构建的内容。 - G. Bach

1

Emacs Lisp有一个名为regexp-opt的函数。请参见源代码和描述。该代码有很好的注释，因此您可能能够移植其中的一些内容。 - legoscia

+1 非常好的问题，但是你是指 h_(?:q1|p2)_[a-c]，对吧？ :) - zx81

你确定需要使用 ?: 吗？但是你说的 [a-c] 比 (a|b|c) 更短。通常，子字符串会比一个字符更长。 - fuenfundachtzig

2个回答

3

你可以尝试使用Aho-Corasick算法从输入字符串中创建有限状态机，然后生成简化的正则表达式应该相对容易。以下是您的输入字符串示例：

h_q1_a
h_q1_b
h_q1_c
h_p2_a
h_p2_b
h_p2_c

将生成一个有限状态机，大多数情况下会像这样：

      [h_]         <-level 0
     /   \
  [q1]  [p2]       <-level 1
     \   /
      [_]          <-level 2
      /\  \
     /  \  \
    a    b  c      <-level 3

现在对于Trie树的每个层级/深度，所有字符串（如果有多个）都将放置在OR括号下面，因此

h_(q1|p2)_(a|b|c)
L0   L1  L2  L3

- sowrov

假设实现在这里是正确的，但它不起作用，因为该算法在第二层没有收敛到一个节点。（这是我所知道的所有前缀树的问题。） - fuenfundachtzig

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

如果您想找到一组字符串的最小有限状态机（FSM），则此问题有一个简单的解决方案。由于结果FSM不能具有循环（否则它将匹配无限数量的字符串），因此仅使用连接和分支（|）运算符即可将其转换为正则表达式。尽管这可能不是最短的正则表达式，但如果您使用的正则表达式库编译为最小化的DFA，则会得到最小的编译后正则表达式。（或者，您可以直接使用像Ragel这样的库与DFA一起使用。）

如果您可以访问标准FSM算法，则该过程很简单：

只需将每个字符串作为状态序列添加到非确定有限状态自动机（NFA）中，每个序列都从起始状态开始。显然，总字符串大小的时间复杂度为O(N)，因为原始字符串中将恰好有一个NFA状态对应一个字符。
从NFA构建确定性有限状态自动机（DFA）。NFA是一棵树，甚至不是DAG，这应该避免了标准算法的指数最坏情况。实际上，在这里你只是构建了一个前缀树，你可以跳过步骤1，直接构建前缀树，并将其直接转换为DFA。前缀树的节点数量不能超过原始字符数（如果所有字符串以不同的字符开头，则节点数可以相同），因此其输出大小为O(N)，但我没有证明它在时间上也是O(N)。
最小化DFA。

DFA最小化是一个经过深入研究的问题。Hopcroft算法是最坏情况下具有O(NS log N)时间复杂度的算法，其中N是DFA中状态的数量，S是字母表的大小。通常，S将被视为常数；无论如何，Hopcroft算法的期望时间要好得多。

对于非循环DFA，存在线性时间算法；最常引用的算法是Dominique Revuz提出的，我在这里的英文描述中找到了一个粗略的描述；原始论文似乎需要付费才能获取，但是Revuz的论文（法语）是可用的。