Wie man Fuzzy-Suchen in Elasticsearch verwendet

Einführung Die Suche in

natürlicher Sprache ist von Natur aus ungenau. Da Computer natürliche Sprache nicht verstehen können, gibt es eine Vielzahl von Suchansätzen, jede mit ihren eigenen Vor- und Nachteilen. Lucene, die Technologie, die Elasticsearch zugrunde liegt, ist ein Schweizer Taschenmesser, das aus vielen Textverarbeitungswerkzeugen besteht. Jedes darin enthaltene Tool ist eine Heuristik, eine algorithmische Abkürzung anstelle von echtem Sprachverständnis. Einige dieser Tools, wie der Snowball Stemmer und der Metaphone Phonetic Analyzer, sind ziemlich ausgefeilt. Diese Tools ahmen grammatikalische bzw. phonetische Aspekte des Sprachverständnisses nach. Andere Tools sind sehr einfach, wie der Präfix-Abfragetyp, der einfach den Anfangsbuchstaben von Wörtern entspricht. Fuzzy-Abfragen liegen in Bezug auf Raffinesse irgendwo in der Mitte dieser Toolbox. Sie finden Wörter, die höchstens eine bestimmte Anzahl von Zeichenänderungen benötigen, bekannt als „Änderungen“, um der Abfrage zu entsprechen. Zum Beispiel würde eine unscharfe Suche nach 'Axt' dem Wort 'Axt' entsprechen, da nur ein einziges Löschen, das Entfernen des 'e', erforderlich ist, um die beiden Wörter zu finden

Eine einfache Fuzzy-Match-Fuzzy-Abfrage

kann am einfachsten durch zusätzliche Argumente zum Match-Abfragetyp ausgeführt werden, wie im Beispiel unter diesem Absatz zu sehen ist. Im Beispiel sollte die letzte Anfrage, eine Suche nach „Vakuum“, die ein zusätzliches A hat, trotzdem das Produkt „Vakuum“ ergeben. Das Unschärfe-Argument gibt an, dass die Ergebnisse mit einem maximalen Bearbeitungsabstand von 2 übereinstimmen. Es sollte beachtet werden, dass Unschärfe nur mit Werten von 1 und 2 verwendet werden sollte, was bedeutet, dass maximal 2 Änderungen zwischen der Abfrage und einem Begriff in einem Dokument zulässig sind. Größere Unterschiede sind viel teurer, effizient zu berechnen, und sie werden von Lucene nicht verarbeitet. Die offizielle Dokumentation bezieht sich immer noch darauf, Unschärfe auf Float-Werte wie 0,5 zu setzen, aber diese Werte sind in der Tat veraltet und es ist schwieriger, darüber nachzudenken

# Erstellen Sie den Index 
 PUT /fuzzy_products 
 # Erstellen Sie das Produktmapping 
 PUT /fuzzy_products/product/_mapping 
 {
" product ": {
" properties ": {
" name ": {
        "type": "string",
        "analyzer": "simple"
      }
}}} # Laden Sie einige Dokumente hoch PUT /fuzzy_products/product/1 
 
 
 
 
 {"name": "Vacuum Cleaner"} 
 PUT /fuzzy_products/product/2 
 {"name": "Turkey Baster"} # Führen Sie eine Fuzzy-Suche durch! 
 

POST /fuzzy_products/product/_search
{
" query ": {
" match ": {
" name ": {
"query": "Vacuummm",
"fuzziness": 2,
"prefix_length": 1
}
}}

} Entfernung ermitteln Die von

Fuzzy-Abfragen zur Bestimmung einer Übereinstimmung sind die Damerau-Levenshtein-Distanzformel. Einfach ausgedrückt, der Damerau-Levenshtein-Abstand zwischen zwei Textstücken ist die Anzahl der Einfügungen, Löschungen, Ersetzungen und Transpositionen, die erforderlich sind, damit eine Zeichenfolge mit der anderen übereinstimmt. Als Beispiel ist der Levenshtein-Abstand zwischen den Wörtern „Axt“ und „Axt“ 1, da eine einzige Löschung erforderlich ist

