4 Grundlegende Konzepte der Volltextsuche

Stellen Sie sich vor, Sie haben die Aufgabe, in einer Bibliothek mit Millionen von Büchern ein bestimmtes Thema zu finden. Ohne ein gutes Organisationssystem wäre dies eine überwältigende Aufgabe. Genau wie eine gut organisierte Bibliothek ein Indexsystem verwendet, nutzt OpenSearch ausgeklügelte Techniken, um Text effizient durchsuchbar zu machen. In diesem Kapitel lernen Sie diese grundlegenden Techniken kennen.

4.1 Der invertierte Index - Fundament der Volltextsuche

Der invertierte Index ist der Kern der Volltextsuche. Denken Sie an das Stichwortverzeichnis am Ende eines Fachbuchs: Dort finden Sie für jeden wichtigen Begriff die Seitenzahlen, auf denen er vorkommt. OpenSearch arbeitet nach einem ähnlichen, aber deutlich ausgefeilteren Prinzip.

Lassen Sie uns dies anhand eines konkreten Beispiels verstehen:

Nehmen wir an, wir haben folgende Produktbeschreibungen:

Dokument 1: "Ergonomische Bluetooth-Tastatur mit deutschem Layout"
Dokument 2: "Deutsche Gaming-Tastatur mit RGB-Beleuchtung"
Dokument 3: "Bluetooth-Maus mit ergonomischem Design"

Ein einfacher invertierter Index würde so aussehen:

ergonomisch   -> {1: [0], 3: [2]}       // [Position im Dokument]
bluetooth     -> {1: [1], 3: [0]}
tastatur      -> {1: [2], 2: [1]}
deutsch       -> {1: [4], 2: [0]}
gaming        -> {2: [0]}
rgb           -> {2: [2]}
maus          -> {3: [1]}

Dieser Index ermöglicht:

• Schnelles Finden aller Dokumente, die bestimmte Begriffe enthalten
• Erkennung der Wortpositionen für Phrasensuchen
• Effiziente Berechnung der Relevanz

4.2 Die Analyse-Pipeline verstehen

Bevor Text in den invertierten Index gelangt, durchläuft er eine Analyse-Pipeline. Diese Pipeline verwandelt rohen Text in suchbare Terme. Stellen Sie sich dies wie eine Fabrik mit verschiedenen Verarbeitungsstationen vor.

4.2.1 Character Filter

Der Character Filter bereitet den Text vor. Er kann zum Beispiel:

• HTML-Tags entfernen
• Sonderzeichen normalisieren
• Bindestriche standardisieren

4.2.2 Beispiel einer Character Filter Konfiguration

{
  "char_filter": {
    "html_strip": {
      "type": "html_strip",
      "escaped_tags": ["b", "i"]
    },
    "german_chars": {
      "type": "mapping",
      "mappings": [
        "ß => ss",
        "ä => ae"
      ]
    }
  }
}

4.2.3 Tokenizer

Der Tokenizer zerlegt den Text in einzelne Token. Dies ist komplexer als eine einfache Trennung an Leerzeichen, da er auch:

• Satzzeichen berücksichtigt
• Abkürzungen erkennt
• Sonderzeichen intelligent behandelt

4.2.4 Beispiel verschiedener Tokenizer in Aktion

// Standard Tokenizer
Input: "Der USB-Stick (32GB) kostet 29,99€"
Output: ["Der", "USB", "Stick", "32GB", "kostet", "29,99", "€"]

// Whitespace Tokenizer
Input: "Der USB-Stick (32GB) kostet 29,99€"
Output: ["Der", "USB-Stick", "(32GB)", "kostet", "29,99€"]

// N-Gram Tokenizer
Input: "Tastatur"
Output: ["Ta", "Tas", "ast", "sta", "tat", "atu", "tur"]

4.2.4.1 N-Gram Tokenizer

Ein N-Gram Tokenizer bietet mehrere Vorteile, insbesondere in Anwendungsfällen, bei denen Teilstrings oder unscharfe Suchanfragen wichtig sind. Die Vorteile lassen sich in folgenden Punkten zusammenfassen:

