Инвертированный список

Инвертированный список Поскольку нам неизвестно, насколько большим будет инвертированный список для термина, когда мы встретим его впервые, сначала мы выделяем память для короткого инвертированного списка, а затем каждый раз удваиваем ее после заполнения (строки 8 и 9). Это значит, что часть памяти будет потеряна и сэкономить память за счет игнорирования идентификаторов терминов в промежуточных структурах данных не удастся. Однако общие требования к памяти для динамически конструируемого индекса блока в алгоритме SPIMI ниже, чем в алгоритме BSBI.

После того как память будет исчерпана, мы записываем индекс блока (состоящий из словаря и инвертированных списков) на диск (строка 12). Однако перед этим термины необходимо отсортировать (строка 11), так как инвертированные списки должны быть записаны в лексикографическом порядке. Это облегчает выполнение заключительного этапа слияния. Если бы инвертированные списки каждого блока были записаны беспорядочно, что слияние блоков в ходе однократного последовательного перебора каждого блока выполнить не удалось бы.

При каждом вызове функция SPIMI-Invert записывает блок на диск, так же как и в алгоритме BSBI. На последнем этапе алгоритма SPIMI (соответствующем строке 7) блоки объединяются в окончательный инвертированный индекс.

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

Временная сложность алгоритма SPIMI равна 0(7), поскольку сортировка лексем не нужна и сложность всех операций не более чем линейно зависит от размера коллекции подробней.

tel-icq