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

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

Определения

Индексный термин — это слово или выражение , которое может иметь основу , описывая или характеризуя документ, например ключевое слово, указанное для журнальной статьи. Позволять $$T=\{t_{1},t_{2},\ \ldots ,\ t_{n}\}$$быть набором всех таких индексных термов.

Документ – это любое подмножество $T$. Позволять $$D=\{D_{1},\ \ldots \ ,D_{n}\}$$быть комплектом всех документов.

$T$ представляет собой серию слов или небольших фраз (индексных терминов). Каждое из этих слов или небольших фраз названо $t_{n}$, где $n$ — номер термина в серии/списке. Вы можете подумать о $T$ как «Условия» и $t_{n}$ как «индексный термин n ».

Слова или небольшие фразы (индексные термины $t_{n}$) могут существовать в документах. Эти документы затем образуют серию/список. $D$ где каждый отдельный документ называется $D_{n}$. Эти документы ( $D_{n}$) может содержать слова или небольшие фразы (индексные термины $t_{n}$) такой как $D_{1}$ может содержать условия $t_{1}$и $t_{2}$ от $T$. Пример этого можно найти в следующем разделе.

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

Запрос — это логическое выражение ${\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}$ можно выразить в дизъюнктивной нормальной форме .)

Любой $Q$ запросы представляют собой набор индексных терминов ( $t_{n}$ или $W_{n}$) выбрал из набора $T$ терминов, которые объединяются с помощью логических операторов для формирования набора условий.

Эти условия затем применяются к множеству $D$ документов, содержащих одинаковые индексные термины ( $t_{n}$) из набора $T$.

Мы стремимся найти комплект документов, удовлетворяющий ${\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 )$$Где $\cup$ означает ИЛИ и $\cap$ означает И как логические операторы.

Пример

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

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

где

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

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

${\textstyle D_{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}}$$Где $S_{1}$ соответствует документам, содержащим термин «вероятность» и $S_{2}$ содержат термин «принятие решения».
2. Наконец, следующие документы ${\textstyle D_{i}}$ извлекаются в ответ на ${\textstyle Q}$: $$Q:\{D_{1},\ D_{2},\ D_{3}\}\ \cap \ \{D_{2}\}\ =\ \{D_{2}\}$$Где запрос ищет документы, содержащиеся в обоих наборах $S$ с помощью оператора пересечения.

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

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

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

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

Недостатки

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

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

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

Хэш-наборы

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

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

Файл подписи

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

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

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

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

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

Ссылки

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