Инвертированный индекс
В информатике ( инвертированный индекс также называемый списком сообщений , файлом сообщений или инвертированным файлом ) — это индекс базы данных, хранящий сопоставление содержимого, такого как слова или числа, с его местоположениями в таблице или документе. или набор документов (названный в отличие от прямого индекса , который сопоставляет документы с содержимым). [1] Цель инвертированного индекса — обеспечить быстрый полнотекстовый поиск за счет увеличения обработки при добавлении документа в базу данных. [2] Инвертированный файл может быть самим файлом базы данных, а не его индексом. Это самая популярная структура данных, используемая в поиска документов . системах [3] используется в больших масштабах, например, в поисковых системах . общего назначения мэйнфреймов на базе Кроме того, несколько важных систем управления базами данных использовали архитектуры инвертированных списков, включая ADABAS , DATACOM/DB и Model 204 .
Существует два основных варианта инвертированных индексов: Инвертированный индекс на уровне записи (или инвертированный индекс файла , или просто инвертированный файл ) содержит список ссылок на документы для каждого слова. Инвертированный индекс на уровне слов (или полный инвертированный индекс , или инвертированный список ) дополнительно содержит позиции каждого слова в документе. [4] Последняя форма предлагает больше функций (например, поиск по фразам ), но требует большей вычислительной мощности и места для создания.
Приложения
[ редактировать ]инвертированного индекса Структура данных является центральным компонентом типичного алгоритма индексирования поисковой системы . [5] Целью реализации поисковой системы является оптимизация скорости запроса: найти документы, в которых встречается слово X. [6] После разработки прямого индекса , в котором хранятся списки слов для каждого документа, его затем инвертируют для создания инвертированного индекса. Запрос прямого индекса потребует последовательной итерации по каждому документу и каждому слову для проверки соответствующего документа. Время, память и ресурсы обработки для выполнения такого запроса не всегда технически реалистичны. Вместо перечисления слов на документ в прямом индексе разработана структура данных инвертированного индекса, в которой перечислены документы по словам.
После создания инвертированного индекса запрос можно решить, перейдя к идентификатору слова (через произвольный доступ ) в инвертированном индексе.
В докомпьютерные времена конкордансы к важным книгам собирались вручную. Это были фактически перевернутые индексы с небольшим количеством сопровождающих комментариев, для создания которых требовалось огромное количество усилий.
В биоинформатике инвертированные индексы очень важны при сборке последовательностей коротких фрагментов секвенированной ДНК. Один из способов найти источник фрагмента — это найти его по эталонной последовательности ДНК. Небольшое количество несоответствий (из-за различий между секвенированной ДНК и эталонной ДНК или ошибок) можно объяснить путем разделения фрагмента на более мелкие фрагменты - по крайней мере один субфрагмент, вероятно, будет соответствовать последовательности эталонной ДНК. Для сопоставления необходимо построить инвертированный индекс всех подстрок определенной длины из эталонной последовательности ДНК. Поскольку человеческая ДНК содержит более 3 миллиардов пар оснований, и нам необходимо хранить подстроку ДНК для каждого индекса и 32-битное целое число для самого индекса, объем памяти для такого инвертированного индекса, вероятно, будет исчисляться десятками гигабайт.
Сжатие
[ редактировать ]По историческим причинам сжатие инвертированных списков и сжатие растровых изображений были разработаны как отдельные направления исследований и только позже были признаны решающими по существу одну и ту же проблему. [7]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Кнут, Д.Э. (1997) [1973]. «6.5. Получение вторичных ключей». Искусство компьютерного программирования (Третье изд.). Ридинг, Массачусетс : Аддисон-Уэсли . ISBN 0-201-89685-0 .
- ^ Солтон, Джерард; Фокс, Эдвард А.; Ву, Гарри (ноябрь 1983 г.). «Расширенный логический поиск информации» . Коммуникации АКМ . 26 (11): 1022–1036. дои : 10.1145/182.358466 . hdl : 1813/6351 .
- ^ Зобель, Джастин; Моффат, Алистер; Рамамоханарао, Котагири (декабрь 1998 г.). «Инвертированные файлы и файлы сигнатур для индексации текста» . Транзакции ACM в системах баз данных . 23 (4). Нью-Йорк: Ассоциация вычислительной техники : 453–490. дои : 10.1145/296854.277632 . S2CID 7293918 .
- ^ Баэса-Йейтс, Рикардо ; Рибейро-Нето, Бертье (1999). Современный поиск информации . Ридинг, Массачусетс : Аддисон-Уэсли Лонгман. п. 192. ИСБН 0-201-39829-Х .
- ^ Зобель, Джастин; Моффат, Алистер (июль 2006 г.). «Инвертированные файлы для текстовых поисковых систем». Обзоры вычислительной техники ACM . 38 (2). Нью-Йорк: Ассоциация вычислительной техники : 6. doi : 10.1145/1132956.1132959 . S2CID 207158957 .
- ^ Поиск информации: внедрение и оценка поисковых систем . Кембридж, Массачусетс: MIT Press. 2010. ISBN 978-0-262-02651-2 . Архивировано из оригинала 05 октября 2020 г. Проверено 8 августа 2010 г.
- ^ Ван, Цзяньго; Линь, Чунбин; Папаконстантину, Яннис; Суонсон, Стивен (9 мая 2017 г.). «Экспериментальное исследование сжатия растровых изображений по сравнению со сжатием инвертированного списка» . Материалы Международной конференции ACM по управлению данными 2017 года . Ассоциация вычислительной техники. стр. 993–1008. дои : 10.1145/3035918.3064007 . Проверено 1 мая 2023 г.
Внешние ссылки
[ редактировать ]- Словарь алгоритмов и структур данных NIST: инвертированный индекс
- Managing Gigabytes for Java — бесплатная система полнотекстового поиска для больших коллекций документов, написанных на Java.
- Lucene — Apache Lucene — это полнофункциональная библиотека системы текстового поиска, написанная на Java.
- Sphinx Search — высокопроизводительная полнофункциональная библиотека системы текстового поиска с открытым исходным кодом, используемая Craigslist и другими организациями, использующими инвертированный индекс.
- Пример реализации Rosetta Code
- Панель инструментов поиска крупномасштабных изображений Калифорнийского технологического института : набор инструментов Matlab, реализующий поиск изображений в мешке слов в инвертированных файлах.