Breaking Paragraphs into Lines [pdf] (1981)(gwern.net)
gwern.net
Breaking Paragraphs into Lines [pdf] (1981)
https://gwern.net/doc/design/typography/tex/1981-knuth.pdf
8 comments
This is the paper in which Knuth and Plass define the bones of the layout algorithm behind TeX. The Knuth-Plass algorithm decides how wide spaces should be on each line and which choices of hyphenation out of some predefined set should be used to lay out a paragraph. It's super readable and generally quite joyful. Knuth describes TeX as a "labor of love", and it shines through that paper.
Reimagined for the AI era by tom7: https://tom7.org/bovex/
I recall implementing this algorithm in C for a new fangled Canon laser printer as my individual project for my CS degree in 1983!
also more recently https://dl.acm.org/doi/abs/10.1145/3704268.3742696
"Paragraph justification is based primarily on shrinking or stretching the interword blanks. While the blanks on a line are all scaled by the same amout, the amount in question varies from line to line. The quality of a paragraph's typographic color largely depends on the aforementioned variation being as small as possible. Yet, TEX'S paragraph justification algorithm addresses this problem in a rather coarse fashion. In this paper, we propose a refinement to the algorithm allowing to improve the situation without disturbing the general behavior of the algorithm too much, and without the need for manual intervention. We analyze the impact of our refinement on a large number of experiments through several statistical estimators. We also exhibit a number of typographical traits relatedto whitespace distribution that we believe may contribute to our perception of homogeneousness."
"Paragraph justification is based primarily on shrinking or stretching the interword blanks. While the blanks on a line are all scaled by the same amout, the amount in question varies from line to line. The quality of a paragraph's typographic color largely depends on the aforementioned variation being as small as possible. Yet, TEX'S paragraph justification algorithm addresses this problem in a rather coarse fashion. In this paper, we propose a refinement to the algorithm allowing to improve the situation without disturbing the general behavior of the algorithm too much, and without the need for manual intervention. We analyze the impact of our refinement on a large number of experiments through several statistical estimators. We also exhibit a number of typographical traits relatedto whitespace distribution that we believe may contribute to our perception of homogeneousness."
I have always loved this work. A classic example of the effective application of mathematical principles to a computing problem.
(1981)
[deleted]
Frank Liang's thesis on hyphenation (developed for/used by TeX), supervised by Donald E. Knuth:
Liang, Franklin Mark (1983) WORD HY-PHEN-A-TION BY COM-PUT-ER, Ph.D. thesis, Stanford University. https://www.tug.org/docs/liang/liang-thesis.pdf