Лучший алгоритм переноса слов?

Ответ 1

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

Function WordWrap (inputString, width)
    Trim the input string of leading and trailing spaces.

    If the trimmed string length is <= the width,
        Return the trimmed string.
    Else,
        Find the index of the last space in the trimmed string, starting at width

        If there are no spaces, use the width as the index.

        Split the trimmed string into two pieces at the index.

        Trim trailing spaces from the portion before the index,
        and leading spaces from the portion after the index.

        Concatenate and return:
          the trimmed portion before the index,
          a line break,
          and the result of calling WordWrap on the trimmed portion after
            the index (with the same width as the original call).

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

Ответ 4

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

Ответ 5

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

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

Вопрос. В .net функция переноса слов встроена в элементы управления, такие как TextBox. Я уверен, что аналогичные встроенные функции существуют и для других языков. Есть ли причина, по которой вы не хотите использовать готовое решение? Это похоже на то, как изобретать колесо.

Ответ 6

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

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

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

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

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

Ответ 7

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

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

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

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

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

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

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

Ответ 8

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

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

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 и a newline.

Затем я установил current в lastChar+1 и пропустил разделители (и если это приведет меня к концу строки, мы закончили, return 0). Установите start, lastChar и current в начало следующей строки.

if(*current == '\0'){
    puts(start);
    return 0;
}

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

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

И, как я написал это, я спросил себя: "Что произойдет, если у меня есть строка, которая является одним словом, которое больше, чем моя длина wapplength". Ну, это не работает. Поэтому я добавил

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

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

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

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

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

Ответ 9

Вот решение на С#. он разлил только слово, превышающее заданный предел, и другие слова остаются как обычно.

        /// <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;
        }

Ответ 10

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

Ответ 11

@ICR, спасибо, что поделились примером С#. Мне не удалось его использовать, но я нашел другое решение. Если есть какой-либо интерес к этому, пожалуйста, не стесняйтесь использовать это: https://web.archive.org/web/20160403050733/http://johan.andersson.net/2010/11/03/wordwrap-function-in -c/. Источник доступен на GitHub.

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

Ответ 12

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

}