Die Damerau-Levenshtein-Distanzformel ist eine Modifikation der klassischen Levenshtein-Distanzformel, die geändert wird, indem die Transposition als gültige Operation hinzugefügt wird. Beide Formeln werden unterstützt, wobei Damerau-Levenshtein die Standardeinstellung ist und klassisches Levenshtein ausgewählt werden kann, indem Transpositionen in der Abfrage auf falsch gesetzt werden. Der Nutzen von Transpositionen zeigt sich im Vergleich der Zeichenketten 'aex' und 'axe'. Wenn Sie die klassische Levenshtein-Distanzformel verwenden, ist 'aex' nicht eine, sondern zwei Bearbeitungen entfernt; das 'e' muss gelöscht werden, danach wird ein neues 'e' an der richtigen Stelle eingefügt, während in Damerau-Levenshtein ein einziger Vorgang, das 'e' und das 'x' vertauscht, genügt. Davon ausgehend würde die Verwendung des klassischen Levenshtein bedeuten, dass „Aex“ genauso weit von „Axe“ entfernt ist wie „Faxe“; ein Beispiel, das zeigt, warum Damerau-Levenshtein in den meisten Fällen intuitiver ist

Insbesondere beim Umgang mit Fuzzy-Suchen ist es wichtig zu verstehen, dass Text in Elasticsearch zuerst einen Analyzer durchläuft, bevor er für die Suche verfügbar gemacht wird. Wenn Daten indexiert werden, werden sie zu sogenannten „Begriffen“ verarbeitet, den tatsächlich durchsuchbaren Einheiten in der Datenbank. Es werden die analysierten Begriffe durchsucht (welche Begriffe sind in Elasticsearch von unten nach oben behandelt), nicht die tatsächlich gespeicherten Dokumente. Das bedeutet, dass bei der Durchführung von Fuzzy-Abfragen der Abfragetext als Ergebnis einer Analyse mit einem unerwarteten Begriffswert verglichen werden kann, was zu manchmal verwirrenden Ergebnissen führt. Das bedeutet auch, dass, wenn Synonyme in einem Feld aktiviert sind, die Synonyme abgeglichen werden können, auch wenn das Wort im Quelltext überhaupt nicht vorkommt. Wenn man zum Beispiel eine Fuzzy-Abfrage über ein ngram-analysiertes Feld verwenden würde, wären die Ergebnisse wahrscheinlich skurril, da Ngrams Wörter in viele kleine Buchstabenkombinationen aufteilen, von denen viele nur ein oder zwei Bearbeitungen entfernt sind, obwohl die tatsächlichen Wörter ziemlich unterschiedlich sind. Das bedeutet auch, dass, wenn Sie beispielsweise einen Schneeballanalysator verwenden, eine unscharfe Suche nach 'running' auf 'run' abgekürzt wird, aber nicht das falsch geschriebene Wort 'runninga' findet, das auf 'runninga' zurückgeht, weil 'run' mehr als 2 Bearbeitungen von 'runninga' entfernt ist. Das kann zu ziemlicher Verwirrung führen, und aus diesem Grund ist es oft sinnvoll, den einfachen Analyzer nur für Text zu verwenden, der für Fuzzy-Abfragen vorgesehen ist, und möglicherweise auch Synonyme zu deaktivieren. Um dies zu verdeutlichen, sehen Sie unten ein Diagramm, das eine Fuzzy-Abfrage zeigt, die anhand eines Schneeballanalysedokuments ausgeführt wird

Die verschiedenen Arten von Fuzzy-Suchen Mehrere Arten der Fuzzy-Suche

werden von Elasticsearch unterstützt und die Unterschiede können verwirrend sein. Die folgende Liste versucht, diese verschiedenen Typen zu disambiguieren

• Abgleichsabfrage + Unschärfe-Option: Das Hinzufügen des Unschärfe-Parameters zu einer Match-Abfrage macht aus einer einfachen Match-Abfrage eine Fuzzy-Abfrage. Analysiert den Abfragetext, bevor die Suche durchgeführt wird.
• Fuzzy-Abfrage: Der Elasticsearch-Fuzzy-Abfragetyp sollte generell vermieden werden. Verhält sich fast wie eine Begriffsabfrage. Analysiert nicht zuerst den Abfragetext.
• fuzzy_like_this/fuzzy_like_this_field : Eine more_like_this-Abfrage, unterstützt aber Unschärfe und hat einen optimierten Bewertungsalgorithmus, der die Merkmale von Fuzzy-Matching-Ergebnissen besser behandelt.
*
• Vorschläge: Vorschläge sind kein eigentlicher Abfragetyp, sondern ein separater Operationstyp (intern auf Fuzzy-Abfragen aufgebaut), der entweder zusammen mit einer Abfrage oder unabhängig ausgeführt werden kann. Suggester eignen sich hervorragend für Funktionen im „Meinten Sie“ -Stil.

