Làm cách nào để tìm kết quả trùng lặp ngắn nhất bằng các cụm từ thông dụng?

Question

Tôi vẫn còn tương đối mới để regex. Tôi đang cố gắng tìm chuỗi văn bản ngắn nhất phù hợp với một mẫu cụ thể, nhưng đang gặp sự cố nếu mẫu ngắn nhất là chuỗi con của một kết hợp lớn hơn. Ví dụ:

import re 
string = "A|B|A|B|C|D|E|F|G" 
my_pattern = 'a.*?b.*?c' 

my_regex = re.compile(my_pattern, re.DOTALL|re.IGNORECASE) 
matches = my_regex.findall(string) 

for match in matches: 
    print match 

in:

A|B|A|B|C 

nhưng tôi muốn nó trở lại:

A|B|C 

Có cách nào để làm điều này mà không cần phải lặp qua mỗi trận đấu để xem liệu nó có chứa một chuỗi con phù hợp không?

Answer 1

Trái ngược với hầu hết các câu trả lời khác ở đây, này có thể được thực hiện trong một regex duy nhất sử dụng một positive lookahead assertion với một capturing group:

>>> my_pattern = '(?=(a.*?b.*?c))' 
>>> my_regex = re.compile(my_pattern, re.DOTALL|re.IGNORECASE) 
>>> matches = my_regex.findall(string) 
>>> print min(matches, key=len) 
A|B|C 

findall() sẽ trả lại tất cả các trận đấu càng tốt, vì vậy bạn cần min() để lấy ngắn nhất.

Cách hoạt động:

• Chúng tôi không phù hợp với bất kỳ văn bản trong regex này, chỉ cần vị trí trong chuỗi (mà động cơ regex bước qua trong một nỗ lực trận đấu).
• Tại mỗi vị trí, công cụ regex nhìn về phía trước để xem liệu regex của bạn có khớp với vị trí này hay không.
• Nếu có, nó sẽ được chụp bởi nhóm chụp.
• Nếu không, nó sẽ không.
• Trong cả hai trường hợp, công cụ regex sau đó tiến lên một ký tự và lặp lại quá trình cho đến khi kết thúc chuỗi.
• Vì xác nhận tra cứu không tiêu thụ bất kỳ ký tự nào, tất cả các kết quả trùng lặp sẽ được tìm thấy.

Answer 2

Không. Perl trả về kết quả dài nhất, bên trái nhất trong khi tuân theo số lượng không tham lam của bạn. Bạn sẽ phải lặp lại, tôi sợ.

Chỉnh sửa: Có, tôi nhận ra tôi đã nói Perl ở trên, nhưng tôi tin điều đó đúng với Python.

Answer 3

Công cụ regex bắt đầu tìm kiếm từ đầu chuỗi cho đến khi tìm thấy kết quả phù hợp rồi thoát. Vì vậy, nếu nó tìm thấy một trận đấu trước khi nó thậm chí xem xét một nhỏ hơn, không có cách nào để bạn có thể buộc nó xem xét các trận đấu sau đó trong cùng một chạy - bạn sẽ phải chạy lại regex trên substrings.

Đặt cờ toàn cầu và chọn chuỗi phù hợp ngắn nhất sẽ không giúp ích gì vì ví dụ của bạn - kết quả ngắn hơn có thể là chuỗi con của một kết quả khớp khác (hoặc được bao gồm một phần trong đó). Tôi tin rằng bạn sẽ phải bắt đầu tìm kiếm tiếp theo từ (1 + chỉ mục của trận đấu trước đó) và tiếp tục như thế.

Answer 4

Tôi không nghĩ rằng nhiệm vụ này có thể được thực hiện bằng một cụm từ thông dụng duy nhất. Tôi không có bằng chứng cho thấy đây là trường hợp, nhưng có khá nhiều thứ không thể thực hiện được với các regex và tôi cho rằng vấn đề này là một trong số chúng. Một số ví dụ điển hình về các hạn chế của các regex được đưa ra trong this blog post.

Answer 5

Đây có thể là ứng dụng hữu ích của sexegers. Đối sánh cụm từ thông dụng được thiên vị về lựa chọn dài nhất, ngoài cùng bên trái. Sử dụng số lượng không tham lam như trong .*? váy phần dài nhất, và đảo ngược cả đầu vào và mẫu có thể nhận được xung quanh các ngữ nghĩa phù hợp ngoài cùng bên trái.

Hãy xem xét các chương trình sau đó kết quả đầu ra A|B|C như mong muốn:

#! /usr/bin/env python 

import re 

string = "A|B|A|B|C|D|E|F|G" 
my_pattern = 'c.*?b.*?a' 

