Wortanfangssuche mit MongoDB

Veröffentlicht am von

Erreichen Webanwendungen bzw. die zugehörigen Daten eine gewisse Komplexität und Größe, wird das Suchen in diesen Daten ein wichtiges Feature. Im Web sind es Benutzer gewohnt, nicht nur nach ganzen Wörten sondern auch über Wortbestandteile zu suchen. Der gängigste Fall ist hierbei die Suche nach Wortanfängen: Der Nutzer tippt die ersten drei Buchstaben eines Wortes ein und erhält alle Einträge, welche mit dem Suchterm beginnen. Die Volltextsuche von MongoDB ermöglicht out-of-the-box jedoch keine Wortanfangssuche. Mit etwas Implementierungsaufwand und einer geschickten Erweiterung der Datenstruktur lässt sich die vorhandene Volltextsuche der MongoDB jedoch auch für eine Wortanfangssuche nutzen.

Das Problem

Bei MongoDB handelt es sich um eine NoSQL Datenbank, in welcher Daten als Dokumente im JSON Format gespeichert werden. MongoDB bringt bereits eine Volltextsuche mit, mit einigen Einschränkungen muss man jedoch leben. So kann bspw. nicht nach beliebigen Wortbestandteilen gesucht werden. Also auch nicht nach Wortanfängen. Einzige Ausnahme: Wortstämme.

Beispiel: Bei einer Wortanfangssuche nach Ber erwarten wir folgende Treffer

Berlin
Berliner Platz
Bern
bereinigen
Berlingo

Die MongoDB Suche nach Berlin würde neben Berlin auch den Eintrag Berliner Platz finden, da der Suchterm ein Wortstamm in Berliner ist. Nicht aber Berlingo. Die MongoDB Suche nach Ber ergibt sogar keinen der oben genannten Treffer.

Lösungsoptionen

Eine mögliche Lösung für das Problem kann die Hinzunahme eines eigenständigen Suchservices wie etwa Elasticsearch oder Apache Solr sein. Damit gehen jedoch entsprechend hohe Aufwände für die Integration des neuen Suchservices in die bestehende Anwendung einher.

Alternativ kann man durch die geschickte Anreicherung der Daten die vorhandene Textsuche der MongoDB so nutzen, dass eine Wortanfangssuche möglich ist. Der Vorteil dieser Lösung liegt im Wegfall des Integrationsaufwandes für einen dedizierten Suchservice.

Wie kann man also die Daten soweit aufbereiten, dass auch Wortanfänge von der MongoDB Textsuche gefunden werden? Die Idee: Wir nutzen N-Gramme!

N-Gramme(?)

N-Gramme sind das Ergebnis der Zerlegung eines Textes in Fragmente. Dieses Konzept wird in der linguistischen Analyse angewandt und dient dazu, statistische Auswertungen von Texten zu erstellen. Das Konzept lässt sich auch auf die Zerlegung einzelner Wörter anwenden. N steht hierbei für die Anzahl der Buchstaben.

Anhand des Wortes berlin mit N=3 ergeben sich die folgenden N-Gramme:

ber
erl
rli
lin

Analog hierzu lässt sich die Liste erweitern mit N=4, N=5 und N=6 etc. N sollte dabei nicht größer werden als die Anzahl der Buchstaben im betreffenden Wort.

Wie hilft uns das bei unserem Problem?

Um die Wortanfangssuche zu unterstützen reicht es in unserem Fall aus, nur die N-Gramme zu bestimmen, welche den Wortanfang enthalten. Auch sollte N >= 3 sein, denn unsere Suchterme haben eine Mindestlänge von 3.

Den Satz Auf dem Berliner Platz scheint die Sonne. zerlegen wir zunächst in einzelne Worte und danach jedes Wort in die entsprechenden N-Gramme:

Auf
dem
Ber
Berl
Berli
Berlin
Berline
Berliner
Pla
Plat
Platz
sch
sche
schei
schein
scheint
die
Son
Sonn
Sonne

Die oben stehende Liste enthält neben allen Worten des Ausgangstextes auch alle möglichen Wortanfänge mit Länge >=3 als einzelne Worte (Welche somit jetzt von der MongoDB Volltextsuche gefunden werden können!).

Implementierung für MongoDB

Die theoretische Lösung für unser Problem ist da. Jetzt muss diese „nur“ noch umgesetzt werden. Angenommen die Dokumente in unsere MongoDB sehen wie folgt aus:

{
  _id: "doc-001",
  description: "Auf dem Berliner Platz scheint die Sonne.",
  temperature: 25.3,
  weather: "sonnenschein, wolkenlos"
},
{
  _id: "doc-002",
  description: "Auf dem Stuttgarter Platz regnet es.",
  temperature: 22.7,
  weather: "regen, stark bewölkt"
},
{
  _id: "doc-003",
  description: "In Bern ist schon wieder Winter.",
  anotherProperty: 3412,
  temperature: 13.7,
  weather: "leicht bewölkt"
}

