Про то, что в поисковых движках (для полнотекстового поиска) обычно есть.
Интересно, что на самом деле ничего очень специфичного именно для поиска вроде как и нет. Т.е. конечно алгоритмов и подходов внутри подобных решений хватает, но чтобы прям только тут, такого ничего не видно.
Базой почти всегда служит инвертированный индекс — множество id документов для каждого ключевого слова, в которых это самое слово встречается. Выглядит это примерно вот так:
using Index = Map<String, Vector<int>>;Правда вектор интов это всё-таки упрощение, т.к. чаще всего хочется хранить что-то более сложное. Например структурку
Posting (вхождение слова в документ), которая хранит всякие разные дополнительные штуки: id поля в документе (можно потом с разными весами их крутить), позиция слова в документе, различные флаги и что угодно ещё. Собственно если у вас именно вектор интов в значении мапки, вы можете его очень сильно пожать. Ловите профит, правда инфы из такого индекса вы получаете мало. Хотя если научиться каким-то образом ужимать весь ваш
Posting в одно чиселко, можно тут и пооптимизировать. Тут правда миллион вопросов возникает: как должен быть устроен
Map? а Vector<Posting>? Эти структуры могут быть примерно чем угодно в зависимости от вашей прикладной области и требований. Т.к. индекс обычно поддерживает очень много разной инфы, приходится очень много сжимать, потому что огромные индексы — неэффективно и больно. Из простого и понятного для последовательностей чисел (в нашем случае например для id документов) можно применять дельта-кодирование, когда вы возрастающую положительную последовательность меняете на разницу с предыдущим:
11, 15, 16, 21, 37, …
11, 4, 1, 5, 16, …
Если же у нас и отрицательные, применяют что-то около zig-zag кодирования.
Но вообще как числа жать, уже давно придумали: elias gamma, golomb, rice, huffman и другое. С ними правда тоже вопросики есть, но можно крутиться.
Можно ещё посмотреть в сторону varint (или group varint/pfor/simple9/simple16).
Но в любом случае надо что-то тут делать, потому что сжимать оч важно.
Важной частью ещё является ранжирование. Учитывая развесистые модели, которые для решения этой задачи используются, эта часть может занимать огромное количество времени. И сверху ещё (т.к. обычно там какой-никакой мль), результаты могут быть с вопросом. Тут рядом считают какие-нибудь статистики вроде TF/BM25, которые в поисковых движках уже стали классикой. Иногда ещё движки, если они разрабываются как SaaS решение, могут предоставлять возможность создавать свои факторы для ранжирования и как-то их крутить. Очень полезно в рамках различных предметных областей, т.к. непонятно, где ваша разработка будет использоваться. Хотя конечно почти наверняка делают более специализированные штуки (например в силу специфики работы, видел движки для екома, но скорее внутри, чем снаружи).
Обычно в движке у вас есть ещё какой-то матчинг (чтобы какие-то результаты по запросу получать), опечаточник, саджест, иногда какие-то атрибутивные real-time обновления, чтобы индекс каждый раз заново не варить (иногда умеют делать фулл индексы real-time, но не совсем, а иногда умеют варить только дельту). Короч очень много всего.
И есть конечно же огромная куча подходов и решений, которые часто встречаются в других областях. Например как в бд (потому что движки это по факту специфические базы данных), как в nlp (кодировки, токенизация, морфология, стемминг/лемминг, языковые модели), ну и интеграции для более гибкой настройки (иногда свой диалект SQL, различные возможности подменять этапы работы с текстом, интеграции с моделями для ранжирования, с библиотеками для векторного поиска (если вдруг надо) и чем угодно ещё).
Постик основан на докладе, но ссылку на него я вам пока не дам, потому что он в закрытом доступе. Как появится запись, обязательно поделюсь.