Eine Match-Abfrage mit dem Unschärfe-Parametersatz ist vielleicht die vielseitigste der Fuzzy-Abfragen. Der Abfragetyp Fuzzy unterstützt genau dasselbe Verhalten, außer dass er keine Analyse für den Abfragetext ermöglicht. Darüber hinaus ist der Fuzzy-Abfragetyp eine Teilmenge der Funktionalität einer Trefferabfrage, was sie eher verwirrend als nützlich macht

Die fuzzy_like_this- oder FLT-Abfragen sind nützlich, um Empfehlungen abzugeben, die auf einem großen Stück Quelltext basieren, der Rechtschreibfehler oder andere Ungenauigkeiten enthalten kann, getrennt durch den Bearbeitungsabstand. Es gibt zwei verschiedene Abfragen in dieser Kategorie fuzzy_like_this und fuzzy_like_this_field, die beide dieselbe Funktionalität bieten, wobei letztere Abfrage die Syntax für den Fall vereinfacht, dass nur ein einziges Feld verwendet wird. Diese Abfragen verwenden einen Parameter, like_text, der aus einem großen Textstück besteht, sagen wir den Hauptteil eines Artikels, und versuchen, Dokumente zu finden, die diesem „ähnlich“ sind. Der Text in dem Artikel wird überprüft und die Abfrageausdrücke werden auf der Grundlage ihrer Häufigkeit im like_text gewichtet, mit speziellen Anpassungen (Deaktivierung des Koordinationsfaktors, Quelltext-basierte IDF), um die verschiedenen Begriffe aus dem Quelltext zu kombinieren. FLT-Abfragen funktionieren am besten für Fälle, in denen der Korpus eine große Anzahl von Rechtschreibfehlern enthält, andernfalls hat eine standardmäßige more_like_this-Abfrage eine bessere Leistung. Weitere Informationen finden Sie in der offiziellen Dokumentation für Fuzzy More Like

Vorschläge sind fantastisch für den Fall, dass ein Benutzer für eine Suche „New York“ eingibt und beabsichtigt hat, „New York“ einzugeben. Anwendungen können vorschlagen, auf der Benutzeroberfläche ein Feld „Meinten Sie“ anzuzeigen, in dem eine mögliche Korrektur empfohlen wird. Beachten Sie, dass die Vervollständigungs-API für den speziellen Fall der Type-Ahead-Suche eine bessere Leistung bietet, da Type-Ahead-Suchen latenzempfindlich sind. Weitere Informationen zu Vorschlaggebern finden Sie auf der Seite mit Suchvorschlägen.

Überlegungen zur Leistung

Obwohl Lucenes Levenshtein-Distanzimplementierung auf dem neuesten Stand der Technik und ziemlich schnell ist, ist sie immer noch viel langsamer als eine einfache Match-Abfrage. Die Laufzeit der Abfrage wächst mit der Anzahl der eindeutigen Begriffe im Index. Das heißt, wenn eine Fuzzy-Suche durchgeführt wird, ist das Hauptkriterium nicht, wie viele Dokumente zurückgegeben werden, sondern wie viele eindeutige Begriffe im Cluster es für die durchsuchten Felder gibt. Wenn es 100 Dokumente mit 10.000 eindeutigen Wörtern pro Stück gibt, ist die Suche in diesem Index langsamer als die Suche in 10.000 Dokumenten, bei denen das durchsuchte Feld nur 100 eindeutige Wörter enthält

