четверг, 12 марта 2009 г.

Полнотекстовый поиск: введение

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

Итак, можно выделить несколько основных способов поиска информации.

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

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

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

Итак, основная особенность полнотекстового поиска заключается в том, что мы ищем не "строгую последовательность символов", а слова (со всеми словоформами). Большинство продуктов, реализующих эту технологию, также позволяют искать "слова, похожие на заданное", использовать булевые операторы и т.п. Кроме того, все коммерческие реализации ищут не по самим строкам/документам, а по индексу, построенному для них.

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

  1. Разбить текст на слова (более точно: лексемы) - за это отвечает лексический аналазитор (tokenizer).
  2. Произвести фильтрацию полученных слов (пропустить некоторые из них (стоп-список), обработать одинаковые и т.п.) - за это отвечает (необязательный) фильтр лексем (token filter).
  3. Найти основу каждого слова (стем) - за это отвечает стеммер (stemmer).

Далее в индексе сохраняется информация о том, какие стемы были найдены в конкретной строке/документе и, возможно, еще какая-то информация (взаимное расположение стемов, их количество и т.п.).

В ходе поиска запрос обрабатывается по-тому же алгоритму, что и исходные строки/документы (хотя возможны и отличия, например на стадии фильтрации). Далее, фактически, мы ищем в индексе те строки/документы, которые содержат стемы, полученные в рзультате обработки поискового запроса (с учетом булевых операторов). Кроме этого, поиск может быть сдела более интеллектуальным: поиск слов, похожих, на заданное, поиск документов, в которых заданные слова встречаются рядом, и т.п. - здесь все зависит от функциональности составленного нами индекса.

Далее я планирую остановиться на двух реализциях данной технологии: MS SQL Server Full Text Search и Apache Solr.

HTH

AlexS

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

Отправить комментарий