Лучший алгоритм переноса слов? [закрыто]

Перенос слов - одна из обязательных функций в современном текстовом редакторе.

Как переносить слова? Какой лучший алгоритм для переноса слов?

Если текст состоит из нескольких миллионов строк, как я могу сделать перенос слов очень быстрым?

Зачем мне решение? Потому что мои проекты должны рисовать текст с разным уровнем масштабирования и одновременно красивым внешним видом.

Рабочая среда - устройства 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.

Стоит ли выделять еще три строки? Или какие-либо другие предложения?

20.08.2008 08:19:29
Что касается вашего обновления и скорости вопроса, не забудьте оптимизировать позже. Сначала напишите свой алгоритм переноса слов. Запустите его на миллион строк, если текст. Если и только если это слишком медленно для ваших требований, то оптимизируйте.
Greg Hewgill 20.08.2008 08:44:19
Вопрос явно не указывает, что это для шрифтов фиксированной ширины, хотя примеры и использование в «текстовом редакторе» подразумевают это. Только в ответе Яакова Эллиса упоминается перенос текста для шрифтов не фиксированной ширины.
Gnubie 1.05.2012 16:27:10
Лучший в каком смысле?
Carl Smith 7.01.2019 10:05:27
10 ОТВЕТОВ

С или без переносов?

Без этого легко. Просто инкапсулируйте свой текст как wordobjects для слова и дайте им метод getWidth (). Затем начните с первого слова, складывая длину строки, пока она не станет больше доступного пространства. Если это так, оберните последнее слово и начните считать снова для следующей строки, начиная с этой и т. Д.

Для переноса вам нужны правила переноса в общем формате, например: hy-phen-a -tion

Тогда это то же самое, что и выше, за исключением того, что вам нужно разделить последнее слово, вызвавшее переполнение.

Хороший пример и учебное пособие о том, как структурировать свой код для превосходного текстового редактора, приведен в книге «Банды четырех шаблонов дизайна» . Это один из основных образцов, на которых они показывают образцы.

4
28.04.2019 22:14:20
Почему за это проголосовали -1? Да, алгоритм жадности не оптимален, но ...
ShreevatsaR 13.05.2009 13:02:19
бьет меня Я тоже был удивлен.
Sven Hecht 19.05.2009 13:16:44
Поскольку неправильно говорить, что это «легко», нетривиально написать эффективный алгоритм для этой работы, даже если вы игнорируете переносы. Также трудно создать любую версию, которая была бы эффективна как для шрифтов фиксированной, так и для переменной ширины. Легко это неправильно, отсюда и голосование вниз.
mjaggard 12.08.2013 12:29:34

Я не знаю каких-либо конкретных алгоритмов, но следующее может быть приблизительным описанием того, как это должно работать:

  1. Для текущего размера текста, шрифта, размера экрана, размера окна, полей и т. Д. Определите, сколько символов может уместиться на строке (если используется фиксированный тип) или сколько пикселей может уместиться на строке (если не фиксированный тип) ).
  2. Проходите строку за символом, вычисляя, сколько символов или пикселей было записано с начала строки.
  3. Когда вы превысите максимальное количество символов / пикселей для строки, вернитесь к последнему пробелу / знаку препинания и переместите весь текст на следующую строку.
  4. Повторяйте, пока не пройдете весь текст в документе.

В .NET функция переноса слов встроена в элементы управления, такие как TextBox. Я уверен, что подобная встроенная функциональность существует и для других языков.

6
21.11.2019 11:32:19

Вот алгоритм переноса слов, который я написал на 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), хотя он не поддерживает перемещение небольших переносимых слов на новую строку вместо их разделения. Это разделяет слова, если они слишком длинные для строки.

Это также довольно специфично с точки зрения культуры, так как я мало знаю о правилах переноса слов в других культурах.

32
22.06.2014 06:33:02
Очень красиво и лаконично. Незначительная ошибка: если строка содержит разрыв строки, curLineLength должен быть установлен в ноль (проще всего добавить '\ n' к разрывным символам, а затем проверить, равно ли слово '\ n').
dbkk 8.12.2009 10:40:55
Также лучше не пытаться ставить дефис при разбиении длинных слов, просто разбивайте их. Правильные дефисы в конце строки - трудная проблема даже для английского языка (не для английского или английского).
dbkk 8.12.2009 10:46:27
Одна ошибка в этом - символы без пробелов. Например, если ваш пользователь ввел LATIN SMALL LETTER E, а затем COMBINING BREVE, и имеет всего 50 слов, вы оставите от 2/3 до 1/2 каждой строки пустыми. Нормализация в FormC будет ограничивать это всякий раз, когда есть один вариант кодовой точки комбинации, но в целом вам нужно будет сканировать и проверять каждый глиф, чтобы увидеть, является ли он пробелом. Небольшая проблема обычно, огромная проблема на некоторых входах.
dhasenan 28.10.2015 21:10:06

Дональд Э. Кнут проделал большую работу над алгоритмом разрыва строки в своей системе набора текста TeX. Возможно, это один из лучших алгоритмов переноса строк - «лучший» с точки зрения визуального отображения результата.

Его алгоритм позволяет избежать проблем с жадным заполнением строк, когда вы можете получить очень плотную линию, за которой следует очень свободная линия.

Эффективный алгоритм может быть реализован с использованием динамического программирования.

Документ о разрыве строк TeX .

25
23.06.2013 23:43:00

Недавно у меня была возможность написать функцию переноса слов, и я хочу поделиться тем, что я придумала.

