Использование индексов для многословных запросов в полнотекстовом поиске (например, веб-поиск)

Я понимаю, что фундаментальным аспектом полнотекстового поиска является использование инвертированных индексов. Таким образом, с инвертированным индексом запрос на одно слово становится тривиальным для ответа. Предполагая, что индекс структурирован следующим образом:

some-word → [doc385, doc211, doc39977,...] (отсортировано по рангу, по убыванию)

Чтобы ответить на запрос для этого слова, решение состоит в том, чтобы найти правильную запись в индексе (который принимает время O (log n)) и представить определенное количество документов (например, первые 10) из списка, указанного в индекс.

Но как насчет запросов, которые возвращают документы, которые соответствуют, скажем, двум словам? Наиболее простая реализация будет следующей:

установите A как набор документов, которые имеют слово 1 (путем поиска индекса).
установите B как набор документов, которые имеют слово 2 (то же).
вычислить пересечение A и B.

Теперь для шага 3, вероятно, потребуется время O (n log n). Для очень больших A и B, которые могут сделать запрос медленным, чтобы ответить. Но поисковые системы, такие как Google, всегда возвращают свой ответ за несколько миллисекунд. Так что это не может быть полный ответ.

Одна очевидная оптимизация заключается в том, что, поскольку поисковая система, подобная Google, в любом случае не возвращает все соответствующие документы, нам не нужно вычислять все пересечения. Мы можем начать с самого маленького набора (например, B) и найти достаточно записей, которые также относятся к другому набору (например, A).

Но разве у нас не может быть следующего худшего случая? Если мы установили A, это набор документов, соответствующих общему слову, а B - это набор документов, соответствующих другому общему слову, все же могут быть случаи, когда A ∩ B очень мало (т.е. Комбинация редка). Это означает, что поисковая система должна линейно проходить через все элементы x члена B, проверяя, являются ли они также элементами A, чтобы найти несколько, которые соответствуют обоим условиям.

Линейный не быстрый. И вы можете найти более двух слов для поиска, поэтому просто использовать parallelism наверняка не все решение. Итак, как оптимизируются эти случаи? У крупномасштабных полнотекстовых поисковых систем используются какие-то составные индексы? Цветные фильтры? Любые идеи?

Ответ 1

Как вы сказали some-word → [doc385, doc211, doc39977,...] (отсортировано по рангу, по убыванию), я думаю, что поисковая система может этого не делать, список документов должен быть отсортирован по doc ID, каждый документ имеет ранг согласно слову.
Когда запрос приходит, он содержит несколько ключевых слов. Для каждого слова вы можете найти список документов. Для всех ключевых слов вы можете выполнить операции слияния и вычислить релевантность документа для запроса. Наконец, верните документ с высоким рейтингом релевантности пользователю.
И процесс запроса может быть распределен для повышения производительности.

Ответ 2

Большинство систем каким-то образом реализуют TF-IDF так или иначе. TF-IDF является продуктом частоты функций и частоты обратного документа.

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

Вы упоминаете Google, но Google оптимизирует поиск с помощью PageRank (ссылки в/из), а также время и близость. Google распространяет данные и использует Map/Reduce для параллелизации операций - для вычисления PageRank + TF-IDF.

Там большое объяснение теории, стоящей за этим в Информационный поиск: внедрение поисковых систем глава 2. Еще одна идея для дальнейшего изучения - также посмотреть как Solr реализует это.

Ответ 3

Даже без ранжирования, мне интересно, как пересечение двух множеств вычисляется так быстро google.

Очевидно, что наихудший сценарий вычисления пересечения для некоторых слов A, B, C - это когда их индексы очень большие, а пересечение очень мало. Типичным случаем будет поиск некоторых очень распространенных ( "популярных" в терминах БД) слов на разных языках.

Попробуйте "конкретный" и "位置 (" сайт "," местоположение ") на китайском и 極端な (" экстремальный ") на японском языке.

Поиск Google для 位置 возвращает "Около 1500 000 000 результатов (0,28 секунды)" Google ищет "конкретные" результаты "Около 2020 000 000 результатов (0,46 секунды)" Поиск в Google "極端な" Около 7 590 000 результатов (0,25 секунд)

Крайне невероятно, что все три члена будут появляться в одном документе, но пусть google им: Поиск Google для "конкретных 位置極端な" возвращает "Около 174 000 результатов (0,13 секунды)"

Добавление русского слова "игра" (игра) Поиск игры: около 212 000 000 результатов (0,37 секунды)

Искать все: "игра конкретный 位置極端な" возвращает около 12 600 результатов (0,33 секунды)

Конечно, возвращаемые результаты поиска нонсенс, и они не содержат всех условий поиска.

Но глядя на время запроса для составленных, я задаюсь вопросом, есть ли какое-либо пересечение, вычисленное по индексам слов вообще. Даже если все находится в ОЗУ и сильно оштрафовано, вычисление пересечения двух наборов с 1 500 000 000 и 2020 000 000 записей - O (n) и вряд ли может быть выполнено за 0,5 секунды, поскольку данные находятся на разных машинах, и они должны общаться.

Должно быть какое-то соединение, но, по крайней мере, для популярных слов, это, безусловно, не делается на всем индексе слова. Добавляя тот факт, что результаты нечеткие, кажется очевидным, что Google использует некоторую оптимизацию вида "отдать некоторые высокоуровневые результаты и остановиться через 0,5 секунды".

Как это реализовано, я не знаю. Любые идеи?

Ответ 4

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

Итак, google начинает пересечение, пока не найдет 10 результатов, а затем сделает статистическую оценку, чтобы рассказать вам, сколько еще результатов она нашла.

Наихудший случай почти невозможно. Если все слова "общие", то пересечение даст первые 10 результатов очень быстро. Если есть редкое слово, то пересечение происходит быстро, поскольку сложность O (N long M), где N - наименьшая группа.

Вам нужно помнить, что google сохраняет индексы в памяти и использует параллельные вычисления. Например, U может разделить проблему на два поиска, каждый из которых ищет только половину веб-страницы, а затем результат marge и делает все возможное. Google имеет миллионы вычислений