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