Cụm từ thông dụng để chỉ khớp với số nhỏ nhất

Question

Tôi có một cụm từ như c.{0,2}?m và một chuỗi như "abcemtcmncefmf". Hiện tại, nó sẽ khớp với ba chất nền: cem, cm và cefm (see here). Nhưng tôi thích chỉ khớp với phần nhỏ nhất trong số này, trong trường hợp này là cm.

Vấn đề của tôi là tôi không có hỗ trợ đối sánh toàn cầu, chỉ là trận đấu đầu tiên, bởi vì tôi đang sử dụng chức năng MariaDB REGEXP_SUBSTR(). Giải pháp hiện tại của tôi là stored procedure mà tôi đã tạo để giải quyết vấn đề của mình. Nhưng nó chậm hơn 10 lần so với biểu thức chính quy cho các trường hợp đơn giản.

Tôi cũng đã thử làm một cái gì đó như: (cm|c.{0,1}?m|c.{0,2}?m), nhưng nó không hoạt động vì nó sẽ khớp với đầu tiên của bất kỳ mẫu nhóm nào, thay vì thử từng cái một trong tất cả chuỗi chủ đề.

Tôi biết rằng cụm từ thông dụng (PCRE) có một số tính năng ma thuật đen, nhưng tôi không tìm thấy gì để giải quyết vấn đề của mình.

---

• Note: Tôi chưa sử dụng mô hình phi tham lam (.{0,2}?) trên mô hình hiện tại của tôi;
• Câu hỏi Regular expression to find smallest possible match không phải là vấn đề của tôi;

Answer 1

Bạn chỉ có thể sử dụng một sự làm thay đổi một chi nhánh reset nhóm:

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

(Kết quả là ở nhóm 1)

hay như thế này:

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

Thành công đầu tiên ful branch thắng.

Answer 2

Có rất nhiều thứ mà cụm từ thông dụng có thể làm - một số trong số đó - như bạn nói - 'ma thuật đen tối'. Nhưng vấn đề cốt lõi là - khá cơ bản, các biểu thức chính quy về lựa chọn văn bản có thể nắm bắt được. Họ không 'làm' so sánh hoặc so sánh đánh giá - chúng có thể khớp hoặc không khớp.

Bạn có thể xem regex đang làm gì, bằng cách bật nó ở chế độ gỡ lỗi. Đối với điều này, tôi sẽ sử dụng perl bởi vì bạn có thể thiết lập 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; 

này sẽ in những gì engine regex đang làm như nó đi:

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)" 

Hy vọng rằng bạn có thể xem những gì nó làm gì ở đây ?

• làm việc kể từ trái sang phải
• lượt truy cập đầu tiên 'c'
• kiểm tra xem nếu 'cm' matches (thất bại)
• kiểm tra xem nếu 'c.m' phù hợp (thành công).
• thoát ra khỏi đây và trả về số lần truy cập.

Bật g và bạn làm cho nó hoạt động nhiều lần - Tôi không thể sao chép lại, nhưng lâu hơn rất nhiều.

Trong khi bạn có thể thực hiện rất nhiều thủ thuật thông minh với PCRE, chẳng hạn như nhìn xung quanh, nhìn về phía trước, tham lam/không phù hợp .... khá cơ bản, tại đây, bạn đang cố gắng chọn nhiều kết quả phù hợp và chọn ngắn nhất . Và regex không thể làm điều đó.

tôi sẽ cung cấp mặc dù - với điều đó cùng perl, quá trình tìm kiếm ngắn nhất là khá dễ dàng:

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

Answer 3

Về mặt kỹ thuật, nó có thể được thực hiện.

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; 

[Ghi chú: Loại bỏ các bổ quantifier sở hữu (+) sẽ rất ảnh hưởng đến hiệu suất.]

Nhưng nó thường là xa, xa hơn để tìm tất cả các trận đấu và xác định vị trí nhỏ nhất.

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