libsearch

libsearch ?

Recherche de texte simple et sans index pour JavaScript, utilisée dans mes projets personnels comme YC Vibe Check, linus.zone/entr et mon logiciel de productivité personnelle. Lisez la source annotée pour comprendre comment cela fonctionne sous le capot.

L'API

Commençons par quelques exemples rapides :

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

Plus formellement, libsearch expose une seule API, la fonction search . Cette fonction prend deux arguments obligatoires et deux arguments facultatifs :

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

• items est une liste d’éléments à rechercher. Généralement, items seront un tableau de chaînes ou un tableau d'objets avec une propriété de chaîne.
• query est une requête de chaîne avec laquelle rechercher la liste des éléments.
• by ( facultatif ) est une fonction de prédicat qui prend un élément parmi items et renvoie une valeur de chaîne par laquelle rechercher cet élément. Par exemple, si items est une liste d'objets comme { name: 'Linus' } , by devra être une fonction x => x.name . Cela a la valeur x => String(x) par défaut, qui fonctionne pour un items de type string[] .
• options ( optionnel ) est un dictionnaire d'options :
  • caseSensitive rend une recherche sensible à la casse. C'est false par défaut.
  • mode contrôle la manière dont les mots de requête incomplets sont mis en correspondance :
    • mode: 'word' exige que chaque mot de requête corresponde uniquement à des mots complets et exacts plutôt qu'à des parties de mots. Par exemple, la requête « Californie » correspondra à « Université de Californie » mais pas à « California n University ».
    • mode: 'prefix' signifie que chaque mot de requête peut être un « préfixe » incomplet du mot correspondant. "Uni Cali" correspondra à la fois à " University of Cali fornia" et " Cali fornian University ". Même dans ce mode, chaque mot de requête doit correspondre quelque part - " Cali fornia" n'est pas une correspondance, car il ne correspond pas à la requête. mot "Uni".
    • mode: 'autocomplete' est un hybride des deux autres modes qui est utile lorsqu'il est utilisé dans des recherches de style autocomplete, où un utilisateur tape continuellement une requête au fur et à mesure que les résultats de la recherche sont renvoyés. Ce mode est identique au mode: 'word' , sauf que le dernier mot recherché peut être incomplet comme en mode: 'prefix' . Cela signifie que "University of Cali" correspondra à " University of Cali fornia", ce qui est utile car l'utilisateur peut trouver sa correspondance avant d'avoir tapé sa requête complète.

Vous pouvez trouver d’autres exemples de la façon dont ces options se combinent dans les tests unitaires.

Installation et utilisation

Sur le Web, avec <script>

Déposez ceci dans votre HTML :

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

Cela exposera la fonction search sous le nom window.libsearch.search .

Via le MNP

npm install libsearch
# or
yarn add libsearch

Et utilisez dans votre code :

 import { search } from 'libsearch' ;

// search(...);

Utiliser des types TypeScript

libsearch est livré avec les définitions de type TypeScript générées à partir du fichier source. L'utilisation de libsearch à partir de NPM devrait les récupérer par le compilateur TypeScript.

Comment ça marche

libsearch vous permet d'effectuer rapidement une recherche de base en texte intégral sur une liste d'objets JavaScript, sans nécessiter un index de recherche prédéfini, tout en offrant un classement TF-IDF raisonnablement bon des résultats. Il n'offre pas le large éventail de fonctionnalités fournies avec les bibliothèques telles que FlexSearch et lunr.js, mais constitue un grand pas en avant text.indexOf(query) > -1 , et est suffisamment rapide pour être utilisable pour rechercher des milliers de documents sur chaque frappe de touche dans mon expérience.

Il y a deux idées clés dans la manière dont libsearch propose cela :

1. Transformer les requêtes en expressions régulières

Les moteurs JavaScript modernes sont livrés avec des moteurs d'expressions régulières hautement optimisés, et libsearch en profite pour une recherche de texte rapide et sans index en transformant les chaînes de requête en filtres d'expressions régulières au moment de la recherche.

