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]

The line adjustment ratio measures the stretch or shrink required to make a candidate line fit. In the finite-glue model, let $N$ be its natural line width, $W$ its target typesetting line width, and $S$ and $T$ the total stretch and shrink coefficients of its typesetting glue. DefineIt is a dimensionless quantity: numerator and denominator are widths measured in the same units. Each glue item uses the same $r$, scaled by its own appropriate coefficient.^[ref]

For $N=30$, $S=4$ and $T=2$, targets 32 and 28 give $r=1/2$ and $r=-1$ respectively. If a nonzero width difference requires a coefficient total of zero, this model cannot make the adjustment. With ordinary bounded shrinkage, $r<-1$ asks the glue to shrink beyond its total allowance and is infeasible. Positive stretch is usually limited by an acceptable-quality threshold rather than by treating $r=1$ as an absolute geometric limit.

The typesetting badness scores spacing quality from the required adjustment, while a line-breaking fitness class records a coarser category for comparison with neighbouring lines. Neither measure alone incorporates every typesetting penalty.

The TeX line penalty, set by \linepenalty, enters the per-line base used to calculate typesetting demerits. In the ordinary finite calculation, a line with typesetting badness $b$ contributes $(\lambda +b{)}^2$ before breakpoint and neighbour-dependent terms, where $\lambda$ denotes the chosen line penalty.^[ref]

The algebra shows how it affects a candidate with $N$ lines:Changing $\lambda$ therefore changes both the line-count term and the way spacing costs enter the comparison.

For a chosen example, assume two feasible layouts have badness profiles $A=(30,0)$ and $B=(0,0,0)$, with all other costs zero and values below saturation. At $\lambda =10$,At $\lambda =100$,The preferred candidate changes. These are illustrative profiles and parameter values. Actual line breaking must also account for feasible endpoints, typesetting penalties and possible line-breaking fitness class changes.

A typesetting demerit is a contribution to the paragraph cost minimized by the Knuth-Plass line-breaking algorithm. It combines spacing quality with break preferences and, when applicable, costs involving neighbouring lines. Thus typesetting badness is one input to the cost rather than the entire objective.^[ref]

Consider the ordinary finite-penalty case in TeX, away from its integer saturation and recovery cases. Let $\lambda$ be the TeX line penalty, $b$ the typesetting badness and $p$ the typesetting penalty, with $-10000<p<10000$ and $|\lambda +b|<10000$. The base contribution isCharges for incompatible line-breaking fitness classes or consecutive hyphenated lines can then be added.

For an illustrative choice $\lambda =10$, $b=20$ and $p=5$, the base is $30^2+5^2=925$. Changing only $p$ to $-5$ gives $30^2-5^2=875$. If an adjacency charge of 100 applies, those become 1025 and 975. These are chosen example parameters, not asserted defaults.

Dynamic programming compares accumulated costs while retaining the dynamic programming state needed by future charges. The lowest-cost break considered alone need not produce the lowest-cost complete text paragraph.

A typesetting penalty expresses how desirable a candidate break is. In the Knuth-Plass line-breaking algorithm's paragraph representation, a penalty item can also have a width that is included only if that break is taken. This lets the model account for a hyphen introduced by hyphenation without printing it in the unbroken word.^[ref]

For example, suppose the material before an optional break uses 29 units and taking the break introduces a hyphen of width 2. At a typesetting line width of 30, the broken line needs $29+2=31$ units before any permitted adjustment of typesetting glue. Testing only the pre-hyphen width would wrongly declare it a fit. A finite penalty can discourage a break while still leaving it available when other choices are worse.

In TeX, values $p\ge 10000$ prohibit a penalty break and $p\le -10000$ force it. Intermediate positive values discourage and negative values encourage it. These are control conventions of the implementation, not physical lengths.^[ref]

The penalty value is an input to the typesetting demerit calculation. It is not the entire paragraph cost: typesetting badness, line-breaking fitness classes and consecutive hyphenated breaks can contribute too. Comparing two penalties alone therefore cannot choose the best text paragraph layout.