Оптимизированное регулярное выражение для N слов вокруг заданного слова (UTF-8) - PullRequest
6 голосов
/ 27 августа 2010

Я пытаюсь найти оптимизированное регулярное выражение, чтобы вернуть N слов (если они есть) вокруг другого, чтобы построить резюме. Строка в UTF-8, поэтому определение «слова» больше, чем просто [a-z]. Строка, которая служит справочным словом, может быть в середине слова или не быть непосредственно окружена пробелами.

У меня уже есть следующее, которое работает, но кажется жадным и задыхается при поиске более 6-7 слов вокруг другого:

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

Это PHP-метод, который я создал для этого, но мне нужна помощь, чтобы регулярное выражение было менее жадным и работало с любым количеством слов вокруг.

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

Если бы у меня была следующая строка $:

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

И позвонил getWordsAround($string, 'vitae', 8, 8) Я бы хотел получить следующий результат:

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

Спасибо за вашу помощь, гуру регулярных выражений.

Ответы [ 5 ]

2 голосов
/ 28 августа 2010

Вот внутренняя функция PHP, которая делает то, что вы хотите. Маловероятно, что вы сможете превзойти это с точки зрения производительности в функции пользовательского пространства.

Не должно быть проблем с использованием этого для функций UTF-8, так как '\ r', '\ n' и '' (и в целом все символы ASCII) не могут появляться как часть другой последовательности символов. Поэтому, если вы передадите действительные данные UTF-8 обоим параметрам, все будет в порядке. Обращение данных UTF-8 так, как если бы вы обычно переворачивали односимвольные кодировки (с strrev), действительно означало бы проблемы, но эта функция этого не делает.

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

}

Из моих тестов функция C работает в 4 раза быстрее, чем версия wuputah (и не имеет проблемы strrev).

2 голосов
/ 27 августа 2010

Как упоминалось ранее, проблема заключается в очень большом количестве возвратов. Чтобы решить эту проблему, я попытался использовать lookbehind и lookahead для привязки совпадения к строке. Итак, я придумал:

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

К сожалению, это не работает, так как вид сзади переменной длины не поддерживается в PCRE (или perl в этом отношении). Итак, у нас осталось:

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

Который захватывает только строку совпадения и до 8 слов после совпадения. Однако, если вы используете флаг PREG_OFFSET_CAPTURE , получите смещение $match[0], поднимите подстроку до этой точки, переверните строку с помощью strrev, получите первые 0-8 слов (используя /\s*(?:\S+\s+){0,8}/), измените совпадение и рекомбинируйте:

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

Вы можете сделать это немного быстрее на очень больших строках, взяв безопасное подмножество символов перед совпадением, например, 100. Тогда вы переворачиваете только строку из 100 символов.

При этом решение, которое не использует регулярные выражения, может работать лучше.

2 голосов
/ 27 августа 2010

Как насчет использования регулярных выражений или другого метода для разделения входного текста на массив слов. Затем бегите по словам с помощью цикла, ища целевое слово. Когда он найден, возьмите нужный фрагмент массива, объедините его и напечатайте.

Чтобы сохранить оригинальный пробел между словами, вы можете включить его в конце каждого слова.

Кроме того, это может быть реализовано как анализатор потока, а не разбивать сначала всю строку.

1 голос
/ 27 августа 2010

Проблема с использованием этого регулярного выражения заключается в том, что он приводит к катастрофическому возврату движка регулярного выражения.Количество попыток увеличивается экспоненциально с размером строки, и это нет хорошо.Возможно, вы захотите изучить атомарную группировку для повышения производительности.

В качестве альтернативы вы можете найти первое вхождение данного слова и начать поиск назад и вперед для слов до желаемой длины.Псевдо-код выхода:

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

Конечно, поиск слов до и после и обработка неполных строк могут привести к большим ошибкам.

1 голос
/ 27 августа 2010

Это работало нормально здесь:

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

Дает:

Lorem Ipsum Dolor Sit Amet, Concetetur Adipiscing Elit. Cras auctor, Felis Non Vehicleula Suscipit,

Выполнение этого регулярного выражения, однако, является абсолютным дерьмом. Я действительно не знаю, как сделать это более эффективным, если не делать это без регулярных выражений.

Причиной того, что производительность является «абсолютным дерьмом» для слов в конце, является то, что движок пытается начать совпадение с каждого символа , а затем продвигает несколько десятков символов, пока не обнаружит, что конец, он не может найти искомую строку и отбрасывает все.

...