Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Классическая модель поиска информации.
Classical information retrieval model
(Стандартная) булева модель поиска информации (BIR) является классической моделью поиска информации (IR) и одновременно первой и наиболее широко используемой. BIR основан на булевой логике и классической теории множеств, в том смысле, что как документы, по которым осуществляется поиск, так и запрос пользователя представляются как наборы терминов (модель "мешка слов"). Поиск осуществляется на основе наличия или отсутствия в документах терминов запроса и соответствия булевым условиям, заданным в запросе.
The (standard) Boolean model of information retrieval (BIR) is a classical information retrieval (IR) model and, at the same time, the first and most adopted one. The BIR is based on Boolean logic and classical set theory in that both the documents to be searched and the user's query are conceived as sets of terms (a bag of words model). Retrieval is based on whether or not the documents contain the query terms and whether they satisfy the boolean conditions described by the query.
Определения
Индексный термин – это слово или выражение, которое может быть подвергнуто стеммингу, описывающее или характеризующее документ, например, ключевое слово, указанное для статьи в журнале. Пусть L – множество всех таких индексных терминов. Документ – это любое подмножество множества L. Запрос – это булево выражение в нормальной форме: где истинно для когда (эквивалентно, запрос может быть представлен в дизъюнктивной нормальной форме). Наша задача – найти множество документов, удовлетворяющих запросу Q. Эта операция называется поиском и состоит из следующих двух шагов:
An index term is a word or expression, which may be stemmed, describing or characterizing a document, such as a keyword given for a journal article. Letbe the set of all such index terms. A document is any subset of Letbe the set of all documents. A query is a Boolean expression in normal form:where is true for when (Equivalently, could be expressed in disjunctive normal form.) We seek to find the set of documents that satisfy This operation is called retrieval and consists of the following two steps:
1. Для каждого элемента из L найти множество документов, удовлетворяющих :
2. Тогда множество документов, удовлетворяющих Q, определяется следующим образом:
1. For each in , find the set of documents that satisfy :2. Then the set of documents that satisfy Q is given by:
Структуры данных и алгоритмы
С чисто формальной математической точки зрения, BIR прост. Однако с практической точки зрения необходимо решить ряд дополнительных задач, связанных с алгоритмами и структурами данных, таких как, например, выбор терминов (ручной, автоматический или комбинированный), стемминг, хеш-таблицы и инвертированная структура файлов и так далее.
From a pure formal mathematical point of view, the BIR is straightforward. From a practical point of view, however, several further problems should be solved that relate to algorithms and data structures, such as, for example, the choice of terms (manual or automatic selection or both), stemming, hash tables, inverted file structure, and so on.
Наборы с гашиш
Другая возможность — использовать хэш-множества. Каждый документ представляется в виде хеш-таблицы, содержащей все отдельные термины этого документа. Поскольку размер хеш-таблицы динамически изменяется при добавлении и удалении терминов, каждый документ будет занимать значительно меньше места в памяти. Однако это приведет к снижению производительности, так как операции со хэш-таблицами сложнее, чем с битовыми векторами. В худшем случае производительность может ухудшиться с O(n) до O(n²). В среднем, снижение производительности не будет существенно отличаться от битовых векторов, а использование памяти будет гораздо эффективнее.
Another possibility is to use hash sets. Each document is represented by a hash table which contains every single term of that document. Since hash table size increases and decreases in real time with the addition and removal of terms, each document will occupy much less space in memory. However, it will have a slowdown in performance because the operations are more complex than with bit vectors. On the worst case performance can degrade from O(n) to O(n2). On the average case, the performance slowdown will not be that much worse than bit vectors and the space usage is much more efficient.
Файл подписи
Каждый документ может быть представлен фильтром Блума, отражающим набор слов в этом документе и хранящимся в битовой строке фиксированной длины, называемой сигнатурой. Файл сигнатур содержит такую объединенную битовую строку для каждого документа в коллекции. Каждый запрос также может быть представлен фильтром Блума, отражающим набор слов в запросе и хранящимся в битовой строке той же фиксированной длины. Битовая строка запроса сравнивается с каждой сигнатурой. Такой файл сигнатур используется в BitFunnel.
Each document can be summarized by Bloom filter representing the set of words in that document, stored in a fixed length bitstring, called a signature. The signature file contains one such superimposed code bitstring for every document in the collection. Each query can also be summarized by a Bloom filter representing the set of words in the query, stored in a bitstring of the same fixed length. The query bitstring is tested against each signature. The signature file approached is used in BitFunnel.