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

是否有一种算法可以从一组字符串生成正则表达式（可能仅限于简化语法），以便对与正则表达式匹配的所有可能字符串进行求值，从而重现初始字符串集？

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

foo(a|b|cd)bar应该匹配fooabar, foobbar and foocdbar.

Examples

给定一组字符串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) would not 是正确的，因为它扩展到 4 个字符串，包括h_p2_b，这不在原始字符串集中。

Use case

我有一长串标签，它们都是通过将子字符串放在一起生成的。我不想打印大量的字符串列表，而是希望有一个紧凑的输出来指示列表中的标签。由于完整列表是通过编程方式生成的（使用有限的前缀和后缀集），我预计紧凑符号（可能）比初始列表短得多。

（（简化的）正则表达式应该尽可能短，尽管我对实用解决方案比最佳解决方案更感兴趣。简单的答案当然是连接所有字符串，例如 A|B|C|D|...然而，这并没有帮助。）

如果您想要找到一组字符串的最小有限状态机 (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 最小化是一个经过充分研究的问题。这霍普克罗夫特算法是最坏的情况O(NS log N)算法，其中N是 DFA 中的状态数量，S是字母表的大小。通常情况下，S将被视为常数；无论如何，Hopcroft 算法的预期时间要好得多。

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