Espressione regolare ottimizzata per N parole attorno a una determinata parola (UTF-8)

Question

Sto cercando di trovare un'espressione regolare per restituire le parole N (se disponibili) attorno a un'altra per creare un riepilogo. La stringa è in UTF-8, quindi la definizione di "parole" è più grande di solo [a-z]. La stringa che funge da parola di riferimento potrebbe essere nel mezzo di una parola o non circondata direttamente da spazi.

ho già ottenuto il seguente che funziona, ma sembra in realtà avido e soffoca quando alla ricerca di più di 6-7 parole intorno a un altro:

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

questo è il metodo PHP che ho costruisco fare ma avrei bisogno di aiuto per far sì che la regex sia meno avida e funzioni per qualsiasi numero di parole.

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

se ho avuto la seguente stringa di $:

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

e chiamò getWordsAround($string, 'vitae', 8, 8) avrei voluto ottenere il seguente risultato:

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

Grazie per il vostro aiuto guru regex.

Answer 1

Questo ha funzionato bene qui:

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

Dà:

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

Le prestazioni di questa espressione regolare, tuttavia, è una schifezza assoluta. Non so davvero come renderlo più efficiente, a meno di farlo senza espressioni regolari.

La ragione per la performance essere "schifezza assoluta" per le parole vicino alla fine è che il motore tenta di avviare una partita in ogni personaggio e poi avanza diverse decine di caratteri fino a quando non scopre che, alla fine, si non riesci a trovare la stringa che stai cercando e scarta tutto.

Answer 2

Che dire dell'uso di un'espressione regolare o di un altro metodo per dividere il testo di input in una serie di parole. Quindi passa attraverso le parole con un loop cercando la parola target. Una volta trovato, prendi la porzione di matrice richiesta, unisciti a essa e stampa.

Per mantenere lo spazio bianco originale tra le parole, è possibile includerlo alla fine di ogni parola.

Inoltre, questo potrebbe essere implementato come un parser di flusso piuttosto che dividere prima l'intera stringa.

Answer 3

Il problema con l'utilizzo di questa espressione regolare è che causa il backtrack del motore regex in modo catastrofico. Il numero di tentativi aumenta esponenzialmente con la dimensione della stringa, ovvero no. Potresti voler esaminare atomic grouping per migliorare le prestazioni.

In alternativa è possibile trovare la prima occorrenza della parola data e iniziare a guardare avanti e indietro per le parole fino alla lunghezza desiderata.Codice 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; 
} 

Naturalmente trovare le parole prima e dopo, e la manipolazione stringhe parziali può ottenere davvero disordinato.

Answer 4

Come accennato in precedenza, il problema è un numero molto elevato di backtracking. Per risolvere questo, ho cercato di usare lookbehind e lookahead per ancorare la partita alla stringa. Così mi si avvicinò con:

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

Purtroppo, questo non funziona, come lookbehinds lunghezza variabile non sono supportati in PCRE (Perl o per quella materia). Così ci ritroviamo con:

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

che cattura solo la stringa partita e fino a 8 parole dopo la partita. Tuttavia, se si use the PREG_OFFSET_CAPTURE flag, ottiene l'offset di $match[0], prendere la sottostringa fino a quel punto, invertire la stringa con strrev, ottenere le prime 0-8 parole (utilizzando /\s*(?:\S+\s+){0,8}/), invertire il match, e ricombinare:

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

Puoi renderlo un po 'più veloce su stringhe molto grandi prendendo un sottoinsieme di caratteri sicuro prima dell'incontro, ad esempio 100. Quindi stai solo invertendo una stringa di 100 caratteri.

Tutto ciò detto, una soluzione che non utilizza espressioni regolari può funzionare meglio.

Answer 5

Ecco una funzione PHP interna che fa ciò che vuoi. È improbabile che sarete in grado di battere queste prestazioni in una funzione user-land.

Non ci dovrebbero essere problemi con questo per le funzioni UTF-8, poiché '\ r', '\ n' e '' (e in generale tutti i caratteri ASCII) non possono apparire come parte di un'altra sequenza di caratteri. Quindi se si passano dati UTF-8 validi su entrambi i parametri, si dovrebbe andare bene. Invertire i dati UTF-8 come normalmente invertireste le codifiche a singolo carattere (con strrev) significherebbe davvero un problema, ma questa funzione non lo fa.

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

} 

Dalle mie prove, la funzione C è 4 volte più veloce rispetto alla versione di wuputah (e non ha il problema di strrev).