libsearch

libbúsqueda?

Búsqueda de texto simple y sin índice para JavaScript, utilizada en mis proyectos personales como YC Vibe Check, linus.zone/entr y mi software de productividad personal. Lea la fuente comentada para comprender cómo funciona bajo el capó.

La API

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

Más formalmente, libsearch expone una única API, la función search . Esta función toma dos argumentos obligatorios y dos argumentos opcionales:

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

• items es una lista de elementos para buscar. Normalmente, items serán una matriz de cadenas o una matriz de objetos con alguna propiedad de cadena.
• query es una consulta de cadena con la que buscar en la lista de elementos.
• by ( opcional ) es una función de predicado que toma un elemento de items y devuelve un valor de cadena por el cual buscar ese elemento. Por ejemplo, si items es una lista de objetos como { name: 'Linus' } , by deberá ser una función x => x.name . Esto tiene el valor x => String(x) de forma predeterminada, que funciona para items de tipo string[] .
• options ( opcional ) es un diccionario de opciones:
  • caseSensitive hace que una búsqueda distinga entre mayúsculas y minúsculas. Es false por defecto.
  • mode controla la forma en que coinciden las palabras de consulta incompletas:
    • mode: 'word' requiere que cada palabra de consulta coincida solo con palabras completas y exactas en lugar de partes de palabras. Por ejemplo, la consulta "California" coincidirá con "Universidad de California ", pero no con "Universidad de California ".
    • mode: 'prefix' significa que cada palabra de consulta puede ser un "prefijo" incompleto de la palabra coincidente. "Uni Cali" coincidirá con " Universidad de California " y " Universidad de California ". Incluso en este modo, cada palabra de consulta debe coincidir en alguna parte: " California " no coincide porque no coincide con la consulta. palabra "Uni".
    • mode: 'autocomplete' es un híbrido de los otros dos modos que es útil cuando se usa en búsquedas de estilo autocompletar, donde un usuario escribe continuamente una consulta a medida que se devuelven los resultados de la búsqueda. Este modo es idéntico al mode: 'word' , excepto que la última palabra de consulta puede estar incompleta como en mode: 'prefix' . Significa que "Universidad de Cali" coincidirá con " Universidad de Cali fornia", lo cual es útil porque el usuario puede encontrar su coincidencia antes de haber escrito su consulta completa.

Puede encontrar más ejemplos de cómo se combinan estas opciones en las pruebas unitarias.

Instalación y uso

En la web, con <script>

Coloca esto en tu HTML:

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

Esto expondrá la función search como window.libsearch.search .

Vía NPM

npm install libsearch
# or
yarn add libsearch

Y usa en tu código:

 import { search } from 'libsearch' ;

// search(...);

Usando tipos de TypeScript

libsearch se entrega con definiciones de tipo TypeScript generadas a partir del archivo fuente. El uso de libsearch de NPM debería hacer que el compilador de TypeScript los recoja.

como funciona

libsearch le permite realizar búsquedas básicas de texto completo en una lista de objetos JavaScript rápidamente, sin necesidad de un índice de búsqueda prediseñado, al tiempo que ofrece una clasificación de resultados TF-IDF razonablemente buena. No ofrece la amplia gama de funciones que vienen con bibliotecas como FlexSearch y lunr.js, pero es un gran paso por encima de text.indexOf(query) > -1 y es lo suficientemente rápido como para poder usarlo para buscar miles de documentos en cada pulsación de tecla en mi experiencia.

Hay dos ideas clave sobre cómo libsearch ofrece esto:

1. Transformar consultas en expresiones regulares.

Los motores JavaScript modernos incluyen motores de expresiones regulares altamente optimizados, y libsearch aprovecha esto para una búsqueda de texto rápida y sin índice al transformar cadenas de consulta en filtros de expresiones regulares en el momento de la búsqueda.

La mayoría de las bibliotecas de búsqueda de texto completo funcionan exigiendo primero al desarrollador que cree una estructura de datos de "índice" que asigne los términos de búsqueda a los documentos en los que aparecen. Esto suele ser una buena compensación, porque hace que parte del trabajo computacional de la "búsqueda" se realice con anticipación, de modo que la búsqueda en sí pueda seguir siendo rápida y precisa. También permite transformaciones sofisticadas y limpieza de datos, como la lematización de los datos indexados, sin destruir la velocidad de búsqueda. Pero al crear prototipos y aplicaciones web simples, a menudo no quería incurrir en la complejidad de tener un paso de "indexación" separado para obtener una solución de búsqueda "suficientemente buena". Un índice debe almacenarse en algún lugar y mantenerse constantemente a medida que el conjunto de datos subyacente cambia y crece.

La tarea principal de un índice de búsqueda es mapear "tokens" o palabras clave que aparecen en el conjunto de datos con los documentos en los que aparecen, de modo que la pregunta "¿qué documentos contienen la palabra X?" es rápido ( O(1) ) para responder en el momento de la búsqueda. Sin un índice, esto se convierte en una pregunta O(n) , ya que cada documento debe escanearse en busca de la palabra clave. Pero a menudo, en el hardware moderno, para conjuntos de datos suficientemente pequeños (de unos pocos MB) típicos de una aplicación web del lado del cliente, n es bastante pequeña, lo suficientemente pequeña como para que O(n) en cada pulsación de tecla no se note.

libsearch transforma una consulta como "Uni de California" en una lista de filtros de expresiones regulares, (^|W)Uni($|W) , (^|W)of($|W) , (^|W)California . Luego "busca" sin necesidad de un índice filtrando el corpus a través de cada una de esas expresiones regulares.

2. Clasificación TF-IDF "suficientemente buena" basada en coincidencias de RegExp y longitud del documento

La métrica TF-IDF convencional se calcula para cada palabra como:

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

Obtener la cantidad de palabras en un documento requiere tokenizar el documento, o al menos dividir el documento por espacios en blanco, lo cual es computacionalmente costoso. Entonces libsearch aproxima esto usando la longitud del documento (número de caracteres).

Utilizando las consultas de expresiones regulares descritas anteriormente, la fórmula TF-IDF de libsearch es:

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

que se calcula para cada palabra a medida que se realiza la búsqueda y luego se agrega al final para clasificarla.

Desarrollo

El código fuente de libsearch está escrito en TypeScript. Para permitir que la biblioteca se utilice en TypeScript, Vanilla Node.js y la web, compilamos dos compilaciones:

• La compilación del módulo ES , que simplemente se verifica con los tipos search.ts y se eliminan los tipos. Este es el código importado cuando se importa libsearch en Node.js
• La compilación del navegador , que exporta la función search principal al window.libsearch global

La compilación del módulo ES se produce con tsc , el compilador TypeScript, y la compilación del navegador minimizada se produce con Webpack.

Comandos NPM/Hilo:

• lint y fmt , que lint y formatean automáticamente el código fuente en el repositorio
• test ejecuta pruebas unitarias en la última versión de la biblioteca; debes ejecutar build:tsc antes de ejecutar test
• Varios comandos build:* orquestan la producción de los diferentes tipos de compilaciones de biblioteca:
  • build:tsc construye la compilación del módulo ES
  • build:w ejecuta build:tsc en cada escritura de archivo
  • build:cjs construye la compilación del navegador a partir de la compilación del módulo ES
  • build:all construye ambas compilaciones, en orden
• clean elimina todos los archivos generados/compilados en dist/
• docs crea la documentación basada en Litterate, que se encuentra en Thesephist.github.io/libsearch.

Antes de pasar a principal o publicar, normalmente ejecuto

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

para asegurarme de que no se me ha olvidado nada.