正则表达式：将 url 与多个 or 表达式匹配的最佳选项是什么

Question

假设您正在尝试匹配与以下 2 条规则兼容的网址：

1. 以单词 .../contactos(/) 结尾
2. 或者在网址中间有 .../gestao/... 一词

最初，我从以下模式开始（模式 1）：

^(?:(?:/.+)+/contactos/?(?!.))|(?:(?:/.*)+/gestao(?:/.+))$

它可以工作，但是在这种情况下所需的负前瞻似乎不合适，所以我用以下模式替换（我们称之为模式 2）：

^(?:(?:/.+)+/contactos/?)$|^(?:(?:/.*)+/gestao(?:/.+))$

主要区别在于，我使用开始/结束锚点来分隔每个表达式，而不是像第一个示例中那样使用一对（我没有在两种情况下捕获组，因此这实际上是两种模式之间的唯一区别） 。通过“隔离”每个“选项”，我可以放弃模式 1 中使用的负前瞻。

由于模式 2 不使用前瞻，我预计它应该比模式 1 更快。但是，情况似乎并非如此。我用 .net 8 构建了一个小型基准测试，看起来模式 1 比匹配 url 的模式稍快。这是我编写的代码（并不是真正有经验的 Benchmark 用户，所以也许我遗漏了一些东西）：

[MemoryDiagnoser]
public class RegexPerformance {
    
    private const string _patternNoCapture = "^(?:(?:/.+)+/contactos/?(?!.))|(?:(?:/.*)+/gestao(?:/.+))$";
    private const string _patternNoCaptureWithStartEndAnchors = "^(?:(?:/.+)+/contactos/?)$|^(?:(?:/.*)+/gestao(?:/.+))$";

    private Regex _noCapture = default!;

    private Regex _noCaptureWithStart = default!;

    [GlobalSetup]
    public void Setup() {
        _noCapture = new (_patternNoCapture,
                               RegexOptions.Compiled | RegexOptions.IgnoreCase);
        
        _noCaptureWithStart = new (_patternNoCaptureWithStartEndAnchors,
                                        RegexOptions.Compiled | RegexOptions.IgnoreCase);
    }
    
    public IEnumerable<string> Urls => [
        "/test/contactos",
        "/test/contactos/",
        "/test/someplace/gestao/123/yyy",
        "/test/someplace/gestao/123"
    ];
    
    [Benchmark]
    [ArgumentsSource(nameof(Urls))]
    public bool MatchPatternNoCapture(string url) => _noCapture.IsMatch(url);
    
    [Benchmark]
    [ArgumentsSource(nameof(Urls))]
    public bool MatchPatternNoCaptureWithStartEndAnchors(string url) => _noCaptureWithStart.IsMatch(url);


}

结果如下：

| Method                                   | url                  | Mean       | Error     | StdDev    | Median     | Allocated |
|----------------------------------------- |--------------------- |-----------:|----------:|----------:|-----------:|----------:|
| MatchPatternNoCapture                    | /test/contactos      |   244.5 ns |   8.25 ns |  23.53 ns |   238.6 ns |         - |
| MatchPatternNoCaptureWithStartEndAnchors | /test/contactos      |   224.3 ns |   3.14 ns |   2.62 ns |   223.5 ns |         - |
| MatchPatternNoCapture                    | /test/contactos/     |   256.6 ns |   5.67 ns |  15.80 ns |   259.9 ns |         - |
| MatchPatternNoCaptureWithStartEndAnchors | /test/contactos/     |   278.6 ns |  18.98 ns |  53.84 ns |   260.6 ns |         - |
| MatchPatternNoCapture                    | /test(...)o/123 [26] | 1,081.5 ns |  37.01 ns | 104.39 ns | 1,057.7 ns |         - |
| MatchPatternNoCaptureWithStartEndAnchors | /test(...)o/123 [26] | 1,367.4 ns | 167.26 ns | 493.18 ns | 1,121.6 ns |         - |
| MatchPatternNoCapture                    | /test(...)3/yyy [30] | 1,861.4 ns |  73.08 ns | 201.28 ns | 1,789.4 ns |         - |
| MatchPatternNoCaptureWithStartEndAnchors | /test(...)3/yyy [30] | 1,925.6 ns |  58.13 ns | 168.65 ns | 1,919.0 ns |         - |

顺便说一句，我用不匹配的 url 运行了另一个简单的测试 (

/test/contactosbad

)，在这种情况下，模式 2 的表现似乎比模式 1 稍好：

| Method                                   | url                | Mean     | Error    | StdDev   | Allocated |
|----------------------------------------- |------------------- |---------:|---------:|---------:|----------:|
| MatchPatternNoCapture                    | /test/contactosbad | 668.4 ns | 13.44 ns | 14.38 ns |         - |
| MatchPatternNoCaptureWithStartEndAnchors | /test/contactosbad | 518.2 ns | 10.30 ns | 14.43 ns |         - |

我必须承认我对这些结果有点困惑。我预计模式 2 的表现会比模式 1 好得多，但情况似乎并非如此。关于为什么会发生这种情况有什么想法吗？

谢谢。

Answer 1

您的两种模式都不好：它们很容易出现灾难性的回溯。

即具有万能点的量化组：

(?:/.+)+

和

(?:/.*)+

。对于稍长一点的输入，这些将花费看似无限的时间来运行。这是 a ReDoS 检查器建议的 115 个字符输入：

/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao/stao

大约 10 秒后，在 regex101.com 上触发了超时。该过程在您的本地计算机/服务器上可能需要更少的时间，但仍然太长。从长远来看，这样一个群的时间复杂度是

O(2^n)

（指数）。

相反，保持简单：

^
(?:
  /.+/contactos/?$
|
  /.+/gestao/.+
)

第一个

.+

以1步运行到最后，然后回溯直到找到固定的

/contactos

（n步）；第二个

.+

执行相同的操作（n 步骤）。第三个不需要回溯，所以也只需要1步；如果您只想要一个布尔值而不是完整匹配，您可以将其替换为单个

.

。总的来说，该模式的时间复杂度为

O(n)

（线性）。

我还没有运行基准测试（咨询 ChatGPT 如何编写正确的 C# 文件），但我希望它的性能优于您的两种模式。举个例子，regex101.com 报告不匹配，输入的时间比上面的例子长十倍，只需约 2 毫秒（在我的机器上）。