Я не знаю, как это делает Google, но я могу рассказать вам, как Я сделал это, когда клиенту нужно что-то подобное:
Начинается с инвертированного индекса, как описано в Avi. Это просто список таблиц для каждого слова в каждом документе, идентификатор документа, слово и оценка релевантности слова в этом документе. (Другой подход состоит в том, чтобы индексировать каждое появление слова индивидуально вместе с его положением, но в этом случае это не требовалось.)
Оттуда, это даже проще, чем описание Avi - нет необходимости делать отдельный поиск для каждого термина. Стандартные операции с базой данных могут легко сделать это за один проход:
SELECT document_id, sum(score) total_score, count(score) matches FROM rev_index
WHERE word IN ('david', 'john') GROUP BY document_id HAVING matches = 2
ORDER BY total_score DESC
При этом будут возвращены идентификаторы всех документов, которые имеют оценки как для «Дэвида», так и для «Иоанна» (т. Е. Оба слова появляются), упорядоченные по некоторой аппроксимации релевантности, и их выполнение займет примерно одно и то же время независимо от того, сколько или как мало терминов, которые вы ищете, так как на производительность IN не влияет размер целевого набора, и он использует простой count, чтобы определить, были ли сопоставлены все термины.
Обратите внимание, что этот упрощенный метод просто добавляет оценку «Дэвид» и оценку «Джон» вместе, чтобы определить общую релевантность; он не принимает порядок / близость / и т.д. из имен в учет. Еще раз, я уверен, что Google учитывает это в своих оценках, но моему клиенту это не нужно.