4.2.4.1.1 Verbesserte Fehlertoleranz

• Durch das Zerlegen von Wörtern in überlappende N-Gramme können auch Suchanfragen erfolgreich verarbeitet werden, die Rechtschreibfehler, Tippfehler oder Variationen enthalten.
• Beispiel: Das Wort Haus mit einem Bigram-Tokenizer (n=2) ergibt die Tokens ha, au, us. Eine Suchanfrage wie hauz würde durch die Ähnlichkeit der N-Gramme (ha, au, uz) trotzdem ein Treffer liefern.

4.2.4.1.2 Teilwortsuche

• N-Gramme ermöglichen die Suche nach Substrings innerhalb von Wörtern, ohne dass Wildcards benötigt werden.
• Beispiel: Bei der Suche nach auto würde ein Tokenizer mit Trigrammen für das Wort Automobil Tokens wie aut, uto, tom, etc. generieren, was eine Übereinstimmung ermöglicht.

4.2.4.1.3 Sprachen mit komplexen Wortformen

• In Sprachen wie Deutsch, wo Wörter durch Kompositionen entstehen (z. B. Krankenhaus, Haustürschlüssel), hilft ein N-Gram Tokenizer, Teilstrings wie Haus, Schlüssel oder Tür zu erkennen, auch wenn sie eingebettet sind.

4.2.4.1.4 Unabhängigkeit von Token-Grenzen

• Im Gegensatz zu Tokenizern, die an Leerzeichen oder Satzzeichen orientiert sind, berücksichtigt der N-Gram Tokenizer auch übergreifende Patterns innerhalb eines Tokens, was besonders für maschinelles Lernen und Textklassifikation nützlich ist.

4.2.4.1.5 Effiziente Ähnlichkeitssuche

• N-Gramme können in Kombination mit Algorithmen wie Jaccard- oder Cosine-Similarity verwendet werden, um Textähnlichkeiten zu berechnen, was beispielsweise bei Duplikaterkennung oder Clustering von Dokumenten hilfreich ist.

4.2.4.1.6 Bessere Leistung bei sprachenübergreifenden Systemen

• In Sprachen ohne klare Wortgrenzen (z. B. Chinesisch oder Japanisch) bieten N-Gramme eine universelle Methode zur Tokenisierung.

4.2.4.1.7 Nachteile und Abwägungen

Obwohl ein N-Gram Tokenizer viele Vorteile hat, gibt es auch einige Nachteile: - Speicherbedarf: Die Anzahl der generierten Tokens steigt mit der Länge des Textes und dem gewählten n, was mehr Speicherplatz und Rechenzeit benötigt. - Rauschen: Kleinere N-Gramme können irrelevante Matches verursachen. - Manuelle Tuning-Anforderungen: Die Wahl eines geeigneten n (z. B. Bigram vs. Trigram) hängt stark vom Anwendungsfall ab.

Ein N-Gram Tokenizer ist ideal für unscharfe Suchanfragen, Ähnlichkeitsvergleiche und Systeme, die mit reichhaltigen und variierenden Textformen arbeiten müssen.

4.2.5 Token Filter

Token Filter bearbeiten die einzelnen Token. Sie können:

• Wörter in Kleinbuchstaben umwandeln
• Stoppwörter entfernen
• Grundformen von Wörtern finden (Stemming)
• Synonyme ersetzen

4.2.6 Beispiel für eine vollständige Analyse-Pipeline

