Premium
Breaking paragraphs into lines
Author(s) -
Knuth Donald E.,
Plass Michael F.
Publication year - 1981
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380111102
Subject(s) - paragraph , backtracking , computer science , line (geometry) , simple (philosophy) , variety (cybernetics) , algorithm , quality (philosophy) , theoretical computer science , artificial intelligence , mathematics , world wide web , philosophy , geometry , epistemology
This paper discusses a new approach to the problem of dividing the text of a paragraph into lines of approximately equal length. Instead of simply making decisions one line at a time, the method considers the paragraph as a whole, so that the final appearance of a given line might be influenced by the text on succeeding lines. A system based on three simple primitive concepts called ‘boxes’, ‘glue’, and ‘penalties’ provides the ability to deal satisfactorily with a wide variety of typesetting problems in a unified framework, using a single algorithm that determines optimum breakpoints. The algorithm avoids backtracking by a judicious use of the techniques of dynamic programming. Extensive computational experience confirms that the approach is both efficient and effective in producing high‐quality output. The paper concludes with a brief history of line‐breaking methods, and an appendix presents a simplified algorithm that requires comparatively few resources.