Булева модель поиска

Информационный поиск (Information retrieval) сегодня – это быстро развивающаяся область знаний, которой занимаются не только отдельные специалисты, но и широко используют миллионы людей, при помощи поисковых систем.

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

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

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

Для осуществления информационного поиска сегодня существует несколько моделей: булева модель, векторная модель, вероятностные модели, модель на основе байесового подхода, также используются блочные модели, языковые и так далее, причем каждая модель имеет свои достоинства и недостатки. В силу того, что в информационном поиске нет одной доминирующей модели, выбор той или иной модели следует осуществлять, исходя из поставленных задач. Из всего перечня существующих моделей самой простой для реализации является булева модель, которая возникла где-то в 50-х годах 20 века.

Модель булева поиска – это модель информационного поиска, в ходе которого можно обрабатывать любой запрос, имеющий вид булева выражения, т.е. выражения, в котором термины (ключевые запросы) используются в сочетании с операциями: AND (логическое «и»), OR (логическое «или»), NOT (логическое отрицание).

В рамках данной модели документ представляется просто как множество слов. Или иными словами, документ это объект, на основе которого строиться система информационного поиска. Группу документов называют коллекцией.

Пример булева поиска

Пусть имеется коллекция, необходимо в ней найти документы, в которых встречается термин 1 (term1) и термин 2 (term2), но не содержится термин 3 (term3). Тогда самым простейшим способом реализации данной задачи – это последовательный пересмотр коллекции. В результате мы можем получить бинарную матрицу инцидентности «термин — документ», где элемент матрицы равен единице, если термин имеется в документе, и 0, если термина в документе нет.

На основании данной матрицы мы можем найти нужный документ. В рассматриваемом примере это Doc1.

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

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

  1. Собрать документы, которые следует индексировать
  2. Разметить текст, превращая каждый документ в список лексем
  3. Преобразовать полученные лексемы в нормальный вид
  4. Проиндексировать документы, в которых имеются термины, и создать инвертируемый индекс.

Обработка запроса по инвертируемому индексу и базовой моделью булевого поиска происходит следующим образом. Предположим нам нужно обработать запрос term1 AND term2, тогда необходимо осуществить следующие этапы обработки поиска:

  1. обнаружить в словаре term1
  2. найти список словопозиций tern1
  3. обнаружить в словаре термин term2
  4. найти список словопозиций term2
  5. найти пересечение списков.

Пересечение списка можно реализовать по средствам известного
алгоритма слияния (merge algorrithms).

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

Подведем некоторые итоги. В основе булевой модели поиска лежат следующие положения:

  1. В основе модели используются следующие категории: термины, документы, коллекция.
  2. Булева логика определяет связь: термин – документ, на основании чего осуществляется поиск
  3. Для обработки запросов используются следующие операции: AND, OR, NOT, пересечение, объединение, разность.

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

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

Используемая литература:

[1] Д. Химстра Модели информационного поиска. Материалы сайта www.intuit.ru

[2] Маннинг, Кристофер Д., Рагхаван, Прабхакар, Шютце, Хайнрих  Введение в информационный поиск. : Пер. с анг. – М.: ООО «И.Д. Вильямс» 2011. – 528 с.: ил. – парал. Тит. Англ.

[3] Каширин К. Основы поисковой оптимизации. Материалы сайта www.advans.ru

4 комментария to “Булева модель поиска”

  1. Сергей Горшков:

    Лично меня всегда интересовали алгоритмы вычисления релевантности. Было бы здорово увидеть статью на эту тему!

  2. Евгений Бурмицкий:

    Нужно тут кнопку в комментах сделать — «+1». Я тоже про релевантность хочу статью. Можете нас с Сергеем отправить по адресу — http://g.zeos.in/?q=%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5%20%D1%80%D0%B5%D0%BB%D0%B5%D0%B2%D0%B0%D0%BD%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8
    но читать статьи знакомых людей как-то интереснее 🙂

  3. Алена Гречиц:

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

Коментарии