Последнее обновление: 18 Апреля 2025 г.

Как найти в тексте соответствие тем или иным ключевым словам?

О возможных алгоритмах лексического поиска по тексту

По сути, это – задача лексического поиска. Такой поиск осуществляют, например, поисковые системы (Яндекс, Google), электронные библиотеки. А в последнее время – еще и искусственный интеллект. При этом ставится задача – как можно быстрее найти в том или ином тексте ключевые слова или слова, релевантные ключевым.

Какие подходы можно использовать для реализации лексического поиска?

На самом деле, подобных подходов, как минимум, несколько. Ниже мы рассмотрим три-четыре из них.

Есть файл объемом 130 кБ, содержащий текст в кодировке UTF-8. Есть также условие на поиск, содержащее ключевые слова и операторы И, ИЛИ:

посредственность && гримерка && (гримаса || скромность) && (скоротстные || офертой) && такелаж && завсегдатаи && Варшавское

По сути, это – логическое условие. Нам необходимо, чтобы оно выполнялось при поиске.

Рассмотрим сразу программный код на языке PHP:

<?php
mb_internal_encoding("UTF-8");

$t0 = microtime(true);
header('Content-type: text/html; charset=utf-8');
echo '<pre>';

$variant = 4;
// 1: eval+stripos
// 2: eval+preg_match
// 3: Регулярные выражения для каждого из искомых слов, применяемые по очереди (сообразно логическим операторам И)
// 4: Универсальное регулярное выражение, включающее в себя все слова, вида "(слово1|слово2)(.*?)(слово1|слово2)(.*?)(слово1|слово2)...и т.д."

$str = 'посредственность && гримерка && (гримаса || скромность) && (скоротстные || офертой) && такелаж && завсегдатаи && Варшавское';
echo 'Исходная строка: ';
echo $str.' ';
$content = file_get_contents('1.txt');

if($variant === 1){
// 1. Путем преобразования поисковой строки в логическое выражение и оценки его при помощи оператора eval, а также при помощи функции stripos

$str_tmp = str_replace('&&', '||', $str);
$str_tmp = str_replace(array('(', ')'), '', $str_tmp);
$str_tmp = preg_replace('/\s+/', ' ', $str_tmp);
$str_Array = array_map('trim', explode('||', $str_tmp));

$bool_rezults = array();

foreach ($str_Array as $elem){
if(stripos($content, $elem) !== false){ // Собственно, поиск слов в содержимом файла
$bool = 1; // true
}else{
$bool = 0; // false
}
$bool_rezults[$elem] = $bool;
}

$str_bool = str_replace(array_keys($bool_rezults), $bool_rezults, $str);

echo 'Строка, преобразованная в логическое выражение, исходя из наличия ее отдельных слов в файле: ';
echo $str_bool .' ';

$str_code = "$bool_expression_REZ = ". $str_bool;
eval($str_code. ";");

echo 'Результат оценки полученного логического выражения при помощи оператора eval: ';
echo '/ bool_expression_REZ = '. $bool_expression_REZ. ' / ';
}

if($variant === 2){
// 2. Путем преобразования поисковой строки в логическое выражение и оценки его при помощи оператора eval, а также при помощи функции preg_match
$str_tmp = str_replace('&&', '||', $str);
$str_tmp = str_replace(array('(', ')'), '', $str_tmp);
$str_tmp = preg_replace('/\s+/', ' ', $str_tmp);
$str_Array = array_map('trim', explode('||', $str_tmp));

$bool_rezults = array();

foreach ($str_Array as $elem){
if(preg_match('/'. $elem. '/', $content) !== false){ // Собственно, поиск слов в содержимом файла
$bool = 1; // true
}else{
$bool = 0; // false
}
$bool_rezults[$elem] = $bool;
}

$str_bool = str_replace(array_keys($bool_rezults), $bool_rezults, $str);

echo 'Строка, преобразованная в логическое выражение, исходя из наличия ее отдельных слов в файле: ';
echo $str_bool .' ';

$str_code = "$bool_expression_REZ = ". $str_bool;
eval($str_code. ";");

echo 'Результат оценки полученного логического выражения при помощи оператора eval: ';
echo '/ bool_expression_REZ = '. $bool_expression_REZ. ' / ';
}

if($variant === 3){
// 3. При помощи регулярного выражения (перебор разных вариантов регулярных выражений)

$str_tmp = preg_replace('[(\s*\|\|\s*)]', '|', $str);
$reg_Array = array_map('trim', explode('&&', $str_tmp));

$REZ = 0;
foreach ($reg_Array as $elem){
if(preg_match('/'. $elem. '/', $content)){
$REZ = 1;
}else{
$REZ = 0;
break;
}
}

echo 'Результат поиска слов при помощи цикла с регулярными выражениями: ';
echo '/ REZ = '. $REZ. ' / ';
}

