zur Übersicht
2. Apr 2018

Exaktes String Matching in der Praxis

Zunächst war mein Interesse an Textsuchalgorithmen eher akademischer Natur - einfach nur den Algorithmus verstehen und implementieren können. Nachdem aus dieser Leidenschaft ein kleines Projekt (StringSearchAlgorithms) enstanden ist - begann ich Vergleiche anzustellen …

Es stellte sich heraus, dass viele Algorithmen zwar im akademischen Sinne funktionieren, aber in der Praxis erschwert (oder gar nicht) einsetzbar sind. Tatsächlich sind die akademischen Algorithmen für ganz bestimmte Situationen optimiert und sehr spezifisch gebunden an:

  • Prozessorarchitekturen
  • Encoding-Formaten
  • Programmiersprachen (APIs)

Es folgt eine Übersicht über die Herausforderungen, die die Praxis an Textsuche stellt.

Nachfolgend betrachte ich die jeweiligen Aspekte für 4 verschiedene Bibliotheken:

Chars oder Bytes (IO)

Viele Algorithmen wurden ursprünglich im C-Zeitalter formuliert wo der Standard-Character noch 8 bit hatte. Je nach Programmiersprache und Dateiformat sind diese Annahmen aber nicht mehr realistisch:

  • bytes in Java haben 8 bit, aber werden generell eher nicht zur Codierung von Strings verwendet
  • chars in Java haben 16 bit, aber werden generell eher nicht zur Codierung von Dateien verwendet
  • UTF-8 ist die meines Erachtens populärste Codierung von Zeichen in Dateien, sie hat aber eine variable bit-Länge

Die Entscheidung ob die Suche nun byte[] oder char[] basiert sein soll, ist nicht ganz so einfach:

Die char[]-basierte Suche funktioniert am Besten, wenn das Suchmuster und der Suchtext beide String- oder char[] basiert sind. Man spart sich hier die Decodierung in bytes und prozessiert zudem potentiell 2 bytes pro Zeichen. Die char[] basierte Suche ist jedoch sehr ungünstig, wenn man in größeren Dateien sucht. Zum einen muss der Text (der potentiell sehr lang sein kann) vollständig encodiert (von byte[] nach char[]) werden. Zum anderen kann nicht wahlfrei auf verschiedene char-Indizes zugegriffen werden, da überhaupt nicht klar ist, an welchem byte der n-te char beginnt wenn man nicht sämtliche n-1 chars davor ausgelesen hat (das Problem tritt nicht auf wenn man generell nur Charsets mit fixen Bitlängen zulässt, ist aber auf Grund der Dominanz von UTF-8 eher unrealistisch).

Umgekehrt ist die byte[]-basierte Suche für Strings nicht so gut. Hier muss eine Decodierung der Strings durchgeführt werden. Bei Dateien ist dies jedoch ein Vorteil, da der wahlfreie Zugriff auf byte-Indizes in Java ohne weiteres performant möglich ist. Eher unschön ist natürlich, dass das Muster (welches vermutlich eher als String vorliegt) vorher ebenfalls in byte[] gewandelt werden muss - und dazu benötigt man dann das korrekte Charset der durchsuchten Datei.

Bezogen auf die betrachtenten Bibliotheken:

  • ESMAJ ist char-basiert.
  • StringSearch arbeitet alternativ auf byte und char.
  • ByteSeek ist byte-basiert und unterstützt primitive konvertierungen von char-basierter Eingabe.
  • StringSearchAlgorithms bietet alternativ Suche über byte und char.

Chars oder Bytes (Algorithmen)

Inspiriert durch den Artikel Efficient Text Searching in Java habe ich jedes Framework auch auf Unicode-Kompatibilität geprüft. Tatsächlich ist die Frage ob char oder byte unterstützt wird nicht nur relevant für das IO sondern auch für den Algorithmus an sich. Fakt ist, dass viele String-Matching-Algorithmen darauf basieren eine Lookup-Tabelle für jedes Zeichen zu verwalten. Das war in Zeiten wo ein Zeichen 8 bit hatte sehr pragmatisch und schnell. Heute wo das Zeichen aber eher 16 bit hat (Unicode) ist die Lookup-Tabelle dann mal statt 256 Zeichen 65.536 Zeichen. Das bedeutet:

  • dass der Preprocessing-Aufwand um den Faktor 256 verlangsamt wird
  • der Hauptspeicheraufwand erheblich steigt
  • die Tabelle für normale europäische Muster/Texte hochredundant ist

