如何高效地将输入字符串与多个正则表达式同时匹配？

Question

如何高效地将输入字符串与多个正则表达式同时匹配？

regexrestpattern-matching

12

如何高效地将一个输入字符串与任意数量的正则表达式匹配？其中一个可能有用的场景是 REST Web 服务。假设我为 REST Web 服务的公共接口想出了许多 URL 模式:

/user/with-id/{userId}
/user/with-id/{userId}/profile
/user/with-id/{userId}/preferences
/users
/users/who-signed-up-on/{date}
/users/who-signed-up-between/{fromDate}/and/{toDate}
…

这里的{...}是指具有命名占位符（类似于正则表达式捕获组）的位置。可以假设这些命名占位符通常不会出现在模式的开头（但它们可能会）。也可以安全地假定任何字符串都不可能匹配多个模式。

现在，Web 服务收到请求。可以逐个将请求的 URI 与一个 URL 模式进行匹配，然后再与下一个进行匹配，以此类推；但对于必须检查的更多模式来说，这可能不会很好地扩展。

有没有有效的算法可以解决这个问题？

输入：

一个输入字符串
一组“互斥”的正则表达式（即任何输入字符串都不能匹配超过一个表达式）

输出：

输入字符串匹配的正则表达式（如果有）。

- stakx - no longer contributing

5个回答

5

标准的解决方法是使用词法分析器生成器，例如Flex（有许多这样的工具可用，通常为每种编程语言提供几个）。这些工具将一组与“令牌”相关的正则表达式（将令牌视为正则表达式匹配的名称）生成有效的有限状态自动机，以同时匹配所有正则表达式。这是线性时间，在输入流的大小上具有非常小的常数；很难要求比此更快的速度。你向它提供字符流，它会输出最佳匹配的正则表达式的令牌名称（处理两个正则表达式可以匹配相同的字符串的情况，请参见词法分析器生成器的定义），并通过识别的内容来推进流。因此，您可以再次应用它来匹配一系列标记的输入流。

不同的词法分析器生成器将允许您以不同的方式捕获已识别的流的不同部分，因此您可以在识别标记后挑选出您关心的部分（例如，对于带引号的文字字符串，您只关心字符串内容，而不是引号）。

- Ira Baxter

尽管我对这个解决方案有一个问题，即所有模式都必须由外部工具预处理，这可能会使更改自己程序配置变得更加复杂。当然，可以在自己的程序中复制lex/flex等的行为，但这可能有点过度设计。 - stakx - no longer contributing

@stakx：如果你想要高效率，那么词法分析器生成器就是答案。如果你不想要重建的代价，那么你必须自己复制它（或选择一个具有内置库的语言，我相信Java的正则表达式可以做到这一点）。对于你提出的RESTful服务示例，我认为使用外部词法分析器增加了构建复杂性并没有增加任何真正的困难：它只是在你的构建过程中增加了一个步骤。 - Ira Baxter

3

如果在url结构中存在层级关系，应该利用它来最大化性能。只有以 /user/ 开头的url可以匹配前三个等级的任意一个，以此类推。

我建议将要匹配的层次结构存储在与url层次结构对应的树中，其中每个节点匹配层次结构中的一级。为了匹配url，将url与所有具有正则表达式 "user "和 "users" 的节点的根进行测试。匹配的url将被测试其子节点，直到在叶子节点中找到匹配项。成功匹配可以作为从根到叶子节点的节点列表返回。从成功匹配的节点中可以获取带有属性值（如 {user-id}）的命名组。

- Anders Forsgren

1

使用命名表达式和OR运算符，即"(?P<re1>...)|(?P<re2>...)|..."。

- pyroscope

2

这样做的性能不会和顺序测试re1、re2等并在第一次匹配时停止大致相同吗？ - Anders Forsgren

@Anders：不一定。如果匹配器实现得很蠢，那么是的，但是这种匹配的高效解决方案已经有很长时间了。请参见我关于词法分析器生成器的答案。 - Ira Baxter

@Ira 当然可以，但是这个建议的答案并不涉及那种类型的词法分析器，只是将所有正则表达式合并成一个具有多个命名组的正则表达式，如果我正确地理解了答案（以及.NET的正则表达式如何工作）。 - Anders Forsgren

1

@Anders：这可能是.NET正则表达式的工作方式，但是a）OP没有特别询问.NET，因此将其作为典型示例举出似乎不太有用，b）有正则表达式引擎（我想是Java的），可以以非愚蠢的方式执行这个操作。 - Ira Baxter

（这与我的问题无关，但我确实没有考虑过.NET，而是Haskell。） - stakx - no longer contributing

1

起初我认为我无法看到这个过程的任何良好优化。

然而，如果你有大量的正则表达式，你可能想要将它们分区（我不确定这是否是技术上的分区）。

我告诉你要做的是：

假设你有20个可能以user开头的URL：

/user/with-id/X
/user/with-id/X/preferences # instead of preferences, you could have another 10 possibilities like /friends, /history, etc

然后，您还有20个可能的URL以users开头：

/users/who-signed-up-on
/users/who-signed-up-on-between     #others: /registered-for, /i-might-like, etc

列表中还有 /products, /companies 等，而不是用户。

在这种情况下，您可以使用“多级”匹配。

首先，匹配字符串的开头。您将一次匹配一个，分别为 /products, /companies, /users，并忽略字符串的其余部分。这样，您就不必测试所有100个可能性。

在确定url以 /users 开头后，您可以仅匹配以 users 开头的可能的 url。

这样，您将减少许多不必要的匹配。您不会匹配所有 /procucts 的可能性字符串。

- Pedro Loureiro

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Savino Sguera · Accepted Answer

Aho-Corasick算法是一种非常快的算法，用于将输入字符串与一组预处理和组织在trie中的模式（实际上是关键字）进行匹配，以加速匹配过程。

有些变体的算法支持正则表达式模式（例如http://code.google.com/p/esmre/），值得一看。

或者，您可以将URL拆分为块，在树中组织它们，然后将URL分割为匹配并逐个遍历树节点。{userId}可以被视为通配符或匹配某个特定格式（例如整数）。

当您到达叶子节点时，就知道了您匹配的URL。