Релевантный поиск с морфологией (без индексации)

Часто перед веб-разработчиками встает задача реализации поиска по сайту. Попробуем сконструировать «велосипед», обладающий следующими характеристиками:

  1. Отсутствие индексной таблицы (индексы — тема отдельной статьи);
  2. Работа с кодировкой UTF-8;
  3. Удаление коротких и стоп-слов;
  4. Морфологическое преобразование русских словоформ;
  5. Сортировка результатов с учетом их релевантности;
  6. Постраничная выдача результатов.

Что нужно?

Нам понадобится рабочий веб-сервер с поддержкой PHP. Для морфологического анализа мы будем использовать русскоязычный стеммер Портера. Кроме этого, нам потребуется список стоп-слов и некоторые функции из проекта PHP UTF-8. Поскольку мы договорились, что не будем использовать индексирование, то в базе данных достаточно одной таблицы приблизительно такого вида:

CREATE TABLE `pages` (
   `id` mediumint(8) unsigned AUTO_INCREMENT,
   `title` text NOT NULL,
   `description` text NOT NULL,
   `content` mediumtext NOT NULL,
   `url` varchar(128) NOT NULL,
   PRIMARY KEY (`id`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8;

Искать страницы будем по их содержимому (content), а в сниппетах выводить название (title) и описание (description). Однако при необходимости вы легко сможете расширить поиск до нескольких полей и даже учитывать это при подсчете релевантности.

Предварительная обработка строки

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

$request = !empty($_GET['search']) ? $_GET['search'] : false;
$p = !empty($_GET['p']) ? (int)$_GET['p'] : 0;
$rpp = 10;

Сократим поисковый запрос до 64 символов (такой длины вполне достаточно) и приведем его к нижнему регистру. Для этого воспользуемся функциями из упомянутого выше проекта PHP UTF-8, архив с которым мы распаковали в директорию utf8. Если ваш рабочий сервер поддерживает mbstring, можете воспользоваться аналогичными функциями оттуда.

header('content-type:text/html; charset=utf-8');
require_once 'utf8/utf8.php';
require_once 'utf8/utils/unicode.php';
require_once 'utf8/utils/specials.php';
$q = utf8_substr($request, 0, 64);
$q = utf8_strtolower($q);

Для корректной работы стеммера необходимо заменить буквы «ё» на «е». Далее удаляем из строки все HTML сущности и специальные символы, а идущие подряд пробелы заменяем единичными экземплярами. Таким образом, получаем подготовленную строку из слов, разделенных пробелами.

$q = strtr($q, array('ё' => 'е'));
$q = preg_replace('/&([a-zA-Z0-9]+);/', ' ', $q);
$q = utf8_strip_specials($q, ' ');
$q = trim(preg_replace('/ +/', ' ', $q));

Морфологический анализатор

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

Есть два основных подхода к морфологическому анализу. Первый и наиболее точный — применение алгоритмов с использованием словарей. В качестве примеров можно привести Ispell и AOT. Минусом такого подхода является более высокая нагрузка на сервер, поскольку объем словарей может достигать десятков мегабайт.

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

В качестве стеммера мы воспользуемся реализацией алгоритма Портера на PHP. Однако вы можете использовать пакет PECL::stem или любой другой по своему усмотрению. Стеммер Портера выглядит таким образом:

define('CHAR_LENGTH', 2);
function stem($word){
   $a = rv($word);
   return $a[0].step4(step3(step2(step1($a[1]))));
}

function rv($word){
   $vowels = array('а','е','и','о','у','ы','э','ю','я');
   $flag = 0;
   $rv = $start='';
   for ($i=0; $i<strlen($word); $i+=CHAR_LENGTH){
      if ($flag == 1) $rv .= substr($word, $i, CHAR_LENGTH); else $start .= substr($word, $i, CHAR_LENGTH);
      if (array_search(substr($word,$i,CHAR_LENGTH), $vowels) !== FALSE) $flag = 1;
   }
   return array($start,$rv);
}

function step1($word){
   $perfective1 = array('в', 'вши', 'вшись');
   foreach ($perfective1 as $suffix) 
      if (substr($word, -(strlen($suffix))) == $suffix && (substr($word, -strlen($suffix) - CHAR_LENGTH, CHAR_LENGTH) == 'а' || substr($word, -strlen($suffix) - CHAR_LENGTH, CHAR_LENGTH) == 'я')) 
         return substr($word, 0, strlen($word)-strlen($suffix));
   $perfective2 = array('ив','ивши','ившись','ывши','ывшись');
   foreach ($perfective2 as $suffix) 
      if (substr($word, -(strlen($suffix))) == $suffix) 
         return substr($word, 0, strlen($word) - strlen($suffix));
   $reflexive = array('ся', 'сь');
   foreach ($reflexive as $suffix) 
      if (substr($word, -(strlen($suffix))) == $suffix) 
         $word = substr($word, 0, strlen($word) - strlen($suffix));
   $adjective = array('ее','ие','ые','ое','ими','ыми','ей','ий','ый','ой','ем','им','ым','ом','его','ого','ему','ому','их','ых','ую','юю','ая','яя','ою','ею');
   $participle2 = array('ем','нн','вш','ющ','щ');
   $participle1 = array('ивш','ывш','ующ');
   foreach ($adjective as $suffix) if (substr($word, -(strlen($suffix))) == $suffix){
      $word = substr($word, 0, strlen($word) - strlen($suffix));
      foreach ($participle1 as $suffix) 
         if (substr($word, -(strlen($suffix))) == $suffix && (substr($word, -strlen($suffix) - CHAR_LENGTH, CHAR_LENGTH) == 'а' || substr($word, -strlen($suffix) - CHAR_LENGTH, CHAR_LENGTH) == 'я')) 
            $word = substr($word, 0, strlen($word) - strlen($suffix));
      foreach ($participle2 as $suffix) 
         if (substr($word, -(strlen($suffix))) == $suffix) 
            $word = substr($word, 0, strlen($word) - strlen($suffix));
      return $word;
   }
   $verb1 = array('ла','на','ете','йте','ли','й','л','ем','н','ло','но','ет','ют','ны','ть','ешь','нно');
   foreach ($verb1 as $suffix) 
      if (substr($word, -(strlen($suffix))) == $suffix && (substr($word, -strlen($suffix) - CHAR_LENGTH, CHAR_LENGTH) == 'а' || substr($word, -strlen($suffix) - CHAR_LENGTH, CHAR_LENGTH) == 'я')) 
         return substr($word, 0, strlen($word) - strlen($suffix));
   $verb2 = array('ила','ыла','ена','ейте','уйте','ите','или','ыли','ей','уй','ил','ыл','им','ым','ен','ило','ыло','ено','ят','ует','уют','ит','ыт','ены','ить','ыть','ишь','ую','ю');
   foreach ($verb2 as $suffix) 
      if (substr($word, -(strlen($suffix))) == $suffix) 
         return substr($word, 0, strlen($word) - strlen($suffix));
   $noun = array('а','ев','ов','ие','ье','е','иями','ями','ами','еи','ии','и','ией','ей','ой','ий','й','иям','ям','ием','ем','ам','ом','о','у','ах','иях','ях','ы','ь','ию','ью','ю','ия','ья','я');
   foreach ($noun as $suffix) 
      if (substr($word, -(strlen($suffix))) == $suffix) 
         return substr($word, 0, strlen($word) - strlen($suffix));
   return $word;
} 

function step2($word){
   return substr($word, -CHAR_LENGTH, CHAR_LENGTH) == 'и' ? substr($word, 0, strlen($word) - CHAR_LENGTH) : $word;
}

function step3($word){
   $vowels = array('а','е','и','о','у','ы','э','ю','я');
   $flag = 0;
   $r1 = $r2 = '';
   for ($i=0; $i<strlen($word); $i+=CHAR_LENGTH){
      if ($flag==2) $r1 .= substr($word, $i, CHAR_LENGTH);
        if (array_search(substr($word, $i, CHAR_LENGTH), $vowels) !== FALSE) $flag = 1;
      if ($flag = 1 && array_search(substr($word, $i, CHAR_LENGTH), $vowels) === FALSE) $flag = 2;
   }
   $flag = 0;
   for ($i=0; $i<strlen($r1); $i+=CHAR_LENGTH){
      if ($flag == 2) $r2 .= substr($r1, $i, CHAR_LENGTH);
        if (array_search(substr($r1, $i, CHAR_LENGTH), $vowels) !== FALSE) $flag = 1;
        if ($flag = 1 && array_search(substr($r1, $i, CHAR_LENGTH), $vowels) === FALSE) $flag = 2;
    }
   $derivational = array('ост', 'ость');
   foreach ($derivational as $suffix) 
      if (substr($r2, -(strlen($suffix))) == $suffix) 
         $word = substr($word, 0, strlen($r2) - strlen($suffix));
   return $word;
}

function step4($word){
   if (substr($word, -CHAR_LENGTH * 2) == 'нн') $word = substr($word, 0, strlen($word) - CHAR_LENGTH);
   else {
      $superlative = array('ейш', 'ейше');
      foreach ($superlative as $suffix) 
         if (substr($word, -(strlen($suffix))) == $suffix) 
            $word = substr($word, 0, strlen($word) - strlen($suffix));
      if (substr($word, -CHAR_LENGTH * 2) == 'нн') $word = substr($word, 0, strlen($word) - CHAR_LENGTH);
   }
   if (substr($word, -CHAR_LENGTH, CHAR_LENGTH) == 'ь') $word = substr($word, 0, strlen($word) - CHAR_LENGTH);
   return $word;
}

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

$stopWords = array(
   'что', 'как', 'все', 'она', 'так', 'его', 'только', 'мне', 'было', 'вот',
   'меня', 'еще', 'нет', 'ему', 'теперь', 'когда', 'даже', 'вдруг', 'если',
   'уже', 'или', 'быть', 'был', 'него', 'вас', 'нибудь', 'опять', 'вам', 'ведь',
   'там', 'потом', 'себя', 'может', 'они', 'тут', 'где', 'есть', 'надо', 'ней',
   'для', 'тебя', 'чем', 'была', 'сам', 'чтоб', 'без', 'будто', 'чего', 'раз',
   'тоже', 'себе', 'под', 'будет', 'тогда', 'кто', 'этот', 'того', 'потому',
   'этого', 'какой', 'ним', 'этом', 'один', 'почти', 'мой', 'тем', 'чтобы',
   'нее', 'были', 'куда', 'зачем', 'всех', 'можно', 'при', 'два', 'другой',
   'хоть', 'после', 'над', 'больше', 'тот', 'через', 'эти', 'нас', 'про', 'них',
   'какая', 'много', 'разве', 'три', 'эту', 'моя', 'свою', 'этой', 'перед',
   'чуть', 'том', 'такой', 'более', 'всю'
);

Построение SQL-запроса

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

(LENGTH(field) - LENGTH(REPLACE(field, word, ""))) / LENGTH(word)

Конечно, правильнее было бы нормализовать количество вхождений длиной текста, так как налицо разница между десятью повторениями в целой книге и пятью — в одном абзаце (второй случай более релевантен, несмотря на меньшее количество совпадений). Однако средствами SQL без применения хранимых процедур невозможно определить общее количество слов в строке. Поэтому придется пренебречь амплитудой объема страниц, считая их приблизительно одинаковыми.

Итак, для начала сформируем части запроса, содержащие конструкцию WHERE и подсчет релевантности. Последняя определяется как сумма вхождений каждой из искомых лемм. Если вы хотите реализовать поиск по нескольким полям таблицы, то нужно соответсвующим образом изменить эти части запроса. При этом можно повысить вес некоторых полей, добавив для них какой-либо коэффициент в формулу подсчета релевантности.

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

$where = 'false';
$relevance = '0';
$count = 0;
$words = explode(' ', $q);
foreach($words as $w){
   if (utf8_strlen($w) < 3 || in_array($w, $stopWords)) continue;
   if ($count++ > 4) break;
   $w = stem($w);
   $where .= ' OR content LIKE "%'.$w.'%"';
   $relevance .= ' + ((LENGTH(content) -
      LENGTH(REPLACE(content, "'.$w.'", ""))) / LENGTH("'.$w.'"))';
}
$relevance .= ' as relevance';