if($variant === 4){
// 4. При помощи общего регулярного выражения с многочисленными |

$str_tmp = preg_replace('[(\s*\|\|\s*)]', '|', $str);
$reg_Array = array_map('trim', explode('&&', $str_tmp));
$reg_str = '('. implode('|', $reg_Array). ')';
echo ' Единичный компонент регулярного выражения для поиска: '.$reg_str. ' ';

$reg_Array_len = sizeof($reg_Array);
$reg_str_All = $reg_str;
for($i=0; $i<$reg_Array_len-1; $i++){
$reg_str_All = $reg_str_All. '([\s\S]*?)' . $reg_str;
}

echo '</pre>';
echo 'Полученное регулярное выражение ('. mb_strlen($reg_str_All, "UTF-8"). ' символов): ';
echo $reg_str_All. ' ';
if(preg_match('/'. $reg_str_All. '/', $content)){
$REZ = 1;
}else{
$REZ = 0;
}
echo 'Результат поиска слов с использованием универсального (длинного) регулярного выражения: ';
echo '/ REZ = '. $REZ. ' / ';
}

echo 'Затрачено времени для '. $variant. '-го варианта: '. (microtime(true) - $t0). ' секунд.';

Программный код демонстрирует работу трех подходов. Выбор того или иного подхода осуществляется при помощи установления значения переменной $variant, равного 1, 2, 3 или 4.

1-й и 2-й подходы

Два первых подхода основаны на поиске ключевых слов в тексте каждого по отдельности и последующей их замене в условии (критерии поиска, представляющем собой строку) на логические переменные false (0) или true (1). После чего полученное логическое выражение оценивается при помощи оператора eval.

Бытует мнение, что eval не стоит применять, за исключением, быть может, таких и только таких ситуаций, когда без него нельзя обойтись. На наш взгляд, это как раз и есть одна из таких ситуаций.

Второй подход от первого отличается лишь тем, что если в первом поиск ключевого слова по тексту осуществлялся при помощи функции stripos, то во втором – при помощи preg_match. В остальном же 1-й и 2-й подходы не отличаются вообще.

3-й подход

