libsearch

libsearch ?

Einfache, indexfreie Textsuche für JavaScript, die ich in meinen persönlichen Projekten wie YC Vibe Check, linus.zone/entr und meiner persönlichen Produktivitätssoftware verwende. Lesen Sie die kommentierte Quelle, um zu verstehen, wie es unter der Haube funktioniert.

Die API

Beginnen wir mit einigen kurzen Beispielen:

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

Formeller ausgedrückt stellt libsearch eine einzige API zur Verfügung, die search . Diese Funktion benötigt zwei erforderliche Argumente und zwei optionale Argumente:

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

• items ist eine Liste der zu durchsuchenden Elemente. Typischerweise handelt es sich items um ein Array von Zeichenfolgen oder ein Array von Objekten mit einer Zeichenfolgeneigenschaft.
• query ist eine Zeichenfolgenabfrage, mit der die Liste der Elemente durchsucht werden soll.
• by ( optional ) ist eine Prädikatfunktion, die ein Element aus items übernimmt und einen Zeichenfolgenwert zurückgibt, anhand dessen nach diesem Element gesucht werden soll. Wenn es sich beispielsweise items um eine Liste von Objekten wie { name: 'Linus' } handelt, muss by eine Funktion x => x.name sein. Dies hat standardmäßig den Wert x => String(x) , was für items vom Typ string[] funktioniert.
• options ( optional ) ist ein Wörterbuch von Optionen:
  • caseSensitive macht eine Suche unter Berücksichtigung der Groß- und Kleinschreibung. Es ist standardmäßig false .
  • mode steuert die Art und Weise, wie unvollständige Abfragewörter abgeglichen werden:
    • mode: 'word' erfordert, dass jedes Abfragewort nur mit vollständigen, genauen Wörtern und nicht mit Wortteilen übereinstimmt. Beispielsweise wird die Suchanfrage „Kalifornien“ mit „University of California “ übereinstimmen, aber nicht mit „ California n University“.
    • mode: 'prefix' bedeutet, dass jedes Abfragewort ein unvollständiges „Präfix“ des übereinstimmenden Worts sein kann. „Uni Cali“ stimmt sowohl mit „ Uni versity of California “ als auch mit „ Cali fornian University “ überein. Auch in diesem Modus muss jedes Abfragewort irgendwo übereinstimmen – „ California “ ist keine Übereinstimmung, da es nicht mit der Abfrage übereinstimmt Wort „Uni“.
    • mode: 'autocomplete' ist eine Mischung aus den beiden anderen Modi, die nützlich ist, wenn sie bei Suchen im Autocomplete-Stil verwendet wird, bei denen ein Benutzer kontinuierlich eine Abfrage eingibt, während Suchergebnisse zurückgegeben werden. Dieser Modus ist identisch mit mode: 'word' , mit der Ausnahme, dass das letzte Abfragewort möglicherweise unvollständig ist, wie im mode: 'prefix' . Dies bedeutet, dass „University of Cali“ mit „ University of California “ übereinstimmt, was nützlich ist, da der Benutzer die Übereinstimmung möglicherweise findet, bevor er seine vollständige Suchanfrage eingegeben hat.

Weitere Beispiele für die Kombination dieser Optionen finden Sie in den Unit-Tests.

Installation und Nutzung

Im Web mit <script>

Fügen Sie dies in Ihren HTML-Code ein:

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

Dadurch wird die search als window.libsearch.search verfügbar gemacht.

Über NPM

npm install libsearch
# or
yarn add libsearch

Und verwenden Sie in Ihrem Code:

 import { search } from 'libsearch' ;

// search(...);

Verwendung von TypeScript-Typen

libsearch wird mit TypeScript-Typdefinitionen geliefert, die aus der Quelldatei generiert werden. Durch die Verwendung von libsearch aus NPM sollten sie vom TypeScript-Compiler erfasst werden.

Wie es funktioniert

Mit libsearch können Sie schnell eine einfache Volltextsuche in einer Liste von JavaScript-Objekten durchführen, ohne dass ein vorgefertigter Suchindex erforderlich ist, und bieten gleichzeitig ein einigermaßen gutes TF-IDF-Ranking der Ergebnisse. Es bietet nicht die breite Palette an Funktionen, die Bibliotheken wie FlexSearch und lunr.js bieten, liegt aber einen großen Schritt über text.indexOf(query) > -1 und ist schnell genug, um für die Suche in Tausenden von Dokumenten verwendet werden zu können Jeder Tastendruck meiner Erfahrung nach.

Es gibt zwei Schlüsselideen, wie libsearch dies liefert:

1. Abfragen in reguläre Ausdrücke umwandeln

