Использование индексов для многословных запросов в полнотекстовом поиске (например, веб-поиск)
Я понимаю, что фундаментальным аспектом полнотекстового поиска является использование инвертированных индексов . Таким образом, с инвертированным индексом ответ на однословный запрос становится тривиальным. Предположим, что индекс имеет следующую структуру:
some-word -> [doc385, doc211, doc39977, ...] (отсортировано по рангу, по убыванию)
Чтобы ответить на запрос этого слова, решение состоит в том, чтобы просто найти правильную запись в индексе (что занимает время O (log n)) и представить заданное количество документов (например, первые 10) из списка указывается в индексе.
Но как насчет запросов, которые возвращают документы, которые соответствуют, скажем, двум словам? Самая простая реализация будет следующая:
- установить A как набор документов, которые имеют слово 1 (путем поиска по индексу).
- установить B как набор документов, которые имеют слово 2 (то же самое).
- вычислить пересечение A и B.
Теперь, третий шаг, вероятно, занимает O (n log n) времени для выполнения. Для очень больших значений A и B, которые могут замедлить ответ на запрос. Но поисковые системы, такие как Google, всегда возвращают свой ответ через несколько миллисекунд. Так что это не может быть полным ответом.
Одна очевидная оптимизация заключается в том, что, поскольку поисковая система, такая как Google, в любом случае не возвращает все совпадающие документы, нам не нужно вычислять все пересечение. Мы можем начать с наименьшего набора (например, B) и найти достаточно записей, которые также принадлежат другому набору (например, A).
Но не можем ли мы все еще иметь следующий наихудший случай? Если мы установили A как набор документов, соответствующих общему слову, и установили B как набор документов, соответствующих другому общему слову, все еще могут быть случаи, когда A ∩ B очень мало (т. Е. Комбинация является редкой). Это означает, что поисковая машина должна линейно пройти через все элементы x члена B, проверяя, являются ли они также элементами A, чтобы найти те немногие, которые соответствуют обоим условиям.
Линейный не быстрый. И у вас может быть больше двух слов для поиска, так что простое использование параллелизма - это еще не полное решение. Итак, как оптимизировать эти кейсы? Используют ли крупномасштабные полнотекстовые поисковые системы какие-то составные индексы? Фильтры Блума? Есть идеи?