La plupart des bibliothèques de recherche en texte intégral fonctionnent en exigeant d'abord du développeur qu'il construise une structure de données « d'index » mappant les termes de recherche aux documents dans lesquels ils apparaissent. Il s'agit généralement d'un bon compromis, car cela déplace une partie du travail informatique de « recherche » à effectuer à l'avance, de sorte que la recherche elle-même peut rester rapide et précise. Il permet également des transformations sophistiquées et un nettoyage des données comme la lemmatisation sur les données indexées sans détruire la vitesse de recherche. Mais lors de la création de prototypes et d'applications Web simples, je ne voulais souvent pas encourir la complexité d'avoir une étape « d'indexation » distincte pour obtenir une solution de recherche « assez bonne ». Un index doit être stocké quelque part et maintenu en permanence à mesure que l'ensemble de données sous-jacent change et grandit.

La tâche principale d'un index de recherche consiste à mapper les « jetons » ou mots-clés qui apparaissent dans l'ensemble de données avec les documents dans lesquels ils apparaissent, de sorte que la question « quels documents contiennent le mot X ? est rapide ( O(1) ) pour répondre au moment de la recherche. Sans index, cela se transforme en une question O(n) , car chaque document doit être numérisé à la recherche du mot-clé. Mais souvent, sur le matériel moderne, pour des ensembles de données suffisamment petits (de quelques Mo) typiques d'une application Web côté client, le n est assez petit, suffisamment petit pour que O(n) à chaque frappe ne soit pas perceptible.

libsearch transforme une requête comme "Uni of California" en une liste de filtres d'expressions régulières, (^|W)Uni($|W) , (^|W)of($|W) , (^|W)California . Il « recherche » ensuite sans avoir besoin d'index en filtrant le corpus à travers chacune de ces expressions régulières.

2. Classement TF-IDF « Assez bon » basé sur les correspondances RegExp et la longueur du document

La métrique TF-IDF conventionnelle est calculée pour chaque mot comme suit :

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

Obtenir le nombre de mots dans un document nécessite de tokeniser le document, ou au moins de diviser le document par espaces, ce qui est coûteux en termes de calcul. Donc libsearch se rapproche de cela en utilisant plutôt la longueur du document (nombre de caractères).

En utilisant les requêtes d'expression régulière décrites ci-dessus, la formule TF-IDF de libsearch est :

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

qui est calculé pour chaque mot au fur et à mesure de la recherche, puis agrégé à la fin pour le tri.

Développement

Le code source de libsearch est écrit en TypeScript. Pour permettre à la bibliothèque d'être utilisée sur TypeScript, Vanilla Node.js et le Web, nous compilons deux versions :

• La construction du module ES , qui est simplement vérifiée par le type search.ts et les types supprimés. C'est le code importé lorsque libsearch est importé dans Node.js
• La version du navigateur , qui exporte la fonction search principale vers le fichier global window.libsearch

La version du module ES est produite avec tsc , le compilateur TypeScript, et la version minifiée du navigateur est ensuite produite avec Webpack.

Commandes NPM/Yarn :

• lint et fmt , qui lintent et formatent automatiquement le code source dans le référentiel
• test exécute des tests unitaires sur la dernière version de la bibliothèque ; vous devriez exécuter build:tsc avant d'exécuter test
• Diverses commandes build:* orchestrent la production des différents types de builds de bibliothèque :
  • build:tsc construit la construction du module ES
  • build:w exécute build:tsc à chaque écriture de fichier
  • build:cjs construit la version du navigateur à partir de la version du module ES
  • build:all construit les deux builds, dans l'ordre
• clean supprime tous les fichiers générés/construits dans dist/
• docs construit la documentation basée sur Litterate, qui se trouve sur Thesephist.github.io/libsearch.

Avant de passer au principal ou à la publication, je lance généralement

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

pour m'assurer que je n'ai rien oublié.