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

Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Июнь 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

(Стандартная) булева модель поиска информации (BIR) ^[1] является классической моделью поиска информации (IR) и, в то же время, первой и наиболее распространенной. Он используется многими ИК-системами по сей день. ^{[ необходима цитата ]} ЗБИ основывается на булевой логике и классической теории множеств в том смысле, что как документы, в которых будет выполняться поиск, так и запрос пользователя задуманы как наборы терминов ( модель набора слов ). Получение зависит от того, содержат ли документы условия запроса.

Определения [ править ]

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

{\ Displaystyle Т = \ {t_ {1}, t_ {2}, \ \ ldots, \ t_ {m} \}}

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

Документ является любое подмножество . Позволять ${\ displaystyle T}$

{\ Displaystyle D = \ {D_ {1}, \ \ ldots \, D_ {п} \}}

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

Запроса является логическим выражением в нормальной форме: ${\ 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. Для каждого in найдите набор документов, которые удовлетворяют :

{\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}}

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

Во - первых, следующие наборы и документов получены (извлечены): ${\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}}$
Наконец, следующие документы извлекаются в ответ на ${\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}$

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

Преимущества [ править ]

Чистый формализм
Легко реализовать
Интуитивная концепция

Недостатки [ править ]

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

Структуры данных и алгоритмы [ править ]

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

Наборы хешей [ править ]

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

Файл подписи [ править ]

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

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

Инвертированный файл [ править ]

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

Ссылки [ править ]

^ Ланкастер, FW; Файен, EG (1973), Информационный поиск в Интернете , Melville Publishing Co., Лос-Анджелес, Калифорния
^ Wartik, Стивен (1992). «Логические операции». Структуры и алгоритмы поиска данных . ISBN компании Prentice-Hall, Inc. 0-13-463837-9. Архивировано из оригинала на 2013-09-28.
^ a b Джастин Зобель; Алистер Моффат; и Котагири Рамамоханарао. «Инвертированные файлы и файлы подписи для индексирования текста» .
^ а б Боб Гудвин; et. al. «BitFunnel: пересмотр подписей для поиска» . 2017 г.
^ Ричард Стартин. «Битовые подписи и фильтры Блума» .

Лашкари, AH; Махдави, Ф .; Ghomi, В. (2009), Булева модель по информационному поиску в поисковых системах , DOI : 10,1109 / ICIME.2009.101

[1] Ланкастер, FW; Файен, EG (1973), Информационный поиск в Интернете , Melville Publishing Co., Лос-Анджелес, Калифорния

[wartik-2] Wartik, Стивен (1992). «Логические операции». Структуры и алгоритмы поиска данных . ISBN компании Prentice-Hall, Inc. 0-13-463837-9. Архивировано из оригинала на 2013-09-28.

[zobel-3] Джастин Зобель; Алистер Моффат; и Котагири Рамамоханарао. «Инвертированные файлы и файлы подписи для индексирования текста» .

[goodwin-4] а б Боб Гудвин; et. al. «BitFunnel: пересмотр подписей для поиска» . 2017 г.

[5] Ричард Стартин. «Битовые подписи и фильтры Блума» .

[1]