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

Question

Я знаю, что инвертированное индексирование - хороший способ индексирования слов, но то, что я смущен, - это то, как поисковые системы фактически хранят их? Например, если слово «google» появляется в документе - 2, 4, 6, 8 с разными частотами, где их следует хранить? Может ли таблица базы данных со отношением «один-ко-многим» сделать любую полезную для их хранения?

Answer 1

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

В конкретном случае Google разумно предположить, что используемая технология основана на технологии BigTable, описанной в 2006 году Фэй Чангом и др. В Bigtable: A Distributed Storage System for Structured Data. Существует мало сомнений в том, что система развилась с тех пор.

Answer 2

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

• У вас только есть один способ доступа к данным (по слову запроса). Вот почему он называется индексом.
• Каждая запись представляет собой список/массив/вектор ссылок на документы, поэтому каждый элемент этого списка очень мал. Единственной другой информацией, кроме хранения идентификатора документа, было бы хранить оценку 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), который является списком документов, в котором происходят оба слова запроса.

Answer 3

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

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

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

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

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

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

Answer 4

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

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

Пример

сказать слово "Привет" появился в Документах 1 и 3, в положениях (3,5,6,200) и (9,10) соответственно.

• Basic Перевернутый Index (обратите внимание, что нет никакого способа, чтобы найти freqs слова, ни там позиции)

"hello" => [1,3]

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

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

Heads Up

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

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

Связанные чтения

Index compression

Postings file compression

Dictionary compression