自动换行

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

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

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

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

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

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

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

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

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

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

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

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

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

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

SpaceLeft := LineWidthfor 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

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

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

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

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

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

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

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

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

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