= Knuth-Plass line-breaking algorithm
{c}
{wiki=Knuth–Plass_line-breaking_algorithm}
The \b[Knuth-Plass line-breaking algorithm] chooses paragraph breaks using <dynamic programming> over a representation of the material as <typesetting boxes>, <typesetting glue> and <typesetting penalties>. Boxes supply unbreakable widths; glue supplies normal spacing together with stretch and shrink allowances; penalties express preferences about permitted breaks and can account for a hyphen added when a break is taken.<Breaking paragraphs into lines by Donald E. Knuth and Michael F. Plass>[pp.1119–1122, summary and formulation]{ref}
<Text justification> makes the glue geometry useful. In an illustrative line, suppose box widths total 24 and two glues each have normal width 3 and stretch allowance 2. To fill width 32, the <line adjustment ratio> is
$$
\boxed{r=\frac{32-(24+3+3)}{2+2}=\frac12.}
$$
Each glue then becomes $3+r\cdot2=4$, giving $24+4+4=32$. This example demonstrates proportional stretching; it is one ingredient of paragraph optimization.
The <dynamic programming state> retains information needed to score later choices. In particular, a <line-breaking fitness class> records a spacing category, allowing an abrupt change between neighbouring lines to affect the cost. Break position alone would discard that relevant history. The original active nodes include line number and fitness class, with the best accumulated demerits stored as their value.<Breaking paragraphs into lines by Donald E. Knuth and Michael F. Plass>[pp.1158–1159, active nodes, line numbers and fitness classes]{ref}
The <line breaking with squared slack cost> example isolates break selection with fixed <word spacing>. Here, adjustable <typesetting glue> and <typesetting penalties> participate in the paragraph optimization. <Donald E. Knuth> and <Michael F. Plass>'s 1981 paper documents the method and its development in the <TeX> project.<Breaking paragraphs into lines by Donald E. Knuth and Michael F. Plass>[pp.1175–1176, authors' historical account]{ref}
Back to article page
