ワード ラップは、最新のテキスト エディターに必須の機能の 1 つです。
ワードラップはどのように処理されますか? ワードラップに最適なアルゴリズムは何ですか?
テキストが数百万行の場合、ワードラップを非常に高速にするにはどうすればよいですか?
なぜこのソリューションが必要なのですか? 私のプロジェクトでは、さまざまなズーム レベルと美しい外観でテキストを描画する必要があるためです。
実行環境は Windows Mobile デバイスです。非常に小さなメモリ サイズで最大 600 MHz の速度。
回線情報はどのように扱えばよいですか？元のデータが 3 行あるとします。
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 行を割り当てる必要がありますか? または他の提案はありますか？
これは、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植字システムの改行アルゴリズムについて多くの作業を行いました。これは間違いなく、改行のための最良のアルゴリズムの1つであり、結果の視覚的外観の点で「最良」です。
彼のアルゴリズムは、非常に密な線の後に非常に緩い線が続く可能性がある貪欲な線の塗りつぶしの問題を回避します。
動的計画法を使用して、効率的なアルゴリズムを実装できます。
最近、ワードラップ関数を書く機会がありました。思いついたことを共有したいと思います。
Go の例とほぼ同じくらい厳格なTDDアプローチを使用しました。「Hello, world!」という文字列をラップするテストから始めました。幅が 80 の場合、"Hello, World!" が返されます。明らかに、動作する最も簡単な方法は、入力文字列をそのまま返すことです。そこから始めて、ますます複雑なテストを作成し、(少なくとも私の目的では) タスクを非常に効率的に処理する再帰的なソリューションにたどり着きました。
再帰的なソリューションの疑似コード:
関数 WordWrap (inputString、幅)
入力文字列の先頭と末尾のスペースを削除します。
トリミングされた文字列の長さが <= 幅の場合、
トリミングされた文字列を返します。
そうしないと、
width から始まる、トリミングされた文字列の最後のスペースのインデックスを検索します
スペースがない場合は、幅をインデックスとして使用します。
トリミングされた文字列をインデックスで 2 つに分割します。
インデックスの前の部分から末尾のスペースを削除し、
およびインデックスの後の部分から先頭のスペース。
連結して返す:
インデックスの前のトリミングされた部分、
改行、
その後、トリミングされた部分で WordWrap を呼び出した結果
インデックス (元の呼び出しと同じ幅)。
これはスペースでのみ折り返します。すでに改行を含む文字列を折り返したい場合は、改行で分割し、各部分をこの関数に送信してから、文字列を再構築する必要があります。それでも、高速なマシンで実行されている VB.NET では、これで約 20 MB/秒を処理できます。
特定のアルゴリズムについては知りませんが、次のように動作する方法の大まかな概要を示すことができます。
.NET では、ワード ラッピング機能が TextBox などのコントロールに組み込まれています。他の言語にも同様の組み込み機能が存在すると確信しています。
ハイフネーションあり/なし？
それがなければ簡単です。テキストを単語ごとに単語オブジェクトとしてカプセル化し、メソッド getWidth() を与えるだけです。次に、最初の単語から始めて、使用可能なスペースよりも大きくなるまで行の長さを合計します。その場合は、最後の単語をラップして、この行から始まる次の行のカウントを再開します。
ハイフネーションでは、次のような一般的な形式のハイフネーション ルールが必要です。
次に、オーバーフローの原因となった最後の単語を分割する必要があることを除いて、上記と同じです。
優れたテキスト エディター用にコードを構成する方法の良い例とチュートリアルは、Gang of Four Design Patterns book に記載されています。パターンを示す主要なサンプルの 1 つです。
私自身のエディター プロジェクトでも同じことを考えていました。私の解決策は、次の 2 段階のプロセスでした。
テキストを表示する必要がある場合は、問題の行を見つけてその場で折り返します。すばやく再描画できるように、この情報をキャッシュに保存してください。ユーザーがページ全体をスクロールしたら、キャッシュをフラッシュして繰り返します。
可能であれば、バックグラウンド スレッドでテキスト全体の読み込み/分析を行ってください。このようにして、文書の残りの部分がまだ検査されている間に、テキストの最初のページを表示することができます。ここでの最も簡単な解決策は、テキストの最初の 16 KB を切り取って、部分文字列に対してアルゴリズムを実行することです。これは非常に高速で、エディターがまだテキストをロードしている場合でも、最初のページを即座にレンダリングできます。
カーソルが最初にテキストの最後にある場合は、同様のアプローチを使用できます。最後の 16 KB のテキストを読み込んで分析するだけです。この場合、2 つの編集バッファーを使用し、ユーザーが 2 番目のバッファーにロックされている間に、最後の 16 KB を除くすべてを最初のバッファーに読み込みます。また、エディターを閉じたときに、スクロール バーが変に見えないように、テキストの行数を覚えておくとよいでしょう。
ユーザーがカーソルを途中に置いてエディターを起動できると、面倒になりますが、最終的には、最終的な問題の延長にすぎません。最後のセッションからのバイト位置、現在の行番号、および合計行数を覚えておく必要があるだけで、さらに 3 つの編集バッファーが必要になるか、途中で 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 文字を超えていない最後の単語の末尾の位置を覚えておく必要があります。
これが私のものです。きれいではありません。私は過去1時間、あちこちに何かを追加して、それを機能させようとして頭を悩ませてきました。私が知っているすべてのエッジケースで機能します。
#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とlastCharと の間のすべての文字を出力しますnewline。
次に、区切り文字を設定currentしlastChar+1てスキップします (そして、文字列の末尾に到達した場合は完了ですreturn 0)。start、lastCharおよびcurrent次の行の先頭に設定します。
の
if(*current == '\0'){
puts(start);
return 0;
}
部分は、短すぎて一度も巻き付けることができない紐用です。短い文字列を試してみましたがうまくいかなかったので、この投稿を書く直前にこれを追加しました。
これはもっとエレガントな方法で実行できると思います。誰かが提案するものを持っているなら、私はそれを試してみたい.
そして、これを書いているとき、「ラップレングスよりも長い 1 単語の文字列があるとどうなるか」と自問しましたが、うまくいきません。だから私は追加しました
if( lastChar == start )
lastChar = current-1;
printLine()ステートメントの前(lastChar移動していない場合は、単語が長すぎて 1 行に収まらないため、とにかく全体を行に配置する必要があります)。
これを書いているので、コードからコメントを削除しましたが、コメントを必要としない方法よりも、これを行うためのより良い方法があるに違いないと本当に感じています。
それが、私がこのことをどのように書いたかという話です。それが人々の役に立てば幸いです。また、誰かが私のコードに満足せず、よりエレガントな方法を提案してくれることを願っています。
これは、すべてのエッジ ケースで機能することに注意してください。つまり、1 行に対して長すぎる単語、wrapLength より短い文字列、および空の文字列です。
@ICR、C# の例を共有してくれてありがとう。
私はそれを使用することに成功しませんでしたが、別の解決策を思いつきました. これに興味がある場合は、これを自由に使用してください: C# の WordWrap 関数。ソースはGitHubで入手できます。
単体テスト/サンプルを含めました。
fold -sgnuは末尾のスペースやその他の悪い動作を残していたので、私が作成した perl ソリューションでチャイムを鳴らすこともできます。このソリューションは、CRLF の行末を処理し、それらをすべて LF に変換しますが、タブやバックスペース、または埋め込まれたキャリッジ リターンなどを含むテキストを (適切に) 処理しません。テキストに最小限の変更を加えます。特に、単語を分割することはありません (変化しませんwc -w)。行にスペースが 1 つしかない (および 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);
}