10

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

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

foo(a|b|cd)bar应该匹配fooabar和。foobbarfoocdbar

例子

给定一组字符串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|...然而，没有帮助。）

4

2 回答 2

4

如果您要查找的是一组字符串的最小有限状态机 (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)算法，其中是NDFA 中的状态数，S是字母表的大小。通常，S将被视为常数；无论如何，Hopcroft 算法的预期时间要好得多。

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

于 2013-04-04T16:06:15.620 回答
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
于 2013-04-04T10:55:22.357 回答