Comments 23
Можно еще на этот проект посмотреть https://github.com/blevesearch/bleve, если интересна тема FTS на go
Всё это есть в sphinxsearch (qsuggets, оператор кворума, биграммы на основе слов), но искать алгоритмы в исходниках дело не самое эффективное.
Из «претензий» к статье: вместо стемминга лучше использовать лемматизацию, да и стоп-слова лучше не выкидывать напрочь, а ранжировать с меньшим весом. Впрочем, ранжирование это очень глубокая нора.
Вот настраивать эти алгоритмы под свои задачи — сложно.
youtu.be/wCGBTjHikwA
Сам автор Сфинкса рассказывает что да как.
Сам же инструмент — ничего особенного из себя не представляет.
Для Go есть такая штука, аналогичная Сфинксу, но на Go писанная и вкомпилируется прямо в программу:
github.com/blevesearch/bleve
Сам по себе Lucene отличный «движок», а в сочетании с идеей токенов, так иногда просто конфетка получается.
Левенштейн в лоб делать нельзя — свалимся иначе в full scan. Можно, например, по заданным паттерну и максимальному расстоянию найти все токены, и затем искать пересечение множества найденных токенов и токенов документов
Можно на fsm. https://blog.burntsushi.net/transducers/
К концу этой статьи он сможет выполнять поиск по миллионам документов менее чем за миллисекунду.
Строго говоря, это не поиск, а лукап в хэшмапе, конечно, он быстрый. Вот только он вообще ничем не лучше разогретого грепа, только жрет гораздо больше памяти и откажется работать на файле достаточно большого размера. Вы бы хоть исходный дамп потоком читали, что ли.
Так что «можно использовать grep, но это не всегда лучшая идея» — пока что чистой воды спекуляция.
Не могу понять почему люди массово не знаю что map это не карта, а отображение в русском языке?)
Вытекает из соответствующего математического понятия.
Вроде бы тема не тривиальная и подразумевает базовые знания математики и компьютерных наук.
p.s.
У меня даже такой критерий сформировался, если человек называет map, картой, он или не учился в профильном вузе или плохо учился. Но в любом случае имеет фундаментальные пробелы.)
Я почему спрашиваю, потому что аналогичный велосипед на go сделал, только у меня не fts, а фасеточный поиск )) И, производительностью я доволен. Однако пришлось делать ниразу не универсальный код — все подогнанно компилятором под мою задачу. Но, я получил на редких дурацких запросах прирост 100х относительно mysql. Ну, и в самых популярных, менее 1мс на запрос.
Понятно что это решение не дотягивает до вылизанного fts-поиска в той же постгре или сфинксе, т.е. придется много простых и дурацких вещей руками делать (типа подсветки найденного результата), так же учитывать расстояние между словами. Но, все же, решение имеет право на существование, по сути, во многом, го для этого и был создан — ускорить кастомным решением то, что универсальным тормозит.
Пишем движок полнотекстового поиска на Go