my_regex = re.compile(my_pattern, re.DOTALL|re.IGNORECASE) 
matches = my_regex.findall(string[::-1]) 

for match in matches: 
    print match[::-1] 

Một cách khác là để thực hiện một mẫu khắt khe hơn. Giả sử bạn không muốn cho phép lặp lại của các nhân vật đã thấy:

my_pattern = 'a[^a]*?b[^ab]*?c' 

dụ của bạn là chung chung và giả tạo, nhưng nếu chúng ta có một ý tưởng tốt hơn về các yếu tố đầu bạn đang làm việc với, chúng tôi có thể cung cấp tốt hơn, nhiều hơn gợi ý hữu ích.

Answer 6

Bạn có thể viết regex theo cách không thể chứa các kết quả phù hợp nhỏ hơn.

Đối với regex của bạn:

a.*?b.*?c 

Tôi nghĩ rằng bạn có thể viết này:

a[^ab]*b[^c]*c 

Đó là khó khăn để có được điều đó đúng, và tôi không thấy bất kỳ cách rõ ràng chính xác tổng quát hơn hoặc nhiều hơn để làm điều đó. (Sửa — trước đó tôi đề nghị một sự khẳng định lookahead tiêu cực, nhưng tôi không thấy một cách để làm cho công việc đó.)

Answer 7

Một Python vòng lặp để tìm kiếm trận đấu ngắn nhất, bởi brute force thử nghiệm mỗi chuỗi con từ trái sang phải, chọn ngắn nhất:

shortest = None 
for i in range(len(string)): 
    m = my_regex.match(string[i:]) 
    if m: 
     mstr = m.group() 
     if shortest is None or len(mstr) < len(shortest): 
      shortest = mstr 

print shortest 

vòng khác, lần này để cho re.findall làm công việc khó khăn của việc tìm kiếm cho tất cả các trận đấu có thể, lực lượng vũ phu sau đó kiểm tra mỗi phù hợp với từ phải sang trái tìm kiếm một chuỗi ngắn hơn:

# find all matches using findall 
matches = my_regex.findall(string) 

# for each match, try to match right-hand substrings 
shortest = None 
for m in matches: 
    for i in range(-1,-len(m),-1): 
     mstr = m[i:]   
     if my_regex.match(mstr): 
      break 
    else: 
     mstr = m 

    if shortest is None or len(mstr) < len(shortest): 
     shortest = mstr 

print shortest 

Answer 8

Không, không có trong công cụ biểu thức chính quy của Python.

mất của tôi cho một chức năng tùy chỉnh, mặc dù:

import re, itertools 

# directly from itertools recipes 
def pairwise(iterable): 
    "s -> (s0,s1), (s1,s2), (s2, s3), ..." 
    a, b = itertools.tee(iterable) 
    for elem in b: 
     break 
    return itertools.izip(a, b) 

def find_matches(rex, text): 
    "Find all matches, even overlapping ones" 
    matches= list(rex.finditer(text)) 

    # first produce typical matches 
    for match in matches: 
     yield match.group(0) 

    # next, run it for any patterns included in matches 
    for match1, match2 in pairwise(matches): 
     subtext= text[match1.start()+1:match2.end()+1] 
     for result in find_matches(rex, subtext): 
      yield result 

    # also test the last match, if there was at least one 
    if matches: 
     subtext= text[matches[-1].start()+1:matches[-1].end()+1] 
     # perhaps the previous "matches[-1].end()+1" can be omitted 
     for result in find_matches(rex, subtext): 
      yield result 

def shortest_match(rex, text): 
    "Find the shortest match" 
    return min(find_matches(rex, text), key=len) 

if __name__ == "__main__": 
    pattern= re.compile('a.*?b.*?c', re.I) 
    searched_text= "A|B|A|B|C|D|E|F|G" 
    print (shortest_match(pattern, searched_text)) 

Answer 9

Một giải pháp regex; nó tìm thấy chỉ sự xuất hiện cuối cùng của * a * b * c:

my_pattern = 'a(?!.*a.*b.*c).*b[^c]*c' 

a(?!.*a.*?b.*?c) đảm bảo rằng không có 'a.*?b.*?c' sau đầu tiên 'A' chuỗi như A | A | B | C hoặc A | B... | A | B | C hoặc A | B | C | A | B | C trong kết quả được loại bỏ

b[^c]*c đảm bảo rằng sau 'B' chỉ có một 'C' chuỗi như A | B | C | B | C hoặc A | B | C | C trong kết quả bị loại trừ

Vì vậy, bạn có kết hợp nhỏ nhất 'a.*?b.*?c'