Полнотекстовый поиск в IndexedDB

Практическое руководство по созданию полнотекстового поиска поверх IndexedDB для borogove - веб-клиента чата, который хранит историю сообщений локально. В IndexedDB нет встроенного полнотекстового поиска, поэтому автор (singpolyma) собирает его с нуля в два этапа: сначала наивное сканирование всей таблицы, затем индексный подход, справляющийся с миллионом сообщений.

Токенизация и стемминг

Оба подхода начинаются с одного и того же пайплайна обработки текста. Функция tokenize() переводит входные данные в нижний регистр, разбивает на слова по границам, отбрасывает одиночные символы и стоп-слова. Опционально стеммер Porter2 приводит словоформы к основам, чтобы "flying" совпадало с "fly". Запрос и сохраняемый текст проходят через один и тот же пайплайн перед сравнением.

Условие совпадения - вхождение множеств: документ подходит, если его множество токенов является надмножеством для множества токенов запроса. Метод Set.isSupersetOf() в JavaScript делает именно это.

Сканирование таблицы

Самый простой вариант: открыть курсор по всему хранилищу сообщений, токенизировать текст каждого сообщения и проверять, содержит ли оно все термины запроса. Это отлично работает для наборов объёмом менее 10 000 сообщений. Дальше итерация по каждой строке начинает ощутимо тормозить.

Поиск по индексу с multiEntry

IndexedDB поддерживает флаг multiEntry: true при создании индекса по массиву. Вместо индексации всего массива как единого ключа база создаёт отдельную запись в B-дереве для каждого элемента - фактически inverted-index. При сохранении сообщения к нему добавляется массив terms (дедуплицированные токены после стемминга), и каждый термин получает собственную запись в индексе со ссылкой на исходное сообщение.

Алгоритм поиска:

1. Токенизировать запрос и применить стемминг
2. Для каждого термина запроса запросить у индекса количество содержащих его сообщений (index.count())
3. Выбрать самый редкий термин - тот, у которого меньше всего совпадений
4. Открыть курсор по индексу только для этого термина
5. Для каждого кандидата проверить, является ли его полный набор терминов надмножеством всех терминов запроса
6. Вручную отсортировать результаты по метке времени (индекс упорядочен по терминам, а не по времени)

Шаг "поиск по самому редкому термину" как раз и обеспечивает скорость. В корпусе из миллиона сообщений даже часто встречающиеся слова могут присутствовать в десятках тысяч сообщений, но самый редкий термин запроса обычно находится менее чем в 10 000. Сканирование 10 тыс. кандидатов вместо 1 млн - это разница между зависанием и мгновенным ответом.

Никаких внешних зависимостей

Вся реализация опирается только на API IndexedDB, Set и токенизатор. Никаких поисковых библиотек, SQLite на WebAssembly или серверных индексов. Это важно для offline-first веб-приложений, которым нужен поиск без раздувания зависимостей.

Ограничения

В статье не рассматривается ранжирование: результаты возвращаются по времени, а не по релевантности. Здесь нет подсчёта очков по TF-IDF или BM25, нет поиска фраз и нечёткого поиска за пределами стемминга. Для строки поиска в чате, где нужно просто "показать сообщения с этими словами", этого вполне достаточно. Для более сложной поисковой системы понадобятся методы hybrid-search.

Индекс multiEntry также требует хранить полный список терминов вместе с каждым сообщением, что примерно удваивает объём хранилища на одно сообщение. В статье это считается приемлемым компромиссом.