2010-08-27 21 views
6

Tôi đang cố gắng tìm một regex được tối ưu hóa để trả về các từ N (nếu có) xung quanh từ khác để tạo bản tóm tắt. Chuỗi nằm trong UTF-8, do đó định nghĩa "từ" lớn hơn [a-z]. Chuỗi có vai trò là từ tham chiếu có thể ở giữa một từ hoặc không được bao quanh bởi dấu cách.Tối ưu hóa regex cho N từ xung quanh một từ đã cho (UTF-8)

Tôi đã nhận được những điều sau đây mà làm việc nhưng dường như thực sự tham lam và nghẹn khi tìm kiếm hơn 6-7 từ xung quanh nhau:

/(?:[^\s\r\n]+[\s\r\n]+[^\s\r\n]*){0,4}lorem(?:[^\s\r\n]*[\s\r\n]+[^\s\r\n]+){0,4}/u 

Đây là phương pháp PHP tôi đã xây dựng để làm nhưng tôi cần được giúp đỡ để regex ít tham lam hơn và làm việc cho bất kỳ số từ nào xung quanh.

/** 
* Finds N words around a specified word in a string. 
* 
* @param string $string The complete string to look in. 
* @param string $find The string to look for. 
* @param integer $before The number of words to look for before $find. 
* @param integer $after The number of words to look for after $find. 
* @return mixed False if $find was not found and all the words around otherwise. 
*/ 
private function getWordsAround($string, $find, $before, $after) 
{ 
    $matches = array(); 
    $find = preg_quote($find); 
    $regex = '(?:[^\s\r\n]+[\s\r\n]+[^\s\r\n]*){0,' . (int)$before . '}' . 
     $find . '(?:[^\s\r\n]*[\s\r\n]+[^\s\r\n]+){0,' . (int)$after . '}'; 
    if (preg_match("/$regex/u", $string, $matches)) { 
     return $matches[0]; 
    } else { 
     return false; 
    } 
} 

Nếu tôi có $ string sau:

"Lorem ipsum dolor sit amet, consectetur adipiscing elit. Cras auctor, 
felis non vehicula suscipit, enim quam adipiscing turpis, eget rutrum 
eros velit non enim. Sed commodo cursus vulputate. Aliquam id diam sed arcu 
fringilla venenatis. Cras vitae ante ut tellus malesuada convallis. Vivamus 
luctus ante vel ligula eleifend condimentum. Donec a vulputate velit. 
Suspendisse velit risus, volutpat at dapibus vitae, viverra vel nulla." 

Và gọi getWordsAround($string, 'vitae', 8, 8) Tôi muốn để có được những kết quả sau:

"Lorem ipsum dolor sit amet, consectetur adipiscing elit. Cras auctor, 
felis non vehicula suscipit," 

Cảm ơn bạn đã rất kinh nghiệm regex giúp đỡ của bạn.

+1

Đối với người mới bắt đầu, '\ s' bao gồm' \ r' và '\ n', vì vậy việc thêm chúng vào cùng một lớp ký tự là thừa. Ngoài ra '[^ \ s]' tương đương với '\ S' – NullUserException

+0

Mẹo được lưu ý, cảm ơn NullUserException. – lpfavreau

+0

Đây là một vấn đề thú vị bằng cách này. Khi tôi trở lại tôi sẽ cố gắng và đưa ra một giải pháp tốt hơn. +1 – NullUserException

Trả lời

1

này làm việc tốt ở đây:

(?:[^\s\r\n]*[\s\r\n]+){0,8}(?:[^\s\r\n]*)consectetur(?:[^\s\r\n]*)(?:[\s\r\n]+[^\s\r\n]*){0,8} 

Cung cấp:

Lorem ipsum dolor sit Amet, consectetur adipiscing elit. Cras auctor, felis non vehicula suscipit,

Hiệu suất của biểu thức chính quy này là tuyệt đối. Tôi thực sự không biết làm thế nào để làm cho điều này hiệu quả hơn, thiếu làm việc đó mà không có biểu thức thông thường.

