Breaking Paragraphs into Lines [pdf] (1981)

(gwern.net)

35 points | by Smaug123 6 days ago

7 comments

  • jll29 10 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 11 hours ago
    Reimagined for the AI era by tom7: https://tom7.org/bovex/
  • karlwilcox 9 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 8 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)