Unicode

The Unicode Line Breaking Algorithm determines a set of positions, known as break opportunities, that are appropriate places in which to begin a new line. The actual line break positions are picked from among the break opportunities by the higher level software that calls the algorithm, not by the algorithm itself, because only the higher level software knows about the width of the display the text is displayed on and the width of the glyphs that make up the displayed text.^[1]

The Unicode character set provides a line separator character as well as a paragraph separator to represent the semantics of the soft return and hard return.

0x2028 LINE SEPARATOR

* may be used to represent this semantic unambiguously

0x2029 PARAGRAPH SEPARATOR

* may be used to represent this semantic unambiguously

Minimum number of lines

A simple way to do word wrapping is to use a greedy algorithm that puts as many words on a line as possible, then moving on to the next line to do the same until there are no more words left to place. This method is used by many modern word processors, such as OpenOffice.org Writer and Microsoft Word. This algorithm always uses the minimum possible number of lines but may lead to lines of widely varying lengths. The following pseudocode implements this algorithm:

SpaceLeft := LineWidth
for each Word in Text
    if (Width(Word) + SpaceWidth) > SpaceLeft
        insert line break before Word in Text
        SpaceLeft := LineWidth - Width(Word)
    else
        SpaceLeft := SpaceLeft - (Width(Word) + SpaceWidth)

Where LineWidth is the width of a line, SpaceLeft is the remaining width of space on the line to fill, SpaceWidth is the width of a single space character, Text is the input text to iterate over and Word is a word in this text.

Minimum raggedness

A different algorithm, used in TeX, minimizes the sum of the squares of the lengths of the spaces at the end of lines to produce a more aesthetically pleasing result. The following example compares this method with the greedy algorithm, which does not always minimize squared space.

For the input text

AAA BB CC DDDDD

with line width 6, the greedy algorithm would produce:

------    Line width: 6
AAA BB    Remaining space: 0
CC        Remaining space: 4
DDDDD     Remaining space: 1

The sum of squared space left over by this method is ${\displaystyle 0^{2}+4^{2}+1^{2}=17}$. However, the optimal solution achieves the smaller sum ${\displaystyle 3^{2}+1^{2}+1^{2}=11}$:

------    Line width: 6
AAA       Remaining space: 3
BB CC     Remaining space: 1
DDDDD     Remaining space: 1

The difference here is that the first line is broken before BB instead of after it, yielding a better right margin and a lower cost 11.

By using a dynamic programming algorithm to choose the positions at which to break the line, instead of choosing breaks greedily, the solution with minimum raggedness may be found in time ${\displaystyle O(n^{2})}$, where ${\displaystyle n}$ is the number of words in the input text. Typically, the cost function for this technique should be modified so that it does not count the space left on the final line of a paragraph; this modification allows a paragraph to end in the middle of a line without penalty. It is also possible to apply the same dynamic programming technique to minimize more complex cost functions that combine other factors such as the number of lines or costs for hyphenating long words.^[3] Faster but more complicated linear time algorithms based on the SMAWK algorithm are also known for the minimum raggedness problem, and for some other cost functions that have similar properties.^[4][5]

History

A primitive line-breaking feature was used in 1955 in a "page printer control unit" developed by Western Union. This system used relays rather than programmable digital computers, and therefore needed a simple algorithm that could be implemented without data buffers. In the Western Union system, each line was broken at the first space character to appear after the 58th character, or at the 70th character if no space character was found.^[6]

The greedy algorithm for line-breaking predates the dynamic programming method outlined by Donald Knuth in an unpublished 1977 memo describing his TeX typesetting system^[7] and later published in more detail by Knuth & Plass (1981).

Knuth's algorithm

• "Knuth & Plass line-breaking Revisited"
• "tex_wrap": "Implements TeX's algorithm for breaking paragraphs into lines." Reference: "Breaking Paragraphs into Lines", D.E. Knuth and M.F. Plass, chapter 3 of _Digital Typography_, CSLI Lecture Notes #78.
• Text::Reflow - Perl module for reflowing text files using Knuth's paragraphing algorithm. "The reflow algorithm tries to keep the lines the same length but also tries to break at punctuation, and avoid breaking within a proper name or after certain connectives ("a", "the", etc.). The result is a file with a more "ragged" right margin than is produced by fmt or Text::Wrap but it is easier to read since fewer phrases are broken across line breaks."
• adjusting the Knuth algorithm to recognize the "soft hyphen".
• Knuth's breaking algorithm. "The detailed description of the model and the algorithm can be found on the paper "Breaking Paragraphs into Lines" by Donald E. Knuth, published in the book "Digital Typography" (Stanford, California: Center for the Study of Language and Information, 1999), (CSLI Lecture Notes, no. 78.)"; part of Google Summer Of Code 2006
• "Bridging the Algorithm Gap: A Linear-time Functional Program for Paragraph Formatting" by Oege de Moor, Jeremy Gibbons, 1997

Other word-wrap links

• the reverse problem -- picking columns just wide enough to fit (wrapped) text (Archived version)
• "Knuth linebreaking elements for Formatting Objects" by Simon Pepping 2006. Extends the Knuth model to handle a few enhancements.
• "a Knuth–Plass-like linebreaking algorithm ... The *really* interesting thing is how Adobe's algorithm differs from the Knuth–Plass algorithm. It must differ, since Adobe has managed to patent its algorithm (6,510,441)."
• "Line breaking" compares the algorithms of various time complexities.