PUT /products
{
  "settings": {
    "analysis": {
      "analyzer": {
        "product_analyzer": {
          "type": "custom",
          "char_filter": [
            "html_strip",
            "german_chars"
          ],
          "tokenizer": "standard",
          "filter": [
            "lowercase",
            "german_stop",
            "german_stemmer",
            "product_synonyms"
          ]
        }
      },
      "char_filter": {
        "german_chars": {
          "type": "mapping",
          "mappings": [
            "ä => ae",
            "ö => oe",
            "ü => ue",
            "ß => ss",
            "Ä => Ae",
            "Ö => Oe",
            "Ü => Ue"
          ]
        }
      },
      "filter": {
        "german_stop": {
          "type": "stop",
          "stopwords": "_german_"
        },
        "german_stemmer": {
          "type": "stemmer",
          "language": "light_german"
        },
        "product_synonyms": {
          "type": "synonym",
          "synonyms": [
            "laptop, notebook => computer",
            "smartphone, handy => mobiltelefon"
          ]
        }
      }
    }
  }
}

4.3 Relevanz und Scoring

Die Relevanzberechnung in OpenSearch basiert auf mehreren Faktoren, ähnlich wie ein Richter verschiedene Aspekte berücksichtigt, um zu einer Entscheidung zu kommen.

4.3.1 TF/IDF - Die Grundlage der Relevanzberechnung

TF/IDF (Term Frequency/Inverse Document Frequency) bewertet die Bedeutung eines Terms in einem Dokument:

1. Term Frequency (TF): Wie oft kommt der Term im Dokument vor?

   TF = √(Anzahl der Vorkommen)

   Die Quadratwurzel verhindert, dass einzelne häufige Terme zu dominant werden.

2. Inverse Document Frequency (IDF): Wie selten ist der Term im gesamten Index?

   IDF = ln(Gesamtzahl Dokumente / (Anzahl Dokumente mit Term + 1))

   Seltene Terme bekommen mehr Gewicht, da sie diskriminierender sind.

4.3.2 Beispiel

GET /products/_explain/1
{
  "query": {
    "match": {
      "description": "Perfekt"
    }
  }
}

führt zum Ergebnis:

{
  "_index": "products",
  "_id": "1",
  "matched": true,
  "explanation": {
    "value": 0.2876821,
    "description": "weight(description:perfekt in 0) [PerFieldSimilarity], result of:",
    "details": [
      {
        "value": 0.2876821,
        "description": "score(freq=1.0), computed as boost * idf * tf from:",
        "details": [
          {
            "value": 2.2,
            "description": "boost",
            "details": []
          },
          {
            "value": 0.2876821,
            "description": "idf, computed as log(1 + (N - n + 0.5) / (n + 0.5)) from:",
            "details": [
              {
                "value": 1,
                "description": "n, number of documents containing term",
                "details": []
              },
              {
                "value": 1,
                "description": "N, total number of documents with field",
                "details": []
              }
            ]
          },
          {
            "value": 0.45454544,
            "description": "tf, computed as freq / (freq + k1 * (1 - b + b * dl / avgdl)) from:",
            "details": [
              {
                "value": 1,
                "description": "freq, occurrences of term within document",
                "details": []
              },
              {
                "value": 1.2,
                "description": "k1, term saturation parameter",
                "details": []
              },
              {
                "value": 0.75,
                "description": "b, length normalization parameter",
                "details": []
              },
              {
                "value": 4,
                "description": "dl, length of field",
                "details": []
              },
              {
                "value": 4,
                "description": "avgdl, average length of field",
                "details": []
              }
            ]
          }
        ]
      }
    ]
  }
}

Das Ergebnis zeigt, wie der Score eines Dokuments (mit der ID 1) für einen Suchbegriff berechnet wurde. Die Details erklären, wie die verschiedenen Faktoren von Elasticsearchs BM25-Similarity-Algorithmus zusammenwirken, um den Score zu bestimmen.

4.3.2.1 Details:

1. Gesamter Score:

   • Der Gesamt-Score beträgt 0.2876821.
   • Dieser Wert entscheidet, wie relevant das Dokument für den Suchbegriff ist.

2. Berechnung des Scores:

   • Der Score basiert auf der Formel:
     Score = Boost × IDF × TF

