Dec 16th, 2019: [DE][Elasticsearch] Zusammengesetzte Worte in Elasticsearch


(xeraa) #1

Zusammengesetzte Worte in Elasticsearch

Deutsch, Finnisch, Koreanisch und die skandinavischen Sprachen haben die, für Volltextsuche unpraktische, Eigenschaft, dass sie Komposita bilden, also mehrere Worte zu einem kombinieren. Das führt beispielsweise dann zu Problemen, wenn man das Wort "Volltextsuche" gespeichert hat und es finden möchte, indem man nur nach "suche" sucht. Doch wie lässt sich diese Anfrage dennoch umsetzen?

Wer die Beispiele selbst ausprobieren möchte, benötigt nur das als Gist verfügbare Docker (Compose) Setup, das sich mit $ docker-compose up starten und docker-compose down -v wieder vollständig entfernen lässt. Kibana wird dadurch unter http://localhost:5601 gestartet und die Abfragen lassen sich in der Console der Developer Tools ausführen.

Die naive Wildcard-Suche

Der naive Ansatz wäre, eine Wildcard-Suche zu verwenden — ähnlich einem LIKE %suche% in SQL. Das würde in Elasticsearch etwa so aussehen:

POST wildcard/_doc
{
  "example": "Volltextsuche"
}

GET wildcard/_search
{
  "query": {
    "wildcard": {
      "example": "*suche*"
    }
  }
}

Doch genau wie in SQL-Datenbanken ist auch in Elasticsearch die Suche mit Wildcards und speziell mit führenden Wildcards äußerst ineffizient und wird nur bei kleinen Datenmengen zufriedenstellend funktionieren. In Kibana lassen sich führende Wildcards deshalb beispielsweise deaktivieren. Deshalb wollen wir diesen Ansatz gleich wieder verwerfen. Doch welche skalierenden Ansätze gibt es?

ngrams als Holzhammer

Manche Probleme lassen sich gut mit dem sprichwörtlichen Holzhammer lösen — nicht übermäßig intelligent, aber mit dem richtigen Maß an Ressourcen.

Dafür werden Worte in Buchstabengruppen aufgeteilt; beispielsweise bei Trigrammen in Gruppen von drei. "Volltextsuche" würde dann als "Vol", "oll", "llt", "lte", "tex",... abgespeichert werden. Das lässt sich auch einfach mit dem _analyze Endpoint ausprobieren, wobei wir zusätzlich nur mit Kleinbuchstaben arbeiten wollen:

GET /_analyze
{
  "tokenizer": {
    "type": "ngram",
    "min_gram": "3",
    "max_gram": "3"
  },
  "filter": [
    "lowercase"
  ],
  "text": "Volltextsuche"
}

Mit dem Ergebnis:

