Как я пытался сделать идеальный нечёткий поиск (и почему в итоге пришлось писать 5 уровней скоринга)

[rusegal]

Из того что приходит на ум, это взять обратный(инвертированный если я правильно помню) индекс из Эластика. Можно еще дерево суффиксов, но он будет по логике есть кратно больше памяти - хотя и улучшит поиск по подстроке.

[MaxNardit]

Инвертированный индекс — первое что приходит в голову для текстового поиска. Для моего кейса (1000–2000 записей in-memory, 0.76 мс на линейном проходе) пока overhead на поддержание индекса не оправдан, но если база вырастет до 10K+ — это первое куда полезу.

Вопрос, который меня мучает: инвертированный индекс решает задачу найти быстро, но моя главная боль была отранжировать правильно — отличить совпадение в контенте от совпадения в метаданных окна. Вы сталкивались с ранжированием поверх инвертированного индекса на клиенте?

Суффиксное дерево для подстрочного поиска — тоже думал, но остановила память. Средняя запись 200–500 символов, бывают 5K+. Есть ли компактные реализации которые на таких объёмах имеют смысл?

[Cheater]

Поиск по всему этому должен работать мгновенно

Я не понял, почему если бэкенд на Rust, то автодополнением ввода занимается js код?? Это же задача бэкенда? Особенно при том что у вас стоит цель выполнять запросы быстро на большом вводе. Есть готовые движки для нечёткого поиска, например fuzzy-matcher в skim (клон fzf на Rust) или превосходящий его в производительности nucleo.

хотел большего: толерантность к опечаткам

Имхо: это то, что называется "solves a non-problem". Очень редко бывает, что юзер опечатывается в коротком вводе который у него перед глазами, и ещё реже, что он не замечает опечатки - просто глядя на экран, или по результатам автодополнения по ошибочному вводу. Обработка опечаток заставляет вас реализовывать сложный и дорогой алгоритм нечёткой близости слов, при том что это нужно в 0.001% случаев. Кроме того нечёткий алгоритм часто даёт много нерелевантных результатов, кто пользуется нечётким поиском по Unix путям к файлов тот знает. Сделайте просто поиск по подстрокам (с нечёткостью только по отношению к регистру и к порядку паттернов, вводимых юзером, т.е. чтобы "def__AbC" подходило под запрос "abc def") и вам этого будет достаточно почти для всего. Ещё лучше сделать алгоритм с обработкой "frecency" - учитыванием как близости к поисковому запросу, так и частотой выигрыша в прежних запросах. Но ок, если вы хотите в эту кроличью нору с опечатками, то, ряд движков автодополнения реализуют подобные алгоритмы с устойчивостью к опечаткам, например frizbee. Fzf насколько я знаю так не умеет, но Skim умеет: https://www.reddit.com/r/neovim/comments/1qpary8/fzfluaskim_now_supports_typo_resistant_fuzzy/ Немного отсылок к теории по этим алгоритмам есть в доках к Nucleo и Frizbee. Известный алгоритм для этого это Smith-Waterman, он вообще для ДНК цепочек, но применим к текстовому поиску. Именно его вариации применяют nucleo и frizbee. Также классика это Levenshtein distance / Levenshtein algorithm.

Также по архитектуре замечание, я так понимаю что если ваш алгоритм обнаруживает результат чёткого поиска, то нечёткий поиск запущен не будет и результаты нечёткого поиска не попадут в выдачу? Правильное поведение здесь это имхо асинхронное формирование списка вывода и обновление его в реальном времени по мере обнаруживания новых результатов.

[MaxNardit]

Спасибо, тут много ценного. По пунктам:

Почему JS, а не Rust? Данные уже живут в JS — загружены из SQLite в React state для рендеринга. Поиск на Rust значил бы IPC round-trip на каждый keystroke. При 0.76 мс на поиск в JS сам IPC overhead может оказаться больше выигрыша. Но вы правы — при росте базы до 10K+ имеет смысл перенести поиск в Rust и отдавать только отфильтрованные ID.

nucleo и frizbee — спасибо, не знал про них. nucleo особенно интересен — Rust-native, быстрый, и если переносить поиск на бэкенд, это первый кандидат. Smith-Waterman тоже посмотрю.

Fuzzy — non-problem? Отчасти согласен, и на практике я к этому пришёл: в текущей версии fuzzy запускается только когда точные фазы нашли < 5 результатов. Первые 4 фазы — это именно то, что вы описали: подстроки + case insensitive + любой порядок токенов + границы слов. Fuzzy — страховка на самом дне выдачи. Разница в 5-й фазе, которая на практике срабатывает редко.

frecency — отличная идея. Сейчас тайбрейкер — last_used, но трекать «какой результат юзер реально выбрал после поиска» и бустить его в будущем — это следующий уровень. Записал.

Асинхронное формирование выдачи — при 0.76 мс на весь пайплайн пользователь не увидит разницы между синхронным и progressive-обновлением. Но если перенести на Rust + nucleo с базой побольше, то да, streaming результатов через IPC был бы правильным паттерном. Ради такой информации и публиковал статью.

[cpud47]

Вместо этого лучше просто скорить совпадения. Например, если пользователь искал "motivating example", то есть большая разница между кейсами:

1. Нашли эти два слова подряд

2. Нашли эти два слова рядом (на расстоянии меньше D слов)

3. Нашли этидва слова в разных концах содержимого

4. Нашли одно слово в содержимом а другое в приложении

Поэтому Вам стоит просто ранжировать совпадения на основании того, а как близко находятся матчи. При этом я не уверен, что вариант 3 более релевантен чем вариант 4 в Вашем случае.

Плюс, обычно стоит давать разные приоритеты разным словам. Например, если у нас почти все элементы пришли из хрома, то поиск по запросу "хром" практически не должен учитывать заголовки. А вот в содержимом слово хром очень даже много значит. Это базово решается при помощи tf-idf (хотя и не совсем классическое применение).