jaroslov / knuth-plass-thoughts
Line-breaking algorithms take a paragraph's-worth of words, and split the words into line-lengthed chunks. The two algorithms many programmer's know of are:
While we happen to agree with (1), we will demonstrate that (2) and (3) are, respectively, not true, and unnecessarily obscure. In fact, the Knuth-Plass algorithm---even in its most naive implementation---is strongly dominated by a light-weight linear run-time, and the implementation of the core algorithm is remarkably straightforward.
We consider the simpler case of line-breaking fixed-width text. Line-breaking proportional fonts (with glue) is a matter of more bookkeeping. Our goal, then, is given a list of words and a line-length, to split those words into separate lines. We will only consider line-breaking of rectangular paragraphs. It is usually natural to try to have the first lines all be as long as possible, with a last line that is potentially much shorter: the greedy algorithm. An implementation could be:
A number of features can be added to this simple line-breaking algorithm, for instance, non-rectangular shapes. To add this feature, we take, as input, a list of line-lengths. we then break each line according to its individual line-length.
