7. Бинарный индекс

Цель

В ЛР3 вы реализовали хранение текстового индекса. Такой формат прост для отладки, но неоптимален во всех отношениях: для файла books.csv размером 1.5 Мб текстовый индекс занимает более 100 Мб.

Цель этой работы — реализовать хранение индекса в бинарном формате. Если в предыдущих ЛР вы действовали достаточно аккуратно, то код поиска останется практически без изменений.

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

Для описания отдельных полей индекса будем использовать записи вида:

<name:type>

Где:

name — имя поля. Нигде не хранится, используется только в целях документации.
type — тип поля. Будем использовать сокращения: u32 — std::uint32_t, i16 — std::int16_t и т. д.

Для хранения строк будем использовать тип string:

string = <length:u8><data:char[]>

Строки хранятся без символа „0“. Таким образом, строка «hello» будет храниться как следующая последовательность:

06 68 65 6c 6c 6f

Где первый байт 06 — длина строки, а последующие — коды символов.

Числа размером более одного байта хранятся в little endian.

Секции

Индекс состоит минимум из четырех секций:

<header>
<dictionary>
<entries>
<docs>

Они хранятся в том же порядке, в котором будут использованы при поиске, однако строить их удобнее в обратном порядке. Опишем форматы секций в порядке их построения.

Секция docs

Прямой индекс. Представляет собой список строк, в нашем случае — список заголовков книг. Формат:

<titles_count:u32>[<string>...]

На этапе построения нужно запомнить отображение: DocumentId -> DocumentOffset, где DocumentOffset — смещение заголовка от начала секции docs. Это смещение будет использоваться в обратном индексе для идентификации документа.

Секция entries

Обратный индекс. Список структур TermInfo, аналогичных содержимому файлов в каталоге entries индекса в текстовом формате. Формат:

[<doc_count:u32>
    [
        <doc_offset:u32>
        <pos_count:u32>
        [<pos:u32> …]
        …
    ]
 …
]

Единственное отличие от текстового индекса: вместо идентификатора документа мы используем doc_offset — смещение, которое запомнили на этапе записи секции docs.

На этапе построения нужно запомнить смещение каждого TermInfo.

Секция dictionary

Словарь. Хранится как префиксное дерево в порядке обхода в глубину. Формат:

<children_count:u32>
[<letter:u8> …]
[<child_offset:u32> …]
<is_leaf:u8>
<entry_offset:u32>?

Где:

children_count — количество дочерних узлов текущего узла.
[<letter:u8>] — массив букв дочерних узлов
[<child_offset:u32>] — массив смещений дочерних узлов от начала секции dictionary
is_leaf — 1, если узел является последним символом в слове, 0 — для промежуточного.
entry_offset — смещение структуры TermInfo для текущего entry. Присутствует только для is_leaf = 1.

Пример.

Пусть в префиксном дереве хранятся слова: pot, past, pass, part и связанные с ними значения 1, 2, 3, 4 соответственно:

digraph G { bgcolor = "#ffffff00"; root [label=nil shape=circle]; root -> p0; p0 [label=p shape=circle]; p0 -> a1; p0 -> o2; o2 [label=o shape=circle]; o2 -> t3; t3 [label=t shape=doublecircle]; a1 [label=a shape=circle]; a1 -> r4; a1 -> s5; s5 [label=s shape=circle]; s5 -> s6; s5 -> t7; t7 [label=t shape=doublecircle]; s6 [label=s shape=doublecircle]; r4 [label=r shape=circle]; r4 -> t8; t8 [label=t shape=doublecircle]; }

Тогда бинарное представление будет таким:

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

Возможный вариант с учетом доработок:

Инициализация аксессора

Сначала нужно получить байтовый массив с содержимым индекса. Можно вычитать весь файл в std::vector<char> или (лучше) отмапить его функцией mmap.
Вычитать секцию Header. Получим доступ к смещениям каждой секции.
Сконструировать аксессор. Для этого нужно передать ему данные индекса и Header. Из заголовка можно получить смещения каждой секции и инициализировать аксессоры каждой секции.

Паника-паника, с чего начать?

С простого. Секция docs самая простая по своей структуре, начните с нее. Напишите вспомогательный класс BinaryBuffer для записи бинарных данных, сериализуйте массив заголовков книг в указанном выше формате, запишите его в файл. Секция достаточно проста, и вы легко сможете проверить корректность данных в hex-редакторе.