3. Индексатор

Цель

Реализовать построитель прямого и обратного индекса. Покрыть тестами.

Основные понятия

Терм — это нормализованное слово, помещаемое в словарь поисковой системы. В нашем случае термами мы будем считать n-граммы, полученные от парсера.

В основе любой поисковой системы лежит обратный индекс. Это ассоциативная структура данных, ключами в которой являются термы, а значениями — список идентификаторов документов и позиций термов в этих документах.

На входе у индексатора документы, содержащие слова. Индексатор «разворачивает» связь Документ -> [слова] и строит структуру терм -> [документы].

Прямой индекс — ассоциативная структура данных, в которой ключ — идентификатор документа, значение — сам документ.

Пример

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

    id  text
199903  The Matrix
200305  The Matrix Reloaded
200311  The Matrix Revolutions

От парсера индексатор получает следующие термы и их позиции:

    id  text
199903  mat:0 matr:0 matri:0 matrix:0
200305  mat:0 matr:0 matri:0 matrix:0 rel:1 relo:1 reloa:1 reload:1
200311  mat:0 matr:0 matri:0 matrix:0 rev:1 revo:1 revol:1 revolu:1

Тогда обратный индекс можно схематично изобразить так:

term    entries

mat:    {199903: [0], 200305: [0], 200311: [0]}
matr:   {199903: [0], 200305: [0], 200311: [0]}
matri:  {199903: [0], 200305: [0], 200311: [0]}
matrix: {199903: [0], 200305: [0], 200311: [0]}

rel:    {200305: [1]}
relo:   {200305: [1]}
reloa:  {200305: [1]}
reload: {200305: [1]}

rev:    {200311: [1]}
revo:   {200311: [1]}
revol:  {200311: [1]}
revolu: {200311: [1]}

Декомпозиция

Один из возможных вариантов декомпозиции:

Здесь:

  • IndexBuilder — stateful-класс, накапливающий данные для индекса по мере добавления документов.

  • Index::docs — прямой индекс.

  • Index::entries — обратный индекс.

  • Сериализация индекса вынесена в отдельный класс TextIndexWriter для упрощения тестирования.

Формат индекса

Ниже приведен рекомендуемый формат индекса. Вы можете спроектировать свой.

index
|-- docs
|   |-- 101
|   |-- 102
|   `-- 103
`-- entries
    |-- 3adb7b
    |-- 9ea46a
    `-- c9a868

  • index/docs — прямой индекс.

  • index/docs/<document_id> — проиндексированный документ

  • index/entries — обратный индекс. Имена вложенных файлов — первые три байта хеша терма. В качестве хеша можно использовать md5 или sha256 (https://github.com/okdshin/PicoSHA2).

Формат файлов обратного индекса index/entries/<term-hash>:

<term> <doc_count> [<doc_id> <pos_count> [<pos> …] …]
...

Здесь:

  • term — текст терма.

  • doc_count — количество документов, в которые входит терм. За ним следуют списки позиций для каждого документа.

  • doc_id — идентификатор документа.

  • pos_count — количество вхождений терма term в документ doc_id

  • pos — номер токена, в который входит терм.

Для примера выше вхождение терма matrix будет выглядеть так:

matrix 3 199903 1 0 200305 1 0 200311 1 0