[Trennmuster] Warum nicht sisisi

[Stephan Hennig]

Am 29.11.2013 22:49, schrieb Herbert Voss:
> Am 29.11.2013 22:12, schrieb Stephan Hennig:
>>> das bezieht sich auf die Trennmusterdateien die im Allgemeinen
>>> < 100 kB sind und ist außerdem extrem abhängig von der maximalen
>>> Trennmusterlänge.
>>
>> Nö, wie geschrieben, O(n) mit n = Wortlänge.  Die Größe der Musterdatei
>> oder einzelner Muster ist völlig unerheblich.  Jedenfalls in der
>> Implementierung in libhyphen, welches von LuaTeX verwendet wird.
>>
>> Es kann sein, dass die Implementierung in traditionellem TeX etwas
>> einfacher ist (mehrere kleinere Tries parallel, statt eines großen
>> Automaten verwendet werden) und dort etwas mehr Tabellenzugriffe nötig
>> sind.  Aber auch dann ist der Algorithmus O(n), nur die
>> zugrundeliegenden Operationen sind geringfügig aufwendiger (mehr
>> Tabellenzugriffe pro Buchstabe).
> 
> Mag sein, aber dann erkläre mir mal, wieso das zeitlich keine Rolle
> spielt, ob ich bei der Ermittlung der Trennstellen von beispielsweise 
> "Krankenschwester" Muster maximaler Länge 3 oder 8 habe?

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.

Zur anderen Antwort:  Angenommen, Patgen würde bei einem Lauf ein Muster
erzeugen, das 8 Zeichen lang ist und auf ein bestimmtes Wort passt.
Dann hat es einen Grund, dass das Muster so lang ist.  Es würde mit
einem kürzeren Muster zu Falschtrennungen anderer Wörter kommen, die
wiederum verhindert werden müssten.  Die einzige Möglichkeit ist
Korrektur-/Ausgleichs-/Kompensationsmuster hinzuzufügen, deren Zweck es
ist, falsche Treffer des kürzeren, unspezifischeren Musters zu
verhindern.  Wird Patgen nun so konfiguriert, dass es in einem anderen
Lauf maximal 7 Zeichen lange Muster erzeugen kann, so wird sich also
zwangsläufig die Zahl der Muster erhöhen.  Auf irgend eine Art muss die
Information, die zum fehlerfreien Trennen der Wortliste benötigt wird,
ja kodiert werden.

Wenn also nur kürzere Muster vorhanden sind, bedeutet das nicht, dass
beim Trennen pro Wortbuchstabe weniger Informationen zu verarbeiten
sind.  Anderenfalls wäre in Patgen etwas faul.

(Wobei das nur ungefähr stimmt.  Patgen geht iterativ vor und ermittelt
keine optimale Lösung.  Der beschriebene Effekt sollte sich aber
nachprüfen lassen.  Irgendwo hatte ich mal Skripten, mit denen man die
(Zahl der) Muster ermitteln konnte, die auf ein Wort passen und
umgekehrt.  Damit könnte man auch Mustersätze danach vergleichen,
wieviele Musterbuchstaben pro Wortbuchstabe zu verarbeiten sind.  Ich
müsste mal suchen ...)

Viele Grüße,
Stephan Hennig