3. Details der Faktoren:

   a. Boost (2.2):

   • Ein konstanter Wert, der die Gewichtung des Feldes oder der Abfrage beeinflusst.
   • In diesem Fall hat das Feld description einen Boost von 2.2.

   b. IDF (Inverse Document Frequency, 0.2876821):

   • Maß für die Seltenheit eines Begriffs im Index.

   • Berechnung:

     IDF = log(1 + (N - n + 0.5) / (n + 0.5))

     • N = 1: Gesamtzahl der Dokumente im Index.
     • n = 1: Anzahl der Dokumente, die den Begriff enthalten.
     • Ergebnis: Der Begriff ist nicht selten, da er in allen verfügbaren Dokumenten vorkommt, was zu einem niedrigen IDF führt.

   c. TF (Term Frequency, 0.45454544):

   • Maß dafür, wie oft der Begriff im Dokument vorkommt, angepasst an die Feldlänge.

   • Berechnung:

     TF = freq / (freq + k1 * (1 - b + b * dl / avgdl))

     • freq = 1: Der Begriff kommt einmal im Feld vor.
     • k1 = 1.2: Sättigungsparameter für die Häufigkeit.
     • b = 0.75: Gewichtung der Längennormalisierung.
     • dl = 4: Länge des Feldes (Anzahl der Begriffe).
     • avgdl = 4: Durchschnittliche Länge der Felder im Index.

4. Relevanz der Berechnung:

   • Da es nur ein Dokument gibt (N = 1) und der Begriff in diesem vorkommt (n = 1), wird der Score maßgeblich von TF beeinflusst. Der geringe IDF-Wert zeigt, dass der Begriff nicht selten ist, was den Gesamtscore senkt.

4.3.3 BM25 - Modern Scoring Algorithm

BM25 ist eine Verfeinerung von TF/IDF, die zusätzlich:

• Dokumentlänge berücksichtigt
• Term Frequency Sättigung einführt
• Feldlängen-Normalisierung ermöglicht

Der Ausdruck erschließt sich dem Betrachter vermutlich nicht gleich, aber die Idee ist einfach:

score = IDF × (TF × (k1 + 1)) / (TF + k1 × (1 - b + b × dl/avgdl))

4.3.3.1 Erläuterung einzelnen Komponenten und ihrer Bedeutung

• IDF (Inverse Document Frequency):
  Dies misst die Seltenheit eines Begriffs im Index. Je seltener ein Begriff in allen Dokumenten vorkommt, desto höher ist sein Einfluss auf den Score. Dadurch werden häufig vorkommende Begriffe wie Artikel oder Konjunktionen abgewertet.

• TF (Term Frequency):
  Dies gibt an, wie oft ein Suchbegriff in einem Dokument vorkommt. BM25 verwendet jedoch keine lineare Gewichtung; stattdessen wird der Einfluss von TF durch den Parameter k1 abgeschwächt. Dadurch werden sehr häufige Begriffe innerhalb eines Dokuments nicht überproportional stark gewichtet.

• k1 (Term Frequency Sättigung):
  Dieser Parameter steuert, wie stark die Häufigkeit eines Begriffs den Score beeinflusst. Ein niedriger Wert von k1 führt dazu, dass zusätzliche Vorkommen eines Begriffs nur noch minimal den Score erhöhen.

• b (Einfluss der Dokumentlänge):
  BM25 berücksichtigt die Länge eines Dokuments, um lange Dokumente, die viele Begriffe enthalten, nicht zu bevorzugen. Der Parameter b bestimmt, wie stark die Länge eines Dokuments die Gewichtung beeinflusst:

  • b = 0: Kein Einfluss der Dokumentlänge.
  • b = 1: Volle Berücksichtigung der Dokumentlänge.

• dl (Dokumentlänge) und avgdl (Durchschnittliche Dokumentlänge):
  Diese Werte werden verwendet, um die relative Länge eines Dokuments im Vergleich zu allen anderen Dokumenten zu berechnen. Wenn ein Dokument länger als der Durchschnitt ist, wird die Gewichtung des Suchbegriffs in diesem Dokument reduziert, da längere Dokumente tendenziell mehr Begriffe enthalten.

4.3.3.2 Vereinfachte Interpretation der Formel

