在现代文本编辑器中，换行是必备功能之一。
如何处理自动换行？什么是最佳自动换行算法？
如果文本有几百万行，如何使自动换行速度非常快？
为什么需要此解决方案？因为我的项目必须使用各种缩放级别绘制文本，并同时具有漂亮的外观。
运行环境是 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.
我应该再分配三行吗？或者有其他建议吗？
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 its 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 like 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
-overflow"的情况），
但它并不倾向于将小的连字符词移到新行而不是分割它们。
如果一行太长，它会将单词分割开。
由于我对其他文化的自动换行规则了解有限，所以这个功能也相对具有文化特定性。
唐纳德·E·克努斯在他的排版系统TeX中进行了许多关于断行算法的工作。可以说，这是最好的断行算法之一，其“最佳”体现在结果的视觉效果上。
他的算法避免了贪婪式的行填充所带来的问题，该问题可能会导致非常密集的一行，接着是非常稀疏的一行。
一个有效的算法可以使用动态规划来实现。
最近我有机会编写一个自动换行的函数，并且想分享一下我的成果。
我采用了一个TDD方法，几乎跟Go example的方法一样严格。我从测试开始，将字符串“Hello, world!”在80个字符宽度下换行返回“Hello, World!”。显然，最简单有效的方法就是不做任何处理地返回输入字符串。从这里开始，我逐渐增加了更多复杂的测试，并最终得到了一个递归解决方案，可以相当高效地处理任务（至少对于我的目的来说）。
递归解决方案的伪代码：
Function WordWrap (inputString, width)
去除输入字符串中前后空格。
如果去除空格后的字符串长度小于或等于宽度，
返回去除空格后的字符串。
否则，
从宽度处开始查找去除空格后的字符串中最后一个空格的索引。
如果没有空格，则使用宽度作为索引。
将去除空格后的字符串分成两部分。
从索引前面的部分去除尾随空格，
从索引后面的部分去除前导空格。
连接并返回：
索引前面的修剪部分，
一个换行符，
并调用WordWrap处理索引后面的修剪部分（使用与原始调用相同的宽度）的结果。
这仅在空格处换行，如果您想换行已经包含换行符的字符串，则需要在换行符处分割它，将每个片段发送到此函数，然后重新组装字符串。即便如此，在运行速度较快的VB.NET上，它也可以处理大约20 MB/秒。
width前面的空格。如果您有不成比例的字体，可以从那里开始测量行，当它超过宽度并记录最后一个空格索引时进行断开。 - Ray使用连字符还是不使用？
如果不使用，很容易，只需将您的文本封装为每个单词的wordobjects，并为它们提供一个getWidth() 方法。然后从第一个单词开始添加行长度，直到大于可用空间。如果是这样，换行并从下一行重新开始计数，以此类推。
如果使用连字号，则需要使用通用格式的连字号规则，例如：hy-phen-a-tion。
然后就与上述相同，但是需要拆分导致溢出的最后一个单词。
有关如何为优秀的文本编辑器构建代码结构的良好示例和教程在《设计模式》（Design Patterns） 一书中给出。这是他们展示模式的主要样本之一。
我今天为了好玩写了一些C语言代码：
以下是我的考虑：
No copying of characters, just printing to standard output. Therefore, since I don't like to modify the argv[x] arguments, and because I like a challenge, I wanted to do it without modifying it. I did not go for the idea of inserting '\n'.
I don't want
This line breaks here
to become
This line breaks
here
so changing characters to '\n' is not an option given this objective.
If the linewidth is set at say 80, and the 80th character is in the middle of a word, the entire word must be put on the next line. So as you're scanning, you have to remember the position of the end of the last word that didn't go over 80 characters.
So here is mine, it's not clean; I've been breaking my head for the past hour trying to get it to work, adding something here and there. It works for all edge cases that I know of.
#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;
}
So basically, I have start and lastChar that I want to set as the start of a line and the last character of a line. When those are set, I output to standard output all the characters from start to end, then output a '\n', and move on to the next line.
Initially everything points to the start, then I skip words with the while(!isDelim(*current)) ++current,++chars;. As I do that, I remember the last character that was before 80 chars (lastChar).
If, at the end of a word, I have passed my number of chars (80), then I get out of the while(chars <= wrapLength) block. I output all the characters between start and lastChar and a newline.
Then I set current to lastChar+1 and skip delimiters (and if that leads me to the end of the string, we're done, return 0). Set start, lastChar and current to the start of the next line.
The
if(*current == '\0'){
puts(start);
return 0;
}
part is for strings that are too short to be wrapped even once. I added this just before writing this post because I tried a short string and it didn't work.
I feel like this might be doable in a more elegant way. If anyone has anything to suggest I'd love to try it.
And as I wrote this I asked myself "what's going to happen if I have a string that is one word that is longer than my wraplength" Well it doesn't work. So I added the
if( lastChar == start )
lastChar = current-1;
before the printLine() statement (if lastChar hasn't moved, then we have a word that is too long for a single line so we just have to put the whole thing on the line anyway).
I took the comments out of the code since I'm writing this but I really feel that there must be a better way of doing this than what I have that wouldn't need comments.
So that's the story of how I wrote this thing. I hope it can be of use to people and I also hope that someone will be unsatisfied with my code and propose a more elegant way of doing it.
It should be noted that it works for all edge cases: words too long for a line, strings that are shorter than one wrapLength, and empty strings.
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），对于没有超过单个空格的文本（和没有 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);
}