Рассматривая запрос «И», например:
"Gaga AND CD"
Вы можете себе представить, что Gaga гораздо реже, чем CD.Другими словами, список рассылки (или перевернутый список, как вы) в Gaga намного короче, чем список для CD.
Давайте предположим, что два небольших списка рассылки для двух слов (япоказывая только doc_ids, которые здесь представляют интерес):
Gaga -> [2, 10, 1023, 2030]
CD -> [1, 2, 6, 8, 15, 32, 43, 52, 92, 115, 326, 401, 560, 564, ... , 1924, 2030, ...]
При поиске по документу за раз мы перебираем списки рассылки в paralell, ища документы, соответствующие запросу (вИ запрос, только каждый документ, который встречается в обоих списках публикаций).
В этом типе поиска мы можем пропускать документы, зная самый редкий термин (Gaga).Таким образом, мы можем использовать его список рассылки как «опорный пункт».Первый doc_id, который нужно искать, это 2, а не 10.Обратите внимание, что мы можем пропустить все doc_ids между 2 и 10 в CD списках рассылки, потому что мы знаем, что это ничего не будет соответствовать.Аналогично, следующий обработанный doc_id - 1023.При обработке 1023 мы можем пропустить не менее 10 документов (от 15 до чего-то после 564), потому что мы знаем, что оно ничего не будет соответствовать.
Алгоритм (для запроса AND)в основном пересечение массива.Когда вы получаете пересечение, вы обрабатываете его.В противном случае вы продолжите пропуск.
ОБНОВЛЕНИЕ : Многие реализации используют Пропуск списков , чтобы избежать сравнения при обработке инвертированных списков.В приведенном выше примере система может использовать список пропусков, чтобы «перейти» на следующую позицию инвертированного списка CD, у которого doc_id близок к 10. Таким образом, нет необходимости сравнивать с 6 и * 1034.*.