Beautiful line breaking

This paragraph was set by your browser, and set greedily: the browser puts words into a line while they fit and carries the next word over without thinking about what comes after. It is fast, but the right edge comes out ragged: one line reaches almost to the edge, another stops halfway because a long word did not fit. TeX, Donald Knuth’s program for typesetting books, does it differently: it looks at the whole paragraph and chooses the breaks so that all the lines are of roughly equal length. Below, this very paragraph is set both ways in a column whose width you can change.

On the left some lines have a deep gap at their right end; on the right the gaps are shallower but more numerous. The sum of squares of the shortfalls, a measure of how even the edge is, is never larger on the right, and the shortest line is usually noticeably longer than on the left. In justified mode the gap has to be handed out to the spaces, and in a narrow column they stretch four or five times their width whichever method is used. Searching over the whole paragraph with a cost that grows as the cube of the stretch, as TeX computes it, removes the worst lines: the most stretched space becomes noticeably narrower, and the scene shows the exact numbers for your browser and font. A narrow column cannot be justified without any holes at all: that needs hyphenation inside words.

On all 119 introductory paragraphs of this catalogue (in their Russian original), in a column of 35 characters, roughly what fits in a line on a phone, greedy setting and the best setting differ in 107 paragraphs. The sum of squares of the shortfalls falls from 35,615 to 30,107, and the shortest line across all paragraphs falls short of the edge not by 29 characters but by 15. In a column of 70 characters 65 paragraphs differ, and the gain is smaller: the wider the column, the more words per line and the easier it is for greed.

The idea

Breaking lines means choosing break points between words. Greedy breaking decides for each line separately and never revisits its decisions. Breaking “over the whole paragraph” gives each line a cost, the greater the shortfall the higher, and looks for the set of breaks with the smallest total cost. Break points are the vertices of a graph, possible lines are its edges, and the best set is the shortest path from the start of the paragraph to its end. The graph is acyclic, so the path is found in a single pass from left to right.

The cost is the square of the shortfall, not the shortfall itself, and this is not a whim. If the number of lines is fixed, the sum of the shortfalls of all lines but the last depends only on the length of the last line: everything else is determined by the column width, the number of lines and the length of the text. Such a cost says nothing about evenness. The square punishes one gap of twelve characters harder than two of six: 144 against 72.

What greedy breaking can do

Greedy breaking has an honest virtue, and it can be proved.

This “greedy stays ahead” argument is the same technique as in the article on greedy algorithms. But it says nothing about the evenness of the edge: greedy setting takes as much as it can into each line and leaves all the gap wherever the next word did not fit.

The graph of break points

Take a sentence from the introductory paragraph of the article on latencies, «Сложение двух чисел — треть наносекунды.» (“Adding two numbers is a third of a nanosecond.”), and a column of 19 characters. The places between words are numbered, and an arc from i to j is a line of the words between them, if it fits.

Greedy breaking follows the longest arcs: «Сложение двух чисел» fills the line completely, and «— треть» is left with a shortfall of 12, a cost of 144. The best path pays 36 twice: «Сложение двух / чисел — треть / наносекунды.», a sum of 72. Along the way it does not start a line with a dash: in Russian typesetting that counts as an error, and TeX puts a break penalty at such places.

Let cost[j] be the smallest cost of setting the first j words if a line ends after word j. Then

cost[j] = the minimum over i < j of cost[i] + (W − the length of the line of words i + 1..j)²,

where the minimum is taken over lines that fit in a column of width W, and for the last line the square is not added.

There is no need to try all i. Start with i = j − 1 and move the start of the line left: the line only gets longer, and as soon as it stops fitting, there is no point looking further left. Each j takes at most L steps, where L is how many words fit in a line. In the listing, on the catalogue’s 9100 words in a column of 35 characters, that is 48,399 steps, about five per word.

Code