{
  "tokens" : [
    {
      "token" : "vol",
      "start_offset" : 0,
      "end_offset" : 3,
      "type" : "word",
      "position" : 0
    },
    {
      "token" : "oll",
      "start_offset" : 1,
      "end_offset" : 4,
      "type" : "word",
      "position" : 1
    },
    ...

Bei der Suche wird "suche" ebenfalls in die Dreiergruppen aufgespaltet, also "suc", "uch" und "che", die alle auch Teil von "volltextsuche" sind. Das funktioniert in Elasticsearch dann so — wir legen das Mapping für die Trigramme an (ohne auf die Details dabei einzugehen), speichern unser Dokument und suchen abschließend danach:

PUT trigram
{
  "settings": {
    "number_of_shards": 1,
    "analysis": {
      "filter": {
        "trigram_filter": {
          "type": "ngram",
          "min_gram": "3",
          "max_gram": "3"
        }
      },
      "analyzer": {
        "trigram_analyzer": {
          "tokenizer": "standard",
          "filter": [
            "lowercase",
            "trigram_filter"
          ]
        }
      }
    }
  },
  "mappings": {
    "_doc": {
      "properties": {
        "example": {
          "type": "text",
          "analyzer": "trigram_analyzer"
        }
      }
    }
  }
}
POST trigram/_doc
{
  "example": "Volltextsuche"
}
GET trigram/_search
{
  "query": {
    "match": {
      "example": "suche"
    }
  }
}

Zusätzlich zum Aufwand bei der Indizierung der Daten wird auch mehr Speicherplatz für alle Trigramme benötigt. Dafür ist der Ansatz universell einsetzbar, benötigt keine zusätzlichen Abhängigkeiten und ist leicht verständlich. Negativ kommt jedoch noch hinzu, dass potentiell weniger relevante Worte gefunden werden wie "Kuchen" oder "Küche". Wie könnte also ein intelligenterer Ansatz aussehen?

Wörterbücher für mehr Intelligenz

Standardmäßig verwendet Elasticsearch regelbasierte Ansätze und keine Wörterbücher, da diese aufwendig bei der Erstellung sind und regelmäßige Pflege benötigen. Häufig sind sie daher mit einer kommerziellen oder restriktiven Lizenz versehen und kommen öfter aus dem universitären Umfeld, da dort die nötigen, billigen Arbeitskräfte verfügbar sind (Studenten). Sehen wir uns dazu zwei verschiedene Ansätze an.

Eigene Wortlisten

Wenn man eine eigene Wortliste erstellt, was bei domänenspezifischem Vokabular häufig notwendig ist, kann man diese mit sprachspezifischen Abteilungsregeln (Hyphenation) kombinieren, um zusammengesetzte Worte richtig aufzuteilen. Dafür muss man im ersten Schritt die Abteilungsregeln auf allen Elasticsearch-Nodes hinterlegen, wofür wir Objects For Formatting Objects (OFFO) verwenden. Wobei wir die Version 1.2 von OFFO verwenden müssen, da 2.0 nicht mit Elasticsearch kompatibel ist.

Im nächsten Schritt lässt sich dann das Mapping damit erstellen und wieder unsere Suche simulieren:

PUT wordlist
{
  "settings": {
    "number_of_shards": 1,
    "analysis": {
      "filter": {
        "german_filter": {
          "type": "hyphenation_decompounder",
          "hyphenation_patterns_path": "hyph/de_DR.xml",
          "word_list": [
            "text",
            "suche"
          ]
        }
      },
      "analyzer": {
        "german_analyzer": {
          "tokenizer": "standard",
          "filter": [
            "lowercase",
            "german_filter"
          ]
        }
      }
    }
  }
}
GET wordlist/_analyze
{
  "analyzer" : "german_analyzer",
  "text" : "Volltextsuche"
}

Das Ergebnis davon sollte keine Überraschung sein, wobei anzumerken ist, dass alle drei gefundenen Worte die selben Start- und Endpositionen haben:

{
  "tokens" : [
    {
      "token" : "volltextsuche",
      "start_offset" : 0,
      "end_offset" : 13,
      "type" : "<ALPHANUM>",
      "position" : 0
    },
    {
      "token" : "text",
      "start_offset" : 0,
      "end_offset" : 13,
      "type" : "<ALPHANUM>",
      "position" : 0
    },
    {
      "token" : "suche",
      "start_offset" : 0,
      "end_offset" : 13,
      "type" : "<ALPHANUM>",
      "position" : 0
    }
  ]
}

(xeraa) #2

Wörterbuch

Alternativ dazu gibt es für Deutsch ein LGPL lizensiertes Wörterbuch von Uwe Schindler, das wiederum auf allen Elasticsearch-Nodes abgespeichert werden muss. Mapping und Abfrage sehen damit so aus:

PUT dictionary
{
  "settings": {
    "number_of_shards": 1,
    "analysis": {
      "filter": {
        "german_filter": {
          "type": "hyphenation_decompounder",
          "word_list_path": "dictionary-de.txt",
          "hyphenation_patterns_path": "hyph/de_DR.xml",
          "only_longest_match": true,
          "min_subword_size": 4
        }
      },
      "analyzer": {
        "german_analyzer": {
          "tokenizer": "standard",
          "filter": [
            "lowercase",
            "german_filter"
          ]
        }
      }
    }
  }
}
GET dictionary/_analyze
{
  "analyzer" : "german_analyzer",
  "text" : "Volltextsuche"
}

Resultat:

{
  "tokens" : [
    {
      "token" : "volltextsuche",
      "start_offset" : 0,
      "end_offset" : 13,
      "type" : "<ALPHANUM>",
      "position" : 0
    },
    {
      "token" : "voll",
      "start_offset" : 0,
      "end_offset" : 13,
      "type" : "<ALPHANUM>",
      "position" : 0
    },
    {
      "token" : "text",
      "start_offset" : 0,
      "end_offset" : 13,
      "type" : "<ALPHANUM>",
      "position" : 0
    },
    {
      "token" : "suche",
      "start_offset" : 0,
      "end_offset" : 13,
      "type" : "<ALPHANUM>",
      "position" : 0
    }
  ]
}

Als Alternative zu Wortlisten oder Wörterbüchern gibt es von Jörg Prante auch ein regelbasiertes Elasticsearch Plugin für Deutsch. Allerdings wird aktuell 6.3 als neueste Version unterstützt, weshalb wir es hier nicht praktisch ausprobieren. Ob die zusätzliche Abhängigkeit, die immer exakt zur Elasticsearch-Version passen muss, aufwiegt, dass man nur mit Regeln auskommt, muss wohl jedes Projekt individuell entscheiden.

Fin

Und damit schließen wir unseren kurzen Überblick, mit deutschen Komposita zu arbeiten, bereits wieder ab. Es gibt noch deutlich mehr Konfigurationsoptionen, aber hier haben wir uns auf die Minimalbeispiele konzentriert. Welcher Ansatz der Beste ist, kommt immer auf die jeweiligen Anforderungen an. Oder um es mit der Lieblingsphrase jedes IT-Consultants zu sagen: It depends...


(mos) #3

Danke @xeraa. Noch ein kleiner Tipp zum regelbasierten decompound-Plugin:

Wir nutzten das regelbasierte Wörterbuch bei uns in Produktion und halten das Plugin up-to-date. Please check our fork: https://github.com/gbigenios/elasticsearch-analysis-decompound … (Im Test gegen die Wörterbuch-Plugins klar im Vorteil ! :grinning: )