Zoptymalizowane wyrażenie regularne dla N słów wokół danego słowa (UTF-8)

Question

Próbuję znaleźć zoptymalizowane wyrażenie regularne, aby zwrócić N słów (jeśli są dostępne) wokół innego, aby zbudować podsumowanie. Łańcuch jest w UTF-8, więc definicja "słów" jest większa niż [a-z]. Ciąg, który służy jako słowo referencyjne, może znajdować się w środku słowa lub nie jest bezpośrednio otoczony spacjami.

Mam już przy poszukiwaniu więcej niż 6-7 słów wokół siebie jedną z następujących działa, ale wydaje się, że faktycznie chciwy i dławi:

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

Jest to metoda PHP Mam zbudować zrobić ale potrzebuję pomocy, by regex był mniej chciwy i pracował dla dowolnej liczby słów.

/** 
* 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; 
    } 
} 

Gdybym miał następujący ciąg: $

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

i nazwał getWordsAround($string, 'vitae', 8, 8) chciałbym uzyskać następujący wynik:

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

Dziękuję za pomoc regex guru.

Answer 1

To działało w porządku tutaj:

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

Daje:

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

Jednak wykonanie tego wyrażenia regularnego jest bezwzględną bzdurą. Naprawdę nie wiem, jak sprawić, by było to bardziej wydajne, bez robienia tego bez wyrażeń regularnych.

Powodem, dla którego spektakl brzmi "bezwzględna bzdura" słów pod koniec, jest to, że silnik próbuje rozpocząć mecz na każdej postaci, a następnie przesuwa się o kilkadziesiąt znaków, dopóki nie dowiaduje się, że ostatecznie nie może znaleźć szukanego ciągu i odrzuca wszystko.

Answer 2

A co z użyciem wyrażeń regularnych lub innej metody podziału tekstu wejściowego na tablicę słów. Następnie przeprowadź słowa za pomocą pętli, szukając słowa docelowego. Po znalezieniu, weź wymagany plaster tablicowy, połącz go i wydrukuj.

Aby zachować oryginalne białe spacje między wyrazami, można dołączyć je na końcu każdego słowa.

Co więcej, może to zostać zaimplementowane jako parser strumienia, zamiast najpierw podzielić cały ciąg.

Answer 3

Problem z używaniem tego wyrażenia regularnego polega na tym, że powoduje ono wycofanie silnika regex. Liczba prób wzrasta wykładniczo wraz z rozmiarem ciągu znaków, co jest dobrym wynikiem. Możesz zajrzeć do atomic grouping, aby poprawić wydajność.

Alternatywnie można znaleźć pierwsze wystąpienie danego słowa i zacząć przeglądać w tył i w przód dla słów do żądanej długości.Kod 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; 
} 

Oczywiście znalezienie słów przed i po, oraz obsługa częściowych ciągów znaków może stać się naprawdę niepotrzebne.

Answer 4

Jak wspomniano wcześniej, problemem jest bardzo duża ilość cofnięć. Aby rozwiązać ten problem, spróbowałem użyć lookbehind i uprzedzającego, aby zakotwiczyć dopasowanie do łańcucha. Więc wymyśliłem:

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

Niestety, to nie działa, jak zmienne lookbehinds długość nie są obsługiwane w PCRE (lub Perl dla tej sprawy). Więc pozostaje nam:

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

Które tylko rejestruje ciąg dopasowania i do 8 słów po meczu. Jednakże, jeśli use the PREG_OFFSET_CAPTURE flag, uzyskać przesunięcie $match[0] podjąć podciąg do tego momentu, odwrócić ciąg z strrev, uzyskać pierwsze 0-8 słowa (za pomocą /\s*(?:\S+\s+){0,8}/), odwrócić mecz i rekombinacji:

$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]; 
} 

Możesz zrobić to nieco szybciej na bardzo dużych ciągach, biorąc bezpieczny podzestaw znaków przed meczem, np. 100. Następnie odwracasz tylko 100 znaków.

Wszystko to, co powiedziawszy, rozwiązanie, które nie używa wyrażeń regularnych, może działać lepiej.

Answer 5

Oto wewnętrzna funkcja PHP, która robi to, co chcesz. Jest mało prawdopodobne, że będziesz w stanie pokonać tę wydajność w funkcji użytkownika ziemi.

Nie powinno być problemu z używaniem tego dla funkcji UTF-8, ponieważ '\ r', '\ n' i '' (i ogólnie wszystkie znaki ASCII) nie mogą pojawiać się jako część innej sekwencji znaków. Więc jeśli przekażesz prawidłowe dane UTF-8 do obu parametrów, powinieneś być w porządku. Odwracanie danych UTF-8 tak, jak normalnie odwrócisz kodowanie pojedynczego znaku (z strrev) będzie oznaczało kłopoty, ale ta funkcja tego nie robi.

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); 
    } 

} 

Z moich badań, funkcja C jest 4 razy szybciej niż wersja wuputah za (i nie ma problemu strrev).