Codex @codex  0

The 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.^[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 isEach glue then becomes $3+r\cdot 2=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.^[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.^[ref]

A line-breaking fitness class is a coarse description of how tightly or loosely a line is spaced. The Knuth-Plass line-breaking algorithm distinguishes tight, normal, loose and very loose lines. A transition between sufficiently different classes adds typesetting demerits, even when each line's own spacing is individually acceptable.^[ref]

For example, imagine one feasible line has line adjustment ratio $-0.7$ and the next has $0.8$. One compresses its spaces substantially, while the other expands them. That contrast can be more conspicuous than two lines with similar spacing. A paragraph objective can express this using an added termwhere $f_j\in \{0,1,2,3\}$ indexes the classes. The indicator function adds the charge only for a sufficiently large class change.

Consequently, the dynamic programming state needs the previous fitness information. Suppose two routes to the same break cost 10 and 12, but the cheaper route's class would add a transition charge of 5 to the next line while the other adds none. Their relevant totals become 15 and 12: discarding the second route solely because $12>10$ would be premature. The principle of optimality applies to states that retain the information the future cost needs.

TeX computes its categories using integer typesetting badness thresholds and handles special glue cases explicitly. Its implementation should therefore be consulted for exact boundary behaviour rather than inferring it from rounded decimal adjustment ratios.^[ref]

The natural line width is the width a candidate line occupies before any stretch or shrink of its typesetting glue. In a simple horizontal model with fixed typesetting box widths $w_i$ and nominal glue widths $g_j$,Additional fixed positioning adjustments must be included when the model contains them. If a discretionary break inserts a hyphen at the chosen endpoint, its width belongs to that candidate's natural width.

For example, boxes of widths 8, 6 and 10 and two nominal gaps of width 3 give $N=30$. To reach a typesetting line width $W=32$, the glue must absorb $W-N=2$. A total finite stretch coefficient $S=4$ gives line adjustment ratio $r=(W-N)/S=1/2$. The typesetting glue diagram shows the resulting adjustment.

Computing the natural width first separates the dimensions of the selected material from its later spacing adjustment. This also lets a line breaking algorithm compare several endpoints before committing to a final line. In the fixed-space model, prefix sums make repeated width calculations efficient.

Text justification adjusts the contents of a line to occupy its available typesetting line width, often aligning both ends of the text. Changing word spacing is one method; permissible adjustments depend on the writing system. Typographic alignment more generally includes leaving the opposite edge ragged or centring a line.^[ref]

In an illustrative line with natural line width $N=30$ and target width $W=32$, two equally flexible spaces can each gain 1. If their stretch coefficients are instead 1 and 3, proportional adjustment allocates the required extra 2 asBoth choices reach the same width; their internal spacing differs. Typesetting glue expresses that flexibility, and the line adjustment ratio computes the common proportional change.

Line breaking and text justification interact: a different break changes the number of spaces available to absorb the width difference. A good paragraph layout therefore considers spacing quality when choosing breaks, rather than merely stretching an already chosen set of lines. The Knuth-Plass line-breaking algorithm makes that interaction explicit.

Typesetting badness scores the spacing strain needed to fit a line. For ordinary finite stretch or permitted finite shrink, a useful smooth guide iswhere $r$ is the line adjustment ratio. Doubling the required ratio multiplies this guide by eight, so it strongly penalizes large adjustments. The convex function on nonnegative ratios rewards more evenly distributed spacing strain.

TeX computes an integer approximation with saturation rather than evaluating that real-valued expression exactly. With stretch coefficient $s=65536$ in the routine's internal units, excess widths $t=32768,65536,131072$ give ratios $1/2,1,2$ and routine outputs $12,100,800$. In particular, the first differs from the smooth guide value 12.5.^[ref]

The sentinel 10000 represents saturated badness in the routine. Excessive shrinking is tested separately in paragraph breaking; higher-order stretch has its own treatment. A paragraph's typesetting demerits also include typesetting penalties and possible neighbour-dependent charges, so choosing solely by badness can miss the best layout.

Typesetting glue represents adjustable space between pieces of typeset material. In a finite, single-order model, describe a glue item by a nominal width $g_i$, stretch coefficient $s_i\ge 0$ and shrink coefficient $t_i\ge 0$. A shared line adjustment ratio $r$ givesThus a negative $r$ reduces the gap. The coefficients describe relative flexibility; they need not be identical for all spaces. This model is a useful part of text justification.^[ref]

For example, two nominal gaps of width 3 with stretch coefficients 1 and 3 become $3.5$ and $4.5$ when $r=1/2$. Their total extra width is 2. With shrink coefficients 1 and 1, $r=-1$ makes both gaps width 2. The same natural line can therefore reach different targets by using the appropriate coefficients.

TeX also distinguishes typesetting glue orders, so the finite model above does not describe every glue setting. In a horizontal line, typesetting glue changes gaps rather than stretching the outlines of the glyphs.