Knuth-Plass-Zeilenumbruchalgorithmus 📖 Wikipedia

Der Knuth-Plass Algorithmus ist ein für Donald Knuths Textsatzsystem TeX entwickelter Zeilenumbruchalgorithmus. Das Verfahren vereint die Probleme der Textausrichtung und der Silbentrennung in einem einzigen Prozess. Dabei nutzt er eine Methode der diskrete dynamischen Programmierung, um eine Verlustfunktion (Loss-Funktion) zu minimieren. Diese dient dazu, die ästhetischen Merkmale des fertigen Schriftbildes quantitativ zu bewerten und zu optimieren.^[1][2][3]

Der Algorithmus unterteilt den Text in einen Datenstrom aus drei Arten von Objekten: Boxes (Boxen), also Inhalte mit fester Breite; Glue (Kleber), Elemente mit flexibler Breite; und Penalties (Strafen), die Stellen, an welchen ein Zeilenumbruch unerwünscht oder – falls der Wert negativ ist – ausdrücklich erwünscht sind.^[2] Die Verlustfunktion, auch „Badness“ (Schlechtheit) genannt, definiert sich über den Grad der Verformung der Glue-Elemente, sowie über zusätzliche Penalties (Strafpunkte), die durch Zeilenumbrüche entstehen.^[1]

Die Entscheidung über Silbentrennung folgt ganz natürlich aus dem Algorithmus. Allerdings müssen die möglichen Trennpunkte innerhalb der Wörter – und optional ihre bevorzugte Gewichtung – zuerst bestimmt und in den Textstrom eingefügt werden. Der ursprüngliche von Knuth und Plass entwickelte Algorithmus umfasst noch keinen Seitenumbruch; er kann jedoch erweitert werden, indem er mit einem Paginierungs-Algorithmus interagiert, wie etwa mit dem von Plass in seiner Dissertation vorgestellten.^[3][4]

Gewöhnlicherweise wird die Kostenfunktion bei dieser Technik so angepasst, dass der verbleibende Abstand am Ende eines Absatzes nicht mitgezählt wird, sodass ein Absatz ohne Strafpunkte mitten in der Zeile aufhören kann. Dieselbe Technik kann zudem erweitert werden, um weitere Faktoren wie die Anzahl der Zeilen oder Kosten für den Umbruch eines langen Wortes zu berücksichtigen.^[2]

Eine naive Suche nach der minimalen „Badness“, bei der jede mögliche Kombination von Zeilenumbrüchen ausprobiert wird, würde eine unpraktikable Zeitkomplexität von ${\displaystyle O(2^{n})}$ haben. Der klassische dynamische Programmieransatz von Knuth und Plass zur Lösung dieses Minimierungsproblems ist im Worst-Case ein ${\displaystyle O(n^{2})}$-Algorithmus, läuft in der Praxis meist viel schneller, beinahe in linearer Zeit, also ${\displaystyle O(n)}$.^[5]

Die Suche nach dem Knuth-Platt-Optimum lässt sich als Spezialfall des „Least-Weight Subsequence“-Problemsdarstellen, welches mit einer Zeitkomplexität von ${\displaystyle O(n)}$ gelöst werden kann.^[6] Dies kann unter anderem mit dem SMAWK-Algorithmus gelöst werden.^[7][8]

Für den Eingabetext

AAA BB CC DDDDD

mit einer Zeilenlänge von 6 würde ein Greedy-Algorithmus (ein „gieriger“ Algorithmus), der so viele Wörter, wie möglich in eine Zeile setzt, bevor er zur nächsten springt, folgendes Ergebnis liefern:

------    Zeilenbreite: 6
AAA BB    Verbleibender Platz: 0
CC        Verbleibender Platz: 4
DDDDD     Verbleibender Platz: 1

Die Summe der Quadrate des verbleibenden Platzes beträgt bei dieser Methode ${\displaystyle 0^{2}+4^{2}+1^{2}=17}$. Die optimale Lösung hingegen erzielt die kleinere Summe von ${\displaystyle 3^{2}+1^{2}+1^{2}=11}$:

------    Zeilenbreite: 6
AAA       Verbleibender Platz: 3
BB CC     Verbleibender Platz: 1
DDDDD     Verbleibender Platz: 1

• Breaking Paragraphs into Lines, die originale Arbeit von Knuth und Plass

1. ↑ ^{a b} The Knuth/Plass line-breaking Algorithm. Abgerufen am 30. März 2024. 
2. ↑ ^{a b c} Knuth, Donald E., Plass, Michael F.: Breaking paragraphs into lines. In: Software: Practice and Experience. Band 11, November 1981, S. 1119–1184, doi:10.1002/spe.4380111102. 
3. ↑ ^{a b} Jonathan, Fine: Line breaking and page breaking. 2000, abgerufen am 20. März 2026. 
4. ↑ Plass, Michael F.: Optimal Pagination Techniques for Automatic Typesetting Systems. 1981, abgerufen am 20. März 2026. 
5. ↑ Jacob N. Smith: knuth-plass-thoughts/plass.md at master · jaroslov/knuth-plass-thoughts. In: GitHub. 2. Oktober 2018, abgerufen am 20. März 2026. 
6. ↑ Robert Wilber: The concave least-weight subsequence problem revisited. In: Journal of Algorithms. Band 9, Nr. 3, September 1988, S. 418–425, doi:10.1016/0196-6774(88)90032-6 (elsevier.com [abgerufen am 20. März 2026]). 
7. ↑ Robert Wilber: The concave least-weight subsequence problem revisited. In: Journal of Algorithms. Band 9, Nr. 3, September 1988, S. 418–425, doi:10.1016/0196-6774(88)90032-6 (elsevier.com [abgerufen am 20. März 2026]). 
8. ↑ Zvi Galil, Kunsoo Park: A linear-time algorithm for concave one-dimensional dynamic programming. In: Information Processing Letters. Band 33, Nr. 6, Februar 1990, S. 309–311, doi:10.1016/0020-0190(90)90215-J (elsevier.com [abgerufen am 20. März 2026]).