Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Introduction
I
T
E
X : standard de facto en matière de qualité typographique
I
En particulier : l’algorithme de mise en forme de paragraphe
N.b. « paragraphe » vs. « alinéa » hors sujet ici ; cf. [Savary1, 2023] et [Savary2, 2023]
I
Le « Knuth-Plass »
I
Développé entre 1977 et 1982
I
« Probablement l’algorithme le plus intéressant de T
E
X »
— Donald Knuth
Le Knuth-Plass fait peur…
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 2/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Pourquoi ?
I
Littérature de référence
I
Breaking Paragraphs into Lines [Knuth, 1981] : 66 pages
Première mouture, avec formalisation algébrique, exemples et applications
I
T
E
X : the Program [Knuth, 1986] : 28 pages (+ césure = 58)
À jour, entrelacée avec le reste de T
E
X
I
L’algorithme de Knuth-Plass n’est pas… un algorithme !
1.4 Un problème de « plus court chemin » single-pair dans un graphe orienté acyclique
[Dijkstra, 1959] (1956), A* [Hart, 1968], etc.
2.4 Une optimisation de type « programmation dynamique » (1950)
[Bellman, 1954]
3.4 Un critère de qualité (fonction de coût) spécique à T
E
X
Compatible avec la programmation dynamique !
4.8 Une implémentation (documentée) très impérative, truée de petites optimisations de très
bas niveau
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 3/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Au Programme
Généralités : Coupure de Ligne, Tolérance, Passes
Représentation : Graphe des Solutions
Qualité : Pénalités, Démérites, Fonction de Coût
Optimisation : Programmation Dynamique
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 5/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Mise en Forme de Paragraphe : Ingrédients
I
Coupure de ligne
I
4 Implicite : espaces inter-mot et points de césure [Liang, 1983]
I
8 Explicite : « pénalités » (\penalty)
I
8 Remarque : césures + ligatures = « discrétionnaires »
\discretionary{-}{}{}, \discretionary{f-}{fi}{ffi}
I
Largeur de ligne
I
4 « Glue » élastique inter-mot : dépend de la police utilisée
I
8 Micro-typographie : crénage élastique (tracking), saillie (crénage de marge), chasse
élastique, etc.
I
Remarque : boîtes + glue + pénalités = modèle très expressif
I
4 Justication
I
8 Autres dispositions, saillie rudimentaire, code, etc. Cf. [Knuth, 1981]
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 6/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Notion de « Tolérance »
I
Complexité théorique exponentielle
I
Pour n points de coupures possibles, 2
n
solutions
I
La plupart sont absurdes
I
Élasticité sous contrôle : 1/3 corps de police +1/2 −1/3
I
Exemple : police 18pt ⇒ 6pt, max 9pt (6 + 3), min 4pt (6 − 2)
I
Réduit considérablement le nombre de solutions raisonnables
I
Critères esthétiques ⇒ recommandations
I
Cependant, limite stricte en compression
I
Tolérance selon T
E
X (« badness »)
I
100 ∗ |% d’élasticité utilisée|
3
I
+∞ si compression maximale ou étirement ≥ 465% (10 000)
I
Dans l’exemple précédent : 6 + 4.65 ∗3 ≈ 20pt, soit plus de trois fois l’espacement normal
I
Remarque : T
E
X peut être inniment tolérant…
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 7/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Le Knuth-Plass en Trois Passes (max)
1. Sans césure, avec \pretolerance
I
Plain/L
A
T
E
X : 100 par défaut (i.e. 100% de l’élasticité disponible)
I
\pretolerance=-1 pour court-circuiter la passe 1
2. Avec césure et \tolerance
I
Plain/L
A
T
E
X : 200 par défaut (i.e. 126% de l’élasticité disponible)
I
Dans l’exemple précédent : 6pt, max 9,78pt (9), min 3,48pt (4)
3. Seulement si \emergencystretch > 0
I
Toujours avec césure et \tolerance
I
Quand ça se passe mal
I
T
E
X produit des lignes débordantes (overfull box)
I
\sloppy (L
A
T
E
X) : \tolerance=9999 \emergencystretch=3em
I
Toujours préférer \emergencystretch à \tolerance=10000 (+∞)
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 8/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Au Programme
Généralités : Coupure de Ligne, Tolérance, Passes
Représentation : Graphe des Solutions
Qualité : Pénalités, Démérites, Fonction de Coût
Optimisation : Programmation Dynamique
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 9/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Graphe des Solutions
Exemple
Viens mon chou sur mes ge-noux avec tes
jou-joux et tes bi-joux. Em-porte des
cailloux pour lan-cer sur les hi-boux
pleins de poux. Un deux trois nous irons
au bois. Quat' cinq six cueillir des
ce-rises. Sept huit neuf dans mon pa-nier
neuf. Dix onze douze elles se-ront toutes
rouges.
I
Largeur : 288pt (10,12cm)
I
2
e
passe (\pretolerance=-1)
I
Espacement recommandé seulement
(\tolerance=100)
Viens
bi-joux.
Em-porte
Em-
porte
poux.
Un
Un
deux
ce-
rises.
ce-rises.
Sept
Sept
huit
elles
se-ront
se-
ront
se-ront
toutes
toutes
rouges.
•
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 10/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Remarques
I
Graphe vs. arbre (partage de noeuds)
I
Paragraphe rectangulaire
I
Ou conserver le numéro de ligne
I
Branches mortes / arbre mort
I
Importance d’une tolérance ajustable
I
Algorithmes gloutons : ligne par ligne
I
First-Fit, Last-Fit
I
Best-Fit (mais dene « best »…)
I
min(% élasticité ou badness)
*
I
Nombreux autres choix possibles
I
Avantages
I
rapides
I
peu coûteux
I
Inconvénients
I
Pas de notion de qualité globale
I
Sensibles aux branches mortes
Viens
bi-joux.
Em-porte
35
Em-
porte
29
poux.
Un
13
Un
deux
28
6
ce-
rises.
20
ce-rises.
Sept
13
15
Sept
huit
95
elles
se-ront
8
se-
ront
16
94
se-ront
toutes
0,5
toutes
rouges.
4
•
0
0
0
0
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 11/27
The area of
a circle is a mean
proportional between any
two regular and similar poly-
gons of which one circumscribes
it and the other is isoperimetric
with it. In addition, the area of the
circle is less than that of any circum-
scribed polygon and greater than that
of any isoperimetric polygon. And
further, of these circumscribed poly-
gons, the one that has the greater
number of sides has a smaller area
than the one that has a lesser num-
ber; but, on the other hand, the
isoperimetric polygon that
has the greater number of
sides is the larger.
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Au Programme
Généralités : Coupure de Ligne, Tolérance, Passes
Représentation : Graphe des Solutions
Qualité : Pénalités, Démérites, Fonction de Coût
Optimisation : Programmation Dynamique
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 12/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Pénalités Locales
Même localement, l’élasticité n’est pas le seul critère esthétique
I
Quatre types de « pénalités » locales
1. Rappel : \penalty (explicite)
2. 0 ≤ \linepenalty (10) ≤ 100 : jouer sur le nombre de lignes
3. −10 000 ≤ \hyphenpenalty (50) ≤ 10 000
4. −10 000 ≤ \exhyphenpenalty (50) ≤ 10 000 : jouer sur la césure
I
Remarques
I
±10 000 ⇐⇒ ±∞ (coupures interdites ou obligatoires)
I
Rappel : césure =⇒ discrétionnaires
ge-noux → "ge" \discretionary{-}{}{} "noux" → \hyphenpenalty
ef-ficace → "e" \discretionary{f-}{fi}{ffi} "cace" → \hyphenpenalty
plate-bande → "plate-" \discretionary{}{}{} "bande" → \exhyphenpenalty
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 13/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Démérites Locaux
Élasticité (badness) + pénalités locales =⇒ « démérites » locaux
1. Coupure interdite (ou badness > tolérance) : n/a
2. Coupure pénalisante : (pénalité de ligne + badness)
2
+ pénalité
2
3. Coupure souhaitée : (pénalité de ligne + badness)
2
− pénalité
2
4. Coupure obligatoire : (pénalité de ligne + badness)
2
I
Remarques
I
Compromis élasticité / césure :
3
q
(
√
10
2
+ 50
2
− 10)/100 = 74%
I
Pénalité (innie) non prise en compte en cas de coupure obligatoire
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 14/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Application au Best-Fit
I
Rappel : min(badness)
*
I
min(démérites locaux)
*
La césure est plus pénalisante que
l’étirement ici (71% < 74%)
Viens
bi-joux.
Em-porte
2063 (71%)
Em-
porte
4027 (-66%)
poux.
Un
512
Un
deux
1470
251
ce-
rises.
3416
ce-rises.
Sept
521
608
Sept
huit
11048
elles
se-ront
320
se-
ront
3161
13269
se-ront
toutes
111
toutes
rouges.
188
•
100
100
100
100
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 15/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Démérites Globaux
Ajoutés aux démérites locaux d’une ligne à la suivante
I
Jouer sur la césure
I
0 ≤ \doublehyphendemerits (10 000) ≤ 10 000 : échelles de césure
I
0 ≤ \finalhyphendemerits (5 000) ≤ 10 000 : césure nale (avant-dernière ligne)
I
Jouer sur la diérence d’étalement
I
Quatre classes d’étalement (« tness classes »)
I
0 ≤ \adjdemerits (10 000) ≤ 10 000 : démérites d’adjacence
0%
-100% -50% 50% 100%
serrée décente
lâche très lâche
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 16/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Application
I
Rappel : Best-Fit / démérites locaux
*
I
Knuth-Plass
*
Note : ≡ Best-Fit / badness
I
Chemin problématique
*
I
Ainsi que plusieurs autres…
Viens
bi-joux.
Em-porte
lâche
Em-
porte
serrée
poux.
Un
lâche
Un
deux
serrée
décente
ce-
rises.
lâche
ce-rises.
Sept
serrée
lâche
Sept
huit
serrée
elles
se-ront
décente
se-
ront
serrée
lâche
se-ront
toutes
décente
toutes
rouges.
décente
•
décente
décente
décente
décente
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 17/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Remarques Finales
I
Démérites
I
locaux : esthétique horizontale
I
globaux : esthétique verticale
I
Paramétrage
I
local (horizontal) en termes de pénalités
I
global (vertical) en termes de démérites (pénalité / badness au carré)
I
Approche « globale » de T
E
X
En réalité, basée uniquement sur des comparaisons de lignes adjacentes…
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 18/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Au Programme
Généralités : Coupure de Ligne, Tolérance, Passes
Représentation : Graphe des Solutions
Qualité : Pénalités, Démérites, Fonction de Coût
Optimisation : Programmation Dynamique
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 19/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Contexte
Rappel : programmation dynamique (1950) [Bellman, 1954]
I
Principe général
1. Découpage du problème global en (plus petits) sous-problèmes
2. Résolution des sous-problèmes pour arriver à la solution globale
I
Remarque : « Diviser pour Régner » (divide and conquer)
I
Sous-problèmes indépendants les uns des autres.
I
Inapplicable ! Justier la n d’un paragraphe nécessite d’avoir justié le début…
I
Caractéristiques
1. Les sous-problèmes dépendent séquentiellement les uns des autres
I
Les sous-problèmes sont dénis récursivement les uns en fonction des autres
2. Le processus de résolution suit nécessairement cette séquence
I
La solution globale contient la séquence des sous-solutions
I
Complexité : 2
n
=⇒ n
2
=⇒ nw
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 20/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Qu’appelle-t-on « Sous-Problème » ?
I
Sous-problème n = s’occuper de la n
e
ligne ? Non !
I
Le « meilleur » choix pour une ligne ne l’est pas nécessairement pour l’ensemble
I
Aucune décision dénitive, mais un ensemble de solutions possibles
I
Sous-problème n = s’occuper des n premières lignes
I
trouver des solutions pour la ligne n en fonction des solutions trouvées pour les précédentes
ligne 1 ligne 2 ligne 3 ligne 4 ligne 5
ss-pb. 1 ss-pb. 2 ss-pb. 3 ss-pb. 4 ss-pb. 5
8
sous-pb. 2
sous-problème 3
sous-problème 4
sous-problème 5
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 21/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Conséquences sur le Graphe des Solutions
1. Résolution séquentielle des sous-problèmes
I
Construction du graphe progressive plutôt que préalable
I
= algorithmes gloutons
2. Aucune décision intermédiaire dénitive
I
Conservation des meilleures branches jusqu’au bout
I
6= algorithmes gloutons
3. Cependant : suppression des moins bons chemins
I
« Moins bons » avec certitude absolue !
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 22/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Élagage du Graphe
I
Conserver un seul accès, le meilleur,
à chaque noeud
I
Problème : les classes d’étalement
empêchent de dénir « meilleur »
I
Solution : des noeuds diérents par
classe d’étalement entrante
I
Nouveau graphe
*
I
Rappel : problème identique
(solution identique) pour des
paragraphes non rectangulaires
Viens
bi-joux.
Em-porte
Em-
porte
poux.
Un
Un
deux
Un
deux
ce-
rises.
ce-rises.
Sept
ce-rises.
Sept
Sept
huit
elles
se-ront
se-
ront
se-
ront
se-ront
toutes
toutes
rouges.
•
lâche
serrée
lâche
serrée
décente
lâche
serrée
lâche
lâche
serrée
lâche
serrée
décente
serrée
lâche
décente
lâche
lâchelâche
décente
décente
décente
décente
décente
décente décente
décente
décente
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 23/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Version Optimisée
Exemple
Viens mon chou sur mes ge-noux avec tes
jou-joux et tes bi-joux. Em-porte des
cailloux pour lan-cer sur les hi-boux
pleins de poux. Un deux trois nous
irons au bois. Quat' cinq six cueillir
des ce-rises. Sept huit neuf dans mon
pa-nier neuf. Dix onze douze elles
se-ront toutes rouges.
ligne décente
ligne lâche
ligne serrée
I
CQFD !
Viens
bi-joux.
Em-porte
Em-
porte
poux.
Un
Un
deux
Un
deux
ce-
rises.
ce-rises.
Sept
ce-rises.
Sept
Sept
huit
elles
se-ront
se-
ront
se-
ront
se-ront
toutes
toutes
rouges.
•
4027
4278
4886
4997
5097
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 24/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Bibliographie
Anéantir Michel (pour en Finir avec les Livres Moches)
Thomas Savary, Blog, 2023.
Le package lua-typo
Thomas Savary, exposé GUTenberg, 2023.
Breaking Paragraphs into Lines
Donald E. Knuth, Michael F. Plass.
Software – Practice and Experience, 11:1119–1184, 1981.
T
E
X: the Program
Donald E. Knuth.
Computers and Typsetting, Volume 2, Addison-Wesley, 1986.
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 25/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Bibliographie (cont.)
Word Hy-phen-a-tion by Com-put-er
Franklin M. Liang.
Stanford University Ph.D, STAN-CS-83-977, 1983.
The theory of dynamic programming
Richard Bellman.
Bulletin of the American Mathematical Society, 60 (6): 503–516, 1954.
A Note on Two Problems in Connexion with Graphs
Edsger W. Dijkstra.
Numerische Mathematik, 1:269–271, 1959.
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Peter Hart, Nils Nilsson, and Bertram Raphael
IEEE Transactions on Systems Science and Cybernetics, 4 (2): 100–7, 1968.
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 26/27
Introduction
Généralités
Représentation
Qualité Optimisation
Bibliographie
Bibliographie (cont.)
Etap
Didier Verna.
github/didierverna/etap.
Interactive and Real-Time Typesetting for Demonstration and Experimentation: Etap
Didier Verna.
TUGboat, 44 (2):242–248, 2023.
Etap: Experimental Typesetting Algorithms Platform
Didier Verna.
15
th
European Lisp Symposium, pp. 48–52, 2022.
Justication de paragraphe : le Knuth-Plass / Exposé GUTenberg, 11 Janvier 2024 – Didier Verna 27/27