Lý do cho hiệu suất là "tuyệt đối crap" cho các từ gần cuối là động cơ cố gắng bắt đầu một trận đấu trên mỗi ký tự và sau đó tiến hành vài chục ký tự cho đến khi phát hiện ra rằng, cuối cùng, nó không thể tìm thấy chuỗi bạn đang tìm kiếm và loại bỏ mọi thứ.

+0

Ví dụ xấu từ phía tôi, xin lỗi vì điều đó. Hãy thử nó với vitae từ. Tôi không biết tại sao nhưng khi nó đi xa hơn trong chuỗi, nó dường như trở nên rất chậm. – lpfavreau

+0

@ Ipf Vâng, đó là lý do tại sao tôi nói nó là tuyệt đối crap. Xem chỉnh sửa của tôi. – Artefacto

+0

Ah, không thấy bản chỉnh sửa. Tôi biết tôi có thể làm điều đó mà không có regex nhưng tôi vẫn muốn xem nếu ai đó có một ý tưởng để tôi có thể học hỏi từ nó. 1 cho lời giải thích từ đồng bằng về lý do tại sao hiệu suất là tuyệt đối crap. :-) – lpfavreau

2

Điều gì về việc sử dụng regex hoặc một số phương pháp khác để chia văn bản nhập thành một mảng từ. Sau đó chạy qua các từ với một vòng lặp tìm kiếm từ mục tiêu. Một khi nó được tìm thấy, sau đó lấy mảng mảng yêu cầu, tham gia nó với nhau và in.

Để duy trì khoảng trắng ban đầu giữa các từ, bạn có thể bao gồm khoảng trắng ở cuối mỗi từ.

Ngoài ra, điều này có thể được triển khai dưới dạng trình phân tích cú pháp luồng thay vì tách toàn bộ chuỗi trước tiên.

+1

Tôi thích ý tưởng trên giấy, nhưng khi bạn thực hiện, bạn sẽ chạy vào khoanh vùng (ví dụ: bạn nên ghép các mảnh lại với nhau trong khi duy trì các dải phân cách ban đầu) như thế nào? – NullUserException

+0

@NullUserException, bạn có thể bao gồm khoảng trắng với mã thông báo từ hoặc triển khai trình phân tích cú pháp luồng để lưu các ranh giới từ N cuối cùng khi nó đi qua chuỗi. –

+0

Nếu anh ta không sử dụng các biểu thức thông thường, anh ta cũng có thể lặp qua chuỗi cho đến khi anh ấy tìm thấy từ anh ấy muốn và sau đó quay lại và tiến lên để tìm các từ xung quanh. Nó sẽ nhanh hơn và chắc chắn hơn bộ nhớ hiệu quả. – Artefacto

1

Vấn đề với việc sử dụng regex này là nó khiến động cơ regex quay trở lại thảm khốc. Số lần thử tăng lên theo cấp số nhân với kích thước của chuỗi và đó là không tốt. Bạn có thể muốn xem xét atomic grouping để cải thiện hiệu suất.

Hoặc bạn có thể tìm thấy sự xuất hiện đầu tiên của từ đã cho và bắt đầu nhìn về phía sau và tiến lên cho các từ có độ dài mong muốn.Mã Pseudo-ish:

$pos = strpos($find); 
$result = $find; 

foreach $word before $pos { 
    $result = $word . $result; 
    $count++ 
    if ($count >= $target) 
     break; 
} 

foreach $word after $pos { 
    $result .= $word; 
    $count++ 
    if ($count >= $target) 
     break; 
} 

Tất nhiên, việc tìm kiếm các từ trước và sau và xử lý các chuỗi một phần có thể rất lộn xộn.

+0

Bạn nên sử dụng một mảng tròn như tôi đã nói trong phần bình luận cho câu trả lời của ar. Việc đi qua một chuỗi UTF-8 không hiệu quả và rất hiệu quả để thực hiện nó. – Artefacto

+0

Cảm ơn bạn đã liên kết về nhóm nguyên tử. Tôi sẽ xem xét nó. – lpfavreau

2

