65.9K
CodeProject 正在变化。 阅读更多。
Home

组合正则表达式搜索

Farhad Alizadeh Noori
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.98/5 (22投票s)

2013年11月10日

CPOL

9分钟阅读

viewsIcon

61360

downloadIcon

1312

本文详细介绍了一种高效的分组正则表达式搜索器的实现。

引言

我最近发现自己处于一种需要搜索一组正则表达式并在给定文档中查找它们所有匹配项的境地。当然，我可以使用 grep 等工具来完成。但我实际上想在应用程序中使用它，而正则表达式代表了某些对象，如果匹配成功，我之后还需要访问它们并进行进一步处理。总之，说服你自己 grep 和类似的工具不适用于这种情况。

一种简单的方法是遍历所有正则表达式并将它们应用于文本。所有正则表达式结果的并集就是搜索结果。这并不是非常高效，因为当前正则表达式引擎的实现（例如 a(BC)\1 匹配 aBCBC）具有回溯功能，其性能会随着正则表达式的大小呈指数级增长。这包括几乎所有常见的编程语言（C#、VB.NET、Java、Python 等）。我也注意到，我并不真正需要这些引擎的回溯功能。我只需要一个非常快速的搜索，可以搜索一组可能成千上万的正则表达式。我需要正常的正则表达式功能，如交替(|)、克莱恩星号(*)、可选子串(?)以及不需要回溯的这类运算符（没有前瞻和后顾）。虽然这限制了系统的能力，但它允许为此任务使用非常高效的数据结构。我在网上找不到任何实现，于是我决定自己动手。

背景

为了理解其中涉及的操作，你需要复习一些计算机科学概念。我将尽力在这里呈现这些想法，以便文章能够相对自给自足。我们将从介绍一些用于表示字符串的正式方法开始。我决定不使用计算机科学的符号来描述它们，因为它们有时可能会让新手感到畏惧。

有限状态机 (FSM)

有限状态机是旨在表示系统的数学模型，其中该系统的行为可以通过一系列状态和这些状态之间的转换来描述。例如，可以考虑通过海关的过程。你从一个初始状态开始，声明你是否有任何需要申报的物品。你填写的文档可以被认为是第一个状态的输入。根据此输入，你可能会转换为代表绿色通道或红色通道的状态，之后你可能会转换为不同的状态。

另一种可能性是将字符串表示为 FSA。为了我们的搜索器，我们将字符串表示为 FSM 或 FSA（有限状态自动机）。在下面的图片中，你可以看到一个由 FSA 表示的字符串的示例。我使用了Graphviz的工具来绘制我的 FSM。

正如在图像中看到的，状态并没有真正代表任何有用的东西，或者你可以说它们代表字符串中的索引。标签，我们稍后会看到，目前对我们来说并不重要。请注意，转换是字符串的实际字符。我们在这里使用 FSA 的原因是，假设你想匹配字符串（abcc）与上面的 FSA，你只需要从初始状态开始，沿着转换路径，看看是否能到达“匹配状态”。这里的匹配状态是最右边的状态。

FSA 可以有自循环；这意味着你可能会通过一次转换回到同一个状态。它们也可以拥有某些类型的转换，称为 epsilon 转换。这些类型的转换允许在不接收任何输入的情况下转换到另一个状态。它们也可能具有同一个输入的多个转换。例如，在我们表示字符串的 FSA 的例子中，我们可以通过输入“a”从一个状态转换到两个不同的状态。

非确定性有限状态自动机 (NFA)

这些实际上是我们到目前为止所描述的 FSM。它们对转换没有任何限制。由于它们可以对同一个输入有多个转换，并且它们也有 epsilon 转换，因此它们被称为非确定性的。例如，在匹配由 NFA 表示的一系列字符串时，你实际上无法确定地决定要采取哪个转换。在这一点上，认识到 NFA 可用于表示多个字符串是很重要的。准确地说，NFA 可以表示在乔姆斯基等级制度下被归类为正则语言的一种语言。由 NFA 表示的任何语言都是正则的，任何正则语言都可以由 NFA 表示。稍后我们将回到这一点。

在上图的 NFA 中，可以看到它具有 epsilon 转换（没有标签的转换）。该图表示“ab*(cd|fg)?”正则表达式。

确定性有限自动机 (DFA)

DFA 是一种 FSA，其转换受到一定的限制。限制如下：

  • 不允许 epsilon 转换。
  • 对于每个唯一的输入，您最多只能有一个转换。例如，在我们字符串 FSA 中，从给定状态出发，我们不能有两个以上的“a”转换。

您需要每个转换都有一个唯一的输入这一事实意味着您可以始终确定地判断是否存在一个转换以及在执行该转换时您会去哪里。DFA 也表示正则语言，任何 NFA 都可以使用我们稍后将实现的子集构造算法转换为等效的 DFA。

方法论

我们将从解析我们的正则表达式并将其转换为 NFA 开始。这很直接。嗯，可以说是。更复杂的部分是解决运算符优先级并实际正确解析正则表达式。

