Word wrap

From Wikipedia, the free encyclopedia
Jump to: navigation, search
For word wrap handling on Wikipedia, see Wikipedia:Line-break handling.

In text display, line wrap is the feature of continuing on a new line when a line is full, such that each line fits in the viewable window, allowing text to be read from top to bottom without any horizontal scrolling.

Word wrap is the additional feature of most text editors, word processors, and web browsers, of breaking lines between and not within words, except when a single word is longer than a line.

A soft return is the break resulting from line wrap or word wrap, whereas a hard return is an intentional break, creating a new paragraph.

Similarly, a hard wrap inserts actual line breaks in the text at wrap points, whereas a soft wrap puts the text into separate lines without inserting line breaks.

Soft wrapping allows line lengths to adjust automatically with adjustments to the width of the user's window or margin settings. Soft wrapping is a standard feature of all modern text editors, word processors, and email clients.

Contents

Word boundaries, hyphenation, and hard spaces [edit]

The soft returns are usually placed after the ends of complete words, or after the punctuation that follows complete words. However, word wrap may also occur following a hyphen inside of a word. This is sometimes not desired, and can be blocked by using a non-breaking hyphen, or hard hyphen, instead of a regular hyphen.

A word without hyphens can be made wrappable by having soft hyphens in it. When the word isn't wrapped (i.e., isn't broken across lines), the soft hyphen isn't visible. But if the word is wrapped across lines, this is done at the soft hyphen, at which point it is shown as a visible hyphen on the top line where the word is broken. (In the rare case of a word that is meant to be wrappable by breaking it across lines but without making a hyphen ever appear, a zero-width space is put at the permitted breaking point(s) in the word.)

Sometimes word wrap is undesirable between adjacent words. In such cases, word wrap can usually be blocked by using a hard space or non-breaking space between the words, instead of regular spaces.

Word wrapping in text containing Chinese, Japanese, and Korean [edit]

In Chinese, Japanese, and Korean, each Han character is normally considered a word,[citation needed] and therefore word wrapping can usually occur before and after any Han character.

Under certain circumstances, however, word wrapping is not desired. For instance,

  • word wrapping might not be desired within personal names, and
  • word wrapping might not be desired within any compound words (when the text is flush left but only in some styles).

Most existing word processors and typesetting software cannot handle either of the above scenarios.

CJK punctuation may or may not follow rules similar to the above-mentioned special circumstances. It is up to line breaking rules in CJK.

A special case of line breaking rules in CJK, however, always applies: line wrap must never occur inside the CJK dash and ellipsis. Even though each of these punctuation marks must be represented by two characters due to a limitation of all existing character encodings, each of these are intrinsically a single punctuation mark that is two ems wide, not two one-em-wide punctuation marks.

Algorithm [edit]

Word wrapping is an optimization problem. Depending on what needs to be optimized for, different algorithms are used.

Minimum length [edit]

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 [edit]

A different algorithm, used in TeX, minimizes the square of the space 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 02 + 42 + 12 = 17. However, the optimal solution achieves the smaller sum 32 + 12 + 12 = 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 O(n2), where 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.[1] Faster but more complicated linear time algorithms are also known for the minimum raggedness problem, and for some other cost functions that have similar properties.[2][3]

History [edit]

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 implementated 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.[4]

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[5] and later published in more detail by Knuth & Plass (1981).

See also [edit]

References [edit]

  1. ^ Knuth, Donald E.; Plass, Michael F. (1981), "Breaking paragraphs into lines", Software: Practice and Experience 11 (11): 1119–1184, doi:10.1002/spe.4380111102 .
  2. ^ Wilber, Robert (1988), "The concave least-weight subsequence problem revisited", Journal of Algorithms 9 (3): 418–425, doi:10.1016/0196-6774(88)90032-6, MR 955150 .
  3. ^ Galil, Zvi; Park, Kunsoo (1990), "A linear-time algorithm for concave one-dimensional dynamic programming", Information Processing Letters 33 (6): 309–311, doi:10.1016/0020-0190(90)90215-J, MR 1045521 .
  4. ^ Harris, Robert W. (January 1956), "Keyboard standardization", Western Union Technical Review 10 (1): 37–42 .
  5. ^ Knuth, Donald (1977), TEXDR.AFT, retrieved 2013-04-07 . Reprinted in Knuth, Donald (1999), Digital Typography, CSLI Lecture Notes 78, Stanford, California: Center for the Study of Language and Information, ISBN 1-57586-010-4 .

External links [edit]

Knuth's algorithm [edit]

Other word-wrap links [edit]

Retrieved from "http://en.wikipedia.org/w/index.php?title=Word_wrap&oldid=555163172"