自动换行

在文本的显示中，换行（line wrap）是指文本在一行已满的情况下转到新行，使得每一行都能在窗口范围看到，不需要任何水平的滚动。

自动换行 （word wrap）是大多数文字編輯器、文書處理器、和网页浏览器的一个附加功能。它用于在行间或一行里的单词间隔处分行，不考虑一个单词超过一行长度的情况。

它通常是在看文档或打印的时候实时完成的，所以没有储存或手动插入换行代码。如果用户改变了文档的边缘，编辑器就会自动重排换行符的位置，保证全部文本都处于可见状态，或者给打字员提供一些便捷的方式重排换行符。

软回车是由于自动换行形成的回车，而硬回车则用于另起一段。

单词边界，断字和硬空格

软回车通常放在一个完整单词的后面，或者紧接完整单词的标点符号后。但是，自动换行也有可能发生在连字号后。

有时候并不需要连字号后的自动换行，这时候可以通过使用所谓的非断字连字号代替一般的连字号。另一方面，也可以在单词中插入不可见的连字号（软连字号），使得文字处理软件可以在该处自动换行。

有时候，单词之间的自动换行是不必要的。这种情况下，可以通过单词之间的硬空格避免自动换行。

在中日韩文本中的自动换行

在中文，日文和韩文中，每个汉字通常被认为是一个词，因此自动换行可以在汉字之前或之后发生。

而在某些情况下，是不需要换行的。例如：

人名处不宜换行
复合词处不宜换行

大多数现有的文字处理和排版软件不能处理上述任意一种情况。

中日韩标点符号可能不遵守上述特殊情况，这些规则通常称为避頭尾（意思是“禁止规则处理”）。

避頭尾有一个总是成立的特例：自动换行永远不能在中日韩越统一表意文字符集中的破折号和省略号之间发生。虽然由于现存字符编码的关系，这些符号需要用两个字符表示，但这些字符实际上是一个两字符宽的符号，而不是两个单字宽的符号对。

算法

自动换行是一个最优化问题。因应不同的需求，有不同的解决办法。

最小长度

自动换行的一个简单的实现是使用贪心算法：将尽可能多的单词放进一行里，直到所有的单词都已经放进去为止。这是很多现代文字处理软件的做法，如Microsoft Word和Open Office 。这个算法在追求最少行数的目标上能够达到最优化。下面是该算法的伪代码实现：

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)

LineWidth指一行的宽度，SpaceLeft指一行中剩余的空格，SpaceWidth是一个空格的宽度，Text是输入的文本，Word是文本中的一个单词。

最小破损度

在TeX中使用的，则是另一个算法，旨在将行尾空格数的平方和最小化，以产生一个更加美观的结果。以上的算法不能完成这一目标，例如：

aaa bb cc ddddd

如果惩罚函数定义为行尾剩余空格数的平方，则贪婪算法会得到一个次优解（为了简化起见，不妨假设采用定宽字体）：

------ 一行的宽度为6
aaa bb 剩余的空格数：0，平方=0
cc     剩余的空格数：4，平方=16
ddddd  剩余的空格数：1，平方=1

总计代价17，而最佳的解决方案是这样的：

------ 一行的宽度为6
aaa    剩余空格数：3 平方=9
bb cc  剩余空格数：1 平方=1
ddddd  剩余空格数：1 平方=1

请注意，第一行在bb前断开了，相对于在bb后断开的解法，可以得到更好的右边界和更低的代价11。

为了解决这个问题，我们需要定义一个惩罚函数 $c(i,j)$ ，用于计算包含单词 ${\text{Word}}[i]$ 到单词 ${\text{Word}}[j]$ 的一行的代价：

c(i,j)=\left({\text{LineWidth}}-(j-i)\cdot {\text{OneSpaceWidth}}-\sum _{k=i}^{j}{\text{WidthOf}}({\text{Word}}[k])\right)^{P}.

其中 $P$ 通常为 $2$ 或 $3$ 。另外，有一些特殊的情况值得考虑：如果结果为负（即单词串不能全部放在一行里），惩罚函数需要反映跟踪或压缩文本以适应一行的代价；如果这是不可能的，则返回 $\infty$

最优解的代价可以用以下的递归式定义：

f(j)={\begin{cases}c(1,j)&{\text{if }}c(1,j)<\infty ,\\\displaystyle \min _{1\leq k<j}{\big (}f(k)+c(k+1,j){\big )}&{\text{if }}c(1,j)=\infty .\end{cases}}

这可以利用动态规划来高效地实现，时间和空间复杂度均为 $O(j^{2})$

参见

外部链接

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, 1999

其他自动换行有关的连接

the reverse problem -- picking columns just wide enough to fit (wrapped) text Archive.is的存檔，存档日期2007-09-27
KWordWrap Class Reference 页面存档备份，存于 used in the KDE GUI
"Knuth linebreaking elements for Formatting Objects" by Simon Pepping 2006. Extends the Knuth model to handle a few enhancements.
"Page breaking strategies" 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)."
"Murray Sargent: Math in Office" 页面存档备份，存于

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.