В рамках постов про поиск расскажу про boolean retrieval model (источник — стенфордская книжка, которую мне накидывали в комментах).
> Почему retrieval? Вообще вот эта вся тема с поиском она скорее про извлечение информации из какого-то множества. Так и говорят: information retrieval (IR).
Предположим, мы хотим найти главы книги, для которых верно, что есть слова A и B, но нет слова C. Конечно, мы можем пройтись по тексту от начала до конца за O(n) и проверить выполнение условий для каждой главы, но в рамках реально огромных текстов и большого количества запросов это может быть неэффективно. Давайте запрепроцессим наш текст (индексируем его, поставив 1, если слово встречается в главе, и 0 иначе):
Ch1 Ch2 Ch3 Ch4 Ch5
A 1 1 0 1 0
B 1 0 1 1 1
C 0 1 1 0 0
D 0 0 0 1 1
…Так для каждого слова имеем булевый вектор. Давай ответим на запрос. Для этого сделаем
AND векторам слов A и B и инвертированного вектора С:11010 & 10111 & 10011 = 10010То есть наши условия выполняются для Ch1 и Ch4.
Boolean retrieval model — модель IR, когда любой запрос можно сформулировать в виде булевых операций над булевыми векторами для термов (терм == токен).
Если взять какие-то более реальные данные, то подобная матрица будет довольно разреженной, потому лучше хранить только единички. Так и появляется инвертированный индекс: когда для каждого терма хранится множество документов, в которых этот терм встречается. В инвертированном индексе обычно хранят постинги (posting) — вся инфа про терм в документе. В примере выше это был факт наличия, но в него можно класть ещё позицию в документе и что угодно ещё.
Множество постингов для терма обычно хранят на диске (предварительно это всё сжимается). Тут конечно встаёт вопрос, в каком виде. С одной стороны, можно хранить
std::vector постингов, так как тут минимален оверхед и данные лежат рядом. С другой стороны для быстрых вставок может лучше подойти какой-нибудь список. Учитывая, что постинги обычно отсортированы, при надобности даже скиплисты можно использовать (писал про них тут).Если мы хотим в рамках boolean retrieval ответить на запрос вроде
A & B, достаточно просто взять постинги для нужных термов и пересечь их.Несложно добавляется и условие на отсутствие терма (
A & B & !C). Это всё тривиально делается двумя указателями.Если в запросе есть
OR, то можно немного улучшить и посмотреть на размеры тех или иных множеств постингов. Условно для (A | B) & (C | D)можно проверить сначала
B & C, если множества постингов для этих термов имеют минимальный размер (возможно потребуется предварительно привести запрос к дизъюнктивной нормальной форме).
Или можно бинарным поиском поискать id документов из более короткого листа постингов в более длинном.
Короче микрооптимизации такие.
Иногда в подобных системах реализуют так называемые proximity operators, которые задают более сложные условия на ответ. Например, как близко слова должны быть расположены в итоговом документе.
Из примеров коммерческого поиска с boolean retrieval model есть westlaw.com (правда там обязательный логин перед использованием).
В противовес этой модели существует ranked retrieval model, в которой запрос это просто текст (все мы пользуемся таким подходом, когда что-то гуглим).