libsearch

libsearch?

Pesquisa de texto simples e sem índice para JavaScript, usada em meus projetos pessoais como YC Vibe Check, linus.zone/entr e meu software de produtividade pessoal. Leia a fonte anotada para entender como ela funciona nos bastidores.

A API

Vamos começar com alguns exemplos rápidos:

 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 ) ;
// => [{...}, {...}, {...}, {...}]

Mais formalmente, libsearch expõe uma única API, a função search . Esta função recebe dois argumentos obrigatórios e dois argumentos opcionais:

 function search < T > (
    items : T [ ] ,
    query : string ,
    by ?: ( it : T ) => string ,
    options ?: {
        caseSensitive : boolean ,
        mode : 'word' | 'prefix' | 'autocomplete' ,
    } ,
) : T [ ]

• items é uma lista de itens a serem pesquisados. Normalmente items serão uma matriz de strings ou uma matriz de objetos com alguma propriedade de string.
• query é uma consulta de string com a qual pesquisar a lista de itens.
• by ( opcional ) é uma função de predicado que pega um item dos items e retorna um valor de string para pesquisar esse item. Por exemplo, se items for uma lista de objetos como { name: 'Linus' } , by precisará ser uma função x => x.name . Isso tem o valor x => String(x) por padrão, que funciona para items do tipo string[] .
• options ( opcional ) é um dicionário de opções:
  • caseSensitive torna uma pesquisa sensível a maiúsculas e minúsculas. É false por padrão.
  • mode controla a forma como as palavras de consulta incompletas são correspondidas:
    • mode: 'word' exige que cada palavra de consulta corresponda apenas a palavras completas e exatas, em vez de partes de palavras. Por exemplo, a consulta "Califórnia" corresponderá a "Universidade da Califórnia ", mas não a "Universidade da Califórnia ".
    • mode: 'prefix' significa que cada palavra de consulta pode ser um "prefixo" incompleto da palavra correspondente. "Uni Cali" corresponderá a " Universidade da Califórnia " e " Universidade da Califórnia ". Mesmo neste modo, cada palavra de consulta deve corresponder a algum lugar - " Califórnia " não é uma correspondência, porque não corresponde à consulta palavra "Uni".
    • mode: 'autocomplete' é um híbrido dos outros dois modos que é útil quando usado em pesquisas no estilo de preenchimento automático, onde um usuário digita continuamente uma consulta à medida que os resultados da pesquisa são retornados. Este modo é idêntico ao mode: 'word' , exceto que a última palavra de consulta pode estar incompleta como em mode: 'prefix' . Isso significa que "Universidade de Cali" corresponderá a " Universidade da Califórnia ", o que é útil porque o usuário pode encontrar a correspondência antes de digitar a consulta completa.

Você pode encontrar mais exemplos de como essas opções se combinam nos testes de unidade.

Instalação e uso

Na web, com <script>

Coloque isso em seu HTML:

 < script src =" https://unpkg.com/libsearch/dist/browser.js " > </ script >

Isso exporá a função search como window.libsearch.search .

Via NPM

npm install libsearch
# or
yarn add libsearch

E use no seu código:

 import { search } from 'libsearch' ;

// search(...);

Usando tipos TypeScript

libsearch vem com definições de tipo TypeScript geradas a partir do arquivo de origem. Usar libsearch do NPM deve fazer com que eles sejam capturados pelo compilador TypeScript.

Como funciona

libsearch permite realizar pesquisas básicas de texto completo em uma lista de objetos JavaScript rapidamente, sem exigir um índice de pesquisa pré-construído, ao mesmo tempo que oferece uma classificação de resultados TF-IDF razoavelmente boa. Ele não oferece a ampla variedade de recursos que vêm com bibliotecas como FlexSearch e lunr.js, mas está um grande passo acima de text.indexOf(query) > -1 e é rápido o suficiente para ser usado na pesquisa de milhares de documentos em cada pressionamento de tecla em minha experiência.

Existem duas ideias principais sobre como o libsearch oferece isso:

1. Transformando consultas em expressões regulares

