Ich suche eine JavaScript-Bibliothek für die Fuzzy-Suche, um ein Array zu filtern. Ich habe versucht mitfuzzyset.js undfuse.js, aber die Ergebnisse sind schrecklich (es gibt Demos, die Sie auf den verlinkten Seiten ausprobieren können).

Nachdem ich etwas über die Levenshtein-Distanz gelesen habe, erscheint es mir als eine schlechte Annäherung an das, wonach Benutzer suchen, wenn sie tippen. Für diejenigen, die nicht wissen, berechnet das System, wie vieleEinfügungen, Streichungen, undAuswechslungen werden benötigt, um zwei Saiten zusammenzubringen.

Ein offensichtlicher Fehler, der im Levenshtein-Demerau-Modell behoben ist, ist, dass beideblub undboob gelten als gleich ähnlich zuBirne (jeweils zwei Substitutionen erforderlich). Es ist jedoch klar, dassBirne ist ähnlicher zublub alsboob ist, und das Modell, das ich gerade erwähnt habe, erkennt dies, indem es berücksichtigtTranspositionen.

Ich möchte dies im Kontext der Textvervollständigung verwenden, wenn ich also ein Array habe['international', 'splint', 'tinder']und meine Frage istint, Ich denkeInternational sollte höher rangieren alsSchiene, obwohl der erstere eine Punktzahl (höher = schlechter) von 10 gegenüber der 3 des letzteren hat.

Also, was ich suche (und erstellen werde, wenn es nicht existiert), ist eine Bibliothek, die Folgendes tut:

Gewichtet die verschiedenen TextmanipulationenGewichtet jede Manipulation unterschiedlich, je nachdem, wo sie in einem Wort vorkommt (frühe Manipulationen sind teurer als späte Manipulationen)Gibt eine nach Relevanz sortierte Ergebnisliste zurück

Ist jemand auf so etwas gestoßen? Mir ist klar, dass StackOverflow nicht der richtige Ort ist, um nach Softwareempfehlungen zu fragen, aber implizit (nicht mehr!) Lautet das oben Gesagte: Denke ich darüber richtig nach?

Bearbeiten

Ich habe einen ... gefundengutes Papier (pdf) zum Thema. Einige Notizen und Auszüge:

Affine Editierentfernungsfunktionen weisen einer Sequenz von Einfügungen oder Löschungen einen relativ geringeren Aufwand zu

die Monger-Elkan-Distanzfunktion (Monge & Elkan 1996), eine affine Variante der Smith-Waterman-Distanzfunktion (Durban et al. 1998) mit bestimmten Kostenparametern

Für dieSmith-Waterman Entfernung (Wikipedia)"Anstatt die Gesamtsequenz zu betrachten, vergleicht der Smith-Waterman-Algorithmus Segmente aller möglichen Längen und optimiert das Ähnlichkeitsmaß." Es ist der n-Gramm-Ansatz.

Eine weitgehend ähnliche Metrik, die nicht auf einem Edit-Distance-Modell basiert, ist die Jaro-Metrik (Jaro 1995; 1989; Winkler 1999). In der Literatur zu Datensatzverknüpfungen wurden mit Varianten dieser Methode, die auf der Anzahl und Reihenfolge der gemeinsamen Zeichen zwischen zwei Zeichenfolgen basiert, gute Ergebnisse erzielt.

Eine Variante davon nach Winkler (1999) verwendet ebenfalls die Länge P des längsten gemeinsamen Präfixes

(scheinen vor allem für kurze Streicher gedacht zu sein)

Aus Gründen der Textvervollständigung scheinen die Ansätze von Monger-Elkan und Jaro-Winkler am sinnvollsten zu sein. Winklers Hinzufügung zur Jaro-Metrik hebt die Wortanfänge wirkungsvoller hervor. Und der affine Aspekt von Monger-Elkan bedeutet, dass die Notwendigkeit, ein Wort zu vervollständigen (was einfach eine Folge von Hinzufügungen ist), es nicht zu stark beeinträchtigt.

Fazit:

Das TFIDF-Ranking schnitt unter mehreren tokenbasierten Abstandsmetriken am besten ab, und eine von Monge und Elkan vorgeschlagene optimierte Abstandsmetrik für die Bearbeitung der affinen Lücke schnitt unter mehreren Abstandsmetriken für die Bearbeitung von Zeichenfolgen am besten ab. Eine überraschend gute Distanzmetrik ist ein schnelles heuristisches Schema, das von Jaro vorgeschlagen und später von Winkler erweitert wurde. Dies funktioniert fast genauso gut wie das Monge-Elkan-Schema, ist jedoch um eine Größenordnung schneller. Eine einfache Möglichkeit, die TFIDF-Methode und den Jaro-Winkler zu kombinieren, besteht darin, die genauen Token-Übereinstimmungen, die in TFIDF verwendet werden, durch ungefähre Token-Übereinstimmungen zu ersetzen, die auf dem Jaro-Winkler-Schema basieren. Diese Kombination schneidet im Durchschnitt etwas besser ab als Jaro-Winkler oder TFIDF und schneidet gelegentlich deutlich besser ab. Die Leistung kommt einer erlernten Kombination mehrerer der besten Metriken, die in diesem Artikel berücksichtigt werden, sehr nahe.