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.

Line breaking selects where a paragraph is divided into successive lines. The choice combines the widths of words and spaces with a measure of acceptable layout. A glyph advance supplies part of the underlying geometry, while the chosen breaks determine which content shares a CSS line box in a web layout.

A greedy algorithm can put as much content as possible on each line before proceeding. Greedy line breaking is easy to compute, but an early choice can leave an awkward short line later. Line breaking with squared slack cost gives a small, explicit example. Suppose four word widths are $3,2,2,5$, each internal space has width 1, and the permitted line width is 7, all in arbitrary consistent units. Greedy grouping produces line lengths $6,2,5$. An alternative grouping produces $3,5,5$. Charging squared unused width on every line except the last givesAn immediately fuller first line can therefore produce a worse paragraph under this particular cost.

Dynamic programming makes the global choice systematic. Let $D(j)$ be the minimum cost for the first $j$ words, and let ${\ell }_{ij}$ include words $i+1$ through $j$ and their internal spaces. For feasible lines, set $c(i,j)=(W-{\ell }_{ij}{)}^2$, except that $c(i,n)=0$ for the final line. ThenPossible break positions form a directed acyclic graph; a feasible line is an edge, so the same calculation finds a shortest path from the start to the end of the paragraph.

Donald E. Knuth and Michael F. Plass developed a richer paragraph-wide method using boxes, adjustable glue and penalties. Their Knuth-Plass line-breaking algorithm accommodates typographic choices beyond the fixed spaces and squared costs in the illustrative model above.^[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]

Michael F. Plass is a computer scientist whose work connects typography with mathematical optimization. With Donald E. Knuth, he coauthored the 1981 paper that describes the Knuth-Plass line-breaking algorithm: choosing breaks for an entire paragraph with dynamic programming, allowing later text to influence earlier choices. The original byline places both authors in Stanford University's Computer Science Department.^[ref]

The authors' historical account credits Michael F. Plass with introducing feasible breakpoints into the developing algorithm in summer 1977, reducing the active possibilities considered. They report its implementation in the first complete version of TeX in March 1978. These dates describe the development of the method, rather than the later publication date.^[ref]

An illustrative spacing calculation shows one ingredient of the model. Suppose fixed boxes total 24 width units and two spaces each have normal width 3 and stretchability 2. Their natural total width is 30. For a target width of 32, the adjustment ratio is $(32-30)/(2+2)=1/2$; each space becomes $3+(1/2)2=4$, giving $24+4+4=32$. This original numerical example shows proportional stretching, before the paragraph-wide choice of breaks.

The full method also represents break preferences with penalties and accounts for relevant relationships between successive lines. Line breaking with squared slack cost is a useful simpler model for understanding global choices, while the published Knuth-Plass line-breaking algorithm handles adjustable spacing and additional preferences.^[ref]

TeX is Donald E. Knuth's programmable system for typography, particularly mathematical typesetting. A document supplies text and instructions; TeX macros and TeX primitives build material whose dimensions determine the eventual page layout. Computer fonts supply glyphs and font metrics, while line breaking selects how a text paragraph is divided. The Knuth-Plass line-breaking algorithm is one of the system's central layout methods.^[ref]

A TeX format supplies a prepared collection of definitions. Plain TeX and LaTeX provide different document interfaces built on TeX technology. For example, in Plain TeX the input $\sqrt{2}$\bye requests a square root expression, $\sqrt{2}$, and ends the document. The computer font, glyph positioning and mathematical typesetting rules determine the printed geometry; the source characters alone are not a picture of the result.

The TeXbook by Donald E. Knuth is the system's user and reference manual. TeX source code by Donald E. Knuth exposes the implementation as a documented computer program, making the paragraph algorithm and its numerical conventions inspectable.^[ref]

A typesetting box is a piece of material treated as one unbreakable item at a given stage of line breaking. The simple paragraph model assigns it a width. A word already assembled from glyphs, or a small diagram placed within text, can be represented by such an item.^[ref]

For example, three boxes of widths 8, 6 and 10 separated by two spaces of width 3 occupy $8+3+6+3+10=30$. Keeping the boxes fixed while changing only the spaces is the model used by typesetting glue. If hyphenation makes an internal split available, the word must instead be represented with that discretionary break; a single indivisible box would hide the choice.

A box's width describes layout advance, which need not equal the exact ink extent of its glyphs. A more complete TeX box also has height and depth relative to a text baseline. These measurements allow boxes to be combined while maintaining baseline geometry.^[ref] The CSS box model uses its own rules for content, padding, borders and margins; interpreting every CSS box as an indivisible paragraph item would lose those distinctions.

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.

The typesetting line width is the horizontal measure that a layout assigns to a particular line. It supplies a target for text justification and a fitting constraint for line breaking. Write it as $W_j$ when it can depend on line number $j$. The Knuth-Plass line-breaking algorithm permits a sequence of target widths, rather than requiring the entire text paragraph to be rectangular.^[ref]

For example, suppose a text column is 40 units wide and first-line indentation reserves 10 units on its first line. ThenWith a fixed gap of width 2, three typesetting boxes of widths 12, 10 and 8 use $12+2+10+2+8=34$ units. They exceed the first line's available width, although they fit a later line in the fixed-space model. When typesetting glue can shrink, feasibility must also account for that permitted shrinkage.

Width and line height measure different directions. Changing the font size can alter both the widths of the typesetting boxes and their vertical metrics, so preserving the same column width does not preserve the same breaks.

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.