自动换行是现代文本编辑器中必备功能之一。
如何处理自动换行？自动换行的最佳算法是什么？
如果文本是几百万行，我怎么能快速地进行自动换行？
为什么我需要解决方案？因为我的项目必须绘制具有各种缩放级别和同时漂亮外观的文本。
运行环境是Windows Mobile设备。最大600 MHz速度，内存尺寸非常小。
我该如何处理行信息？我们假设原始数据有三行。
THIS IS LINE 1.
THIS IS LINE 2.
THIS IS LINE 3.
之后，中断文本将显示如下：
THIS IS
LINE 1.
THIS IS
LINE 2.
THIS IS
LINE 3.
我应该再分配三行吗？还是其他任何建议？
这是我用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溢出）虽然它不支持将小的带连字符的单词移动到换行符而不是拆分它们。如果它们对于一条线太长，它会分裂单词。
它也具有相当的文化特色，因为我对其他文化的包装规则知之甚少。
我也可以使用我制作的perl解决方案，因为gnu fold -s正在留下尾随空间和其他不良行为。此解决方案不会（正确）处理包含制表符或退格键或嵌入式回车符等的文本，尽管它确实处理CRLF行结尾，将它们全部转换为LF。它对文本进行了微小的更改，特别是它从不拆分一个单词（不会更改wc -w），对于行中不超过单个空格（并且没有CR）的文本，它不会更改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);
}
@ICR，感谢分享C＃示例。我没有成功使用它，但提出了另一种解决方案。如果您对此感兴趣，请随意使用：https://web.archive.org/web/20160403050733/http://johan.andersson.net/2010/11/03/wordwrap-function-in-c/。来源可用on GitHub。
我已经包含了单元测试/样本。
Donald E. Knuth在他的TeX排版系统中对断线算法做了大量工作。这可以说是最好的断线算法之一 - 在结果的视觉外观方面“最好”。
他的算法避免了贪婪线填充的问题，你可以得到一条非常密集的线，然后是一条非常松散的线。
可以使用动态编程来实现有效的算法。
我不知道是否有人会读到这个看到这个问题有多久，但我最近有机会写一个自动换行功能，我想分享我想出的东西。我使用的TDD方法几乎与Go example的方法一样严格。我开始测试包裹字符串“Hello，world！”在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。
我不知道任何具体的算法，但下面不会大致说明它应该如何工作：
问题：在.net中，自动换行功能内置于TextBox等控件中。我确信其他语言也存在类似的内置功能。您是否有理由不想使用预先构建的解决方案？这似乎是重新发明轮子的方式。
有或没有连字符？
没有它很容易。只需将文本封装为每个单词的wordobjects，并为它们提供方法getWidth（）。然后从第一个单词开始，将行长加起来，直到它大于可用空间。如果是这样，请包装最后一个单词并再次开始计数从下一行开始计算，等等。
使用连字符时，您需要使用通用格式的连字符规则，例如：hy-phen-a-tion
然后它与上面的相同，除了你需要拆分导致溢出的最后一个字。
有关如何为优秀文本编辑器构建代码的一个很好的示例和教程，请参阅Gang of Four Design Patterns一书。这是他们展示模式的主要样本之一。
我对自己的编辑器项目也想知道同样的事情。我的解决方案分为两个步骤：
当您需要显示文本时，找到有问题的行并将其包装好。请记住缓存中的此信息以便快速重绘。当用户滚动整个页面时，刷新缓存并重复。
如果可以，请在后台线程中加载/分析整个文本。这样，您可以显示文本的第一页，同时仍在检查文档的其余部分。这里最简单的解决方案是删除前16KB的文本并在子字符串上运行算法。这非常快，并允许您即时渲染第一页，即使您的编辑器仍在加载文本。
当光标最初位于文本末尾时，您可以使用类似的方法;只需阅读最后16KB的文本并进行分析。在这种情况下，使用两个编辑缓冲区并在用户锁定到第二个缓冲区时将除最后16KB之外的所有缓冲区加载到第一个缓冲区中。并且您可能想要记住关闭编辑器时文本有多少行，因此滚动条看起来并不奇怪。
当用户可以使用光标在中间的某个位置启动编辑器时，它会变得毛茸茸，但最终，它只是最终问题的扩展。只需要记住上一个会话的字节位置，当前行号和总行数，你需要三个编辑缓冲区，或者你需要一个编辑缓冲区，你可以在中间删除16KB。
或者，在加载文本时锁定滚动条和其他界面元素;允许用户在完全加载时查看文本。
这是我今天为了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，我想设置为一行的开头和一行的最后一个字符。当这些设置完成后，我从头到尾输出到stdout所有字符，然后输出一个'\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;
}
部分用于太短的字符串甚至一次。我在写这篇文章之前添加了这个，因为我尝试了一个简短的字符串，但它没有用。
我觉得这可能是更优雅的方式。如果有人有任何建议，我很乐意尝试。
当我写这篇文章的时候，我问自己“如果我的字符串是一个比我的长度更长的字符串会发生什么”嗯它不起作用。所以我加了
if( lastChar == start )
lastChar = current-1;
在printLine()声明之前（如果lastChar没有移动，那么我们有一个单词对于一行来说太长了，所以我们只需将整个事情放在线上）。
因为我写这篇文章，所以我从代码中删除了这些注释，但我真的觉得必须有一种比我不需要注释的更好的方法。
这就是我写这个东西的故事。我希望它对人们有用，我也希望有人对我的代码不满意，并提出一种更优雅的方式。
应该注意的是，它适用于所有边缘情况：对于一行来说，单词太长，比一个wrapLength短的字符串，以及空字符串。
这是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);
}
}
}