The listing sets all the catalogue’s introductory paragraphs greedily and over the whole paragraph in columns of 35 and 70 characters, compares the sums of squares and the shortest lines, and at the end prints one paragraph both ways, marking each line’s shortfall with dots.

How TeX does it

Donald Knuth and Michael Plass described their algorithm for breaking a paragraph into lines in 1981. It is richer than our model in four ways.

• Spaces stretch. TeX justifies, and each space has a natural width, a stretchability and a shrinkability. A line can be shrunk, not only stretched, and the cost is not the shortfall but how far the spaces deviate from their natural width. A line’s “badness” grows as the cube of this deviation: 100·r³, where r is the fraction of the allowance used.
• Penalties. A break can be forbidden or made more expensive: inside a word at a hyphenation point, before a dash, after a short preposition. Penalties are added for two hyphenated lines in a row and for a very tight line next to a very loose one.
• Hyphenation inside words. The hyphenation points in words come from a separate pattern-based algorithm by Frank Liang from 1983; for the graph they are simply new vertices with a penalty.
• Pruning. Lines that would have to be stretched or shrunk beyond the permitted limit are not considered at all, and of the break points only the “active” ones are kept in play, those from which the current word can still be reached. So in practice the algorithm runs in almost linear time.

A non-breaking space in this model is a space without a vertex: the line cannot be broken there. In the Russian text, for example, the digit groups of the number 1 515 185 802 420 673 in the paragraph from the listing are glued with them. And this site’s paragraphs are also hyphenated by the browser, as the text has hyphens: auto, so real setting has more vertices than our model.

What browsers can do

Ordinary line breaking in browsers is greedy: a page has to appear quickly, and the setting is recomputed on every change of window width. But in 2023 two CSS properties appeared. text-wrap: balance evens out short blocks such as headings: according to the Chrome developers’ description, the browser uses binary search to find the narrowest column at which the number of lines does not grow; that is the article’s second problem. text-wrap: pretty asks for a paragraph to be set better. Chromium revisits only the last four lines in that case, so as not to leave a lone word at the end, while WebKit in 2025 began applying it to the whole paragraph. Here is how it looks in your browser:

What it costs

Greedy breaking is O(n): one addition and one comparison per word. Breaking over the whole paragraph is O(n·L) time and O(n) memory; with L within ten or twenty words that is a few times more expensive than greedy, but for a paragraph of a hundred words a fraction of a millisecond. It gets expensive when recomputation is constant: on every change of window width, in every paragraph of a long page. That is why browsers long confined themselves to greedy breaking, while TeX, which sets a book once, could afford to search.

If a line’s cost is a convex function of the shortfall, like the square, there are methods faster than O(n·L): the problem reduces to finding minimums in a matrix with a monotone structure, for which linear algorithms are known. In practice a simple search with an early loop exit is enough.

Where it works

Typesetting books and papers. TeX and LaTeX break paragraphs into lines by Knuth and Plass.

The web. Headings with text-wrap: balance and paragraphs with text-wrap: pretty, where the browser supports them. On this site the mathematics course is set this way: card headings with balance, introductory paragraphs with pretty. The text of this catalogue is broken in the ordinary, greedy way.

Terminals, code editors, mail programs. Greedy breaking: with a monospaced font and a ragged edge the gain from searching is small, and simplicity matters more.

History

Knuth started writing TeX in 1977, unhappy with how the second volume of his “The Art of Computer Programming” had been typeset. The algorithm that looks at the whole paragraph was described by him and his doctoral student Michael Plass in 1981 in the paper “Breaking paragraphs into lines”. The pattern-based hyphenation algorithm was described by Frank Liang, also Knuth’s student, in his 1983 dissertation. The properties text-wrap: balance and pretty appeared in browsers in 2023.

Problems

The first is the smallest sum of squares of the shortfalls: that very shortest path through the break points. The second is what a browser does with text-wrap: balance: the narrowest column with no more lines.