Лучший алгоритм переноса слов?
Перенос слов - одна из обязательных функций в современном текстовом редакторе.
Вы знаете, как обрабатывать перенос слов? Какой лучший алгоритм для переноса слов?
обновлено: если текст состоит из нескольких миллионов строк, как я могу сделать перенос слов очень быстрым?
обновлено: зачем мне решение? Потому что мои проекты должны рисовать текст с разным уровнем масштабирования и одновременно красивым внешним видом.
обновлено: рабочая среда - устройства Windows Mobile. Максимальная скорость 600 МГц с очень маленьким объемом памяти.
обновлено: как мне обрабатывать информацию о линиях? Давайте предположим, что исходные данные состоят из трех строк.
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 строки? Или какие-либо другие предложения?
12 ответов
Вот алгоритм переноса слов, который я написал на 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-overflow), хотя он не способствует перемещению небольших переносимых слов на новую строку, а не разбивает их. Это разделяет слова, если они слишком длинные для строки.
Это также довольно специфично с точки зрения культуры, так как я мало знаю о правилах переноса слов в других культурах.
Дональд Э. Кнут проделал большую работу над алгоритмом разрыва строки в своей системе набора текста TeX. Возможно, это один из лучших алгоритмов переноса строк - "лучший" с точки зрения визуального отображения результата.
Его алгоритм позволяет избежать проблем с жадным заполнением линий, когда вы можете получить очень плотную линию, за которой следует очень свободная линия.
Эффективный алгоритм может быть реализован с использованием динамического программирования.
Я не знаю, будет ли кто-нибудь когда-нибудь читать это, видя, сколько лет этому вопросу, но у меня была возможность недавно написать функцию переноса слов, и я хочу поделиться тем, что я придумал. Я использовал подход TDD, почти такой же строгий, как и в примере с Go. Я начал с теста, заключающего строку "Привет, мир!" на ширине 80 должен возвращаться "Hello, World!" Очевидно, что самое простое, что работает, - это вернуть входную строку без изменений. Исходя из этого, я проводил все более сложные тесты и получил рекурсивное решение, которое (по крайней мере, для моих целей) довольно эффективно справляется с задачей.
Псевдокод для рекурсивного решения:
Функция WordWrap (inputString, ширина)
Обрезать входную строку начальных и конечных пробелов.
Если длина обрезанной строки <= ширина,
Верните урезанную строку.
В противном случае,
Найти индекс последнего пробела в обрезанной строке, начиная с ширины
Если пробелов нет, используйте ширину в качестве индекса.
Разделите обрезанную строку на две части по указателю.
Обрезать конечные пробелы от части до индекса,
и начальные пробелы из части после индекса.
Конкатенация и возврат:
усеченная часть перед указателем,
разрыв строки,
и результат вызова WordWrap на обрезанной части после
индекс (с той же шириной, что и исходный вызов).
Это переносит только пробелы, и если вы хотите обернуть строку, которая уже содержит разрывы строк, вам нужно разбить ее на разрывы строк, отправить каждый фрагмент этой функции и затем снова собрать строку. Тем не менее, в VB.NET, работающем на быстрой машине, это может обрабатывать около 20 МБ / с.
Что касается вашего обновления и скорости вопроса, не забудьте оптимизировать позже. Сначала напишите свой алгоритм переноса слов. Запустите его на миллион строк, если текст. Если и только если это слишком медленно для ваших требований, то оптимизируйте.
Я не знаю каких-либо конкретных алгоритмов, но следующее не будет грубым описанием того, как это должно работать:
- Для текущего размера текста, шрифта, размера экрана, размера окна, полей и т. Д. Определите, сколько символов может уместиться на строке (если используется фиксированный тип) или сколько пикселей может уместиться на строке (если не фиксированный тип).
- Проходите строку за символом, вычисляя, сколько символов или пикселей было записано с начала строки.
- Когда вы пропустите максимальный размер символов / пикселей для строки, вернитесь к последнему знаку пробела / пунктуации, переместите весь текст на следующую строку.
- Повторяйте, пока не пройдете весь текст в документе.
Вопрос: В.net функция переноса слов встроена в такие элементы управления, как TextBox. Я уверен, что подобная встроенная функциональность существует и для других языков. Есть ли причина, по которой вы не хотите использовать готовое решение? Это похоже на то, как изобретать велосипед.
С или без переносов?
без этого легко. Просто инкапсулируйте ваш текст как wordobjects для каждого слова и дайте им метод getWidth(), затем начните с первого слова, добавляя длину строки, пока она не станет больше доступного пространства. если это так, оберните последнее слово и начните считать снова для следующего ряда, начиная с этого ecetera.
При использовании переносов вам нужны правила переноса в общем формате, например: hy-phen-a-tion
Затем то же самое, что и выше, за исключением того, что вам нужно разделить последнее слово, вызвавшее переполнение.
Хороший пример и учебное пособие о том, как структурировать ваш код для превосходного текстового редактора, приведен в книге "Банды четырех шаблонов дизайна". Это один из основных образцов, на которых они показывают образцы.
Я задавался вопросом, то же самое для моего собственного редактора проекта. Мое решение состояло из двух этапов:
- Найдите концы строк и сохраните их в массиве.
- Для очень длинных линий найдите подходящие точки разрыва примерно с интервалом 1K и сохраните их также в массиве строк. Это для того, чтобы поймать "4MB текст без единого переноса строки".
Когда вам нужно отобразить текст, найдите нужные строки и оберните их на лету. Запомните эту информацию в кеше для быстрой перерисовки. Когда пользователь прокрутит всю страницу, очистите кеш и повторите.
Если вы можете, загрузите / проанализируйте весь текст в фоновом потоке. Таким образом, вы уже можете отобразить первую страницу текста, пока остальная часть документа все еще проверяется. Самое простое решение здесь - вырезать первые 16 КБ текста и запустить алгоритм на подстроке. Это очень быстро и позволяет вам визуализировать первую страницу мгновенно, даже если ваш редактор все еще загружает текст.
Вы можете использовать аналогичный подход, когда курсор изначально находится в конце текста; просто прочитайте последние 16 КБ текста и проанализируйте это. В этом случае используйте два буфера редактирования и загрузите все, кроме последних 16 КБ, в первый, пока пользователь заблокирован во втором буфере. И вы, вероятно, захотите вспомнить, сколько строк имеет текст при закрытии редактора, поэтому полоса прокрутки не выглядит странно.
Это становится проблематично, когда пользователь может запустить редактор с курсором где-то посередине, но, в конечном счете, это только расширение конечной проблемы. Только вам нужно запомнить позицию байта, текущий номер строки и общее количество строк из последнего сеанса, плюс вам нужно три буфера редактирования или вам нужен буфер редактирования, где вы можете вырезать 16 КБ в середине.
Или заблокируйте полосу прокрутки и другие элементы интерфейса во время загрузки текста; это позволяет пользователю просматривать текст, пока он полностью загружается.
Вот мой, над которым я работал сегодня для развлечения в Си:
Вот мои соображения:
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;
}
часть для строк, которые являются слишком короткими, чтобы быть обернутыми даже один раз. Я добавил это непосредственно перед написанием этого поста, потому что я попробовал короткую строку, и она не сработала.
Я чувствую, что это может быть выполнимо более элегантным способом. Если кому-то есть что предложить, я бы с удовольствием попробовал.
И когда я писал это, я спрашивал себя: "Что произойдет, если у меня будет строка, которая на одно слово длиннее моей длины"? Ну, это не работает. Поэтому я добавил
if( lastChar == start )
lastChar = current-1;
перед printLine() заявление (если lastChar не сдвинулся, у нас есть слово, которое слишком длинное для одной строки, так что нам все равно нужно просто поставить все в строку).
Я удалил комментарии из кода, так как я пишу это, но я действительно чувствую, что должен быть лучший способ сделать это, чем тот, который у меня есть, который не нуждался бы в комментариях.
Это история о том, как я написал эту вещь. Я надеюсь, что это может быть полезно для людей, и я также надеюсь, что кто-то будет недоволен моим кодом и предложит более элегантный способ сделать это.
Следует отметить, что он работает для всех крайних случаев: слишком длинных слов для строки, строк, длина которых меньше одного wrapLength, и пустых строк.
Я не могу требовать безошибочности этого, но мне нужно было одно слово, которое завернуто и подчиняется границам отступа. Я ничего не заявляю об этом коде, кроме того, что он работал для меня до сих пор. Это метод расширения, который нарушает целостность 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#. Разлито единственное слово с превышением заданного лимита, а остальные слова остаются как обычно.
/// <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;
}
Я также могу вмешаться в решение 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#. Мне не удалось его использовать, но я нашел другое решение. Если есть какой-либо интерес к этому, пожалуйста, не стесняйтесь использовать это: http://johan.andersson.net/2010/11/03/wordwrap-function-in-c/
Я включил модульные тесты / образцы.
Спасибо!