Что касается 3-го подхода, то там вначале критерий поиска разбивается по операторм И (&&). После чего каждая из полученных частей (отдельных слов или их совокупностей, объединенных оператором ИЛИ (||) используется в качестве регулярного выражения в функции preg_match.

Следует отметить, что программный код для 3-го подхода адаптирован, исходя из имеющегося критерия поиска по ключевым словам (см. переменную $str). Если же этот критерий будет иметь иной вид (например, иначе будут расположены скобки), то, скорее всего, придется менять программный код. Ну, или писать логико-синтаксический анализатор. Что в общем случае является непростой задачей.

Т.е. 3-й подход не является универсальным, в отличие от первого и второго подходов.

4-й подход

Он основан на разбиении критерия (поисковой строки с ключевыми словами, содержащими, быть может, операторы И, ИЛИ) на отдельные части, соединяемые операторами И. Из всех таких частей создается конструкция вида

(часть1|часть2|…|частьN)

Затем к ней добавляется выражение, позволяющее искать любые символы:

([\s\S]*?)

Отметим, что можно было бы использовать (.*?), но это не учитывает, в частности, переносы строк.

В итоге, например, для наличия трех операторов И получится примерно следующее:

Такой трюк позволяет учесть возможность наличия слов в анализируемом тексте не в том порядке, в котором они содержатся в критерии для поиска (переменная $str), а в ином. Если такой порядок неизвестен. А он может быть произвольным.

При наличии шести операторов И регулярное выражение увеличится соответствующим образом. Например, в используемом нами примере его длина составила 767 символов. Приводить его здесь не будем. Но, вы можете посмотреть его самостоятельно, указав $variant = 4 и запустив программный код.

В связи с этим стоит отметить, что возможности такого подхода не безграничны. Ибо функции поиска по регулярным выражениям РНР могут проявлять «норов» и не находить соответствия при том, что фактически оно есть. При этом, к сожалению, никакой ошибки PHP не выдает. Это – один из багов РНР, по крайней мере, имеющийся в 5-й версии.

Поэтому при сколько-нибудь длинном регулярном выражении (если число операторов И будет достаточно высоким) этот подход использовать нельзя.

Кроме того, непонятно, корректен ли 4-й подход при мало-мальски сложных критериях поиска; например, как быть с таким критерием(?):

посредственность && гримерка || гримаса && скромность

точнее,

(посредственность && гримерка) || (гримаса && скромность)

Ясно, что представленный программный код (делающий разбиение критерия на части по символам &&) для этой цели уже не годится. Т.е. придется, опять же, проектировать лексико-синтаксический анализатор.

Примерный результат работы:

Исходная строка:

посредственность && гримерка && (гримаса || скромность) && (скоротстные || офертой) && такелаж && завсегдатаи && Варшавское Результат поиска слов при помощи цикла с регулярными выражениями: / REZ = 1 / Затрачено времени для 3-го варианта: 0.042603015899658 секунд.

Как обычно, проведем экспериментальное исследование скорости работы этих трех разных подходов в РНР5 и РНР8.

Типичные времена выполнения в РНР5

Вот что оказалось в PHP5:

1 подход: 0,03-0,07 чек.
2 подход: 0,008-0,03 сек.
3 подход: 0,02-0,05 сек.
4 подход: 0,03-0,06 сек.

Как видно, наиболее быстро работает 2-й вариант, с использованием функции preg_match.

Что, кстати, является довольно любопытным. Дело в том, что функция stripos не является основанной на регулярных выражениях и, вроде бы, не должна предполагать более высокое время выполнения. Но, на практике оказалось не так: функция preg_match работает быстрее.

Типичные времена выполнения в РНР8

1 подход: 0,001-0,008 чек.
2 подход: 0,001-0,007 сек.
3 подход: 0,001-0,007 сек.
4 подход: 0,001-0,008 сек.

Здесь видим, что время выполнения, как обычно, в PHP8 примерно на порядок ниже, чем для РНР5.

Обратим внимание на более существенный разброс времен выполнения в PHP8, в отличие от PHP5. Видимо, это обусловлено особенностями кэширования программных кодов средой РНР.

Есть еще один возможный подход (5-й)

Это если, в продолжение 3-го и 4-го подходов, составлять общее, единое регулярное выражение. И если с операторами ИЛИ проблем нет, технология регулярных выражений легко позволяет использовать оператор |, который является, по сути, регулярным ИЛИ. А вот с операторами И – все гораздо сложнее. Поэтому придется делать перебор.

Дело в том, что ключевые слова в анализируемом тексте могут вовсе необязательно идти именно в том порядке, в котором они заданы в критерии поиска.

Например, рассмотрим три последние слова, объединенных при помощи И:

такелаж && завсегдатаи && Варшавское

Очевидно, что для трех указанных слов придется анализировать 3! = 6 вариантов регулярных выражений:

такелаж.*?завсегдатаи.*?Варшавское
такелаж.*?Варшавское.*?завсегдатаи
Варшавское.*?такелаж.*?завсегдатаи
Варшавское.*?завсегдатаи.*?такелаж
завсегдатаи.*?такелаж.*?Варшавское
завсегдатаи.*?Варшавское.*?такелаж

Таким образом, вычислительная сложность, число разных регулярных выражений данного подхода, являющегося универсальным при использовании регулярных выражений, составит О(n!), где n – число слов, объединенных оператором И. Легко подсчитать, что для используемого в этой статье число слов (выражений) соединенных оператором И, составляет 7. Следовательно, для его применения придется сформировать и проверять 7! = 5040 регулярных выражений.

Поэтому данный подход просто нереально применять на сколько-нибудь сложных критериях. Т.е. это – самый ресурсозатратный подход. Поэтому мы даже не стали проводить эксперименты для его проверки.

Собственно, в 4-м подходе осуществляется такой же перебор, только он происходит не в цикле, не «вручную», а автоматически самим (одним) регулярным выражением.

Что касается 3-го подхода, то он требует написания функциональности для разбора критерия поиска. Т.е. вначале требуется сделать анализ выражений в скобках, объединенных операторами ИЛИ. Затем как-то пытаться по очереди анализировать присутствие/отсутствие слов, соединенных операторами И.

Надо сказать, что реализация подобной функциональности – достаточно непростая задача. Что-то из области искусственного интеллекта.

Ну, да, зато без использования eval.

Тогда как первые два подхода основаны на, быть может, не совсем стандартном решении: на замене искомых ключевых слов на логические переменные (ложь/истина). Ведь, в самом деле, критерий поиска-то представляет собой нечто, очень схожее с логическим выражением.

Если слово присутствует в тексте, то вместо него подставляем истину. Если нет – то ложь. И, как видим, такое решение вполне оправдывается. Для обеих версий РНР оно работает достаточно быстро. При этом программирование такого подхода является сравнительно несложным.

А вот что касается конкретной функции поиска (preg_match или stripos) – опять же, особой разницы в быстродействии нет. Но, если хочется добиться максимальной производительности, следует, конечно, проводить дополнительные эксперименты.

Комментарии:

Всего комментариев:0