В информатике инвертированный индекс ( также называемый списком сообщений , файлом сообщений или инвертированным файлом ) — это индекс базы данных, хранящий сопоставление содержимого, например слов или чисел, с его местоположением в таблице , документе или наборе документов (названный в отличие от прямого индекса , который сопоставляет документы с содержимым). [1] Цель инвертированного индекса — обеспечить быстрый полнотекстовый поиск за счет увеличения обработки при добавлении документа в базу данных. [2] Инвертированный файл может быть самим файлом базы данных, а не его индексом. Это самая популярная структура данных, используемая в системах поиска документов , [3] используемая в больших масштабах, например, в поисковых системах . Кроме того, несколько значительных систем управления базами данных общего назначения на базе мэйнфреймов использовали архитектуры инвертированных списков, включая ADABAS , DATACOM/DB и Model 204 .
Существует два основных варианта инвертированных индексов: инвертированный индекс на уровне записи (или инвертированный файловый индекс или просто инвертированный файл ) содержит список ссылок на документы для каждого слова. Инвертированный индекс на уровне слова (или полный инвертированный индекс или инвертированный список ) дополнительно содержит позиции каждого слова в документе. [4] Последняя форма предлагает больше функциональности (например, поиск по фразам ), но требует больше вычислительной мощности и места для создания.
Структура данных инвертированного индекса является центральным компонентом типичного алгоритма индексации поисковой системы . [5] Целью реализации поисковой системы является оптимизация скорости запроса: поиск документов, в которых встречается слово X. [6] После разработки прямого индекса , который хранит списки слов на документ, он затем инвертируется для разработки инвертированного индекса. Запрос прямого индекса потребует последовательной итерации по каждому документу и к каждому слову для проверки соответствующего документа. Время, память и ресурсы обработки для выполнения такого запроса не всегда технически реалистичны. Вместо того, чтобы перечислять слова на документ в прямом индексе, разрабатывается структура данных инвертированного индекса, которая перечисляет документы на слово.
После создания инвертированного индекса запрос можно разрешить, перейдя к идентификатору слова (через случайный доступ ) в инвертированном индексе.
В докомпьютерные времена конкордансы к важным книгам собирались вручную. Это были фактически инвертированные индексы с небольшим количеством сопроводительных комментариев, требовавших огромных усилий для создания.
В биоинформатике инвертированные индексы очень важны при сборке последовательностей коротких фрагментов секвенированной ДНК. Один из способов найти источник фрагмента — это выполнить его поиск по референтной последовательности ДНК. Небольшое количество несовпадений (из-за различий между секвенированной ДНК и референтной ДНК или ошибок) можно учесть, разделив фрагмент на более мелкие фрагменты — по крайней мере один подфрагмент, скорее всего, будет соответствовать референтной последовательности ДНК. Соответствие требует построения инвертированного индекса всех подстрок определенной длины из референтной последовательности ДНК. Поскольку человеческая ДНК содержит более 3 миллиардов пар оснований, и нам нужно хранить подстроку ДНК для каждого индекса и 32-битное целое число для самого индекса, требования к хранению для такого инвертированного индекса, вероятно, составят десятки гигабайт.
По историческим причинам сжатие инвертированного списка и сжатие битовой карты разрабатывались как отдельные направления исследований, и только позже было признано, что они решают по сути одну и ту же проблему. [7]