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

Классическая модель поиска информации

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

Определения

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

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

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

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

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

Запрос представляет собой логическое выражение в нормальной форме: где истинно , когда . (Эквивалентно, может быть выражено в дизъюнктивной нормальной форме .) ${\textstyle Q}$ $${\displaystyle Q=(W_{1}\ \lor \ W_{2}\ \lor \ \cdots )\land \ \cdots \ \land \ (W_{i}\ \lor \ W_{i+1}\ \lor \ \cdots )}$$ ${\textstyle W_{i}}$ ${\displaystyle D_{j}}$ ${\displaystyle t_{i}\in D_{j}}$ ${\textstyle Q}$

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

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

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

1. Для каждого из найдите набор документов, удовлетворяющих : 2. Тогда набор документов, удовлетворяющих Q, определяется следующим образом: Где означает ИЛИ и означает И как логические операторы. ${\textstyle W_{j}}$ ${\textstyle Q}$ ${\textstyle S_{j}}$ ${\textstyle W_{j}}$ $${\displaystyle S_{j}=\{D_{i}\mid W_{j}\}}$$ $${\displaystyle (S_{1}\cup S_{2}\cup \cdots )\cap \cdots \cap (S_{i}\cup S_{i+1}\cup \cdots )}$$ ${\displaystyle \cup }$ ${\displaystyle \cap }$

Пример

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

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

где

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

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

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

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

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

Тогда комплект документов следующий: ${\textstyle D}$

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

где $${\displaystyle {\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}$

$${\displaystyle Q={\text{probability}}\land {\text{decision-making}}}$$Затем, чтобы получить соответствующие документы:

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

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

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

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

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

Недостатки

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

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

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

Хэш-наборы

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

Файл подписи

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

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

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

Файл инвертированного индекса состоит из двух частей: словаря, содержащего все термины, используемые в коллекции, и инвертированного индекса для каждого отдельного термина, в котором перечислены все документы, в которых этот термин упоминается. ^{[4] [5]}

Рекомендации

1. Ланкастер, ФРВ; Файен, Э.Г. (1973), Информационный поиск в режиме онлайн , Melville Publishing Co., Лос-Анджелес, Калифорния
2. «Поиск информации». МТИ Пресс . Проверено 9 декабря 2023 г.
3. Вартик, Стивен (1992). «Булевы операции». Структуры и алгоритмы информационного поиска. ISBN Прентис-Холл, Inc. 0-13-463837-9. Архивировано из оригинала 28 сентября 2013 г.
4. Джастин Зобель; Алистер Моффат; и Котагири Рамамоханарао. «Инвертированные файлы и файлы сигнатур для индексации текста».
5. Боб Гудвин; и другие. «BitFunnel: новый взгляд на сигнатуры для поиска». 2017.
6. Ричард Стартин. «Побитовые подписи и фильтры Блума».

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