[Trennmuster] Warum nicht sisisi

[Stephan Hennig]

Am 04.12.2013 19:25, schrieb Stephan Hennig:

> 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.

Kommen wir zum Zerlegungsproblem.  Ich werden hier ausgehend von einem
einfachen Verfahren nach und nach ein schnelles, lineares Verfahren
(bezogen auf die Zeichenkettenlänge) entwickeln, welches unabhängig von
der Musterlänge ist.  Dieses Verfahren wird meines Wissens auch in
libhyphen und damit in LuaTeX verwendet.  Ob TeX82 ein echt lineares
Verfahren verwendet, entzieht sich meiner Kenntnis.

Eine Zeichenkette der Länge n besteht aus insgesamt n*(n+1)/2
Teilzeichenketten der Längen 1, 2, ..., n.  Als Teil des
Trennalgorithmus müssen von all diesen Teilzeichenketten diejenigen
ermittelt werden, die auch in der Trennmustermenge enthalten sind.  Wir
haben es hier mit einem kombinatorischen Problem zu tun, dessen Lösung
eine Aufzählung und Überprüfung sämtlicher Teilzeichenketten erfordert.
 Für einen schnellen Algorithmus benötigen wir eine möglichst geschickte
Aufzählung der Teilzeichenketten.

Eine Möglichkeit ist, zunächst alle Teilzeichenketten der Länge 1 zu
untersuchen, danach die der Länge 2 usw.  Für die Zeichenkette 'abc'
erhalten wir so nacheinander die Zeichenketten

a b c   ab bc   abc

Eine andere Möglichkeit ist, zunächst alle Zeichenketten zu untersuchen,
die an Position 1 beginnen, danach diejenigen, die an Position 2
beginnen usw.  Damit erhält man

a ab abc   b bc   c

Wie können auch umgekehrt aufzählen: zunächst alle Teilzeichenketten,
die an Position 1 enden, danach diejenigen, die an Position 2 enden usw.

a   b ab   c bc abc

In der letzten E-Mail hatte ich erwähnt, dass sich mit Tries
gleichzeitig Zeichenketten suchen lassen, die vom Anfang her
übereinstimmen.  Das passt perfekt zur zweiten Zerlegungsmethode.  Und
genau die wählen wir auch.

Zunächst werden sämtliche Muster (ohne Ziffern, die sind für die
Zerlegung nämlich uninteressant) als Schlüssel in einem Trie
gespeichert.  Danach wird für eine gegebene Zeichenkette in einer
äußeren Schleife über alle Zeichenpositionen iteriert.  An jeder
Position suchen wir im Trie nach der längsten an dieser Position
beginnenden Zeichenkette und notieren dabei sämtliche gefundenen
Zeichenketten.

Angenommen, der Trie enthält die Muster b, bc und abd.  Dann suchen wir
mit der Beispielzeichenkette 'abc' an Position 1 schrittweise nach den
Zeichenketten a, ab, abc und finden keine davon.  An Position 2 suchen
wir b und bc.  Beide Ketten werden gefunden.  An Position 3 wird nach c
gesucht, jedoch wieder nicht gefunden.

Bei diesem Verfahren werden die einzelnen Zeichen der Zeichenkette zum
Teil mehrfach betrachtet.  Wieviele Zeichen in der inneren Schleife zu
prüfen sind, hängt stark von der betrachteten Zeichenkette ab. Bei der
Zeichenkette 'xxx' wird an jeder Position bereits nach einem Zeichen
festgestellt, dass der Trie keine passenden Schlüssel enthält, weil kein
Schlüssel mit dem Buchstaben x beginnt.  Alle Zeichen brauchen in diesem
Fall also nur einmal betrachtet zu werden.  Das Vorhandensein von
innerer und äußerer Schleife riecht aber sehr nach quadratischer
Laufzeit.  Eine erste Verbesserung dieses Verfahrens und weshalb das
hier gezeigte Verfahren in der Praxis tatsächlich bereits ein lineares
Laufzeitverhalten aufweist, zeige ich in der nächsten E-Mail.

Viele Grüße,
Stephan Hennig