Như đã đề cập trước đó, sự cố là một số lượng rất lớn của quá trình tải lại. Để giải quyết điều này, tôi đã cố gắng sử dụng lookbehind và lookahead để neo kết quả khớp với chuỗi. Vì vậy, tôi đã đưa ra:

/consectetur(?<=((?:\S+\s+){0,8})\s*consectetur)\s*(?=((?:\S+\s+){0,8}))/ 

Thật không may, điều này không có tác dụng, vì không có hỗ trợ độ dài thay đổi trong PCRE (hoặc perl cho vấn đề đó). Vì vậy, chúng tôi còn lại với:

/consectetur\s*(?:\S+\s+){0,8}/ 

Chỉ ghi lại chuỗi trận đấu và tối đa 8 từ sau trận đấu. Tuy nhiên, nếu bạn use the PREG_OFFSET_CAPTURE flag, được bù đắp của $match[0], lấy substring đến thời điểm đó, đảo ngược chuỗi với strrev, có 0-8 từ đầu tiên (sử dụng /\s*(?:\S+\s+){0,8}/), đảo ngược trận đấu, và tái tổ hợp:

$s = "put test string here"; 
$matches = array(); 
if (preg_match('/consectetur\s*(?:\S+\s+){0,8}/', $s, $matches, PREG_OFFSET_CAPTURE)) { 
    $before = strrev(substr($s, 0, $matches[0][1])); 
    $before_match = array(); 
    preg_match('/\s*(?:\S+\s+){0,8}/', $before, $before_match); 
    echo strrev($before_match[0]) . $matches[0][0]; 
} 

Bạn có thể làm cho nó nhanh hơn một chút trên các chuỗi rất lớn bằng cách lấy một tập con an toàn của các ký tự trước trận đấu, như 100. Sau đó, bạn chỉ đảo ngược chuỗi ký tự 100.

Tất cả những gì được nói, một giải pháp không sử dụng cụm từ thông dụng có thể hoạt động tốt hơn.

+0

Đã chỉnh sửa để thêm mã PHP thực. Dường như làm việc tuyệt vời trên chuỗi thử nghiệm. – wuputah

+0

Tôi nghĩ rằng tôi đã đọc ở đâu đó có một vấn đề với PREG_OFFSET_CAPTURE vì nó trả về bù đắp byte thay vì số ký tự thực tế và strrev không tương thích nhiều byte. Điều này sẽ làm việc tuyệt vời trên một chuỗi latin-1 nhưng không phải UTF-8 tôi sợ. Và đảo ngược UTF-8 trong PHP là không hiệu quả, ít nhất là các chức năng tôi đã thử. – lpfavreau

+0

Bạn thực sự muốn bù đắp byte cho 'substr', không phải là bù đắp ký tự. Khi đảo ngược chuỗi trong UTF-8, hiệu quả của mã như vậy có thể được thực hiện khá không đáng kể nếu bạn thiết lập một độ dài 'substr' hợp lý để nắm bắt, ví dụ: '($ trước * 20)' byte. Bất kỳ vấn đề mã hóa nào sẽ là lúc bắt đầu của chuỗi, chuỗi này sẽ bị cắt bỏ khi bạn đối sánh với các từ '$ trước'. – wuputah

2

Đây là một hàm PHP bên trong thực hiện những gì bạn muốn. Nó không chắc bạn sẽ có thể đánh bại hiệu suất này-khôn ngoan trong một chức năng người sử dụng đất. Không có vấn đề gì khi sử dụng chức năng này cho các hàm UTF-8, vì '\ r', '\ n' và '' (và nói chung tất cả các ký tự ASCII) không thể xuất hiện như là một phần của chuỗi ký tự khác. Vì vậy, nếu bạn chuyển dữ liệu UTF-8 hợp lệ cho cả hai tham số, bạn nên ổn. Đảo ngược dữ liệu UTF-8 như bạn thường sẽ đảo ngược mã hóa ký tự đơn (với strrev) thực sự có nghĩa là rắc rối, nhưng chức năng này không làm điều đó.

