Regex optimizada para N palabras alrededor de una palabra determinada (UTF-8)

Question

Estoy tratando de encontrar una expresión regular optimizada para devolver las N palabras (si está disponible) alrededor de otra para crear un resumen. La cadena está en UTF-8, por lo que la definición de "palabras" es más grande que solo [a-z]. La cadena que sirve como palabra de referencia podría estar en medio de una palabra o no estar directamente rodeada de espacios.

ya tengo los siguientes que funciona, pero parece realmente codicioso y se ahoga en la búsqueda de más de 6-7 palabras alrededor de otro:

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

Este es el método PHP que he construyo hacer eso, pero necesitaría ayuda para que la expresión regular sea menos codiciosa y funcione para cualquier cantidad de palabras.

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

si tuviera el siguiente $ cadena:

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

y llamó getWordsAround($string, 'vitae', 8, 8) que me gustaría obtener el siguiente resultado:

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

Gracias por su ayuda gurús de expresiones regulares.

Answer 1

Esto funcionó muy bien aquí:

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

Da:

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

El rendimiento de esta expresión regular, sin embargo, es una basura absoluta. Realmente no sé cómo hacer esto más eficiente, a menos que lo haga sin expresiones regulares.

La razón para el desempeño de ser "basura absoluta" para las palabras cerca del final es que el motor intenta iniciar un partido en cada personaje, para ir avanzando varias docenas de caracteres hasta que se entera de que, al final, se no puede encontrar la cadena que está buscando y descarta todo.

Answer 2

¿Qué pasa con el uso de una expresión regular u otro método para dividir el texto de entrada en una matriz de palabras? Luego, repase las palabras con un bucle buscando la palabra objetivo. Una vez que se encuentra, toma la porción de matriz requerida, únela e imprime.

Para mantener el espacio en blanco original entre las palabras, puede incluirlo al final de cada palabra.

Además, esto podría implementarse como un analizador de flujo en lugar de dividir toda la cadena primero.

Answer 3

El problema con el uso de esta expresión regular es que hace que el motor regex retroceda catastróficamente. El número de intentos aumenta exponencialmente con el tamaño de la cadena, y eso es no bueno. Es posible que desee consultar atomic grouping para mejorar el rendimiento.

Alternativamente, podría encontrar la primera aparición de la palabra dada y comenzar a mirar hacia atrás y hacia adelante para palabras hasta la longitud deseada.código de 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; 
} 

Por supuesto, la búsqueda de las palabras antes y después, y el manejo de cadenas parciales puede volver muy sucia.

Answer 4

Como se mencionó anteriormente, el problema es una gran cantidad de retroceso. Para resolver esto, intenté usar lookbehind y lookahead para anclar la coincidencia a la cadena. Así que se me ocurrió:

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

Por desgracia, esto no funciona, como lookbehinds de longitud variable no se admiten en PCRE (Perl o para el caso). Así que nos quedamos con:

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

Lo que sólo captura la cadena de búsqueda y hasta 8 Declaraciones tras el partido. Sin embargo, si use the PREG_OFFSET_CAPTURE flag, conseguir el desplazamiento de $match[0], tomar la subcadena hasta ese momento, invertir la cadena con strrev Obtenga las primeras 0-8 palabras (usando /\s*(?:\S+\s+){0,8}/), invierta el partido, y recombinar:

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

Puede hacer que sea más rápido en secuencias muy grandes tomando un subconjunto seguro de caracteres antes de la coincidencia, como 100. Entonces solo está invirtiendo una cadena de 100 caracteres.

Dicho todo esto, una solución que no usa expresiones regulares puede funcionar mejor.

Answer 5

Aquí hay una función interna de PHP que hace lo que quiere. Es poco probable que puedas superar este rendimiento en una función usuario-terreno.

No debería haber ningún problema al usar esto para las funciones UTF-8, ya que '\ r', '\ n' y '' (y en general todos los caracteres ASCII) no pueden aparecer como parte de otra secuencia de caracteres. Entonces, si pasa datos válidos de UTF-8 a ambos parámetros, estará bien. Invertir los datos UTF-8 como lo haría normalmente con las codificaciones de un solo carácter (con strrev) significaría problemas, pero esta función no hace eso.

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

} 

De mis pruebas, la función C es 4 veces más rápido que la versión de wuputah (y no tiene el problema de strrev).