Durchsuchbar machen möchten wir die Dokumente bezüglich der Werte description und weather. Wir müssen für jedes Dokument

  1. die Werte der properties weather und description konkatenieren,
  2. diesen Wert in eine Liste einzelner Worte zerlegen und
  3. für jedes dieser Worte die N-Gramme berechnen (beginnend mit N=3 bis N=length wobei length die Länge des jeweiligen Wortes ist).
  4. Das Ergebnis schreiben wir auf die Property _search des betreffenden Dokumentes.

Für die Implementierung nutzen wird NodeJS sowie das sehr umfangreiche npm package natural

const { RegexpTokenizer} = require('natural');

// assume we got the doc from our MongoDB
const doc = {
  _id: "doc-001",
  description: "Auf dem Berliner Platz scheint die Sonne.",
  temperature: 25.3,
  weather: "sonnenschein, wolkenlos"
};
const searchable = `${doc.description} ${doc.weather}`;


/*
 * Create new Tokenizer to seperate words out of a string.
 * We use dot, question mark, exclamation mark, comma and whitespace as separators
 */ 
const tokenizer = new RegexpTokenizer({
  pattern: /\.|\s|\?|!|,/
});

// create a list of words out of our searchable string using tokenizer
const wordList = tokenizer.tokenize(searchable);


/* 
 * now for each word in our wordList calculate ngrams 
 * and push them to nGrams array
 */
let nGrams = [];
wordList.forEach(word => {
  // words with length < 3 are just used as they are
  if (word.length < 3) {
    nGrams.push(word)
  } else {
    for (let i = 3; i <= word.length; i++) {
      /*
       * create prefix ngrams starting with length = 3 up to word.length
       * and push them to nGrams array
       */
      nGrams.push(word.substring(0, i));
    }
  }
});


/*
 * Now add new _search property on existing doc 
 * containing a whitespace seperated list of all ngrams.
 * Save the document and back to mongoDB.
 */
doc._search = nGrams.join(' ');

Der oben stehende Code muss für jedes Dokument ausgeführt werden. Es bietet sich an, dass bei allen schreibenden Zugriffen auf Dokumente (Create and Update) vor dem Speichern in die Datenbank die Anreicherung des Dokumentes mit den _search Werten erfolgt.

Unsere Dokumente sehen nach der Anpassung wie folgt aus:

{
  _id: "doc-001",
  description: "Auf dem Berliner Platz scheint die Sonne.",
  temperature: 25.3,
  weather: "sonnenschein, wolkenlos",
  _search: "Auf dem Ber Berl Berli Berlin Berline Berliner Pla Plat Platz sch sche schei schein scheint die Son Sonn Sonne son sonn sonnen sonnens sonnensc sonnensch sonnensche sonnenschei sonnenschein wol wolk wolke wolken wolkenl wolkenlo wolkenlos"
},
{
  _id: "doc-002",
  description: "Auf dem Stuttgarter Platz regnet es.",
  temperature: 22.7,
  weather: "regen, stark bewölkt",
  _search: "Auf dem Stu Stut Stutt Stuttg Stuttga Stuttgar Sutttgart Stuttgarte Stuttgarte Stuttgarter Pla Plat Platz reg regn regne regnet es reg rege regen sta star stark bew bewö bewöl bewölk bewölkt"
},
{
  _id: "doc-003",
  description: "In Bern ist schon wieder Winter.",
  anotherProperty: 3412,
  temperature: 13.7,
  weather: "leicht bewölkt",
  _search: "In Ber Bern ist sch scho schon wie wied wiede wieder Win Wint Winte Winter lei leic leich leicht bew bewö bewöl bewölk bewölkt"
}

Zum Schluss legen wir in der MongoDB einen neuen Index vom typ text an, welcher nur die property _search unserer Dokumente indexiert. Hierbei verzichten wir auf die Wortstammsuche (da wir diese nicht mehr benötigen) indem wir als language none angeben (default_language: "none"):

// we tell mongoDB to index property '_search' with an index of type 'text' 
db.collection.createIndex(
  {
    _search: "text"
  },
  {
    default_language: "none"
  }
);

Fazit

Mit relativ wenig Implementierungsaufwand und einer geschickten Erweiterung unserer Datenstruktur können wir die vorhandene Volltextsuche der MongoDB nutzen, um eine Wortanfangssuche zu implementieren.

Quellen

  1. Text Search – MongoDB Manual
  2. Elasticsearch
  3. Apache solr
  4. N-Gramme
  5. NPM Package natural