Я использовал подход TDD, почти такой же строгий, как и в примере с Go . Я начал с теста, заключающего строку «Привет, мир!» на ширине 80 должно возвращаться «Hello, World!». Ясно, что самое простое, что работает, - это вернуть входную строку без изменений. Исходя из этого, я проводил все более сложные тесты и получил рекурсивное решение, которое (по крайней мере, для моих целей) довольно эффективно справляется с задачей.

Псевдокод для рекурсивного решения:

Функция WordWrap (inputString, ширина)
    Обрезать входную строку начальных и конечных пробелов.

    Если длина обрезанной строки <= ширина,
        Верните урезанную строку.
    В противном случае,
        Найти индекс последнего пробела в обрезанной строке, начиная с ширины

        Если пробелов нет, используйте ширину в качестве индекса.

        Разделите обрезанную строку на две части по указателю.

        Обрезать конечные пробелы от части до индекса,
        и начальные пробелы из части после индекса.

        Конкатенация и возврат:
          усеченная часть перед указателем,
          разрыв строки,
          и результат вызова WordWrap на обрезанной части после
            индекс (с той же шириной, что и исходный вызов).

Это переносит только пробелы, и если вы хотите обернуть строку, которая уже содержит разрывы строк, вам нужно разбить ее на разрывы строк, отправить каждый фрагмент этой функции и затем снова собрать строку. Тем не менее, в VB.NET, работающем на быстрой машине, это может обрабатывать около 20 МБ / с.

22
21.11.2019 11:37:35

Я задавался вопросом о том же самом для моего собственного редактора проекта. Мое решение состояло из двух этапов:

  1. Найдите конец строки и сохраните их в массиве.
  2. Для очень длинных линий найдите подходящие точки разрыва примерно с интервалом 1K и сохраните их также в массиве строк. Это для того, чтобы поймать «4 МБ текста без разрыва строки».

Когда вам нужно отобразить текст, найдите нужные строки и оберните их на лету. Запомните эту информацию в кеше для быстрой перерисовки. Когда пользователь прокрутит всю страницу, очистите кеш и повторите.

Если вы можете, загрузите / проанализируйте весь текст в фоновом потоке. Таким образом, вы уже можете отобразить первую страницу текста, пока остальная часть документа еще рассматривается. Самое простое решение здесь - вырезать первые 16 КБ текста и запустить алгоритм на подстроке. Это очень быстро и позволяет вам визуализировать первую страницу мгновенно, даже если ваш редактор все еще загружает текст.

Вы можете использовать аналогичный подход, когда курсор изначально находится в конце текста; просто прочитайте последние 16 КБ текста и проанализируйте это. В этом случае используйте два буфера редактирования и загрузите все, кроме последних 16 КБ, в первый, пока пользователь заблокирован во втором буфере. И вы, вероятно, захотите вспомнить, сколько строк имеет текст при закрытии редактора, поэтому полоса прокрутки не выглядит странно.

Это становится проблематично, когда пользователь может запустить редактор с курсором где-то посередине, но в конечном итоге это только расширение конечной проблемы. Только вы должны помнить позицию байта, текущий номер строки и общее количество строк из последнего сеанса, плюс вам нужно три буфера редактирования или вам нужен буфер редактирования, где вы можете вырезать 16 КБ в середине.

Или заблокируйте полосу прокрутки и другие элементы интерфейса во время загрузки текста; это позволяет пользователю просматривать текст, пока он полностью загружается.

3
21.11.2019 11:40:54

@ICR, спасибо, что поделились примером C #.

Мне не удалось его использовать, но я нашел другое решение. Если есть какой-либо интерес к этому, пожалуйста, не стесняйтесь использовать это: Функция WordWrap в C # . Источник доступен на GitHub .

Я включил модульные тесты / образцы.

0
21.11.2019 11:42:27

Я не могу требовать безошибочности этого, но мне нужно было одно слово, которое завернуто и подчиняется границам отступа. Я ничего не заявляю об этом коде, кроме того, что он работал для меня до сих пор. Это метод расширения, который нарушает целостность 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);
        }
    }
}
1
22.04.2015 20:06:41

Я также могу вмешаться в решение 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);

}
0
4.12.2015 21:33:21

Вот мой, над которым я работал сегодня для развлечения в Си:

Вот мои соображения:

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что я хочу установить в качестве начала строки и последний символ строки. Когда они установлены, я вывожу на стандартный вывод все символы от начала до конца, затем выводю 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;
}

часть для строк, которые являются слишком короткими, чтобы быть обернутыми хотя бы один раз. Я добавил это прямо перед написанием этого поста, потому что я попробовал короткую строку, и она не сработала.

Я чувствую, что это может быть выполнимо более элегантным способом. Если кому-то есть что предложить, я бы с удовольствием попробовал.

И когда я написал это, я спросил себя: «Что произойдет, если у меня будет строка, которая на одно слово длиннее моей длины»? Ну, это не работает. Поэтому я добавил

if( lastChar == start )
     lastChar = current-1;

перед printLine()оператором (если lastCharон не сдвинулся, то у нас есть слово, которое слишком длинное для одной строки, так что мы все равно просто помещаем все это в строку).

Я удалил комментарии из кода, так как я пишу это, но я действительно чувствую, что должен быть лучший способ сделать это, чем тот, который у меня есть, который не нуждался бы в комментариях.

Вот история о том, как я написал эту вещь. Я надеюсь, что это может быть полезным для людей, и я также надеюсь, что кто-то будет недоволен моим кодом и предложит более элегантный способ сделать это.

Следует отметить, что он работает для всех крайних случаев: слишком длинных слов для строки, строк, длина которых меньше одного wrapLength, и пустых строк.

2
8.03.2017 05:25:39