Es gibt unterschiedliche Verfahren wie man mit der Problematik umgeht:

  • die Problematik entsteht nicht, wenn man bereits byte-basiert sucht, das Pattern ist dann potentiell etwas länger, aber die Tabelle ist nur 256 Einträge groß
  • die Problematik entsteht auch nicht, wenn keine Lookup-Tabellen verwendet werden
  • die Tabelle kann komprimiert werden, dazu gibt es verschiedene Strategien
  • Oft ist der Bereich der gültigen Zeichen numerisch dicht beeinander, anstatt also alle Einträge zu verwalten verwaltet man nur den Bereich in dem sich die relevanten Zeichen befinden (mit etwas Glück, z.B. bei ASCII-Zeichen) ist dieser Bereich sogar kleiner als 256 Einträge. Ein wenig Aufwand entsteht hier, weil beim Lookup noch Grenzen geprüft werden müssen.
  • Manche Algorithmen verwenden Tabellen für Heuristiken. Die einzige Anforderung ist, dass die Heuristik das Ergebnis nicht überschätzt. Eine mögliche Kompression ist die Abbildung der Einträge auf einen kleineren Umfang (kollidierende Schlüssel passend die Heuristik auf das Minimum an). Im Idealfall kollidieren bei der Schlüsselabbildung keine Schlüssel, andernfalls ist der Algorithmus etwas langsamer.

Bezogen auf die betrachtenten Bibliotheken:

  • ESMAJ geht bezüglich Unicode den naiven Weg: Hier werden tatsächlich Tabellen von der Größe von 65.536 erzeugt. ESMAJ hat wie schon gesagt einen ernormen Hauptspeicherverbrauch. Die schlimmsten Ausprägungen entstehen aber nicht bei den tabellenbasierten Algorithmen, meine Vermutung ist aber, dass die betroffenen Algorithmen (überwiegend Automatenbasierte Lösungen) ebenfalls an der Bitlänge scheitern, weil ihr Hauptspeicherverbrauch nicht nur linear von der bitlänge abhängig ist.
  • StringSearch komprimiert die Tabellen verlustfrei (soweit ich das richtig interpretiere). Ein Nachteil der verlustfreien Kompression ist, dass der Zugriff auf einzelne Lookups nicht nur eine Berechnung sondern mehrere erfordert.
  • ByteSeek ist von Unicode nicht betroffen, da es byte[]-basiert ist.
  • StringSearchAlgorithms verwendet verlustbehaftete und verlustfreie Kompression von Lookup-Tabellen (separat pro Algorithmus konfigurierbar) bei den betroffenen Algorithmen.

Strings, Arrays oder Streams

Ein weiterer Aspekt ist, wie die chars/bytes angeliefert werden. Wirklich große Dateien sollten nicht als char[]/byte[] angeliefert werden müssen, weil der Hauptspeicher solche Eigenheiten nicht gerne mitmacht. D.h. jeder String-Matching-Algorithmus sollte nicht nur in Arrays suchen können sondern auch in Streams/Readern/Buffern.

Bezogen auf die betrachtenten Bibliotheken:

  • ESMAJ hat diese Nuancen wohl gar nicht betrachtet. Es ist char[]-basiert und beherrscht keine Suche in Strömen oder Puffern. Eine Skalierbarkeit für größere Dateien ist nicht gegeben.
  • StringSearch bietet zwar Suchen mit char[] und byte[] an, allerdings keine Suche in Strömen und Puffern. Eine Skalierbarkeit für größere Dateien ist nicht gegeben.
  • ByteSeek ist byte[]-basiert und hat effiziente Implementierungen für die Suche in Strömen und Puffern. ByteSeek kann somit auf für größere Dateien skalieren.
  • StringSearchAlgorithms ist char[] oder byte[]-basiert und beherrscht die Suche in Strömen. StringSearchAlgorithms kann somit auf für größere Dateien skalieren.

Fazit

Bei der Betrachtung fiel auf, dass ESMAJ und StringSearch nicht auf große Textmengen skalieren, da beide nicht in Readern/Inputstreams/Buffern lesen können. Bei ESMAJ kommt noch hinzu, dass der Performance-Overhead für char-Tabellen (mit 65.536 Einträgen) dominant gegenüber dem eigentlichen Algorithmus wird. StringSearch hat diesen Overhead nur dann, wenn Zeichen aus weit entfernten Unicode-Regionen verwendet werden.

Deutlich praktischer erweisen sich hier ByteSeek (byte[]-basiert und stream-fähig) und StringSearchAlgorithms (char[]/byte[]-Varianten und reader/stream-fähig). ByteSeek (und die byte[]-Variante von StringSeachAlgorithms) hat keine Einschränkung mit großen Alphabeten. Die char[]-Variante von StringSearchAlgorithms ist im Fall von verlustfreier Kompression ähnlich hauptspeicherintensiv wie ESMAJ.

Einen praktischen Vergleich der einzelnen Bibliotheken anhand diverser Benchmarks findet man unter StringBench.

zur Übersicht