Сжатие индекса

Сжатие индекса кодирует списки вхождений инвертированного индекса компактно, так что поисковая система хранит меньше данных и быстрее отвечает на запросы.

Definition

Сжатие индекса — это применение методов целочисленного и строкового кодирования к словарю и спискам вхождений инвертированного индекса с целью уменьшения занимаемого им объема памяти при сохранении быстрой декодируемости списков вхождений во время обработки запросов.

Scope

Эта тема охватывает методы сжатия инвертированных индексов, особенно кодирование промежутков идентификаторов документов и частот терминов с использованием целочисленных кодов переменной длины и выровненных по словам. Она рассматривает сжатие словарей, кодирование промежутков (дельт), классические коды, такие как унарный, гамма и Голомба-Райса, байт-ориентированные и блочные схемы, такие как переменная длина байта и PForDelta, а также компромисс между степенью сжатия и скоростью декодирования. Она исключает построение самого индекса и стратегию оценки запросов, которая его использует.

Core questions

• Почему кодирование промежутков между идентификаторами документов эффективно сжимает списки вхождений?
• Какие целочисленные коды используются и как они соотносят степень сжатия со скоростью декодирования?
• Как сжимается сам словарь терминов?
• Как можно декодировать сжатые списки вхождений достаточно быстро, чтобы поддерживать низкую задержку запросов?
• Как сжатие взаимодействует с поведением кэша и стоимостью ввода/вывода?

Key concepts

• кодирование промежутков (дельт)
• кодирование переменной длиной байта
• коды гамма и Голомба-Райса
• PForDelta и блочные коды
• сжатие словаря
• степень сжатия
• пропускная способность декодирования
• SIMD / векторизованное декодирование

Key theories

Кодирование промежутков в списках вхождений

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

Компромисс между сжатием и скоростью

Битово-выровненные коды, такие как гамма и Голомб, максимизируют сжатие, но декодируются медленно, тогда как байт-ориентированные и блочные коды, такие как переменная длина байта и PForDelta, жертвуют некоторой степенью сжатия ради гораздо более быстрого, векторизуемого декодирования, что часто обеспечивает общую производительность запросов.

Clinical relevance

Сжатие имеет решающее значение для работы поиска в масштабе: оно уменьшает индексы, чтобы они помещались в память или на меньший объем хранилища, сокращает ввод/вывод и улучшает локальность кэша, тем самым снижая как задержку запросов, так и затраты на оборудование. Все производственные поисковые системы и библиотеки поиска с открытым исходным кодом используют сжатые списки вхождений.

History

Компактное кодирование текстовых индексов развивалось параллельно с инвертированными файлами, при этом классические битово-выровненные коды (унарный, гамма, Голомб) были систематизированы в работе «Managing Gigabytes» 1990-х годов. По мере того как веб-поиск требовал все более быстрого декодирования, байт-ориентированные и блочные схемы, такие как переменная длина байта и PForDelta, а затем векторизованные декодеры, способные обрабатывать миллиарды целых чисел в секунду, сместили акцент в сторону скорости.

Key figures

• Alistair Moffat
• Ian H. Witten
• Daniel Lemire
• Justin Zobel

Seminal works

• wittenmgb1999
• lemire2015
• manning2008

Frequently asked questions

Как сжатый индекс может быть быстрее несжатого?

Сжатие уменьшает объем данных, считываемых с диска или из памяти, что часто является узким местом. Современные целочисленные коды декодируются очень быстро, часто с использованием векторных инструкций, поэтому время, сэкономленное на вводе/выводе, и лучшее поведение кэша более чем компенсируют работу по декодированию.

Почему хранятся промежутки вместо необработанных идентификаторов документов?

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