Инвертированный индекс - Inverted index

В Информатика, инвертированный индекс (также называемый файл сообщений или же инвертированный файл) это индекс базы данных сохранение сопоставления содержимого, такого как слова или числа, с его местоположениями в стол, или в документе или наборе документов (названных в отличие от форвардный индекс, который сопоставляет документы с контентом). Инвертированный индекс предназначен для быстрого полнотекстовый поиск, за счет увеличения объема обработки при добавлении документа в базу данных. Инвертированный файл может быть самим файлом базы данных, а не ее индексом. Это самая популярная структура данных, используемая в поиск документов системы,[1] широко используется, например, в поисковые системы. Кроме того, несколько важных универсальных мэйнфрейм -основан системы управления базами данных использовали архитектуры перевернутого списка, в том числе АДАБАС, ДАТАКОМ / БД, и Модель 204.

Существует два основных варианта инвертированных индексов: A инвертированный индекс на уровне записи (или же инвертированный индекс файла или просто инвертированный файл) содержит список ссылок на документы по каждому слову. А инвертированный индекс на уровне слов (или же полный инвертированный индекс или же перевернутый список) дополнительно содержит позиции каждого слова в документе.[2] Последняя форма предлагает больше функций (например, поиск по фразе ), но для создания требуется больше вычислительной мощности и места.

Приложения

Инвертированный индекс структура данных является центральным компонентом типичного алгоритм индексации поисковой системы. Цель реализации поисковой системы - оптимизировать скорость запроса: найти документы, в которых встречается слово X. Когда форвардный индекс , в котором хранятся списки слов для каждого документа, затем он инвертируется для создания инвертированного индекса. Запрос прямого индекса потребует последовательной итерации по каждому документу и каждому слову для проверки совпадающего документа. Время, память и ресурсы обработки для выполнения такого запроса не всегда технически реалистичны. Вместо перечисления слов для каждого документа в прямом индексе разрабатывается структура данных инвертированного индекса, в которой перечисляются документы на каждое слово.

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

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

В биоинформатике инвертированные индексы очень важны для сборка последовательности коротких фрагментов секвенированной ДНК. Один из способов найти источник фрагмента - найти его по эталонной последовательности ДНК. Небольшое количество несоответствий (из-за различий между секвенированной ДНК и эталонной ДНК или ошибок) можно объяснить путем деления фрагмента на более мелкие фрагменты - по крайней мере, один субфрагмент, вероятно, будет соответствовать эталонной последовательности ДНК. Сопоставление требует построения инвертированного индекса всех подстрок определенной длины из эталонной последовательности ДНК. Поскольку человеческая ДНК содержит более 3 миллиардов пар оснований, и нам нужно хранить подстроку ДНК для каждого индекса и 32-битное целое число для самого индекса, требования к хранилищу для такого инвертированного индекса, вероятно, будут составлять десятки гигабайт.

Сжатие

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

Смотрите также

Библиография

  • Кнут, Д. Э. (1997) [1973]. «6.5. Получение дополнительных ключей». Искусство программирования (Третье изд.). Ридинг, Массачусетс: Эддисон-Уэсли. ISBN  0-201-89685-0.
  • Зобель, Джастин; Моффат, Алистер; Рамамоханарао, Котагири (декабрь 1998 г.). «Инвертированные файлы по сравнению с файлами сигнатур для текстового индексирования». Транзакции ACM в системах баз данных. Нью-Йорк: Ассоциация вычислительной техники. 23 (4): 453–490. Дои:10.1145/296854.277632. S2CID  7293918.
  • Зобель, Джастин; Моффат, Алистер (июль 2006 г.). «Инвертированные файлы для текстовых поисковых систем». Опросы ACM Computing. Нью-Йорк: Ассоциация вычислительной техники. 38 (2): 6. Дои:10.1145/1132956.1132959. S2CID  207158957.
  • Баеза-Йейтс, Рикардо; Рибейро-Нето, Бертье (1999). Современный информационный поиск. Ридинг, Массачусетс: Эддисон-Уэсли Лонгман. п. 192. ISBN  0-201-39829-X.
  • Солтон, Джерард; Фокс, Эдвард А .; Ву, Гарри (1983). «Поиск расширенной логической информации». Commun. ACM. ACM. 26 (11): 1022. Дои:10.1145/182.358466. HDL:1813/6351. S2CID  207180535.
  • Поиск информации: внедрение и оценка поисковых систем. Кембридж, Массачусетс: MIT Press. 2010 г. ISBN  978-0-262-02651-2.

Рекомендации

  1. ^ Зобель, Моффат и Рамамоханарао 1998
  2. ^ Баеза-Йетс и Рибейро-Нето, 1999 г., п. 192
  3. ^ Цзяньго Ван; Чунбин Линь; Яннис Папаконстантину; Стивен Суонсон.«Экспериментальное исследование сжатия растровых изображений по сравнению со сжатием с инвертированным списком».2017.doi: 10.1145 / 3035918.3064007

внешняя ссылка