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

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

Definition

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

Scope

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

Core questions

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

Key concepts

• словарь терминов
• список вхождений
• идентификаторы документов
• позиционный индекс
• хранение частоты терминов
• блочная сортировка на основе индексирования (BSBI)
• однопроходное индексирование в памяти (SPIMI)
• слияние и обновление индекса

Key theories

Организация словаря и списков вхождений

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

Масштабируемое построение индекса

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

Clinical relevance

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

History

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

Key figures

• Justin Zobel
• Alistair Moffat
• Steffen Heinz

Seminal works

• zobel2006
• heinz2003
• manning2008

Frequently asked questions

Почему он называется «инвертированным» индексом?

Обычный (прямой) индекс перечисляет для каждого документа термины, которые он содержит. Инвертированный индекс обращает это сопоставление, чтобы перечислить для каждого термина документы, которые его содержат. Эта инверсия именно то, что делает поиск по терминам быстрым.

Для чего используется позиционный индекс?

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