Mecanismos JavaScript modernos vêm com mecanismos de expressão regular altamente otimizados, e libsearch aproveita isso para pesquisa de texto rápida e sem índice, transformando strings de consulta em filtros de expressão regular no momento da pesquisa.

A maioria das bibliotecas de pesquisa de texto completo funcionam primeiro exigindo que o desenvolvedor construa uma estrutura de dados de "índice" mapeando os termos de pesquisa para os documentos nos quais eles aparecem. Isso geralmente é uma boa compensação, porque faz com que parte do trabalho computacional de "pesquisa" seja feito com antecedência, de modo que a pesquisa em si possa permanecer rápida e precisa. Ele também permite transformações sofisticadas e limpeza de dados, como lematização nos dados indexados, sem destruir a velocidade de pesquisa. Mas ao construir protótipos e aplicativos web simples, muitas vezes eu não queria incorrer na complexidade de ter uma etapa de "indexação" separada para obter uma solução de pesquisa "boa o suficiente". Um índice precisa ser armazenado em algum lugar e mantido constantemente à medida que o conjunto de dados subjacente muda e cresce.

A principal tarefa de um índice de pesquisa é mapear “tokens” ou palavras-chave que aparecem no conjunto de dados para os documentos em que aparecem, de modo que a pergunta “quais documentos contêm a palavra X?” é rápido ( O(1) ) para responder no momento da pesquisa. Sem um índice, isso se transforma em uma questão O(n) , pois cada documento precisa ser digitalizado em busca da palavra-chave. Mas muitas vezes, em hardware moderno, para conjuntos de dados pequenos o suficiente (de alguns MBs) típicos de um aplicativo Web do lado do cliente, n é muito pequeno, pequeno o suficiente para que O(n) em cada pressionamento de tecla não seja perceptível.

libsearch transforma uma consulta como "Uni of California" em uma lista de filtros de expressões regulares, (^|W)Uni($|W) , (^|W)of($|W) , (^|W)California . Em seguida, ele "pesquisa" sem precisar de um índice, filtrando o corpus por meio de cada uma dessas expressões regulares.

2. Classificação TF-IDF "boa o suficiente" com base em correspondências RegExp e comprimento do documento

A métrica TF-IDF convencional é calculada para cada palavra como:

 ( # matches ) / ( # words in the doc ) * log ( # total docs / # docs that matched )

Obter o número de palavras em um documento requer a tokenização do documento ou, pelo menos, a divisão do documento por espaços em branco, o que é computacionalmente caro. Portanto, libsearch aproxima isso usando o comprimento do documento (número de caracteres).

Usando as consultas de expressão regular descritas acima, a fórmula TF-IDF da libsearch é:

 ( # RegExp matches ) / ( doc . length ) * log ( # docs / # docs that matched RegExp )

que é calculado para cada palavra à medida que a pesquisa é realizada e, em seguida, agregado no final para classificação.

Desenvolvimento

O código-fonte do libsearch é escrito em TypeScript. Para permitir que a biblioteca seja usada em TypeScript, vanilla Node.js e na web, compilamos duas compilações:

• O módulo ES build , que é apenas o tipo search.ts verificado e os tipos removidos. Este é o código importado quando libsearch é importado em Node.js
• A construção do navegador , que exporta a função search principal para o window.libsearch global

A construção do módulo ES é produzida com tsc , o compilador TypeScript, e a construção minificada do navegador é produzida posteriormente com Webpack.

Comandos NPM/Yarn:

• lint e fmt , que lint e formatam automaticamente o código-fonte no repositório
• test executa testes de unidade na versão mais recente da biblioteca; você deve executar build:tsc antes de executar test
• Vários comandos build:* orquestram a produção de diferentes tipos de construções de biblioteca:
  • build:tsc constrói o módulo ES build
  • build:w executa build:tsc em cada gravação de arquivo
  • build:cjs constrói a construção do navegador a partir do módulo ES build
  • build:all compila ambas as compilações, em ordem
• clean remove todos os arquivos gerados/construídos em dist/
• docs cria a documentação baseada no Litterate, que fica em thesephist.github.io/libsearch.

Antes de enviar para principal ou publicação, geralmente executo

yarn fmt && yarn build:all && yarn test && yarn docs

para ter certeza de que não esqueci nada.