是否有提供按模式（正则表达式）查找的数据结构？

Question

我已经多次遇到这种情况：有些文本可能会匹配多种模式，而您想根据其模式来做一些特定的事情。

过去，我一直只使用正则表达式列表，并进行迭代直到找到匹配项。

我想知道的是，是否存在更有效的数据结构。例如，如果我使用的是C＃，则是带有Regex键的Dictionary。

我意识到，如果模式都是前缀或后缀，那么像Trie这样的东西就有意义。我不清楚这是否适用于一般情况。

在我看来，这里的按键碰撞可能还有些含糊；例如，如果某些文本匹配多个模式，应该返回什么？（我认为在这种情况下，不确定的结果可能会很好；但是只要记录了行为，我就可以了。）

无论如何，.NET或其他地方是否存在这样的数据结构？

Answer 1

我们假设这些正则表达式确实是正则表达式。然后，每个都可以转换为非确定性有限自动机，后者可以转换为确定性有限自动机，可以在输入长度的 O(n) 时间内对其进行评估。

但它没有解决同时匹配多个正则表达式的问题。我们可以通过创建一个如下所示的单个正则表达式来实现此目的：(regexp1|regexp2|...)，并将其转换为单个 NFA/DFA。向自动机的分支添加一些工具，以跟踪哪个特定的正则表达式生成与输入匹配的路径，并且您已经得到了匹配器，输入字符串的长度仍然是 O(n)。

此技术不支持任何使语言变得非规则的“正则表达式”功能，例如反向引用。

另一个缺点是生成的 DFA 可能很大。也可以直接评估 NFA，这可能较慢，但具有更好的记忆行为。

实际上，用代码表达这个想法也很容易，而不必担心自动机的问题。只需使用匹配组：

combined_regexp = (regexp1)|(regexp2)|...

在评估时，只需查看哪个组与输入匹配即可。

请记住，大多数正则表达式实现/库在某些极端情况下的行为非常糟糕，它们可能需要指数时间来编译或匹配正则表达式。我不确定这在实践中存在多大问题。Google 的RE2库是专门为避免这种病态行为而设计的库，但可能还有其他库。

另一个问题可能是，除非您的正则表达式实现专门宣传 O(n) 行为，否则它可能只是依次尝试每个替代方案。在这种情况下，这种方法不会给你带来任何好处。