GrabDuck

Полнотекстовый поиск и его возможности

:

Многие СУБД поддерживают методы полнотекстового поиска (Fulltext search), которые позволяют очень быстро находить нужную информацию в больших объемах текста.

В отличие от оператора LIKE, такой тип поиска предусматривает создание соответствующего полнотекстового индекса, который представляет собой своеобразный словарь упоминаний слов в полях. Под словом обычно понимается совокупность из не менее 3-х не пробельных символов (но это может быть изменено). В зависимости от данных словаря может быть вычислена релевантность – сравнительная мера соответствия запроса найденной информации.

В статье рассказывается как работать с полнотекстовым поиском на примере БД MySQL, а так же приведу примеры «нестандартного» использования данного механизма.

В MySQL возможности полнотекстового поиска (только для MyISAM-таблиц) поддерживаются начиная с версии 3.23.23. В последующих версиях механизм потерпел существенные доработки и расширения, в тоге превратившись в мощное средство для создания поисковых механизмов веб-приложений. Главная особенность – быстрый поиск слов в очень больших объемах текстовой информации.

Индекс FULLTEXT


Итак, чтобы работать с полнотекстовым поиском, сначала нам нужно создать соответствующий индекс. Он называется FULLTEXT, и может быть наложен на поля CHAR, VARCHAR и TEXT. Причем, как и в случае с обычным индексом – если происходит поиск по 2-м полям, то нужен объединенный индекс 2-х полей, используйте поиск по одному полю – нужен индекс только этого поля. Например:

CREATE TABLE `articles` (
`id` int(10) unsigned NOT NULL auto_increment,
`title` varchar(200) default NULL,
`body` text,
PRIMARY KEY (`id`),
FULLTEXT KEY `ft1` (`title`,`body`),
FULLTEXT KEY `ft2` (`body`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

В этом примере создается таблица с 2-мя полнотекстовыми индексами: ft1 и ft2, которые можно использовать для поиска в полях title и body, или только в body. Только в поле title искать не получится.

Конструкция MATCH-AGAINST


Собственно для самого полнотекстового поиска в MySQL используется конструкция MATCH(filelds)… AGAINST(words). Она может работать в различных режимах, которые достаточно сильно между собой отличаются. Для всех действует следующее правило: данная конструкция возвращает условную релевантность, но способ вычисления которой может быть разным в зависимости от режима. Еще стоит добавить что во всех режимах поиск всегда регистрозависимый. Далее более подробно о каждом из них.

MATCH-AGAINST IN NATURAL LANGUAGE MODE


— это основной вид поиска, который используется по умолчанию, т.е. если режим не указан:

SELECT * FROM `articles` WHERE MATCH (title,body) AGAINST ('database');

В этом примере мы ищем слово database в полях title и body таблицы articles на основе индекса ft1 (см. пример создания таблицы выше). Выборка будет автоматически отсортирована по релевантности – это происходит в случае указания конструкции MATCH-AGAINST внутри блока WHERE и не задано условие сортировки ORDER BY.

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

SELECT *, MATCH (title,body) AGAINST ('database') as REL
FROM `articles`
WHERE REL > 0;

— этот запрос выдаст ошибку: поле Rel не определено. Что бы работало, придется продублировать данную конструкцию:

SELECT *, MATCH (title,body) AGAINST ('database') as REL
FROM `articles`
WHERE MATCH (title,body) AGAINST ('database') > 0;

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

В примере выше в переменной REL будет вычислена релевантность. Эта величина зависит прежде всего от количества слов в полях tilte и body, того насколько близко данное слово встречается к началу текста, отношения количества встретившихся слов к количеству всех слов в поле и др.

Например, релевантность будет не нулевая, если слово database встретится либо в title, либо body, но если оно встретится и там и там, значение релевантности будет выше, нежели если оно два раза встретится в body.

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

Еще следует заметить что для IN NATURAL LANGUAGE MODE действует так называемое «50% threshold». Это означает, что если слово встречается более чем в 50% всех просматриваемых полей, то оно не будет учитываться, и поиск по этому слову не даст результатов.

MATCH-AGAINST IN BOOLEAN MODE


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

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

Еще особенностями бинарного режима является отсутствие автоматической сортировки в случае указания условия WHERE, однако для сортировки можно использовать алиас:

SELECT *,
MATCH (title,body) AGAINST ('+database MySQL' IN BOOLEAN MODE) as REL
FROM `articles`
WHERE MATCH (title,body) AGAINST ('+database MySQL' IN BOOLEAN MODE)
ORDER BY REL;

Пример выведет все записи содержащие слово database, но если в записи присутствует слово MySQL, то его релевантность будет выше. Записи будут отсортированы по релевантности.

В бинарном режиме отсутствует ограничение «50% threshold». Бинарный режим можно использовать и без создания полнотекстового индекса, однако это будет работать очень медленно.

MATCH-AGAINST IN NATURAL LANGUAGE MODE WITH QUERY EXPANSION


Или просто «WITH QUERY EXPANSION». Работает примерно также, как NATURAL LANGUAGE MODE, с той лишь разницей, то в результат поиска попадают не только совпадения с шаблоном, но и возможные логические совпадения. Это работает примерно так:

Сначала MySQL выполняет запрос аналогичный NATURAL LANGUAGE MODE и формирует результат. По этому результату производится попытка вычислить слова, которые так же имеют высокую релевантность для полученной выборки. В случае, если эти слова присутствуют производится поиск и по ним тоже, но значение их на релевантность будет существенно ниже. Отдается смешанная выборка – сначала те результаты, где слово присутствует, а потом те, которые были получены в результате «повторного» поиска.

WITH QUERY EXPANSION не рекомендуется использовать для больших объемов информации, так как в результат может попасть очень много лишнего.


Пара слов об алгоритмах поиска


Ну, конечно полнотекстовый поиск можно использовать прежде всего для написания алгоритмов поиска. :-) Я не буду заострять на них внимание, скажу просто что при индексации текстовой информации может понадобиться сложный алгоритм обработки, например такой:
  1. убрать все HTML-теги
  2. убрать все непечатные символы, знаки препинания и тому подобное
  3. убрать все слова длинной менее 3-х символов
  4. перевести все слова в нижний регистр

— это только в самом простом случае, без учета морфологии, подсветки, учета ключевых слов и кодировки.

Соответственно, с поисковым запросом надо сделать тоже самое. Режим поиска используется любой – как удобнее… А вообще поиск – это отдельная тема, про которую нужна отдельная статья.

Раскрытие связок многое-ко-многим


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

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

Однако можно выполнить денормализацию по следующей схеме:

Теперь, что бы выбрать группы, принадлежащие к пользователю 2 можно сделать:

SELECT *
FROM `groups`
WHERE MATCH (groups) AGAINST ('+user2' IN BOOLEAN MODE);

Это будет работать намного быстрее, чем исходный вариант (с 3-ей таблицей). Аналогично с группами, но если подобные выборки нам в принципе не нужны, то можно обойтись без соответствующего поля в таблице групп. Тогда получится что-то вроде «односторонней» связи M:N. То есть можно вычислить все M, которые принадлежат к N, не нельзя сделать обратного.

В этом случае, как правило, используется IN BOOLEAN MODE.

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

Использование релевантности как меры отношения одного объекта к другому


Один из алгоритмов для вычисления статей, «похожих» на данную статью. Всё просто: берутся теги данной статьи, и делается полнотекстовый запрос по полю с тегами всех остальных статей с сортировкой по релевантности (если она нужна). Естественно, сначала вылезут те, которые содержат максимальное совпадение по тегам.

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

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

И кое-что в заключение:


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