自动换行是现代文本编辑器的必备功能之一。
如何处理自动换行？换行的最佳算法是什么？
如果文本是几百万行，我怎样才能使自动换行非常快？
为什么我需要解决方案？因为我的项目必须绘制具有各种缩放级别的文本并同时具有漂亮的外观。
运行环境为 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;
}
}
它相当原始——它在空格、制表符和破折号上分割。它确实确保破折号粘在它之前的单词上（所以你不会以 stack\n-overflow 结束），尽管它不赞成将带连字符的小单词移动到换行符而不是拆分它们。如果它们对于一行来说太长，它确实会拆分单词。
它在文化上也相当具体，因为我对其他文化的自动换行规则了解不多。
Donald E. Knuth 在他的 TeX 排版系统中对换行算法做了很多工作。这可以说是最好的换行算法之一——就结果的视觉外观而言是“最好的”。
他的算法避免了贪婪线填充的问题，在这种情况下，您最终会得到一条非常密集的线，然后是一条非常松散的线。
可以使用动态规划来实现有效的算法。
最近有机会写了一个自动换行功能，想分享一下自己的想法。
我使用的TDD方法几乎与Go 示例中的方法一样严格。我从包装字符串“Hello, world!”的测试开始。宽度为 80 时应返回“Hello, World!”。显然，最简单的方法是原封不动地返回输入字符串。从那开始，我进行了越来越复杂的测试，并最终得到了一个递归解决方案，它（至少对于我的目的）非常有效地处理了任务。
递归解决方案的伪代码：
函数 WordWrap（输入字符串，宽度）
修剪前导和尾随空格的输入字符串。
如果修剪后的字符串的长度 <= 宽度，
返回修剪后的字符串。
别的，
查找修剪后的字符串中最后一个空格的索引，从宽度开始
如果没有空格，则使用宽度作为索引。
在索引处将修剪后的字符串分成两部分。
从索引之前的部分修剪尾随空格，
以及索引后部分的前导空格。
连接并返回：
索引前的修剪部分，
换行符，
以及在修剪后的部分上调用 WordWrap 的结果
索引（与原始调用具有相同的宽度）。
这仅在空格处换行，如果要换行已包含换行符的字符串，则需要在换行符处将其拆分，将每个部分发送到此函数，然后重新组合字符串。即便如此，在快速机器上运行的 VB.NET 中，这可以处理大约 20 MB/秒。
我不知道任何具体的算法，但以下可能是它应该如何工作的粗略概述：
在 .NET 中，自动换行功能内置于 TextBox 等控件中。我确信其他语言也存在类似的内置功能。
带或不带连字符？
没有它很容易。只需将您的文本封装为每个单词的 wordobjects 并给它们一个方法 getWidth()。然后从第一个单词开始累加行长度，直到它大于可用空间。如果是这样，包装最后一个单词并重新开始计算下一行，以此类推。
使用断字，您需要采用通用格式的断字规则，例如：hy-phen-a-tion
然后它与上面的相同，只是您需要拆分导致溢出的最后一个单词。
Gang of Four Design Patterns一书中提供了一个很好的示例和教程，说明如何为优秀的文本编辑器构建代码。这是他们展示模式的主要样本之一。
对于我自己的编辑器项目，我想知道同样的事情。我的解决方案是一个两步过程：
当您需要显示文本时，找到有问题的行并将它们快速换行。在缓存中记住此信息以便快速重绘。当用户滚动整个页面时，刷新缓存并重复。
如果可以，请在后台线程中加载/分析整个文本。这样，您就可以在文档的其余部分仍在检查时显示文本的第一页。这里最简单的解决方案是删除前 16 KB 的文本并在子字符串上运行算法。这非常快，即使您的编辑器仍在加载文本，您也可以立即呈现第一页。
当光标最初位于文本末尾时，您可以使用类似的方法；只需阅读最后 16 KB 的文本并对其进行分析。在这种情况下，使用两个编辑缓冲区并将除最后 16 KB 之外的所有内容加载到第一个缓冲区中，而用户被锁定到第二个缓冲区中。当你关闭编辑器时，你可能想记住文本有多少行，所以滚动条看起来并不奇怪。
当用户可以将光标放在中间某处启动编辑器时，它会变得很棘手，但最终它只是最终问题的扩展。只需要记住字节位置、当前行号和上次会话的总行数，另外还需要三个编辑缓冲区，或者需要一个可以在中间切掉 16 KB 的编辑缓冲区。
或者，在文本加载时锁定滚动条和其他界面元素；允许用户在完全加载时查看文本。
我不能声称它没有错误，但我需要一个单词包裹并遵守缩进边界的东西。除了到目前为止它对我有用之外，我对这段代码没有任何要求。这是一种扩展方法，违反了 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);
}
}
}
这是我今天在 C 语言中工作的乐趣：
以下是我的考虑：
不复制字符，只打印到标准输出。因此，由于我不喜欢修改 argv[x] 参数，并且因为我喜欢挑战，所以我想在不修改的情况下进行。我没有考虑插入'\n'.
我不想
This line breaks here
成为
This line breaks
here
因此，鉴于此目标，将字符更改'\n'为不是一种选择。
如果线宽设置为 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我想设置为一行的开头和一行的最后一个字符。设置好后，我将所有字符从头到尾输出到标准输出，然后输出 a '\n'，然后继续下一行。
最初一切都指向开始，然后我跳过带有while(!isDelim(*current)) ++current,++chars;. 当我这样做时，我记得 80 个字符 ( lastChar) 之前的最后一个字符。
如果在一个单词的末尾，我已经通过了我的字符数（80），那么我就离开了while(chars <= wrapLength)。start我输出andlastChar和 a之间的所有字符newline。
然后我设置current并lastChar+1跳过分隔符（如果这导致我到字符串的末尾，我们就完成了，return 0）。将start,lastChar和设置current为下一行的开头。
这
if(*current == '\0'){
puts(start);
return 0;
}
部分是用于太短而无法包装一次的字符串。我在写这篇文章之前添加了这个，因为我尝试了一个短字符串但它不起作用。
我觉得这可能以更优雅的方式可行。如果有人有什么建议，我很乐意尝试。
当我写这篇文章时，我问自己“如果我的字符串是一个比我的 wraplength 长的单词会发生什么” 好吧，它不起作用。所以我添加了
if( lastChar == start )
lastChar = current-1;
在printLine()语句之前（如果lastChar没有移动，那么我们有一个单词对于单行来说太长了，所以我们只需要把整个东西放在一行上）。
自从我写这篇文章以来，我从代码中删除了注释，但我真的觉得必须有比我不需要注释的更好的方法来做到这一点。
这就是我如何写这个东西的故事。我希望它可以对人们有用，我也希望有人对我的代码不满意，并提出一种更优雅的方法。
应该注意的是，它适用于所有边缘情况：对于一行来说太长的单词、短于一个 wrapLength 的字符串和空字符串。
@ICR，感谢分享 C# 示例。
我没有成功使用它，但我想出了另一个解决方案。如果对此有任何兴趣，请随时使用： C# 中的 WordWrap 函数。源代码在 GitHub 上可用。
我已经包含了单元测试/示例。
我不妨加入我制作的 perl 解决方案，因为 gnufold -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);
}