- Word wrap
Word wrap or line wrap is the feature, supported by most
text editors, word processors, and web browsers, of automatically replacing some of the blank spaces between words by line breaks, such that each line fits in the viewable window, allowing text to be read from top to bottom without any horizontal scrolling.
It is usually done
on the flywhen viewing or printing a document, so no line break code is manually entered, or stored. If the user changes the margins, the editor will either automatically reposition the line breaks to ensure that all the text will "flow" within the margins and remain visible, or provide the typist some convenient way to reposition the line breaks.
soft returnand hard return.
Word boundaries, hyphenation, and hard spaces
The soft returns are usually placed after the end of complete words, or after the punctuation that follows complete words. However, word wrap may also occur following a
Word wrap following hyphens is sometimes not desired, and can be avoided by using a so-called non-breaking hyphen instead of a regular hyphen. On the other hand, when using word processors, invisible hyphens, called soft hyphens, can also be inserted inside words so that word wrap can occur following the soft hyphens.
Sometimes, word wrap is not desirable between words. In such cases, word wrap can usually be avoided by using a
hard spaceor non-breaking space between the words, instead of regular spaces.
Word wrapping in text containing Chinese, Japanese, and Korean
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
typesettingsoftware cannot handle either of the above scenarios. CJKpunctuation may or may not follow rules similar to the above-mentioned special circumstances; such rules are usually referred to by the Japanese term kinsoku shori(禁則処理, literally “prohibition rule handling”).
A special case of kinsoku shori, 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.
The naive way to solve the problem is to use a
greedy algorithmthat 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 Microsoft Wordand Open Office. The following pseudocode implements this algorithm:
SpaceLeft := LineWidth for each Word in Text if Width(Word) > SpaceLeft insert line break before Word in Text SpaceLeft := LineWidth - Width(Word) else SpaceLeft := SpaceLeft - (Width(Word) + SpaceWidth)
LineWidthis the width of a line,
SpaceLeftis the remaining width of space on the line to fill,
SpaceWidthis the width of a single space character,
Textis the input text to iterate over and
Wordis a word in this text.
TeXuses a different "breaking algorithm" that considers the entire paragraph as a whole,breaking it into lines in a way that is often considered "more aesthetically pleasing" than the greedy algorithm. (TeX also uses a hyphenation algorithmto break words across lines).
While the greedy algorithm is often adequate, it doesn't give the optimal solution if you want the remaining space on the end of each line to be as small as possible. Consider the following text:
aaa bb cc ddddd
If the cost function of a line is defined by the remaining space squared, the greedy algorithm would yield a sub-optimal solution for the problem (for simplicity, consider a
------ Line width: 6 aaa bb Remaining space: 0 (cost = 0 squared = 0) cc Remaining space: 4 (cost = 4 squared = 16) ddddd Remaining space: 1 (cost = 1 squared = 1)
Summing to a total cost of 17, while the optimal solution would look like this:
------ Line width: 6 aaa Remaining space: 3 (cost = 3 squared = 9) bb cc Remaining space: 1 (cost = 1 squared = 1) ddddd Remaining space: 1 (cost = 1 squared = 1)
The difference here is that the first line is broken before
bbinstead of after it, yielding a better right margin and a lower cost 11.
To solve the problem we need to define a cost function that computes the cost of a line consisting of the words to from the text:
Where typically is or . There are some special cases to consider: If the result is negative (that is, the sequence of words cannot fit on a line), the cost needs to reflect the cost of tracking or condensing the text it to fit; if that is not possible, it needs to return .
The cost of the optimal solution can be defined as a
Computation can be greatly optimized using
dynamic programming. In terms of implementation, it seems that the computation of is unnecessary when (where ); it will be infinite anyway.
* [http://defoe.sourceforge.net/folio/knuth-plass.html "Knuth & Plass line-breaking Revisited"]
* [http://oedipus.sourceforge.net/texlib/ "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.
* [http://search.cpan.org/~mward/Text-Reflow-1.05/Reflow.pm 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."
* [http://www.nabble.com/Initial-soft-hyphen-support-t2970713.html adjusting the Knuth algorithm] to recognize the "soft hyphen".
* [http://wiki.apache.org/xmlgraphics-fop/KnuthsModel 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 [http://wiki.apache.org/xmlgraphics-fop/GoogleSummerOfCode2006/FloatsImplementationProgress Google Summer Of Code 2006]
* [http://citeseer.ist.psu.edu/23630.html "Bridging the Algorithm G
] by Oege de Moor, Jeremy Gibbons, 1999
Other word-wrap links:
* [http://www.efg2.com/Lab/Library/Graphics/CircleWordWrap.htm circular word wrap]
* [http://www.codecomments.com/message230162.html the reverse problem -- picking columns just wide enough to fit (wrapped) text]
* [http://api.kde.org/4.x-api/kdelibs-apidocs/kdeui/html/classKWordWrap.html KWordWrap Class Reference] used in the KDE GUI
* [http://www.leverkruid.eu/GKPLinebreaking/elements.html "Knuth linebreaking elements for Formatting Objects"] by Simon Pepping 2006. Extends the Knuth model to handle a few enhancements.
* [http://wiki.apache.org/xmlgraphics-fop/PageLayout/ "Page breaking strategies"] Extends the Knuth model to handle a few enhancements.
* [http://www.techwr-l.com/archives/0504/techwhirl-0504-00203.html "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)." [http://www.techwr-l.com/archives/0504/techwhirl-0504-00206.html ]
* [http://blogs.msdn.com/murrays/archive/2006/11/15/lineservices.aspx "Murray Sargent: Math in Office"]
Wikimedia Foundation. 2010.