Инвертированный файл

Инвертированный файл представляет собой структуру, которая состоит из двух частей:

• словарь, содержащий все термы, встретившиеся в коллекции и ссылку на массив данных «пост-листа» для каждого из них. Помимо того возможно наличие специальных структур, ускоряющих поиск слова в словаре.
• пост-листы, представляющие собой массив информации обо всех вхождениях данного слова в документы коллекции.

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

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

В случае, если в пост-листе хранятся идентификаторы в возрастающем порядке, компактнее будет хранить их разность, чем идентификаторы целиком. Сами же числа сохраняют с применением техник кодирования чисел:

• кодов переменной длины. Например, первые семь байтов каждого бита передают значимую часть числа, последний байт обозначает оканчивается ли на этом число или нет.
• гамма и дельта кодирование Элиса и параметрические коды Голомба.

В случаях, когда требуется эффективное сжатие коротких пост-листов, имеет смысл объединять списки для нескольких слов. В этом случае получается список идентификаторов, который может быть эффективно кодирован одним из способов компактного хранения чисел. У каждого идентификатора указывается слово или список слов из объединенного списка, которые в нем встречаются. Можно указывать их номера, сжатые методом Хаффмана.

В случае реализации индекса на основе В+ деревьев на размер пост-листа накладывается ограничение реализации. Для того, чтобы разместить длинные пост-листы в индексе применяются два метода:
1. разбиение пост-листа. Один пост-лист размещается в нескольких записях. В этом случае ключем дерева является не только слово, но и первое значение в пост-листе.
2. вынесение длинных пост-листов во внешнюю, по отношению к дереву, структуру.

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

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

Изменения индексной информации делятся на массовые, при которых изменяется большое число документов и имеет смысл полное перестроение индекс, и одиночные, при которых полного перестроения не происходит. Полное перестроение используется при начальной инициализации индекса. При этом в выделенной области оперативной памяти собирается индекс по части документов, при заполнении сохраняется во временных файлах, а потом многопоточным слиянием объединяется в единую индексную структуру.
В случае реализации индекса через В+ деревья эффективно происходит добавление и удаление информации, разбиение длинных пост-листов позволяет эффективно обновлять только нужные их части, не считывая остальные.