我使用 Dijkstra 的移位-规约算法实现了这个解析过程。简而言之，该算法使用两个堆栈来压入运算符和操作数。你基本上从左侧开始，不断地将运算符和操作数添加到这两个堆栈中。当一个运算符被压入堆栈，并且它的优先级低于堆栈顶部元素时，所有已压入的操作都会使用另一个堆栈中的已压入操作数进行执行。在处理完所有这些操作后，结果将被压入操作数堆栈。这会一直持续到正则表达式处理完毕。我不会详细介绍这个过程，因为互联网上已经有相关资料了。例如，你可以从这里开始。

到目前为止，我们已经能够将正则表达式转换为 NFA。从这里开始，有两种方法可以搜索一系列 NFA。一种方法是对每个正则表达式运行子集算法，然后将它们合并在一起；另一种方法是将所有正则表达式合并在一起，然后在创建的大型自动机上运行子集算法。我认为前者方法更有效，因为子集算法本身并不高效，通过在较小的自动机上运行它然后进行合并，我们可以节省一些时间。

无论我们是在合并过程之前还是之后运行子集算法，我们仍然需要将所有这些解析后的正则表达式分组在一起。我们可以通过将所有正则表达式“或”在一起来实现。我通过添加一个初始状态并将 epsilon 转换指向所有创建的 NFA 的开头来做到这一点。在此步骤之后，我从这个巨大的 NFA 创建一个 DFA。请注意，即使我们已经从每个正则表达式创建了 DFA，合并产生的自动机仍然是一个 NFA。

由此产生的 NFA 现在在一个漂亮的模型中表示了所有分组的正则表达式。请注意，我们将搜索减少为只匹配这个最终 NFA 中的单词。现在我们可以运行子集算法来消除 NFA 中的冗余。从技术上讲，产生的 DFA 可以进一步简化，得到一个最少状态数的简化 DFA。将 DFA 转换为简化 DFA 的算法是高效的。真正的问题在于将巨大的 NFA 转换为 DFA（状态数量呈指数级增长），但正如您在实践中会看到的，这通常不是问题。

我将尽快更新这篇文章，介绍 DFA 简化算法。

如果您需要有关此算法的更多信息，可以访问此维基百科页面，其中描述了 Aho-Corasick字符串匹配搜索。

Using the Code

代码和算法中存在一些你应该注意的假设。首先，当前支持的运算符集如下：

  • 克莱恩星号(*) 和 +
  • 交替 (|)
  • 可选运算符(?)
  • 括号

当然，这个列表可以轻松扩展，只要运算符不强制要求后视、前视或回溯。如果你已经有一组正则表达式，你需要做的是检查它们是否具有支持的运算符。它们不应该包含任何不支持的运算符。如果你在添加运算符方面有任何问题，请告诉我，我会尽力为你添加。

这是一个测试程序

class Program
{
    static void Main(string[] args)
    {
        FSM NFA = GetOredRegexes();
 
        string syt = NFA.GetDotRepresentation() + "\n";
        FSM DFA = NFAToDFA.ConvertNFAToDFA(NFA);
 
        DrawWithGraphviz(NFA, "NFA");
        DrawWithGraphviz(DFA, "DFA");
    }
 
    private static void DrawWithGraphviz(FSM FSA, string fileName)
    {
        ProcessStartInfo info = new ProcessStartInfo();
        info.Arguments = string.Format(@"-Tjpg -o C:\GraphvizOutput\{0}.jpg", fileName);
        info.FileName = @"c:\Program Files (x86)\Graphviz2.34\bin\dot.exe";
        info.UseShellExecute = false;
        info.RedirectStandardInput = true;
 
        using (Process proc = Process.Start(info))
        {
            StreamWriter sw = proc.StandardInput;
            string syt = FSA.GetDotRepresentation() + "\n";
            sw.Write(syt);
        }
    }
 
    private static FSM GetOredRegexes()
    {
        List<Regex> regexes = new List<Regex>();
 
        regexes.Add(new Regex("ab*(cd|fg)?"));
        regexes.Add(new Regex("ab(bas|umusa)"));
        regexes.Add(new Regex("abc(de)*"));
        regexes.Add(new Regex("ab(cd|de)gph*"));
        regexes.Add(new Regex("a(cd)?dg"));
 
        FSM oredNFA = new FSM();
        regexes.ForEach(regex => oredNFA |= FSM.Parse(regex.ToString()));
        return oredNFA;
    }
}

这是上述代码段的输出

NFA

产生的 DFA

如上所述，初始 NFA 中的状态数量被大大减少以生成 DFA。每个状态只有一个转换这一事实意味着，在进行匹配时，任何时候我们只需要关注 DFA 中的当前位置。这与 NFA 不同，NFA 允许同一个字符有多个输出，我们需要携带所有不同位置的指针。总而言之，搜索更加快速、简单和优雅。

历史

  • 2013年11月2日 - 初稿...
  • 2013年11月11日 - 发布 1.0
  • 2013年12月10日 - 发布 1.1 修正文本中的拼写错误
  • 2014年1月14日 - 发布 1.2 修正文本中的拼写错误
  • 2014年2月1日 - 发布 1.3 修复了像 a*b 这样的模式的 bug
© . All rights reserved.