自动换行

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

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

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

单词边界,断字和硬空格[编辑]

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

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

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

在包含汉字、日文与韩文的文本中的自动换行[编辑]

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

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

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

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

中日韩标点符号可能不遵守上述特殊情况,这些规则通常称为避頭尾(日本术语ja:禁則処理 ,意思是“禁止规则处理”)。

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

算法[编辑]

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

最小长度[编辑]

自动换行的一个简单的实现是使用贪心算法:将尽可能多的单词放进一行里,直到所有的单词都已经放进去为止。这是很多现代文字处理软件的做法,如Microsoft WordOpen 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通常为23。另外,有一些特殊的情况值得考虑:如果结果为负(即单词串不能全部放在一行里),惩罚函数需要反映跟踪或压缩文本以适应一行的代价;如果这是不可能的,则返回\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[编辑]

其他自动换行有关的连接[编辑]