顯示文字時, 換行(line wrap)是指文字在一行已滿後轉到新行,使每行都可在視窗範圍看到,不需水平滾動。

自動換行(word wrap)是大多數文字編輯器文書處理器、和網頁瀏覽器的附加功能。用於在行間或一行里的單詞間隔處分行,不考慮單一單詞超過一行長度的情況。

它通常是在看文檔或打印的時候實時完成,所以沒有儲存或人手插入換行代碼[來源請求]。如果改變文檔邊緣,編輯器就會自動重排換行符的位置,保證全部文字都處於可見狀態,或者給打字員提供一些便捷的方式重排換行符。

軟回車是由於自動換行形成的回車;硬回車則用於另起一段。

單詞邊界、斷字和硬空格

編輯

軟回車通常放在完整單詞後面,或者緊接完整單詞的標點符號後,但也可能在連字號後。

連字號後可用非斷字連字號代替一般連字號避免自動換行,也可在單詞中插入隱形連字號(軟連字號)使文字處理軟件在該處自動換行。

單詞間可用硬空格避免自動換行。

中日韓文字的自動換行

編輯

中文日文韓文中,漢字常認為是一個詞,因此自動換行可以在漢字之前或之後發生。

而在某些情況下,是不需換行。例如:

  • 人名處不宜換行
  • 複合詞處不宜換行

大多數現有的文字處理和排版軟件不能處理上述任何情況。

中日韓標點符號可能不遵守上述特殊情況,這些規則常稱為避頭尾日語禁則処理(意思是「禁止規則處理」)。

避頭尾英語Line breaking rules in East Asian languages有一個總是成立的特例:自動換行永遠不能在中日韓越統一表意文字符集中的破折號省略號之間發生。雖然由於現存字符編碼的關係,這些符號需要用兩個字符表示,但這些字符實際上是一個兩字符寬的符號,而不是兩個單字寬的符號對。

算法

編輯

自動換行是最優化問題。因應不同的需求,有不同的解決辦法。

最小長度

編輯

自動換行可用貪心算法簡單實現:儘可能將單詞放進一行,直到所有單詞都放進去。這是很多現代文字處理軟件的做法,如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。

解決這問題需定義懲罰函數 ,用於計算包含單詞 到單詞 的一行的代價:

 

其中 通常為  。另外,有一些特殊的情況值得考慮:如果結果為負(即單詞串不能全部放在一行里),懲罰函數需要反映跟蹤或壓縮文字以適應一行的代價;如果這是不可能的,則返回 

最優解的代價可以用以下的遞歸式定義:

 

這可以利用動態規劃來高效地實現,時間和空間複雜度均為 

參見

編輯

外部連結

編輯

Knuth's algorithm

編輯

其他自動換行有關的連接

編輯