Silbentrennung in HTML - Teil 2

Project has moved

For the most recent documentations and versions of Hyphenator please go to http://code.google.com/p/hyphenator/

Abstract

Dieser Artikel behandelt im ersten Teil die Problematik der Silbentrennung (Hyphenation) in Webbrowsern und führt im zweiten Teil als möglichen Lösungsansatz eine automatische Silbentrennung an. Diese beruht auf dem Ansatz von Liang, verwendet die Trennmuster für die deutsche Silbentrennung aus der LaTeX-Distribution und ist in JavaScript implementiert.
In diesem Dokument wurde die Silbentrennung durch das Script vorgenommen; verändern Sie die Fenstergrösse um das Resultat zu sehen.

This Article treats in its first part the problem of word hyphenation in current webbrowsers. In its second part a javascript doing automatic word hyphenation is presented as a possible solution. This script relies on Liangs thesis and uses hyphenation patterns from the LaTeX-Distribution.

Liangs Thesis

Frankling Mark Liang erarbeitete 1983 im Rahmen seiner Doktorarbeit einen Algorithmus für die automatische Silbentrennung für das Textsatzsystem (La)TeX. Damals war es wichtig, dass das Programm möglichst wenig Arbeitsspeicher brauchte – eine Wörterliste mit allen Wörtern und Trennstellen kam also nicht in Frage.
Liangs Doktorvater und Schöpfer von (La)Tex, Donald Knuth, hatte bereits einen Algorithmus programmiert, der englische Wörter trennen konnte, indem unter anderem Präfixe und Suffixe abgetrennt wurden. Liang ging aber weiter.

Er hat aus einer Wortliste mit Trennstellen eine Reihe von Zeichenmustern berechnet, die zusammen mit Zahlwerten auf mögliche Trenn- und Nichttrennstellen rückschliessen lassen. Dabei markieren ungerade Zahlen mögliche Trennstellen. Diese Muster (patterns) sehen etwa so aus:
1be 2il 2lb n1tr 1nu 1si tr6.
Möchte man für ein bestimmtes Wort Trennstellen finden, sucht man alle passenden Muster heraus und kombiniert die Zahlen – eine höhere Zahl überschreibt dabei eine kleinere.

Für das Wort Silbentrennung passen die oben bereits aufgezeigten Muster und ergeben:

 s i l b e n t r e n n u n g 
      1b e
  2i l
    2l b
           n1t r
                    1n u
1s i
             t r6
-----------------------------
1s2i2l1b e n1t r6e n1n u n g

Es wird also Sil|ben|tren|nung getrennt.

Liang hat bei der Berechnung der Muster mit verschiedenen Parametern experimentiert, wobei er lieber eine Trennstelle nicht fand, statt eine falsche auszugeben. Bei seinen Tests stellte sich heraus, dass mit nur knapp 5000 Mustern beinahe 90% aller Trennstellen gefunden werden konnten. Um aber alle Trennstellen zu finden waren an die 20'000 Muster nötig – zuviel für damalige Rechner.

Nach diesem Schema wurden daraufhin für viele Sprachen Trennmuster berechnet und es wird heute für die Silbentrennung unter anderem in OpenOffice und LaTeX verwendet.
Die Trennmuster sind online bei CTAN erhältlich und stehen unter der «LaTeX Project Public License».

Implementierung in JavaScript

Dank des geringen Speicherbedarfs und seiner Einfachheit eignet sich Liangs Algorithmus hervorragend für den Einsatz im Web. Wie sich zeigen wird, benötigt das gesammte Skript inklusive Trennmuster höchstens 100KB und ist hinreichend schnell.
(Alle Zeitmessungen fanden auf einem älteren PowerMac G4/933MHz in Safari 2.0.4 statt. Neuere Rechnermodelle dürften wesentlich schneller sein.)

Aufbereitung der Trennmuster

Zuerst habe ich versucht, die Trennmuster direkt, also in der Form n1tr zu übernehmen. In dieser Form ist auch der sprachenspezifische Ersatz der Trennmuster denkbar. Das Skript brauchte so nur etwa 40KB, dafür aber zwei Sekunden, um diese Trennmuster einzulesen.
Deshalb habe ich die Muster auch in JSON notiert ({"ntr":"0100"}), wodurch der Speicherbedarf auf 92KB aufgebläht wurde. Das Einlesen der Muster gelang so aber in 30ms.

Für die Implementierung eines Tries, wie sie Liang vorschlägt, ist JavaScript allerding zu langsam (vorausgesetzt, ich habe alles richtig gemacht). Mit einem Trie könnten zwar viele Suchläufe nach Mustern vermieden werden; das Suchen im Trie war in meinen Tests aber soviel langsamer als das Suchen im Objekt, dass diese Ersparnis mehr als zunichte gemacht wurde. Wirklich schneller wäre ein Trie nur, wenn er von der JavaScript-Core zur Verfügung gestellt würde.

Das Script ist für die Einbindung in eigene Webseiten frei erhältlich.

Ausserdem habe ich eine Bookmarklet-Version entwickelt. Damit lässt sich auf jeder x-beliebigen Seite mit einem Klick auf das Bookmarklet die Silbentrennung durchführen. Um das Bookmarklet zu erhalten, einfach diesen Link als Lesezeichen speichern (mit rechter Maustaste anklicken und dann «Link als Lesezeichen» oder so ähnlich auswählen oder einfach auf die Lesezeichenleiste ziehen).

Einsatz des Skripts

Das Script trennt nach dem Aufruf von Hyphenator.hyphenateDocument() sämtlichen Text aller Elemente mit dem Attribut class="hyphenate" – auch den Text in deren Kindelementen.

Ich möchte an dieser Stelle nocheinmal darauf hinweisen, dass die Suchfunktion einiger Browser nach der Silbentrennung nicht mehr korrekt funktioniert. Das Skript sollte also mit Bedacht eingesetzt werden.

Ich freue mich auf Lob, Kritik und Korrekturen (mit letzteren zwei kann ich allerdings am meisten anfangen ;-)