Поскольку мы намереваемся получать результаты постранично, нам понадобятся два SQL-запроса. Из первого мы узнаем общее количество искомых страниц, а с помощью второго выберем необходимые для отображения (в количестве, указанном в $rpp), отсортировав их по убыванию релевантности.

$tq = mysql_query('SELECT count(*) as n FROM pages WHERE '.$where.' LIMIT 1');
$tr = mysql_fetch_array($tq);
$total = $tr[0];
$rows = mysql_query('SELECT
      title as `title`,
      description as `description`,
      url as `url`,
      LOWER(content) as `content`,
      '.$relevance.'
   FROM pages WHERE '.$where.' ORDER BY relevance DESC
   LIMIT '.($p * $rpp).', '.$rpp);

Вывод результатов

Остается только отобразить форму ввода запроса вместе с результатами поиска:

echo '<form action="">';
echo '<input type="search" name="search" value="'.stripslashes($request).'" />';
echo '<input type="submit" value="Искать" />';
echo '</form>';
echo '<h2>'.($total ? 'Найдено документов: '.$total : 'Ничего не найдено').'</h2>';
echo '<section>';
while($r = mysql_fetch_array($rows)){
   echo '<article>';
   echo '<h3><a href="'.$r['url'].'">'.$r['title'].'</a></h3>';
   echo '<p>'.$r['description'].'</p>';
   echo '</article>';
}
echo '</section>';

И наконец, добавим ссылки для перемещения между страницами результатов:

if ($total){ 
   $url = '?search='.$request; 
   $radius = 5; 
   $current = $p; 
   $offset = $current * $rpp; 
   $lastPage = ceil($total / $rpp) - 1; 
   if ($lastPage){ 
      echo '<nav>'; 
      if ($current > $radius) echo '<a href="'.$url.'">1</a>&nbsp;'; 
      for($i = max(0, $current - $radius);  
         $i <= min($lastPage, $current + $radius); $i++) 
         if ($current == $i) echo '&nbsp;<b>'.($i+1).'</b>&nbsp;'; 
         else { 
            echo '&nbsp;<a href="'.$url.($i ? '&amp;p='.$i : '').'">'; 
            if (($i == $current - $radius && $i > 0) ||  
               ($i == $current + $radius && $i < $lastPage)) echo '&hellip;'; 
               else echo $i+1; 
            echo '</a>&nbsp;'; 
         } 
      if ($current < $lastPage - $radius)  
         echo '&nbsp;<a href="'.$url.'&amp;p='.$i.'/">'.($lastPage+1).'</a>'; 
      echo '</nav>'; 
   } 
}

Исключение тегов и атрибутов

Серьезным минусом безындексной реализации является поиск по всему документу, включая теги и их атрибуты. Например, намереваясь найти страницы со словом «article», вы найдете также и все документы с одноименным тегом. Это не страшно, если у вас русскоязычный сайт о цветах или автомобилях. Хуже, если ваши пользователи действительно часто ищут слова вроде «article», «section», «script» и т. д. Помочь в этом случае может хранимая процедура MySQL, удаляющая из строки все теги. Выглядит она следующим образом:

SET GLOBAL log_bin_trust_function_creators=1; 
DROP FUNCTION IF EXISTS fnStripTags; 
DELIMITER | 
CREATE FUNCTION fnStripTags( Dirty varchar(4000) ) 
RETURNS varchar(4000) 
DETERMINISTIC 
BEGIN 
   DECLARE iStart, iEnd, iLength int; 
   WHILE Locate( '<', Dirty ) > 0 And Locate( '>', Dirty, Locate( '<', Dirty )) > 0 DO 
      BEGIN 
         SET iStart = Locate( '<', Dirty ), iEnd = Locate( '>', Dirty, Locate('<', Dirty )); 
         SET iLength = ( iEnd - iStart) + 1; 
         IF iLength > 0 THEN 
            BEGIN 
               SET Dirty = Insert( Dirty, iStart, iLength, ''); 
            END; 
         END IF; 
      END; 
   END WHILE; 
   RETURN Dirty; 
END; 
| 
DELIMITER ;

Хранимые процедуры поддерживаются в системе InnoDB, но не в MyISAM. Поэтому использование этой возможности остается на ваше усмотрение.

11 комментариев

Хорошая статья, всё работает. Только в коде случайно попал &nbsp; из Морфологического анализатора в функции function step1 на 3-й строке перед if.
Автору спасибо.

Антон из Ставрополя @ 8 декабря 2011

И вам спасибо!
Опечатку поправил.

Алексей @ 8 декабря 2011

Вот я немного модифицировал ваш скрипт.
Добавил возможность выбора метода поиска.
Исходник: http://pastebin.com/i3h12ieE
Рабочий пример: http://ncgti.ru/?page=search/search

Антон из Ставрополя @ 8 декабря 2011

Занятная штука. Почерпнул для себя немного кода. Отдельный респект!

Орион @ 8 мая 2012

При копировании строки
$q = strtr($q, array('ё' => 'e')); //замена ё на е
неправильно происходила замена букв, т.к. в коде написана английская буква "e". Ее нужно заменить на русскую "е"

гость @ 16 августа 2013

Спасибо, исправил.

Алексей @ 13 сентября 2013

можно пример какой нибудь, исходники,
чтоб понять что да как))
а то чайникам(то бишь мне ) не совсем понятно((

Арго @ 22 апреля 2014

Спасибо! Статья актуальна.
Но когда же выйдет продолжение с индексированием данных?

Том @ 23 апреля 2014

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

энергетик @ 29 ноября 2014

Бесполезная штука враках задачи "сделать поиск релевантный без индексов", к тому же малопроизводительный иза отсуствия индексов и UDF mysql

Начиная с 5.6 Mysql умеет использовать FULLTEXT index для InnoDB.

Sphinx все же лучшие решение для поиска по релевантности морфологии итд. Благодаря настройке формул ранжирования

Александр @ 17 апреля 2015

Спасибо большое!
Получилось очень здорово, но только после небольшой доработки. У меня не работает вот так, $a[1] - всегда возвращает пустоту
return $a[0].step4(step3(step2(step1($a[1]))));

работает вот так
return step4(step3(step2(step1($a[0]))));

Скажите пожалуйста, что делает функция rv($word)? В ней переменная $flag == 1 только на последней букве слова, последняя итерация цикла, соответственно функция всегда возвращает $rv = '' (пусто)

Кристина @ 26 ноября 2015