Пользователь
0,0
рейтинг
18 сентября 2008 в 15:31

Разработка → Полнотекстовый поиск и его возможности

Многие СУБД поддерживают методы полнотекстового поиска (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 не рекомендуется использовать для больших объемов информации, так как в результат может попасть очень много лишнего.

Использование FULLTEXT SEARCH


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


Ну, конечно полнотекстовый поиск можно использовать прежде всего для написания алгоритмов поиска. :-) Я не буду заострять на них внимание, скажу просто что при индексации текстовой информации может понадобиться сложный алгоритм обработки, например такой:
  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.

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

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


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

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

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

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


Несмотря на все возможности полнотекстовых индексов, стоит учитывать, что сами индексы занимают очень значительное место на диске, и изменения таблиц с ними будет выполняться значительно дольше.
Артемий @enartemy
карма
269,6
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (34)

  • +11
    Круто. Но как подсказывает мне опыт Sphinx — идеальное решение, его использование существенно упрощает жизнь и серверу, и разработчику.
    • +1
      Смотря для каких целей, если там тысяча или десять тысяч небольших текстов, то сфинкс — это стреляние баллистическими ракетами по мухам, ибо fulltext проще построить, не требует отдельного демона и он realtime (сфинкс же реалтайм только имитироват может и то это не одной командой делается).

      А вот если текста (или вообще записей-атрибутов) дофига — то да, сфинкс — король.
      • +1
        ладно вам. как вы решите вопросы релевантности и морфологии????
        • –3
          если речь идет о русском языке, можно поставить общеизвестный Яндекс.Сервер
      • –2
        статья хорошая, спасибо, а вот с данным комментарием я ни разу не согласен.
        Сфинкс — простой и быстрый способ. И легковесный. Поэтому пожалуйста, не «надо ля-ля» про баллистические ракеты разводить :)

        ваш совет с яндекс сервером уж всяко ничуть не лучше, чем сфинкс, если в задачи входит создание поиска с русской морфологией (… а вот если помимо русского нужны ещё немецкая и английская морфология? куда у нас отправится яндекс.сервер? правильно — в /dev/null)

        :)
      • 0
        не одной командой делается).

        indexer --all --rotate --config /my/config/file.conf

        какая вторая команда? :)
    • +2
      Я вообще-то не столько про поиск, сколько про полнотекстовый индекс и его возможости писал.
      Если уж на то пошло, тогда уж и mnogosearch можно вспомнить, хоть он и морально устарел, и вообще дословно алгоримы расказать… Но статья все же несколько не об этом.
    • НЛО прилетело и опубликовало эту надпись здесь
    • +1
      Ага, на виртуальных серверах и небольших проектах, ага) А искать то и в небольших проектах приходится :)
  • +3
    enartemy, вы как минимум опаздали на пару лет со статьёй…
    • +4
      Знаете, а лучше поздно, чем никогда. :-)
  • 0
    Только вчера начал пробовать Sphinx, но статью почитал, спасибо =)
  • +3
    — Кстати, на эту схему очень хорошо ложится тегирование информации, но там не все так просто и это опять же отдельная тема.

    почитал-бы с удовольствием — автор пиши еще!
  • +1
    пожалуйста, добавьте в таги русские слова: «полнотекстовый поиск» «поиск»
  • 0
    спасибо. лично для меня очень полезно
  • 0
    Респект автору! Давно искал статьи на эту тему и вот те на… Спасибо огромное!
  • 0
    Ошибочку в начале исправьте:
    Главная особенность – быстрый поиск слов в очень больших объемах тестовой информации.
  • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    позволю себе немного оффтопа:
    есть несколько миллионов файлов (в пределах 1-10). приходится искать файлы по их метаданным (имя и мозможно диапазон fileSize). в сущности обычный поисковик файлов. таких велосипедов много в локальных сетях.

    идеальным вариантом для такой системы будет СУБД (пусть будет mysql) с очень быстрым LIKE '%%'. к сожалению приходится иметь дело с реальными системами с постоянными апдейтами таблиц (удаление старых ссылок на файлы, добавление новых ссылок на файлы) и LIKE '%%' жутко тормозит.

    писать собственную СУБД накладно. LIKE неэффетиивен. скорее всего прийдется реализовать движок в котором реляционная СУБД будет использоваться как support tool. сейчас остановился на варианте с токенизацией — индексом с токенами из имен файлов. пытаюсь придумать наименее дешевую реализацию.
    возможно среди заинтересовавшихся этой статьей есть опытные архитекторы и просто жертвы высоких нагрузок :)
    • 0
      Sphinx посмотрите.
      В базе будете первичные данные хранить без каких либо накладных индексов, а искать сфинксом — сказка.
      Поиск по двум индексам и мердж этих индексов по ночам даст возможность риал-тайм индексации.
    • НЛО прилетело и опубликовало эту надпись здесь
      • 0
        с токенами еще интереснее: можно отказаться от LIKE '%%' и отправлять запросы к маленькой табличке с |tokenId|fileId|. хорошая избирательность достигается при ширине токена в 3 символа. токены строятся только по полюfileName (путь к файлу в отдельном столбце и не токенизируется) выборка WHERE tokenName IN( 'tokenId' ) будет очень шустрой

        при всей своей простоте это довольно дорогая схема. прийдется реализовывать только если не найду более простое, дешевое и элегантное решение.
        • 0
          ошибся :(
          WHERE tokenId IN( 'tokenId', ..., 'tokenId' )
          • НЛО прилетело и опубликовало эту надпись здесь
            • НЛО прилетело и опубликовало эту надпись здесь
  • +2
    Раньше я считал вот эту статью лучшей по fulltext поиску в mysql на русском
    valera.ws/2007.08.29~fulltext_search_in_mysql/#more-8
    а теперь даже не знаю :)
  • –4
    Статья однобокая, речь идёт только о MySQL. Почему бы не указать сразу об этом в названии статьи?
    • 0
      Следовало внимательнее читать:

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

      Примеры — да, mysql. Но привденные алгоритмы относятся не только к mysql, а вообще полнотествому поиску.
    • 0
      кстати, Николай.
      к сожалению, не удалось посетить во вторник мероприятие. вы не выложите где-нибудь матерьялец?
  • 0
    Кстати, несмотря на возможности алиасов, при запросах конструкцию приходится повторять в разных местах, что усложняет запросы. Вот например нельзя написать так:

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

    Если заменить WHERE на HAVING то можно и не повторять конструкцию. Надо только посмотреть, что будет быстрее HAVING или еще раз посчитать?
    • +1
      Я конечно могу ошибаться, но при HAVING необходимо GROUP BY, т.к. HAVING — это условие групповой операции. А с группировкой запрос палюбому будет работать медленее.
      • 0
        В стандарте необходимо, но на mysql можно без GROUP BY.
        Испытано на mysql 5.0.24
        Цитата из документации:
        A HAVING clause can refer to any column or alias named in a select_expr in the SELECT list or in outer subqueries, and to aggregate functions. However, the SQL standard requires that HAVING must reference only columns in the GROUP BY clause or columns used in aggregate functions.
        • +1
          Специально проверил. Вот выводы:

          Да, действительно, с HAVING делать можно. Но!

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

          Даёт:
          possible_keys: NULL
          keys: NULL
          rows: 6
          extra: NULL

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

          Даёт:
          possible_keys: ft1
          keys: ft1
          rows: 1
          extra: Using where

          — то есть, это работает, но лучше этого не делать. Ключи таблицы аналогичны примеру в статье.
          Тест на MySQL 4.1.16
          • +1
            Все правильно, имменно поэтому в мане по mysql написано что лучше использовать where.
            Поэтому же в начальном комментарии я и написал что нужно сначала проверить скорость выполнения запроса в одном и втором случае. Для данного случая можем получить выигрыш в скорости, а может и нет.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.