自動換行

顯示文字時，換行（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} <pre> 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. </pre> \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
- 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"