Textsuche in Java (mit der JDK-API)

Textsuche ist eine recht häufiges Problemstellung, die immer dann auftritt, wenn wir prüfen ob ein String in einem anderen vorkommt. Die JDK-Standard-API bietet hier ein paar Grundfunktionalitäten, allerdings gibt es deutlich effizientere Methoden, insbesondere für größere Muster und größere Texte.

Dieser Beitrag könnte für diejenigen von Interesse sein, die sich für Textsuche und die Möglichkeiten der Java-API (bzw. Alternativen darüber hinaus) interessieren.

Textsuche (String-Searching, String-Matching)

Bei Textsuche (oder String Matching) geht es darum ein Suchwort (Suchmaske, Muster) in einem Text (Dokument) zu finden. Idealerweise produziert ein Textsuchalgorithmus alle Vorkommnisse des Suchworts im Text. In den folgenden Code-Beispielen nennen wir die Variable für das Suchwort needle, die für den Text haystack.

Textsuche mit java.lang.String

Die einfachste Methode, die üblicherweise auch gar nicht als Textsuche empfunden wird stellt die Klasse java.lang.String zur Verfügung in Form von String.indexOf. Wer die Position nicht benötigt, sondern nur die Information ob das Wort enthalten ist, kann auch auf String.contains ausweichen. Eine Textsuche würde dann etwa so aussehen:

int find(String needle, String haystack) {
  return haystack.indexOf(needle);
}

Java verwendet hier einen naiven Such-Algorithmus, um die Position zu bestimmen. Naiv bedeutet hier, dass der zu durchsuchende Text zeichenweise prozessiert wird. Bei zur Suchwort passenden Anfangszeichen wird ein Prozess gestartet, der an der übereinstimmenden Position startet und so lange die folgenden Zeichen vergleicht bis ein Unterschied auftritt oder eine vollständige Übereinstimmung erreicht wurde. Dieser Algorithmus ist für kleine Suchmasken und kleine Texte ausreichend, bei echten Texten und echten Wörtern aber sehr langsam.

Textsuche mit java.util.Matcher

Eine weitere nicht immer ganz intuitive Möglichkeit der Textsuche bietet java.util.Matcher mit der Methode java.util.Matcher.find. Eigentlich sucht diese Methode nach regulären Ausdrücken, aber da jedes Suchwort auch eine Entsprechung als regulärer Ausdruck hat, funktioniert dies auch für die Suche nach konstanten Texten.

int find(String needle, String haystack) {
  String escapedNeedle = Pattern.quote(needle);

  Pattern pattern = Pattern.compile(escapedNeedle);

  Matcher matcher = pattern.matcher(haystack);

  if (matcher.find()) {
    return matcher.start();
  } else {
    return -1;
  }
}

Die konkrete Implementierung ist noch optimierbar, aber zunächst stellt sich ohnehin die Frage, warum die sonst eher langsame Matcher.find-Methode zur Textsuche geeignet ist:

Das liegt daran, dass die Methode java.util.Matcher.find zunächst prüft ob das Suchwort ein einfaches Literal (RegEx ohne Operatoren). In dem Fall wird nicht die RegEx-Engine vewendet sondern ein Boyer-Moore-Algorithmus. Die Performance ist sehr ordentlich, auch für lange Texte und lange Suchwörter.

Mehr zur Textsuche …

Grundsätzlich deckt die Java-Standard-API nur einen sehr geringen Teil des Gebiets Textsuche ab. Es gibt sehr viele Algorithmen, die das Problem effizient lösen. Sie unterscheiden sich vor allem hinsichtlich ihrer Optimierung:

• auf große/kleine Alphabete
• auf kurze/lange Muster
• auf große/kleine Texte

Ich werde in einem weiteren Blog-Beitrag etwas detaillierter auf solche Algorithmen eingehen.

… und zur Multi-Text-Suche

Außerdem gibt es noch ein verwandtes Problem, welches die Java-API nicht effizient löst - die Multi-Text-Suche (Multi-String-Matching). Hierbei wird nicht nur ein Wort in einem Text gesucht, sondern mehrere. Man könnte annehmen, dass die Verwendung von Matcher.find mit einem Audruck (Wort1|Wort2|...|WortN) eine ähnliche Optimierung vornimmt wie mit Wort1, aber leider funktioniert die Optimierung der Suche nur für konstante Worte und nicht für endliche Sprachen (reguläre Sprachen mit endlich vielen Wörtern).

Bibliotheken zur Textsuche

Ich vermute, dass das übliche Vorgehen bei Textsuche-Problemen ist, sich selbst einen Algorithmus zu schreiben. Es gibt ein paar wenige Projekte, die zum großen Teil aber schlecht getestet und bestensfalls experimentell zu bezeichnen sind. Um solche Bibliotheken zu bewerten, habe ich die Benchmarkbibliothek StringBench entwickelt und die populären Kandidaten damit getestet:

Es fällt auf, dass viele Bibliotheken den Benchmark nicht bestanden haben. Das liegt daran, dass in einigen Situationen eine Zeitüberschreitung eintritt (länger als 1 Minute). Kritisch ist das, weil bereits der naive Algorithmus die Zeitgrenze ohne weiteres erreicht. Meine Vermutung ist, dass alle fehlschlagenden Bibliotheken ein Problem mit einer hohen Trefferanzahl haben - grundsätzlich verhalten sie sich nämlich schon so performant wie man es von den entsprechenden Algorithmen erwarten würde. Ich hoffe diese Performance-Probleme werden in späteren Updates behoben.