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

Question

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

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

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

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

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

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

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

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

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

Answer 1

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

Answer 2

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

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

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

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

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

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

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

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

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

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

Как это реализовано, я не знаю. Есть идеи?

Answer 3

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

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

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

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

Answer 4

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

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

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

Вам нужно помнить, что Google хранит свои индексы в памяти и использует параллельные вычисления. Например, U может разделить задачу на два поиска, каждый из которых ищет только половину сети, а затем пометить результат и взять лучший. У Google миллионы компьютеров