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

有没有一种算法可以从一组字符串中产生一个正则表达式（可能仅限于一种简化的语法），从而评估匹配正则表达式的所有可能的字符串，从而再现最初的一组字符串？

为非常“复杂”的语法（包括任意重复，断言等）的正则表达式语法找到这样的算法可能是不切实际的，因此，让我们从一个简单的算法开始，它只允许子字符串的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 | ...然而，这并没有帮助。）

---

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

---

如果你想找到的是一组字符串的最小有限状态机（FSM），这个问题有一个直接的解决方案。 由于生成的FSM不能有循环（否则它将匹配无限数量的字符串），所以使用仅连接和分离（ | ）运算符应该很容易转换为正则表达式。 虽然这可能不是最短的正则表达式，但如果使用的正则表达式库编译为最小化的DFA，它将导致最小的编译正则表达式。 （或者，您可以直接在Ragel这样的库上使用DFA。）

该过程很简单，如果您有权访问标准的FSM算法：

通过将每个字符串添加为一系列状态来制作非确定性有限状态自动机（NFA），每个序列从开始状态开始。 由于原始字符串中的每个字符只会有一个NFA状态，因此显然在字符串的总大小中为O(N) 。

从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的论文（法文）是可用的。

链接地址: http://www.djcxy.com/p/70639.html

上一篇: Find simplest regular expression matching all given strings

下一篇: What is the IE equivalent for webkit overflow scrolling : touch