Булева модель поиска информации

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

Определения

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

$$T=\{t_{1},t_{2},\ \ldots ,\ t_{m}\}$$

быть набором всех таких индексных термов.

Документ – это любое подмножество $T$. Позволять

$$D=\{D_{1},\ \ldots \ ,D_{n}\}$$

быть комплектом всех документов.

Запрос — это логическое выражение ${\textstyle Q}$ в нормальной форме:

$$Q=(W_{1}\ \lor \ W_{2}\ \lor \ \cdots )\land \ \cdots \ \land \ (W_{i}\ \lor \ W_{i+1}\ \lor \ \cdots )$$

где ${\textstyle W_{i}}$ верно для $D_{j}$ когда $t_{i}\in D_{j}$. (Эквивалентно, ${\textstyle Q}$ можно выразить в дизъюнктивной нормальной форме .)

Мы стремимся найти комплект документов, удовлетворяющий ${\textstyle Q}$. Эта операция называется поиском и состоит из следующих двух шагов:

1. Для каждого ${\textstyle W_{j}}$ в ${\textstyle Q}$, найдите набор ${\textstyle S_{j}}$ документов, удовлетворяющих ${\textstyle W_{j}}$:

$$S_{j}=\{D_{i}\mid W_{j}\}$$

2. Тогда набор документов, удовлетворяющих Q, определяется следующим образом:

$$(S_{1}\cup S_{2}\cup \cdots )\cap \cdots \cap (S_{i}\cup S_{i+1}\cup \cdots )$$

Пример

Пусть набор оригинальных (реальных) документов будет, например,

$O=\{O_{1},\ O_{2},\ O_{3}\}$

где

${\textstyle O_{1}}$ = «Принцип Байеса: принцип, согласно которому при оценке параметра следует изначально предположить, что каждое возможное значение имеет равную вероятность (равномерное априорное распределение)».

${\textstyle O_{2}}$ = « Байесовская теория принятия решений : математическая теория принятия решений, которая предполагает функции полезности и вероятности и согласно которой выбираемое действие является действием Байеса, то есть действием с наивысшей субъективной ожидаемой полезностью. Если бы у кого-то было неограниченное время и расчеты власть, с которой можно принимать любое решение, эта процедура была бы лучшим способом принятия любого решения».

${\textstyle O_{3}}$ = «Байесовская эпистемология : Философская теория, которая утверждает, что эпистемический статус предложения (т.е. насколько хорошо оно доказано или хорошо установлено) лучше всего измеряется вероятностью и что правильный способ пересмотра этой вероятности определяется байесовской кондиционализацией или чем-то подобным. Байесовский эпистемолог будет использовать вероятность для определения и исследования взаимосвязи между такими понятиями, как эпистемический статус, поддержка или объяснительная сила».

Пусть набор ${\textstyle T}$ терминов быть:

$$T=\{t_{1}={\text{Bayes' principle}},t_{2}={\text{probability}},t_{3}={\text{decision-making}},t_{4}={\text{Bayesian epistemology}}\}$$

Тогда набор ${\textstyle D}$ документов выглядит следующим образом:

$$D=\{D_{1},\ D_{2},\ D_{3}\}$$

где

$${\begin{aligned}D_{1}&=\{{\text{probability}},\ {\text{Bayes' principle}}\}\\D_{2}&=\{{\text{probability}},\ {\text{decision-making}}\}\\D_{3}&=\{{\text{probability}},\ {\text{Bayesian epistemology}}\}\end{aligned}}$$

Пусть запрос ${\textstyle Q}$ быть:

$$Q={\text{probability}}\land {\text{decision-making}}$$

Затем, чтобы получить соответствующие документы:

1. Во-первых, следующие наборы ${\textstyle S_{1}}$ и ${\textstyle S_{2}}$ документов ${\textstyle D_{i}}$ получены (получены):
   $${\begin{aligned}S_{1}&=\{D_{1},\ D_{2},\ D_{3}\}\\S_{2}&=\{D_{2}\}\end{aligned}}$$
2. Наконец, следующие документы ${\textstyle D_{i}}$ извлекаются в ответ на ${\textstyle Q}$
   $$Q:\{D_{1},\ D_{2},\ D_{3}\}\ \cap \ \{D_{2}\}\ =\ \{D_{2}\}$$

Это означает, что исходный документ ${\textstyle O_{2}}$ (соответствует ${\textstyle D_{2}}$) это ответ на ${\textstyle Q}$.

Очевидно, что если существует более одного документа с одинаковым представлением, извлекается каждый такой документ. Такие документы в БИР неотличимы (иными словами, эквивалентны).

Преимущества

• Чистый формализм
• Легко реализовать
• Интуитивная концепция
• Если результирующий набор документов либо слишком мал, либо слишком велик, сразу понятно, какие операторы будут производить соответственно больший или меньший набор.
• Это дает (экспертным) пользователям ощущение контроля над системой. Сразу понятно, почему документ был получен по запросу.

Недостатки

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

Структуры данных и алгоритмы

С чисто формальной математической точки зрения BIR прост. Однако с практической точки зрения необходимо решить несколько дополнительных проблем, связанных с алгоритмами и структурами данных, таких как, например, выбор терминов (ручной или автоматический выбор или оба), стемминг , хеш-таблицы , инвертированная файловая структура. , и так далее.

Хэш-наборы

Основная статья: хеширование функций

Другая возможность — использовать хэш-наборы . Каждый документ представлен хеш-таблицей, которая содержит каждый термин этого документа. Поскольку размер хеш-таблицы увеличивается и уменьшается в реальном времени при добавлении и удалении термов, каждый документ будет занимать гораздо меньше места в памяти. Однако при этом будет наблюдаться снижение производительности, поскольку операции более сложны, чем с битовыми векторами . В худшем случае производительность может ухудшиться с O( n ) до O( n ² ). В среднем, замедление производительности будет не намного сильнее, чем у битовых векторов, а использование пространства будет гораздо более эффективным.

Файл подписи

Каждый документ можно суммировать с помощью фильтра Блума, представляющего набор слов в этом документе, хранящихся в битовой строке фиксированной длины, называемой подписью.Файл подписи содержит одну такую ​​битовую строку наложенного кода для каждого документа в коллекции.Каждый запрос также может быть суммирован с помощью фильтра Блума, представляющего набор слов в запросе, хранящихся в битовой строке той же фиксированной длины.Битовая строка запроса проверяется на соответствие каждой сигнатуре.

Подходящий файл подписи используется в BitFunnel .

Инвертированный файл

Основная статья: инвертированный индекс

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

Ссылки

• Лашкари, АХ; Махдави, Ф.; Гоми, В. (2009), «Булева модель поиска информации для поисковых систем», Международная конференция 2009 г. по управлению информацией и инженерии , стр. 385–389, doi : 10.1109/ICIME.2009.101 , ISBN  978-0-7695-3595-1 , S2CID   18147603