正则表达式只匹配最小的

Question

我有一个像 c.{0,2}?m 这样的表达式和一个像 "abcemtcmncefmf" 这样的字符串。目前它将匹配三个子字符串：cem、cm 和 cefm (see here)。但我喜欢只匹配其中最小的一个，在本例中，cm.

我的问题是我没有全局匹配支持，只有第一个匹配，因为我正在使用我创建的 MariaDB REGEXP_SUBSTR() function. My current solution is a stored procedure 来解决我的问题。但它比简单情况下的正则表达式慢 10 倍。

我也试过做类似的事情：(cm|c.{0,1}?m|c.{0,2}?m)，但它没有用，因为它会匹配任何组模式中的第一个，而不是在所有主题字符串中一个一个地尝试。

我知道正则表达式 (PCRE) 有一些 黑魔法 功能，但我没有找到任何可以解决我的问题的东西。

注意：我还在我当前的模式上使用非贪婪模式（.{0,2}?）；
问题Regular expression to find smallest possible match不是我的问题;

Answer 1

正则表达式可以做很多事情 - 正如您所说，其中一些是 'dark magic'。但核心问题是——从根本上说，正则表达式是关于文本 selection 可以捕获的。它们 'do' 不匹配比较或评估 - 它们要么匹配要么不匹配。

您可以通过在调试模式下启用它来查看正则表达式的作用。为此，我将使用 perl 因为您可以设置 use re 'debug';':

#!/usr/bin/env perl

use strict;
use warnings;

use re 'debug';

my @matches = "abcemtcmncefmf" =~ m/(cm|c.m|c..m)/;
print join "\n", @matches;

这将打印正则表达式引擎正在执行的操作：

Compiling REx "(cm|c.m|c..m)"
Final program:
   1: OPEN1 (3)
   3:   TRIE-EXACT[c] (19)
        <cm> (19)
        <c> (9)
   9:     REG_ANY (10)
  10:     EXACT <m> (19)
        <c> (15)
  15:     REG_ANY (16)
  16:     REG_ANY (17)
  17:     EXACT <m> (19)
  19: CLOSE1 (21)
  21: END (0)
stclass AHOCORASICK-EXACT[c] minlen 1 
Matching REx "(cm|c.m|c..m)" against "abcemtcmncefmf"
Matching stclass AHOCORASICK-EXACT[c] against "abcemtcmncefmf" (14 bytes)
   0 <> <abcemtcmnc>         | Scanning for legal start char...
   2 <ab> <cemtcmncef>       | Charid:  1 CP:  63 State:    1, word=0 - legal
   3 <abc> <emtcmncefm>      | Charid:  0 CP:  65 State:    2, word=2 - fail
   3 <abc> <emtcmncefm>      | Fail transition to State:    1, word=0 - fail
Matches word #2 at position 2. Trying full pattern...
   2 <ab> <cemtcmncef>       |  1:OPEN1(3)
   2 <ab> <cemtcmncef>       |  3:TRIE-EXACT[c](19)
   2 <ab> <cemtcmncef>       |    State:    1 Accepted: N Charid:  1 CP:  63 After State:    2
   3 <abc> <emtcmncefm>      |    State:    2 Accepted: Y Charid:  0 CP:  65 After State:    0
                                  got 2 possible matches
                                  TRIE matched word #2, continuing
   3 <abc> <emtcmncefm>      |  9:  REG_ANY(10)
   4 <abce> <mtcmncefmf>     | 10:  EXACT <m>(19)
   5 <abcem> <tcmncefmf>     | 19:  CLOSE1(21)
   5 <abcem> <tcmncefmf>     | 21:  END(0)
Match successful!
Freeing REx: "(cm|c.m|c..m)"

希望您能在这里看到它在做什么？

从左到右工作
命中第一个'c'
检查 'cm' 是否匹配（失败）
检查 'c.m' 是否匹配（成功）。
在这里退出并 returns 命中。

打开 g，您可以多次使用它 - 我不会重现它，但它要长得多。

虽然您可以使用 PCRE 做很多巧妙的技巧，例如环顾四周、向前看、greedy/nongreedy 匹配....从根本上讲，在这里，您正在尝试 select 多个有效匹配，并选择最短的。 regex 不能那样做。

虽然我会提供 - 使用相同的 perl，找到最短的过程非常简单：

use List::Util qw/reduce/;
print  reduce { length( $a ) < length( $b ) ? $a : $b } @matches;

Answer 2

技术上是可以做到的。

my ($match) = /
   ^
   (?:(?! c[^m]{0,2}m ).)*+         # Skip past area with no matches.
   (?:
      (?:(?! c[^m]{0,1}m ).)*+      # Skip past area with no matches except longuest.
      (?:
         (?:(?! c[^m]{0,0}m ).)*+   # Skip past area with no matches except 2 longuest.
      )?
   )?
   ( c[^m]{0,2}m )
/xs;

[注意：删除所有格修饰符 (+) 将极大地 影响性能。]

但找到所有匹配项并找到最小的匹配项通常要好得多。

use List::Util qw( reduce );
my ($match) = reduce { length($a) <= length($b) ? $a : $b } /c[^m]{0,2}m/g;

Answer 3

您可以简单地在 分支重置 组中使用交替：

/^(?|.*(cm)|.*(c.m)|.*(c..m))/s

(结果在第1组)

或者像这样：

/^.*\Kcm|^.*\Kc.m|^.*\Kc..m/s

第一个成功的分支获胜。

正则表达式只匹配最小的

Regular expression to match smallest only

regex

perl

pcre