PHP_FUNCTION(surrounding_text) 
{ 
    struct circ_array { 
     int *offsets; 
     int cur; 
     int size; 
    } circ_array; 
    long before; 
    long after; 
    char *haystack, *needle; 
    int haystack_len, needle_len; 
    int i, in_word = 0, in_match = 0; 

    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "ssll", 
     &haystack, &haystack_len, &needle, &needle_len, &before, &after) 
     == FAILURE) 
     return; 

    if (needle_len == 0) { 
     php_error_docref(NULL TSRMLS_CC, E_WARNING, 
      "Cannot have empty needle"); 
     return; 
    } 

    if (before < 0 || after < 0) { 
     php_error_docref(NULL TSRMLS_CC, E_WARNING, 
      "Number of words after and before should be non-negative"); 
     return; 
    } 

    /* saves beggining of match and words before */ 
    circ_array.offsets = safe_emalloc(before + 1, sizeof *circ_array.offsets, 0); 
    circ_array.cur = 0; 
    circ_array.size = before + 1; 

    for (i = 0; i < haystack_len; i++) { 
     if (haystack[i] == needle[in_match]) { 
      in_match++; 
      if (!in_word) { 
       in_word = 1; 
       circ_array.offsets[circ_array.cur % circ_array.size] = i; 
       circ_array.cur++; 
      } 
      if (in_match == needle_len) 
       break; /* found */ 
     } else { 
      int is_sep = haystack[i] == ' ' || haystack[i] == '\n' || haystack[i] == '\r'; 

      if (in_match) 
       in_match = 0; 

      if (is_sep) { 
       if (in_word) 
        in_word = 0; 
      } else { /* not a separator */ 
       if (!in_word) { 
        in_word = 1; 
        circ_array.offsets[circ_array.cur % circ_array.size] = i; 
        circ_array.cur++; 
       } 
      } 
     } 
    } 

    if (in_match != needle_len) { 
     efree(circ_array.offsets); 
     RETURN_FALSE; 
    } 


    /* find words after; in_word is 1 */ 
    for (i++; i < haystack_len; i++) { 
     int is_sep = haystack[i] == ' ' || haystack[i] == '\n' || haystack[i] == '\r'; 
     if (is_sep) { 
      if (in_word) { 
       if (after == 0) 
        break; 
       after--; 
       in_word = 0; 
      } 
     } else { 
      if (!in_word) 
       in_word = 1; 
     } 
    } 

    { 
     char *result; 
     int start, result_len; 
     if (circ_array.cur < circ_array.size) 
      start = circ_array.offsets[0]; 
     else 
      start = circ_array.offsets[circ_array.cur % circ_array.size]; 

     result_len = i - start; 
     result = emalloc(result_len + 1); 
     memcpy(result, &haystack[start], result_len); 
     result[result_len] = '\0'; 

     efree(circ_array.offsets); 
     RETURN_STRINGL(result, result_len, 0); 
    } 

} 

Từ thử nghiệm của tôi, hàm C nhanh hơn 4 lần so với phiên bản wuputah (và không gặp vấn đề strrev).

+0

Ồ, điều này thật ấn tượng. 1 có thể tìm cách nhanh nhất để giải quyết vấn đề này. Tôi không có thời gian để kiểm tra nó, trên thực tế, tôi chưa bao giờ biên soạn chức năng PHP của riêng mình và tôi không chắc nó sẽ thuận tiện cho việc phân phối nó, nhưng dù sao, nó cũng không loại bỏ bất cứ thứ gì giải quyết vấn đề đó. Tôi vẫn đang tìm kiếm một giải pháp chỉ có PHP nhưng điều này sẽ nhận được điểm anyway! Cảm ơn! – lpfavreau

+0

Nhân tiện, khi khai báo is_sep, bạn kiểm tra hai lần cho '\ n' vì vậy tôi đoán bạn có thể xóa một séc ở đó. – lpfavreau

+0

@Ipfavreau OK, tôi đã xóa phần bổ sung '\ n'. Cảm ơn. – Artefacto

Các vấn đề liên quan