TeXs Trennalgorithmus

Wie im letzten Post (Feature der Woche »Silbentrennung«) schon angedeutet, gibt es hier eine Zusammenfassung, wie die Silbentrennung in TeX (und damit auch im speedata Publisher) funktioniert. Detailliert ist sie in Franklin Liangs Dissertation »Word Hy-phen-a-tion by Com-put-er« nachzulesen (zu finden auf der Seite der TUG).

Der Trennalgorithmus funktioniert statisch, das heißt, jedes Wort wird gleich getrennt, egal wo es in einem Satz vorkommt oder welche Bedeutung es hat. So wird nicht zwischen Staub-ecken und Stau-becken unterschieden. Grundlage für die musterbasierte Trennung ist eine Datei mit Einträgen wie

1auto
1to
2dc
2hn
2u1t
3bah
3mä
a2u
c4h
d1ch
h2en.
o1b
uto1
ä1d

Die Datei enthält in der Regel etliche tausend solcher Einträge. Diese Einträge sind Wortbestandteile mit Zahlen zwischen einzelnen Buchstaben. In den Zahlen steckt die Information darüber, ob an dieser Stelle getrennt werden darf oder nicht, und welche Priorität diese Regel hat. Man kennt solche Hilfen wie »Trenne nie st, denn es tut ihm weh.« (die inzwischen ja nicht mehr gilt). So könnte man dieses Verbot mit s4t ausdrücken. Hier bedeuten gerade Zahlen, dass nicht getrennt werden darf, ungerade Zahlen erlaubte Trennstellen. Und je höher die Zahl, desto mehr Gewicht hat sie. Für die Trennstelle bei Haus-tür könnte man mit einem zusätzlichem Muster haus5t die obige Regel aufheben, da 4 kleiner ist als 5.

Die Vorgehensweise ist nun folgende. Wenn man ein Wort hat, für das man die erlaubten Trennstellen ermitteln möchte, wandelt man es erst in Kleinbuchstaben um und fügt vorne und hinten ein Wortbegrenzungszeichen ein, bei TeXs Trennmustern ist das ein Punkt. So wird aus Autobahn ».autobahn.« Dann probiert man alle Trennmuster durch, ob sie irgendwo in dieses Wort passen. In diesem Beispiel sind das die Muster a2u, 1auto, 2u1t, uto1, 1to, o1b, 3bah und 2hn. Die Zahlen lässt man für das Ausprobieren weg. Hier werden die Muster an die passende Stelle unter das Wort geschrieben:

       .  a  u  t  o  b  a  h  n  .
--------------------------------------
a2u         2
1auto    1
2u1t        2  1
uto1                 1
1to            1
o1b                  1
3bah                 3
2hn                        2
--------------------------------------
Maximum
       .  a  u  t  o  b  a  h  n  .
         1  2  1  0  3  0  2  0  0

Es wird also das Maximum aller Zahlen in einer Spalte gebildet und dann wird das Wort wieder zusammengesetzt, im Beispiel also .1a2u1to3bah2n. Die Nullen kann man einfügen, muss man aber nicht. Dann werden die geraden Zahlen gelöscht: .1au1to3bahn. Dann werden alle ungeraden Zahlen durch Trennmöglichkeiten ersetzt und die Punkte für die Wortbegrenzung weggelassen: -au-to-bahn. Es sind also drei Trennstellen erlaubt: am Anfang vor dem Wort (das ist natürlich Unfug und fällt weg), dann bei au- und to-.

Im nächsten Beispiel gibt es ein Muster mit einem Wortende und einmal einen Konflikt zwischen a1d (Trennung erlaubt) und 2dc (Trennung nicht erlaubt):

       .  m  ä  d  c  h  e  n  .
3mä      3
ä1d            1
2dc            2
d1ch              1
c4h                  4
h2en.                   2

Maximum
       .  m  ä  d  c  h  e  n  .
         3     2  1  4  2

Hier ist die einzige erlaubte Trennung zwischen d und ch. TeX wählt die Parameter so, dass die ersten drei Zeichen eines Wortes und die letzten beiden Zeichen nicht getrennt werden. Daher fällt die erste 3 bei dem letzten Beispiel weg.

Nachtrag 8.9.2016: auf github liegt ein in Go geschriebenes Programm, das den Algorithmus umsetzt.