3 ms·

Breaking Paragraphs into Lines [pdf] (1981)

37 points by Smaug123 10mo ago

qmr 10mo ago
(1981)
Smaug123 10mo ago
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.
deleted 10mo ago
[deleted]
omnicognate 10mo ago
Reimagined for the AI era by tom7: https://tom7.org/bovex/ https://tom7.org/bovex/
jll29 10mo ago
As a companion: 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 https://www.tug.org/docs/liang/liang-thesis.pdf
karlwilcox 10mo ago
I recall implementing this algorithm in C for a new fangled Canon laser printer as my individual project for my CS degree in 1983!
lambdaone 10mo ago
I have always loved this work. A classic example of the effective application of mathematical principles to a computing problem.
mjoin 10mo ago
also more recently https://dl.acm.org/doi/abs/10.1145/3704268.3742696 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."

37 points by Smaug123 10mo ago

qmr 10mo ago

(1981)

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.

deleted 10mo ago

[deleted]

omnicognate 10mo ago

Reimagined for the AI era by tom7: https://tom7.org/bovex/ https://tom7.org/bovex/

jll29 10mo ago

As a companion: 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 https://www.tug.org/docs/liang/liang-thesis.pdf

karlwilcox 10mo ago

I recall implementing this algorithm in C for a new fangled Canon laser printer as my individual project for my CS degree in 1983!

lambdaone 10mo ago

I have always loved this work. A classic example of the effective application of mathematical principles to a computing problem.

mjoin 10mo ago

also more recently https://dl.acm.org/doi/abs/10.1145/3704268.3742696 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."