4. Поиск и ранжирование

Цель

Реализовать алгоритм поиска документов по обратному индексу и простейшую функцию оценки релевантности документа.

Руководство

На входе у поисковика:

1. Текст запроса.

2. Конфиг: параметры парсера и прочие настройки, если потребуется.

3. Объект для доступа к индексу (IndexAccessor).

IndexAccessor предоставляет следующие возможности:

1. Получение содержимого документа по его идентификатору.

2. Получение списка документов по терму.

Алгоритм:

1. Распарсить текст запроса.

2. Для каждого терма запроса извлечь список документов, в которые он входит. На этом этапе уместно вычислить следующие величины:

   • \(\mathit{tf}(t, d)\) — term frequency, количество вхождений терма \(t\) в документ \(d\).

   • \(\mathit{df}(t)\) — document frequency, количество документов, в которых встречается терм \(t\).

3. Для каждого документа вычислить оценку по формуле:

   \[\mathit{score}(q, d) = \sum_{t \in q}{\mathit{tf}\text{-}\mathit{idf}(t, d)}\]

   Где:

   \[\mathit{tf}\text{-}\mathit{idf}(t, d) = \mathit{tf}(t, d) \cdot \mathit{idf}(t)\]
   \[\mathit{idf}(t) = ln \left( \frac{N}{\mathit{df}(t)} \right)\]

   \(N\) — общее количество документов в индексе.

4. Отсортировать результаты по убыванию \(\mathit{score}\). В качестве стабилизирующего фактора сортировки можно использовать id документа.

Пример

Пусть в индексе хранятся следующие документы:

id   text
100  Hello World
101  Bye World
102  Hello Earth

Для компактности примера пропустим этап выделения n-грам и будем считать, что каждое слово является термом. Тогда обратный индекс выглядит так:

bye:   {101: [0]}
earth: {102: [1]}
hello: {100: [0], 102: [0]}
world: {100: [1], 101: [1]}

Поиск:

query: bye earth

parsed_query: ["bye", "earth"]

# Для каждого терма получаем список документов и считаем tf и df.
bye:
   doc_ids: [101]
   tf:
      101: 1
   df: 1

earth:
   doc_ids: [102]
   tf:
      102: 1
   df: 1

score("bye earth", 101)
   = tf-idf("bye", 101) + tf-idf("earth", 101)
   = 1 * ln(3 / 1)      + 0
   ≈ 1.098612

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

 id      score   text
101   1.098612   Bye World
102   1.098612   Hello Earth

Рассмотрим другой запрос:

query: Hello World

parsed_query: ["hello", "world"]

hello:
   doc_ids: [100, 102]
   tf:
      100: 1
      102: 1
   df: 2

world:
   doc_ids: [100, 101]
   tf:
      100: 1
      101: 1
   df: 2

score("hello world", 100)
   = tf-idf("hello", 100) + tf-idf("world", 100)
   = 1 * ln(3 / 2)        + 1 * ln(3 / 2)
   ≈ 0.810930

score("hello world", 101)
   = tf-idf("hello", 101) + tf-idf("world", 101)
   = 0                    + 1 * ln(3 / 2)
   ≈ 0.405465

score("hello world", 102)
   = tf-idf("hello", 102) + tf-idf("world", 102)
   = 1 * ln(3 / 2)        + 0
   ≈ 0.405465

Выдача примет вид:

 id      score   text
100   0.810930   Hello World
101   0.405465   Bye World
102   0.405465   Hello Earth

Структура проекта

Индексатор остается без изменений.

TextIndexAccsessor — класс, предоставляющий доступ на чтение к данным построенного индекса.

Дополнительно

Что произойдет, если индексация и поиск будут выполнены с разными настройками парсера? Предложите и реализуйте решение этой проблемы.