Moderne JavaScript-Engines werden mit hochoptimierten Engines für reguläre Ausdrücke ausgeliefert, und libsearch nutzt dies für eine schnelle, indexfreie Textsuche, indem es Abfragezeichenfolgen zum Suchzeitpunkt in Filter für reguläre Ausdrücke umwandelt.

Bei den meisten Volltextsuchbibliotheken muss der Entwickler zunächst eine „Index“-Datenstruktur erstellen, die Suchbegriffe den Dokumenten zuordnet, in denen sie vorkommen. Dies ist in der Regel ein guter Kompromiss, da dadurch ein Teil der Rechenarbeit der „Suche“ vorgezogen wird, sodass die Suche selbst schnell und genau bleiben kann. Es ermöglicht auch ausgefallene Transformationen und Datenbereinigungen wie Lemmatisierung der indizierten Daten, ohne die Suchgeschwindigkeit zu beeinträchtigen. Beim Erstellen von Prototypen und einfachen Web-Apps wollte ich jedoch oft nicht die Komplexität eines separaten „Indizierungsschritts“ auf mich nehmen, um eine „ausreichend gute“ Suchlösung zu erhalten. Ein Index muss irgendwo gespeichert und ständig gepflegt werden, wenn sich der zugrunde liegende Datensatz ändert und wächst.

Die Hauptaufgabe eines Suchindex besteht darin, „Tokens“ oder Schlüsselwörter, die im Datensatz vorkommen, den Dokumenten zuzuordnen, in denen sie vorkommen, sodass die Frage „Welche Dokumente enthalten das Wort X?“ beantwortet werden können. ist zur Suchzeit schnell zu beantworten ( O(1) ). Ohne Index wird dies zu einer O(n) -Frage, da jedes Dokument nach dem Schlüsselwort durchsucht werden muss. Aber auf moderner Hardware ist das n bei ausreichend kleinen Datensätzen (von einigen MB), wie sie für eine clientseitige Web-App typisch sind, oft ziemlich klein, klein genug, dass O(n) bei jedem Tastendruck nicht wahrnehmbar ist.

libsearch wandelt eine Abfrage wie „Uni of California“ in eine Liste regulärer Ausdrucksfilter um, (^|W)Uni($|W) , (^|W)of($|W) , (^|W)California . Anschließend „sucht“ es, ohne dass ein Index erforderlich ist, indem es den Korpus nach jedem dieser regulären Ausdrücke filtert.

2. „Gut genug“ TF-IDF-Rangliste basierend auf RegExp-Übereinstimmungen und Dokumentlänge

Die herkömmliche TF-IDF-Metrik wird für jedes Wort wie folgt berechnet:

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

Um die Anzahl der Wörter in einem Dokument zu ermitteln, ist eine Tokenisierung des Dokuments oder zumindest eine Aufteilung des Dokuments durch Leerzeichen erforderlich, was rechenintensiv ist. Daher nähert sich libsearch diesem Wert an, indem es stattdessen die Länge des Dokuments (Anzahl der Zeichen) verwendet.

Unter Verwendung der oben beschriebenen Abfragen mit regulären Ausdrücken lautet die TF-IDF-Formel von libsearch:

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

Dieser wird während der Suche für jedes Wort berechnet und am Ende zur Sortierung aggregiert.

Entwicklung

Der Quellcode von libsearch ist in TypeScript geschrieben. Damit die Bibliothek in TypeScript, Vanilla Node.js und im Web verwendet werden kann, kompilieren wir zwei Builds:

• Der ES-Modul-Build , der nur durch search.ts typgeprüft und Typen entfernt wird. Dies ist der Code, der importiert wird, wenn libsearch in Node.js importiert wird
• Der Browser-Build , der die search in die globale window.libsearch exportiert

Der ES-Modul-Build wird mit tsc , dem TypeScript-Compiler, erstellt, und der minimierte Browser-Build wird weiter mit Webpack erstellt.

NPM/Yarn-Befehle:

• lint und fmt , die den Quellcode im Repository linten und automatisch formatieren
• test führt Unit-Tests für den neuesten Build der Bibliothek durch; Sie sollten build:tsc ausführen, bevor Sie test ausführen
• Verschiedene build:* -Befehle orchestrieren die Erstellung der verschiedenen Arten von Bibliotheks-Builds:
  • build:tsc erstellt den ES-Modul-Build
  • build:w führt build:tsc bei jedem Dateischreibvorgang aus
  • build:cjs erstellt den Browser-Build aus dem ES-Modul-Build
  • build:all erstellt beide Builds der Reihe nach
• clean entfernt alle generierten/Build-Dateien in dist/
• docs erstellt die Litterate-basierte Dokumentation, die sich unter Thesephist.github.io/libsearch befindet.

Bevor ich zum Hauptmenü oder zur Veröffentlichung gehe, führe ich normalerweise Folgendes aus

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

um sicherzustellen, dass ich nichts vergessen habe.