Der Hauptgrund für diese Langsamkeit ist, dass eine Standardabfrage den Begriffsindex, eine interne Datenstruktur, die von Lucene verwendet wird, schnell auf Treffer überprüfen und Dokumente mithilfe der binären Suche extrem schnell finden kann. Dieser Prozess ist selbst bei großen Wörterbüchern schnell, da binäre Suchen gut skalierbar sind. Fuzzy-Abfragen verwenden dagegen einen fortgeschritteneren Algorithmus mit einem DFA, der eine große Anzahl von Begriffen verarbeiten muss. Die Verarbeitung der viel größeren Anzahl von Begriffen, die für eine Fuzzy-Suche erforderlich sind, ist immer langsamer als eine einfache binäre Suche. Zum Beispiel dauert die Durchführung einer Fuzzy-Suche im englischsprachigen Wikipedia-Datensatz etwa 320 ms für den Begriff „Historie“ bei einer Min_Similarity von 2, während eine einfache Treffersuche nach demselben Begriff nur 35 ms dauert, was einem Unterschied um eine Größenordnung entspricht. Bei einer Min_Similarity von 1 beträgt die Suchzeit nur 150 ms. Es sollte beachtet werden, dass diese Tests nicht auf statistisch fundierte Weise durchgeführt wurden und diese Zeiten durch spezifische Faktoren, die für einzelne Anwendungen spezifisch sind, erheblich beeinflusst werden können. Insbesondere der Wikipedia-Datensatz enthält viel mehr Begriffe als eine große Anzahl gängiger Anwendungsfälle

Leistung kann erheblich verbessert werden, indem verlangt wird, dass Treffer exakte Präfixübereinstimmungen mit der Abfrage haben. Das verkürzt den Suchraum dramatisch auf Kosten der Tatsache, dass Wörter mit einem Rechtschreibfehler am Anfang nicht gefunden werden. Je länger die Präfixlänge, desto schneller die Beschleunigung. Wenn Sie eine Präfixlänge von 1 angeben, wird die oben erwähnte 320-ms-Abfrage auf nur 104 ms reduziert. Die Erhöhung dieser Zahl führte zu weiteren Geschwindigkeitszuwächsen. Im Allgemeinen ist es ratsam, ein Präfix für Datensätze mit einer großen Anzahl von Begriffen zu verlangen, da sonst die Leistung schlecht wird, oft innerhalb von Hunderten von Millisekunden

Die Einstellung max_expansions, die die maximale Anzahl von Begriffen definiert, mit der die Fuzzy-Abfrage übereinstimmt, bevor die Suche gestoppt wird, kann auch dramatische Auswirkungen auf die Leistung einer Fuzzy-Abfrage haben. Das Kürzen der Abfrageausdrücke hat jedoch einen negativen Effekt, da einige gültige Ergebnisse aufgrund der vorzeitigen Beendigung der Anfrage möglicherweise nicht gefunden werden. Es ist wichtig zu verstehen, dass das Abfragelimit max_expansions auf Shard-Ebene funktioniert, was bedeutet, dass, selbst wenn es auf 1 gesetzt ist, mehrere Begriffe übereinstimmen können, die alle aus unterschiedlichen Shards stammen. Dieses Verhalten kann den Anschein erwecken, als ob max_expansions nicht gültig ist. Seien Sie also vorsichtig, dass das Zählen eindeutiger Begriffe, die zurückgegeben werden, keine gültige Methode ist, um festzustellen, ob max_expansions

Alternativen zu Fuzzy-Matching

Fuzzy-Matching ist nicht immer das richtige Tool für den Job, oft können ungenaue Übereinstimmungen durch andere Techniken gefunden werden. Das Phonetische Analyse-Plugin enthält eine Reihe faszinierender Tools zur Annäherung von Übereinstimmungen, wie zum Beispiel den Metaphon-Analyzer, der Wörter findet, die ähnlich klingen wie andere Wörter. Wenn zum Beispiel sichergestellt werden muss, dass Wörter wie rennen und gelaufen beide als gleichwertig betrachtet werden, ist ein intelligenter Analysator wie ein Schneeball-Analysator vorzuziehen. Alternativ, zur Überprüfung von Rechtschreibfehlern, kann die N-Gramm-Analyse, wie in diesem kurzen Tutorial beschrieben, je nach Datensatz bei der Abfrage um einiges schneller ablaufen. N-Grams gehen jedoch mit zusätzlichem Speicher-/Speicherverbrauch, etwas mehr Indexzeitverarbeitung und einem langen Schwanz von Fehlalarmen nach guten Übereinstimmungen einher

Weitere Lektüre

• Es gibt auch ein Video, Finite State Automata in Lucene and Solr, von einer Präsentation von Dawid Weiss, die Levenshtein und andere Automaten in Lucene behandelt
.