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

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

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

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

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

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

Статья о разрыве линии TeX .

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

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

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

    If the trimmed string's 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 mb/sec.

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

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

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

С переносами или без них?

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

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

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

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

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

1. Найдите концы линий и сохраните их в массиве.
2. Для очень длинных линий найдите подходящие точки разрыва примерно через 1K интервалов и сохраните их в линейном массиве. Это для того, чтобы поймать "4MB text without a single line break".

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

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

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

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

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

Вот мой, над которым я сегодня работал для удовольствия в C:

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

1) Отсутствие копирования символов, просто печать в stdout. Поэтому, поскольку я не люблю изменять аргументы 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 , которые я хочу установить в качестве начала строки и последнего символа строки. Когда они установлены, я вывожу в stdout все символы от начала до конца, затем выводим '\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;
}

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

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

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

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

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

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

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

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

Вот решение в 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;
        }

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

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

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

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

}