libsearch
1.0.0
Простой текстовый поиск без индексирования для JavaScript, используемый в моих личных проектах, таких как YC Vibe Check, linus.zone/entr, и в моем личном программном обеспечении для повышения производительности. Прочтите аннотированный источник, чтобы понять, как это работает.
Начнем с нескольких быстрых примеров:
import { search } from 'libsearch' ; // on Node.js
const { search } = window . libsearch ; // in the browser
const articles = [
{ title : 'Weather in Berkeley, California' } ,
{ title : 'University report: UC Berkeley' } ,
{ title : 'Berkeley students rise in solidarity...' } ,
{ title : 'Californian wildlife returning home' } ,
] ;
// basic usage
search ( articles , 'berkeley cali' , a => a . title ) ;
// => [{ title: 'Weather in Berkeley, California' }]
search ( articles , 'california' , a => a . title ) ;
// => [
// { title: 'Weather in Berkeley, California' },
// { title: 'Californian wildlife returning home' },
// ]
// mode: 'word' only returns whole-word matches
search ( articles , 'california' , a => a . title , { mode : 'word' } ) ;
// => [{ title: 'Weather in Berkeley, California' }]
// case sensitivity
search ( articles , 'W' , a => a . title , { caseSensitive : true } ) ;
// => [{ title: 'Weather in Berkeley, California' }]
// empty query returns the full list, unmodified
search ( articles , '' , a => a . title ) ;
// => [{...}, {...}, {...}, {...}] Более формально, libsearch предоставляет единственный API — функцию search . Эта функция принимает два обязательных и два необязательных аргумента:
function search < T > (
items : T [ ] ,
query : string ,
by ?: ( it : T ) => string ,
options ?: {
caseSensitive : boolean ,
mode : 'word' | 'prefix' | 'autocomplete' ,
} ,
) : T [ ]items — это список элементов для поиска. Обычно items представляют собой массив строк или массив объектов с некоторым строковым свойством.query — это строковый запрос, с помощью которого осуществляется поиск в списке элементов.by ( необязательный ) — это функция-предикат, которая берет элемент из items и возвращает строковое значение, по которому можно искать этот элемент. Например, если items представляет собой список объектов типа { name: 'Linus' } , by должна быть функцией x => x.name . По умолчанию оно имеет значение x => String(x) , которое работает для items типа string[] .options ( необязательный ) — это словарь опций:caseSensitive делает поиск чувствительным к регистру. По умолчанию это false .mode контролирует способ сопоставления неполных слов запроса:mode: 'word' требует, чтобы каждое слово запроса соответствовало только полным и точным словам, а не частям слов. Например, запросу «Калифорния» будет соответствовать « Калифорнийский университет», но не « Калифорнийский университет».mode: 'prefix' означает, что каждое слово запроса может быть неполным «префиксом» совпадающего слова. «Университет Калифорнии» будет соответствовать как « Университету Калифорнии », так и « Калифорнийскому университету ». Даже в этом режиме каждое слово запроса должно где-то совпадать — « Калифорния » не является совпадением, поскольку оно не соответствует запросу. слово «Универ».mode: 'autocomplete' — это гибрид двух других режимов, который полезен при использовании в поиске в стиле автозаполнения, когда пользователь постоянно вводит запрос по мере того, как возвращаются результаты поиска. Этот режим идентичен mode: 'word' , за исключением того, что последнее слово запроса может быть неполным, как в mode: 'prefix' . Это означает, что «Калифорнийский университет» будет соответствовать « Калифорнийскому университету », что полезно, поскольку пользователь может найти совпадение до того, как введет полный запрос.Дополнительные примеры того, как эти параметры сочетаются друг с другом, можно найти в модульных тестах.
<script>Добавьте это в свой HTML:
< script src =" https://unpkg.com/libsearch/dist/browser.js " > </ script > Это предоставит функцию search как window.libsearch.search .
npm install libsearch
# or
yarn add libsearchИ используйте в своем коде:
import { search } from 'libsearch' ;
// search(...);libsearch поставляется с определениями типов TypeScript, сгенерированными из исходного файла. Использование libsearch из NPM должно помочь компилятору TypeScript их подобрать.
libsearch позволяет быстро выполнять базовый полнотекстовый поиск по списку объектов JavaScript, не требуя предварительно созданного индекса поиска, предлагая при этом достаточно хорошее ранжирование результатов TF-IDF. Он не предоставляет широкого спектра функций, которые есть в таких библиотеках, как FlexSearch и lunr.js, но является большим шагом вперед по сравнению с text.indexOf(query) > -1 и достаточно быстр, чтобы его можно было использовать для поиска в тысячах документов. каждое нажатие клавиши по моему опыту.
Есть две ключевые идеи того, как libsearch обеспечивает это:
Современные движки JavaScript поставляются с высокооптимизированными движками регулярных выражений, и libsearch использует это преимущество для быстрого текстового поиска без индексов, преобразуя строки запроса в фильтры регулярных выражений во время поиска.
Большинство библиотек полнотекстового поиска сначала требуют от разработчика создания «индексной» структуры данных, сопоставляющей условия поиска с документами, в которых они встречаются. Обычно это хороший компромисс, поскольку при этом часть вычислительной работы по «поиску» выполняется заранее, поэтому сам поиск может оставаться быстрым и точным. Он также позволяет выполнять сложные преобразования и очистку данных, например лемматизацию индексированных данных, без ущерба для скорости поиска. Но при создании прототипов и простых веб-приложений мне часто не хотелось брать на себя сложности, связанные с отдельным этапом «индексации», чтобы получить «достаточно хорошее» решение для поиска. Индекс необходимо где-то хранить и постоянно поддерживать по мере изменения и роста базового набора данных.
Основная задача поискового индекса — сопоставить «токены» или ключевые слова, которые появляются в наборе данных, с документами, в которых они появляются, так что вопрос «какие документы содержат слово X?» быстро ( O(1) ) отвечает во время поиска. Без индекса это превращается в вопрос O(n) , поскольку каждый документ необходимо сканировать на предмет ключевого слова. Но часто на современном оборудовании для достаточно небольших наборов данных (несколько МБ), типичных для клиентского веб-приложения, n довольно мало, достаточно мало, чтобы O(n) при каждом нажатии клавиши было незаметно.
libsearch преобразует запрос типа «Университет Калифорнии» в список фильтров регулярных выражений, (^|W)Uni($|W) , (^|W)of($|W) , (^|W)California . Затем он «ищет» без необходимости использования индекса, фильтруя корпус по каждому из этих регулярных выражений.
Обычная метрика TF-IDF вычисляется для каждого слова как:
( # matches ) / ( # words in the doc ) * log ( # total docs / # docs that matched )Чтобы узнать количество слов в документе, требуется токенизировать документ или, по крайней мере, разделить его по пробелам, что требует больших вычислительных затрат. Таким образом, libsearch аппроксимирует это, используя вместо этого длину документа (количество символов).
Используя запросы регулярных выражений, описанные выше, формула TF-IDF libsearch имеет следующий вид:
( # RegExp matches ) / ( doc . length ) * log ( # docs / # docs that matched RegExp )который вычисляется для каждого слова при выполнении поиска, а затем в конце суммируется для сортировки.
Исходный код libsearch написан на TypeScript. Чтобы библиотеку можно было использовать в TypeScript, ванильном Node.js и в Интернете, мы скомпилировали две сборки:
search.ts и удаляются типы. Это код, импортируемый при импорте libsearch в Node.js.search в глобальный файл window.libsearch Сборка модуля ES создается с помощью tsc , компилятора TypeScript, а мини-сборка браузера дополнительно создается с помощью Webpack.
Команды NPM/Yarn:
lint и fmt , которые анализируют и автоматически форматируют исходный код в репозитории.test запускает модульные тесты последней сборки библиотеки; вам следует запустить build:tsc перед запуском testbuild:* управляют созданием различных типов сборок библиотек:build:tsc собирает сборку модуля ESbuild:w запускает build:tsc при каждой записи файлаbuild:cjs собирает сборку браузера из сборки модуля ES.build:all собирает обе сборки по порядкуclean удаляет все сгенерированные файлы/файлы сборки в dist/docs создает документацию на основе Litterate, которая находится по адресу thisphist.github.io/libsearch.Прежде чем отправить на главную страницу или опубликовать, я обычно запускаю
yarn fmt && yarn build:all && yarn test && yarn docsчтобы убедиться, что я ничего не забыл.
