Сохранение инвертированного индекса

Маловероятно, что для этой цели используются полноценные SQL-подобные базы данных. Во-первых, он называется инвертированным индексом, потому что это просто индекс. Каждая запись является просто ссылкой. Поскольку нереляционные базы данных и хранилища ключей-значений стали излюбленной темой в отношении веб-технологий.

• У вас есть только один способ доступа к данным (по слову запроса). Вот почему он называется индексом.
• Каждая запись представляет собой список/массив/вектор ссылок на документы, поэтому каждый элемент этого списка очень мал. Единственной другой информацией, помимо хранения documentID, будет сохранение оценки tf-idf для каждого элемента.

Как это использовать:

Если у вас есть одно слово запроса («google»), вы ищете в перевернутом индексе документы, в которых встречается это слово (2,4,6,8 в вашем примере). Если у вас есть оценки tf-idf, вы можете отсортировать результаты, чтобы сначала сообщить о наиболее подходящем документе. Затем вы идете и ищете, на какие документы ссылаются идентификаторы документов 2,4,6,8, и сообщаете их URL-адрес, а также фрагмент и т. д. URL-адрес, фрагменты и т. д., вероятно, лучше всего хранить в другой таблице или хранилище ключей-значений.

Если у вас есть несколько слов запроса («google» и «altavista»), вы просматриваете II для обоих слов запроса и получаете два списка идентификаторов документов (2,4,6,8 и 3,7,8,11, 19). Вы берете пересечение обоих списков, которым в данном случае является (8), то есть список документов, в которых встречаются оба слова запроса.

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

В конкретном случае Google разумно предположить, что используемая в настоящее время технология основана на BigTable технология, описанная в 2006 году Фей Чанг и соавторами в книге Bigtable: распределенная система хранения структурированных данных. Однако нет никаких сомнений в том, что с тех пор система развивалась.

Традиционно инвертированный индекс записывается непосредственно в файл и хранится где-то на диске. Если вы хотите выполнить логический поисковый запрос (независимо от того, содержит ли файл все слова в запросе или нет), сообщения могут выглядеть так, как если бы они хранились непрерывно в файле.

Term_ID_1:Frequency_N:Doc_ID_1,Doc_ID_2,Doc_ID_N.Term_ID_2:Frequency_N:Doc_ID_1,Doc_ID_2,Doc_ID_N.Term_ID_N:Frequency_N:Doc_ID_1,Doc_ID_2,Doc_ID_N

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

Наряду с индексом вам нужно знать, где все находится в файле, поэтому сопоставления также должны храниться где-то в другом файле. Например, при наличии term_id карта должна вернуть позицию в файле, содержащую этот индекс, а затем можно перейти к этой позиции. Поскольку Frequency_id записывается в проводках, вы знаете, сколько doc_id читать из файла. Кроме того, потребуется сопоставление идентификаторов с фактическим названием термина/документа.

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

Еще одна стратегия для очень небольшого варианта использования — использовать матрицу документов терминов.

Возможное решение

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

Пример

Произнесите слово «привет» в документах 1 и 3 на позициях (3, 5, 6, 200) и (9, 10) соответственно.

• Базовый инвертированный индекс (обратите внимание, что нет способа найти ни частоты слов, ни их позиции)

"hello" => [1,3]

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

"hello" => [1:<3,5,6,200> , 3:<9,10>]

Осторожно

Будет ли теперь ваш индекс занимать намного больше места? Вы держите пари!

Вот почему рекомендуется сжимать индекс. Существует несколько вариантов сжатия списка сообщений с использованием кодирования пробелов и еще больше вариантов сжатия словаря с использованием общих алгоритмов сжатия строк.

Похожие материалы

Сжатие индекса

Сжатие файлов сообщений

Сжатие словаря