{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T00:19:49Z","timestamp":1773706789064,"version":"3.50.1"},"reference-count":47,"publisher":"Wiley","issue":"11","license":[{"start":{"date-parts":[[2006,10,27]],"date-time":"2006-10-27T00:00:00Z","timestamp":1161907200000},"content-version":"vor","delay-in-days":9126,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[1981,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 \u2018boxes\u2019, \u2018glue\u2019, and \u2018penalties\u2019 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\u2010quality output. The paper concludes with a brief history of line\u2010breaking methods, and an appendix presents a simplified algorithm that requires comparatively few resources.<\/jats:p>","DOI":"10.1002\/spe.4380111102","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T11:52:24Z","timestamp":1163764344000},"page":"1119-1184","source":"Crossref","is-referenced-by-count":95,"title":["Breaking paragraphs into lines"],"prefix":"10.1002","volume":"11","author":[{"given":"Donald E.","family":"Knuth","sequence":"first","affiliation":[]},{"given":"Michael F.","family":"Plass","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,27]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Computer Typesetting: Experiments and Prospects","author":"Barnett Michael P.","year":"1965"},{"key":"e_1_2_1_3_2","first-page":"121","article-title":"Look! No hands!","volume":"57","author":"Duncan C. J.","year":"1964","journal-title":"The Penrose Annual"},{"key":"e_1_2_1_4_2","volume-title":"Computers and Intractability","author":"Garey Michael R.","year":"1979"},{"key":"e_1_2_1_5_2","volume-title":"Dynamic Programming","author":"Bellman Richard","year":"1957"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.42.0136"},{"key":"e_1_2_1_7_2","volume-title":"TEX and METAFONT: New Directions in Typesetting","author":"Knuth Donald E.","year":"1979"},{"key":"e_1_2_1_8_2","first-page":"144","volume-title":"Kinder\u2010 und Hausm\u00e4rchen, first published in Berlin, 1812. For the history of this story see Heinz R\u00f6lleke, Die Altese M\u00e4rchensammlung der Br\u00fcder Grimm","author":"Ludwig Jakob","year":"1979"},{"key":"e_1_2_1_9_2","first-page":"133","article-title":"Computer typesetting: an evaluation of the problems","volume":"7","author":"Duncan C. J.","year":"1963","journal-title":"Printing Technology"},{"key":"e_1_2_1_10_2","volume-title":"Seminumerical Algorithms, Vol. 2 of The Art of Computer Programming","author":"Knuth Donald E.","year":"1981"},{"key":"e_1_2_1_11_2","unstructured":"A.Frey Manuel Nouveau de Typographie Paris(1835) 2 vols."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-9984-5"},{"key":"e_1_2_1_13_2","unstructured":"Donald E.Knuth \u2018BLAISE a preprocessor for PASCAL \u2019 file BLAISE.DEK[up doc] at SU\u2010AI on the ARPA network (March1979). The program itself is on file BLAISE.SAI[tex dek]."},{"key":"e_1_2_1_14_2","unstructured":"Donald E.Knuth Tau Epsilon Chi: A System for Technical Text book in preparation."},{"key":"e_1_2_1_15_2","first-page":"138","volume-title":"Correct Composition, Vol. 2 of The Practice of Typography","author":"Theodore Low De Vinne","year":"1901"},{"key":"e_1_2_1_16_2","first-page":"80","article-title":"On Modern Typography","volume":"4","author":"Shaw George Bernard","year":"1940","journal-title":"The Dolphin"},{"key":"e_1_2_1_17_2","volume-title":"Historical Catalogue of the Printed Editions of Holy Scripture in the library of The British and Foreign Bible Society","author":"Darlow T. H.","year":"1911"},{"key":"e_1_2_1_18_2","volume-title":"The Greatest Polyglot Bibles","author":"Hall Basil","year":"1966"},{"key":"e_1_2_1_19_2","unstructured":"Jim\u00e9nezde Cisneros sponsor Uetus testamentum multiplici lingua nunc primo impressum Industria Arnaldi Guillelmi de Brocario in Academia Complutensi 1522. [The printing was completed in 1517 but papal permission to publish this book was delayed for several years.]"},{"key":"e_1_2_1_20_2","unstructured":"Aug. Giustiniani Psalterium Genoa 1516."},{"key":"e_1_2_1_21_2","unstructured":"Benedictus Arias Montanus editor Biblia Sacra Hebraice Chaldaice Gr\u0153ce & Latine Christoph. Plantinus Antwerp 1569\u20131573."},{"key":"e_1_2_1_22_2","volume-title":"Biblia Sacra Polgyglotta","author":"Waltonus Brianus","year":"1657"},{"key":"e_1_2_1_23_2","volume-title":"Biblia Sacra Gr\u0153ce, Latine & Germanice","author":"Wolder David","year":"1596"},{"key":"e_1_2_1_24_2","first-page":"354","volume-title":"Roots of Scientific Thought","author":"Houghton Walter E.","year":"1957"},{"key":"e_1_2_1_25_2","volume-title":"Mechanick Exercises","author":"Moxon Joseph","year":"1683"},{"key":"e_1_2_1_25_3","unstructured":"Reprinted by the Typothetae of New York 1896 with preface and notes byT. L.De Vinne;"},{"key":"e_1_2_1_25_4","volume-title":"Mechanick Exercises","year":"1958"},{"key":"e_1_2_1_25_5","unstructured":"but these reprints do not capture the full feeling of the original with its less sumptuous seventeenth\u2010century workmanship. Quoted passages are from vol. 2 pp.214\u2013215 226 245 248."},{"key":"e_1_2_1_26_2","unstructured":"D. G.Berri The Art of Printing London 1864."},{"key":"e_1_2_1_27_2","volume-title":"The Art of Spacing","author":"Bartels Samual A.","year":"1926"},{"key":"e_1_2_1_28_2","unstructured":"G. P.Bafour A. R.Blanchard andF. H.Raymond \u2018Automatic Composing Machine \u2019 U.S. Patent 2762485 September 11 1956."},{"key":"e_1_2_1_28_3","unstructured":"(See also British patent 771551 and"},{"key":"e_1_2_1_28_4","unstructured":"French patent 1103000.)"},{"issue":"2","key":"e_1_2_1_29_2","first-page":"65","article-title":"A new method for text composition\u2014The BBR System","volume":"5","author":"Bafour G.","year":"1961","journal-title":"Printing Technology"},{"key":"e_1_2_1_30_2","volume-title":"Nroff\/Troff User's Manual","author":"Ossanna Joseph F.","year":"1975"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPC.1972.6591969"},{"key":"e_1_2_1_32_2","volume-title":"Computer Composition using PAGE\u20101","author":"Pierson John","year":"1972"},{"key":"e_1_2_1_33_2","unstructured":"Information International Inc. PAGE\u20103Composition Language privately distributed. First edition October 31 1975; second edition October 20 1976. The language is sometimes called \u2018PAGE\u2010III\u2019 because of the company that created it."},{"key":"e_1_2_1_34_2","first-page":"176","volume-title":"Advances in Computer Typesetting [Proceedings of the 1966 International Computer Typesetting Conference]","author":"Cooper P. I.","year":"1967"},{"key":"e_1_2_1_35_2","volume-title":"[Untitled] Moderators' summaries of the papers presented at the International Computer Typesetting Conference at the University of Sussex","year":"1966"},{"key":"e_1_2_1_36_2","volume-title":"\u2018Justification with fewer hyphens,\u2019 Rainbow Memo 170","author":"Pringle Alison M.","year":"1980"},{"key":"e_1_2_1_37_2","volume-title":"Heuristics for the line division problem in computer justified text","author":"Samet Hanan","year":"1980"},{"key":"e_1_2_1_38_2","first-page":"176","volume-title":"Advances in Computer Typesetting","author":"Parks H. D.","year":"1967"},{"key":"e_1_2_1_39_2","first-page":"143","volume-title":"Proc. ASIS Workshop on Computer Composition","author":"Parks Herman","year":"1971"},{"key":"e_1_2_1_40_2","first-page":"88","volume-title":"Paragraphs on Printing","author":"Rogers Bruce","year":"1943"},{"key":"e_1_2_1_41_2","unstructured":"U.S. Government Printing Office Style Manual Washington D.C. 1973. The quote is from rule 22 (catch?)."},{"key":"e_1_2_1_42_2","unstructured":"Michael J.ClancyandDonald E.Knuth \u2018A programming and problem\u2010solving seminar \u2019 report STAN\u2010CS\u201077\u2010606 Computer Science Department Stanford University April1977 85\u201388."},{"key":"e_1_2_1_43_2","unstructured":"Michael F.Plass \u2018Optimal pagination techniques for automatic typesetting systems \u2019 Ph.D. thesis Stanford University June1981."}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.4380111102","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.4380111102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T05:59:24Z","timestamp":1699768764000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.4380111102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981,11]]},"references-count":47,"journal-issue":{"issue":"11","published-print":{"date-parts":[[1981,11]]}},"alternative-id":["10.1002\/spe.4380111102"],"URL":"https:\/\/doi.org\/10.1002\/spe.4380111102","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"value":"0038-0644","type":"print"},{"value":"1097-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981,11]]}}}