[Trennmuster] Warum nicht sisisi

[Stephan Hennig]

Am 30.11.2013 09:19, schrieb Stephan Hennig:

>>> Darauf habe ich zwei Antworten.  Eine ist eine Erklärung anhand des
>>> Algorithmus.  Das bekomme ich heute Abend nicht mehr hin, versuche über
>>> das Wochenende aber, das kurz zu skizzieren.
>
> Das ist gerade nicht der Fall. :-)  Der Trick liegt in der Verwendung
> der Datenstruktur Trie, in der TeX die Muster speichert.  Wer sich dafür
> interessiert, kann sich schon mal schlau machen, wie so ein Trie grob
> funktioniert.  Ich spiele das Trennen dann mal an einem Beispiel durch.

Bei Herbert kann ich etwas Vorwissen voraussetzen, für eine
allgemeinverständliche(re) Erklärung des Zerlegungsproblems sind jedoch
ein paar Sätze mehr nötig.  Selbstverständlich habe ich am Wochenende
keine Zeit gefunden, daher werde ich die Beschreibung des Algorithmus
auf mehrere Schnipsel verteilen.

Ich werde die Datenstruktur Trie hier nicht im Detail erläutern.  Ich
beziehe ich mich hier auf Tries in der einfachsten Form, ohne jegliche
Art von Optimierung und gehe nur auf einige Eigenschaften ein, auf die
ich später Bezug nehmen werde.  Ebenso werde ich nicht auf den gesamten
Trennalgorithmus eingehen.  Ich werde hier lediglich zeigen, wie ein
Wort der Länge l in O(l) Zeit in die passenden Teilmuster einer
gegebenen Mustermenge zerlegt werden kann.

Die Datenstruktur Trie ist ein Baum, in dem große Mengen an Wörtern
platzsparend gespeichert werden können, indem die Redundanz der
Datenmenge (eine Liste von Wörtern bzw. Zeichenketten) gezielt
verringert wird.  Beginnen Wörter mit derselben Teilzeichenkette, so
wird diese nicht mehrmals gespeichert.  Tries werden anschaulich auch
als Präfixbaum bezeichnet.  "Präfix" bezieht sich hier allerdings nicht
auf morphologische Präfixe, sondern auf beliebige Zeichenkettenanfänge.

Eine kurze technische Beschreibung (die nicht in erster Linie der
Anschaulichkeit dient, sondern einige Fakten zusammenträgt): Ein Trie
besteht aus Knoten und gerichteten Kanten.  Die Knoten entsprechen
(irgendwelchen) Zuständen während der Suche nach einer Zeichenkette, zum
Beispiel kann ein Knoten dem Zustand "Zeichenkette XYZ gespeichert"
entsprechen.  Die Kanten entsprechen zulässigen Übergängen zwischen
Knoten und repräsentieren einzelne Buchstaben der gespeicherten
Zeichenketten.  Von einem Knoten können mehrere Kanten ausgehen.  (In
jeden Knoten führt wiederum nur genau eine Kante hinein, außer in die
Wurzel.)  In der Menge der von einem bestimmten Knoten ausgehenden
Kanten kann jeder Buchstabe höchstens ein Mal vertreten sein.  Es gibt
also keine zwei Kanten, die von einem Knoten ausgehen und denselben
Buchstaben repräsentieren.

Die Suche nach einem bestimmten Wort in einem Trie läuft folgendermaßen
ab: Man geht nacheinander die Buchstaben des Wortes durch.  Ausgehend
von der Wurzel prüft man am aktuellen Knoten, ob eine ausgehende Kante
existiert, die den aktuell betrachteten Buchstaben repräsentiert.  Wenn
ja, so wird der Zielknoten der gefundenen Kante zum aktuellen Knoten und
man fährt mit dem nächsten Buchstaben fort.  Wenn nicht, ist die Suche
fehlgeschlagen.  Sind keine weiteren Buchstaben vorhanden, so prüft man
abschließend, ob der aktuelle Knoten eine gespeicherte Zeichenkette
repräsentiert (Zustand "Zeichenkette XYZ gespeichert").  Wenn ja, ist
das Wort im Trie gespeichert.  Wenn nein, ist die Suche ebenfalls
fehlgeschlagen.

Zwei Eigenschaften machen Tries interessant, zum Beispiel für die
Speicherung von Wörterbüchern zur Rechtschreibkontrolle:

  1. Die bereits erwähnte Platzersparnis gegenüber zum Beispiel einem
     Array.  (Die Größe der Platzersparnis ist allerdings abhängig von
     der konkreten Implementierung der Datenstruktur Trie.)

  2. Die Suche nach einem bestimmten Wort der Länge l erfordert
     höchstens l Schritte.

     Zum Vergleich, in einem sortierten Array benötigt man zur Suche
     durch Bisektion höchstens log2(n) Schritte, wobei n jedoch nicht
     die Wortlänge ist, sondern die Anzahl der gespeicherten Wörter.
     Bei einem Wörterbuch mit 500.000 Wörtern benötigte man also bis zu
     19 Schritte.  Da die meisten Wörter aber deutlich kürzer sind, ist
     ein Trie einem sortierten Array bezüglich der Geschwindigkeit
     vorzuziehen.

Die Platzersparnis spielt für TeX bei der Worttrennung keine Rolle,
Trennmuster sind in jedem Fall eine überschaubare Datenmenge.  Die
Möglichkeit der schnellen Suche nach einzelnen Zeichenketten allein ist
für TeX auch nicht das entscheidende, sondern eine weitere Eigenschaft:

  3. Man kann nach l Suchschritten nicht nur in Erfahrung bringen, ob
     ein bestimmtes Wort der Länge l im Trie gespeichert ist, sondern
     mehr.  Nämlich, ob auch irgendwelche Anfangsteilwörter des
     gesuchten Wortes im Trie gespeichert sind.  Dazu muss im oben
     angegebenen Suchverfahren lediglich /jeder/ besuchte Knoten darauf
     geprüft werden, ob er eine gespeicherte Zeichenkette repräsentiert.
     Man kann in Tries also schnell nach mehreren Wörtern gleichzeitig
     suchen, die vom Anfang her gesehen übereinstimmen.

     Ein Beispiel: Wenn in einem Trie die Wörter 'Tal' und 'Talent'
     gespeichert sind, so erfährt man während der Suche nach dem Wort
     'Talente' nicht nur, dass das Wort nicht enthalten ist, sondern
     auch, dass die Wörter 'Tal' und 'Talent' enthalten sind.

Diese letzte Eigenschaft lässt sich bei der Anwendung von Tries zur
Rechtschreibprüfung nicht so recht gewinnbringend einsetzen.  Bei der
Zerlegung von Wörtern, wie TeX sie für die Worttrennung vornimmt,
allerdings schon.  Dazu später mehr.

Viele Grüße,
Stephan Hennig