自動換行是現代文本編輯器中必備功能之一。最佳單詞包裝算法？
你知道如何處理自動換行嗎？ 什麼是最好的換行算法？
已更新： 如果文本是幾百萬行，我怎樣才能讓文字換行非常快？
已更新：爲什麼我需要解決方案？因爲我的項目必須繪製各種縮放級別的文字，同時美麗的外觀。
已更新：運行環境是Windows Mobile設備。最大600MHz的速度，非常小的內存大小。
已更新：我應該如何處理線路信息？假設原始數據有三行。
THIS IS LINE 1.
THIS IS LINE 2.
THIS IS LINE 3.
字破文本後會顯示這樣的：
THIS IS
LINE 1.
THIS IS
LINE 2.
THIS IS
LINE 3.
我應該撥出3行嗎？還是有其他建議？
有或沒有連字？
沒有它的容易。只需將您的文本作爲每個單詞的wordobjects進行包裝，然後爲它們提供一種方法getWidth（），然後從第一個單詞開始，將行長加起來，直至大於可用空間。如果這樣的話包裝最後一個字，並開始再次計算下一行，從這個ecetera開始。
隨着斷字，你需要在一個共同的格式斷字的規則，如：HY - 苯A-重刑
那麼它上面一樣，除非你需要分割已經造成了溢出的最後一個字。
「四人幫」設計模式書中給出了一個很好的示例和如何爲優秀的texteditor構建代碼的教程。它是他們展示模式的主要樣本之一。
爲什麼這個投票是-1？授予貪婪算法並不理想，但... – ShreevatsaR 2009-05-13 13:02:19
擊敗了我。我也很驚訝。 – 2009-05-19 13:16:44
我不知道任何特定的算法，但不會下面是它如何工作的一個大致的輪廓：
問題：在.net中，文字包裝功能是內置於TextBox等控件中的。我相信其他語言也存在類似的內置功能。是否有理由不使用預先構建的解決方案？這似乎是重塑車輪的方向。
關於您的更新和速度問題，請記住稍後優化。首先，編寫你的文字包裝算法。如果文字在一百萬行上運行。如果且僅當對您的要求太慢，則優化。
這裏是我用C＃編寫的一個單詞包裝算法。翻譯成其他語言應該相當容易（除了可能的IndexOfAny）。
static char[] splitChars = new char[] { ' ', '-', '\t' };
private static string WordWrap(string str, int width)
{
string[] words = Explode(str, splitChars);
int curLineLength = 0;
StringBuilder strBuilder = new StringBuilder();
for(int i = 0; i < words.Length; i += 1)
{
string word = words[i];
// If adding the new word to the current line would be too long,
// then put it on a new line (and split it up if it's too long).
if (curLineLength + word.Length > width)
{
// Only move down to a new line if we have text on the current line.
// Avoids situation where wrapped whitespace causes emptylines in text.
if (curLineLength > 0)
{
strBuilder.Append(Environment.NewLine);
curLineLength = 0;
}
// If the current word is too long to fit on a line even on it's own then
// split the word up.
while (word.Length > width)
{
strBuilder.Append(word.Substring(0, width - 1) + "-");
word = word.Substring(width - 1);
strBuilder.Append(Environment.NewLine);
}
// Remove leading whitespace from the word so the new line starts flush to the left.
word = word.TrimStart();
}
strBuilder.Append(word);
curLineLength += word.Length;
}
return strBuilder.ToString();
}
private static string[] Explode(string str, char[] splitChars)
{
List<string> parts = new List<string>();
int startIndex = 0;
while (true)
{
int index = str.IndexOfAny(splitChars, startIndex);
if (index == -1)
{
parts.Add(str.Substring(startIndex));
return parts.ToArray();
}
string word = str.Substring(startIndex, index - startIndex);
char nextChar = str.Substring(index, 1)[0];
// Dashes and the likes should stick to the word occuring before it. Whitespace doesn't have to.
if (char.IsWhiteSpace(nextChar))
{
parts.Add(word);
parts.Add(nextChar.ToString());
}
else
{
parts.Add(word + nextChar);
}
startIndex = index + 1;
}
}
這是相當原始的 - 它分裂在空間，標籤和破折號。它確實確保破折號堅持它之前的單詞（所以你不會結束堆棧\ n溢出），儘管它不贊成將小的帶連字符的單詞移動到換行符而不是將它們分開。如果它們對於一條線太長，它就會分裂出單詞。
這也是相當文化上的具體，因爲我不太瞭解其他文化的包裝規則。
Donald E. Knuth在他的TeX排版系統中做了很多關於換行算法的工作。這可以說是斷線的最佳算法之一 - 在結果的視覺外觀方面「最好」。
他的算法可以避免貪婪線條填充的問題，在這種情況下，最終會出現非常密集的線條，然後會出現非常鬆散的線條。
一個有效的算法可以使用動態編程來實現。
我不知道是否有人會看到這個問題，看看這個問題有多大，但我有機會最近寫一個自動換行函數，我想分享我想出來的。我使用的TDD方法幾乎和Go example一樣嚴格。我開始測試包裝字符串「你好，世界！」在80寬度應該返回「你好，世界！」顯然，最簡單的工作就是不返回輸入字符串。從那開始，我做了越來越複雜的測試，最後得到了一個遞歸解決方案（至少對我來說）能夠非常有效地處理任務。
的僞代碼遞歸解決方案：
Function WordWrap (inputString, width)
Trim the input string of leading and trailing spaces.
If the trimmed string's length is <= the width,
Return the trimmed string.
Else,
Find the index of the last space in the trimmed string, starting at width
If there are no spaces, use the width as the index.
Split the trimmed string into two pieces at the index.
Trim trailing spaces from the portion before the index,
and leading spaces from the portion after the index.
Concatenate and return:
the trimmed portion before the index,
a line break,
and the result of calling WordWrap on the trimmed portion after
the index (with the same width as the original call).
在空間這隻包裹，如果你想換行已包含換行符的字符串，你需要把它換行分割，互送件到這個函數，然後重新組裝字符串。即使如此，在快速機器上運行的VB.NET中，這可以處理大約20 mb/sec。
我想知道我自己的編輯器項目的同樣的事情。我的解決方案是一個兩步過程：
當您需要顯示文本時，找到有問題的行並將其快速包裝。將這些信息記住在緩存中以便快速重繪。當用戶滾動整個頁面時，刷新緩存並重復。
如果可以，請在後臺線程中加載/分析整個文本。這樣，當文檔的其餘部分仍在檢查時，您可以顯示文本的第一頁。這裏最簡單的解決方案是將第一個16KB的文本剪掉，並在子字符串上運行算法。這是非常快的，即使您的編輯器仍在加載文本，您也可以立即渲染第一頁。
當光標最初位於文本的末尾時，您可以使用類似的方法;只需閱讀最後的16KB文本並分析即可。在這種情況下，使用兩個編輯緩衝區，並在用戶鎖定到第二個緩衝區的同時，將除最後16KB以外的所有內容加載到第一個緩衝區中。你可能想要記住關閉編輯器時文本有多少行，所以滾動條看起來不奇怪。
當用戶可以用光標在中間的某處啓動編輯器時，它會變得毛茸茸的，但最終它只是最終問題的延伸。只需要記住上一次會話的字節位置，當前行號和總行數，再加上需要三個編輯緩衝區，或者需要一個編輯緩衝區，您可以在中間切掉16KB。
或者，在文本加載時鎖定滾動條和其他界面元素;它允許用戶在完全加載時查看文本。
@ICR，感謝您分享C＃示例。 我沒有成功使用它，但提出了另一種解決方案。如果對此有興趣，請隨時使用： http://johan.andersson.net/2010/11/03/wordwrap-function-in-c/
我已經包含了單元測試/樣本。
謝謝！
這裏是C＃中的解決方案。它溢出了超過給定限制的唯一字，其他字仍然如常。
/// <summary>
/// Word wraps the given text to fit within the specified width.
/// </summary>
/// <param name="text">Text to be word wrapped</param>
/// <param name="width">Width, in characters, to which the text
/// should be word wrapped</param>
/// <returns>The modified text</returns>
public static string WordWrap(string text, int width)
{
int pos, next;
StringBuilder sb = new StringBuilder();
// Lucidity check
if (width < 1)
return text;
// Parse each line of text
for (pos = 0; pos < text.Length; pos = next)
{
// Find end of line
int eol = text.IndexOf(Environment.NewLine, pos);
if (eol == -1)
next = eol = text.Length;
else
next = eol + Environment.NewLine.Length;
// Copy this line of text, breaking into smaller lines as needed
if (eol > pos)
{
do
{
int len = eol - pos;
if (len > width)
len = BreakLine(text, pos, width);
sb.Append(text, pos, len);
sb.Append(Environment.NewLine);
// Trim whitespace following break
pos += len;
while (pos < eol && Char.IsWhiteSpace(text[pos]))
pos++;
} while (eol > pos);
}
else sb.Append(Environment.NewLine); // Empty line
}
return sb.ToString();
}
/// <summary>
/// Locates position to break the given line so as to avoid
/// breaking words.
/// </summary>
/// <param name="text">String that contains line of text</param>
/// <param name="pos">Index where line of text starts</param>
/// <param name="max">Maximum line length</param>
/// <returns>The modified line length</returns>
private static int BreakLine(string text, int pos, int max)
{
// Find last whitespace in line
int i = max;
while (i >= 0 && !Char.IsWhiteSpace(text[pos + i]))
i--;
// If no whitespace found, break at maximum length
if (i < 0)
return max;
// Find start of whitespace
while (i >= 0 && Char.IsWhiteSpace(text[pos + i]))
i--;
// Return length of text before whitespace
return i + 1;
}
我不能說這個沒有缺陷，但我需要一個單詞包裝並遵守縮進邊界的文字。除了迄今爲止的工作方式，我對這個代碼沒有任何聲明。這是一個擴展方法，並且違反了StringBuilder的完整性，但可以使用您希望的任何輸入/輸出。
public static void WordWrap(this StringBuilder sb, int tabSize, int width)
{
string[] lines = sb.ToString().Replace("\r\n", "\n").Split('\n');
sb.Clear();
for (int i = 0; i < lines.Length; ++i)
{
var line = lines[i];
if (line.Length < 1)
sb.AppendLine();//empty lines
else
{
int indent = line.TakeWhile(c => c == '\t').Count(); //tab indents
line = line.Replace("\t", new String(' ', tabSize)); //need to expand tabs here
string lead = new String(' ', indent * tabSize); //create the leading space
do
{
//get the string that fits in the window
string subline = line.Substring(0, Math.Min(line.Length, width));
if (subline.Length < line.Length && subline.Length > 0)
{
//grab the last non white character
int lastword = subline.LastOrDefault() == ' ' ? -1 : subline.LastIndexOf(' ', subline.Length - 1);
if (lastword >= 0)
subline = subline.Substring(0, lastword);
sb.AppendLine(subline);
//next part
line = lead + line.Substring(subline.Length).TrimStart();
}
else
{
sb.AppendLine(subline); //everything fits
break;
}
}
while (true);
}
}
}
我可能也附和一個Perl的解決方案，我做了，因爲GNU fold -s離開尾隨空格等不良行爲。這個解決方案沒有（正確）處理包含製表符或者退格符或者嵌入式回車等的文本，儘管它處理CRLF行結束符，將它們全部轉換爲LF。它對文本進行最小限度的更改，尤其是它從不拆分一個單詞（不會更改wc -w），對於行中不超過單個空格且沒有更改的文本，它不會更改wc -c（因爲它用LF代替空間而不是插入 LF）。
#!/usr/bin/perl
use strict;
use warnings;
my $WIDTH = 80;
if ($ARGV[0] =~ /^[1-9][0-9]*$/) {
$WIDTH = $ARGV[0];
shift @ARGV;
}
while (<>) {
s/\r\n$/\n/;
chomp;
if (length $_ <= $WIDTH) {
print "$_\n";
next;
}
@_=split /(\s+)/;
# make @_ start with a separator field and end with a content field
unshift @_, "";
push @_, "" if @_%2;
my ($sep,$cont) = splice(@_, 0, 2);
do {
if (length $cont > $WIDTH) {
print "$cont";
($sep,$cont) = splice(@_, 0, 2);
}
elsif (length($sep) + length($cont) > $WIDTH) {
printf "%*s%s", $WIDTH - length $cont, "", $cont;
($sep,$cont) = splice(@_, 0, 2);
}
else {
my $remain = $WIDTH;
{ do {
print "$sep$cont";
$remain -= length $sep;
$remain -= length $cont;
($sep,$cont) = splice(@_, 0, 2) or last;
}
while (length($sep) + length($cont) <= $remain);
}
}
print "\n";
$sep = "";
}
while ($cont);
}
這裏是我的，我是工作在今天的樂趣在C：
這裏是我的考慮：
1）字符的任何拷貝，只是打印到標準輸出。因此，由於我不喜歡修改argv [x]參數，並且因爲我喜歡挑戰，所以我想在不修改它的情況下做到這一點。我沒有去插入'\n'的想法。
2）我不想
This line breaks here
成爲
This line breaks
here
因此更改字符'\n'沒有給出這一目標的選項。
3）如果線寬設置爲80，並且第80個字符位於單詞的中間，則整個單詞必須放在下一行。所以當你掃描的時候，你必須記住最後一個字沒有超過80個字符的位置。
所以這裏是我的，它不乾淨;在過去的一個小時裏，我一直在努力讓它工作，在這裏和那裏添加一些東西。它適用於我所知道的所有邊緣情況。
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int isDelim(char c){
switch(c){
case '\0':
case '\t':
case ' ' :
return 1;
break; /* As a matter of style, put the 'break' anyway even if there is a return above it.*/
default:
return 0;
}
}
int printLine(const char * start, const char * end){
const char * p = start;
while (p <= end) putchar(*p++);
putchar('\n');
}
int main (int argc , char ** argv) {
if(argc <= 2) exit(1);
char * start = argv[1];
char * lastChar = argv[1];
char * current = argv[1];
int wrapLength = atoi(argv[2]);
int chars = 1;
while(*current != '\0'){
while(chars <= wrapLength){
while (!isDelim(*current)) ++current, ++chars;
if(chars <= wrapLength){
if(*current == '\0'){
puts(start);
return 0;
}
lastChar = current-1;
current++,chars++;
}
}
if(lastChar == start)
lastChar = current-1;
printLine(start,lastChar);
current = lastChar + 1;
while(isDelim(*current)){
if(*current == '\0')
return 0;
else
++current;
}
start = current;
lastChar = current;
chars = 1;
}
return 0;
}
所以基本上，我有start和lastChar我想設置爲線的開始和行的最後一個字符。當這些被設置時，我輸出到標準輸出所有字符從開始到結束，然後輸出一個'\n'，並繼續到下一行。
最初一切指向開始，然後我跳過while(!isDelim(*current)) ++current,++chars;的單詞。當我這樣做時，我記得80個字符之前的最後一個字符（lastChar）。
如果在一個單詞的末尾，我已經通過了我的字符數（80），那麼我將跳出while(chars <= wrapLength)塊。我輸出了start和lastChar和newline之間的所有字符。
然後我將current設置爲lastChar+1並跳過分隔符（如果這導致我到字符串的末尾，我們就完成了，return 0）。將start,lastChar和current設置爲下一行的開頭。
的
if(*current == '\0'){
puts(start);
return 0;
}
部分是太短要甚至一度包裹字符串。我在寫這篇文章之前就添加了這個，因爲我嘗試了一個簡短的字符串，但它不起作用。
我覺得這可能是更好的方式可行。如果有人有任何建議，我很樂意嘗試。
而當我寫這篇文章的時候，我問自己「如果我的字符串是比我的長度長的字符，會發生什麼事情」，那麼它不起作用。所以我以前printLine()語句添加
if(lastChar == start)
lastChar = current-1;
（如果lastChar沒有移動，那麼我們有一個詞是單行過長，所以我們只要把整個事情就行了反正） 。
自從我寫這篇文章以來，我把註釋從代碼中拿出來了，但我真的覺得必須有更好的方法來做到這一點，而不是我所不需要的評論。
這就是我寫這個東西的故事。我希望它對人們有用，我也希望有人會不滿意我的代碼，並提出一個更優雅的方式。
應當指出的是，它適用於所有的邊緣情況：單詞太長的線，即短於一個wrapLength字符串和空字符串。
問題沒有明確規定，它是固定寬度的字體，雖然例子，在「文本編輯器」意味着使用它。只有雅科夫埃利斯的回答提到非固定寬度字體的文字換行。 – Gnubie 2012-05-01 16:27:10