Breaking Paragraphs into Lines [pdf] (1981)

(gwern.net)

35 points | by Smaug123 6 days ago

8 comments

  • jll29 18 hours 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

  • Smaug123 6 days 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.
  • omnicognate 18 hours ago
    Reimagined for the AI era by tom7: https://tom7.org/bovex/
  • mjoin 6 hours ago
    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."

  • karlwilcox 16 hours 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 16 hours ago
    I have always loved this work. A classic example of the effective application of mathematical principles to a computing problem.
  • qmr 6 days ago
    (1981)