• Der Zähler (TF × (k1 + 1)):
  Verstärkt die Bedeutung von Begriffen, die häufig vorkommen, bis zu einem bestimmten Punkt, an dem der Effekt durch k1 gesättigt wird.

• Der Nenner (TF + k1 × (1 - b + b × dl/avgdl)):
  Führt eine Normalisierung durch, die sowohl die Sättigung der Term Frequency (TF) als auch die relative Länge des Dokuments berücksichtigt.

D.h. BM25 gleicht die Balance zwischen Häufigkeit eines Begriffs, seiner Seltenheit im gesamten Index und der Länge des Dokuments aus. Dies macht es flexibler und realistischer als den klassischen TF/IDF-Ansatz. Die Parameter k1 und b können angepasst werden, um die Gewichtung für spezifische Anwendungsfälle zu optimieren.

4.3.4 Score

Der Score in Elasticsearch ist nicht auf 1 normiert! Der Score ist ein relativer Wert, der die Relevanz eines Dokuments im Vergleich zu anderen Dokumenten in der Ergebnismenge ausdrückt.

4.3.4.1 Wichtige Punkte:

1. Relativität des Scores:
   • Der Score eines Dokuments hat nur Bedeutung im Kontext der anderen Scores innerhalb derselben Suchabfrage.
   • Der höchste Score wird normalerweise als das “relevanteste” Ergebnis betrachtet, aber es gibt keine obere Grenze wie 1.
2. Keine Normierung:
   • Elasticsearch verwendet die BM25-Similarity, die Scores anhand der Häufigkeit, Seltenheit und Gewichtung der Begriffe berechnet. Diese Werte sind nicht normiert und können je nach Boosting, IDF und TF variieren.
   • Ein Dokument kann daher theoretisch auch Scores größer als 1 haben, abhängig von den Boosts und der Gewichtung.
3. Wenn nur ein Dokument:
   • In ihrem Fall gibt es nur ein Dokument im Index (N = 1), daher ist der IDF relativ niedrig. Der Score scheint klein, hat aber trotzdem keinen direkten Bezug zu einer Normierung.
4. Normierung erzwingen:
   • Wenn Sie normierte Scores möchten, müssten Sie entweder in ihrem Code nach der Suchabfrage den höchsten Score ermitteln und alle Scores durch diesen teilen, oder ein alternatives Scoring verwenden.

4.4 Query-Ausführung verstehen

Wenn Sie eine Suchanfrage stellen, durchläuft sie mehrere Phasen:

4.4.1 Phase 1: Query-Phase

4.4.2 Phase 2: Fetch-Phase

Diese zweiphasige Ausführung ermöglicht:

• Effiziente Verarbeitung großer Datenmengen
• Präzise Relevanzbewertung
• Schnelle Antwortzeiten

4.5 Praktische Optimierungstechniken

4.5.1 Effiziente Filterung

Filter statt Queries verwenden, wenn keine Relevanzberechnung benötigt wird:

// Weniger effizient
GET /products/_search
{
  "query": {
    "bool": {
      "must": [
        {
          "range": {
            "price": {
              "gte": 100
            }
          }
        }
      ]
    }
  }
}

// Effizienter
GET /products/_search
{
  "query": {
    "bool": {
      "filter": [
        {
          "range": {
            "price": {
              "gte": 100
            }
          }
        }
      ]
    }
  }
}

4.5.2 Field-Mapping optimieren

Mappings an die Suchanforderungen anpassen:

PUT /products
{
  "mappings": {
    "properties": {
      "sku": {
        "type": "keyword",
        "index": true,
        "doc_values": true
      },
      "description": {
        "type": "text",
        "index": true,
        "norms": true,
        "index_options": "positions"
      }
    }
  }
}

4.5.3 Caching-Strategien

Filter-Resultate werden automatisch gecacht. Konsistente Query-Strukturen fördern effektives Caching:

// Bessere Cache-Nutzung
GET /products/_search
{
  "query": {
    "bool": {
      "filter": [
        {
          "term": {
            "status": "active"
          }
        }
      ]
    }
  }
}