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

Question

是否存在可以从一组字符串生成正则表达式(可能仅限于简化语法)的算法,以便对与正则表达式匹配的所有可能字符串的求值重现初始字符串集？

使用非常"复杂"的语法(包括任意重复,断言等)为正则表达式的语法找到这样的算法可能是不现实的,所以让我们从一个只允许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 | ...然而,没有帮助.)

Answer 1

如果您想要找到一组字符串的最小有限状态机 (FSM)，那么这个问题有一个直接的解决方案。由于生成的 FSM 不能有循环（否则它将匹配无限数量的字符串），因此仅使用连接和析取 ( ) 运算符就可以轻松转换为正则表达式|。尽管这可能不是最短的正则表达式，但如果您使用的正则表达式库编译为最小化的 DFA，它将生成最小的已编译正则表达式。（或者，您可以直接将 DFA 与 Ragel 等库一起使用。）

如果您可以使用标准 FSM 算法，则过程很简单：

1. 只需将每个字符串添加为状态序列，每个序列都从起始状态开始，即可创建非确定性有限状态自动机 (NFA)。显然，O(N)在字符串的总大小中，因为原始字符串中的每个字符都恰好有一个 NFA 状态。

2. 从 NFA 构造确定性有限状态自动机 (DFA)。NFA 是一棵树，甚至不是 DAG，它应该避免标准算法的指数最坏情况。实际上，您只是在这里构建了一个前缀树，您可以跳过步骤 1 并直接构建前缀树，将其直接转换为 DFA。前缀树的节点数不能多于原始字符数（如果所有字符串都以不同的字符开头，则可以具有相同数量的节点），因此它的输出有O(N)大小，但我没有从顶部证明我的想法是，现在也正是O(N)时候。

3. 最小化 DFA。

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

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

Answer 2

您可以尝试使用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

现在，对于特里树的每个级别/深度，所有刺痛（如果有多个）都将放在OR括号内，因此

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