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

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

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

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

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

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

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


person popopome    schedule 20.08.2008    source источник
comment
Что касается вашего вопроса об обновлении и скорости, не забудьте оптимизировать позже. Сначала напишите свой алгоритм переноса слов. Запустите его на миллионе строк, если текст. Если и только если он слишком медленный для ваших требований, оптимизируйте.   -  person Greg Hewgill    schedule 20.08.2008
comment
Вопрос явно не указывает, что это для шрифтов фиксированной ширины, хотя примеры и использование в текстовом редакторе подразумевают это. Только в ответе Яакова Эллиса упоминается перенос текста для шрифтов нефиксированной ширины.   -  person Gnubie    schedule 01.05.2012
comment
Лучшее в каком смысле? Самый красивый, самый быстрый, самый маленький, самый простой, самый умный ...   -  person Carl Smith    schedule 07.01.2019


Ответы (10)


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

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

person ICR    schedule 20.08.2008
comment
Очень красиво и лаконично. Незначительная ошибка: если строка содержит разрыв строки, curLineLength следует установить в ноль (проще всего добавить '\ n' к разрывающим символам, а затем проверить, равно ли слово '\ n'). - person dbkk; 08.12.2009
comment
Также лучше не пытаться ставить дефис при разделении длинных слов, просто разорвите их. Правильный дефис в конце строки - сложная проблема даже для английского (а не английского или английского языков). - person dbkk; 08.12.2009
comment
Одна ошибка в этом - символы без пробелов. Например, если ваш пользователь ввел LATIN SMALL LETTER E, за которым следует COMBINING BREVE, и у него всего 50 слов, вы оставите от 2/3 до 1/2 каждой строки пустыми. Нормализация до FormC ограничит это всякий раз, когда есть один вариант кодовой точки комбинации, но в целом вам нужно сканировать и проверять каждый глиф, чтобы увидеть, является ли это символом интервала. Небольшая проблема, как правило, огромная проблема с некоторыми входами. - person dhasenan; 29.10.2015

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

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

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

Статья о разрыве строк в TeXе.

person Bjarke Ebert    schedule 12.11.2008

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

Я использовал подход TDD, почти такой же строгий, как и подход из Пример использования. Я начал с теста, в котором заключена строка «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 МБ / с.

person Instance Hunter    schedule 13.05.2009

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

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

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

person Yaakov Ellis    schedule 20.08.2008

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

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

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

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

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

person Sven Hecht    schedule 20.08.2008
comment
Почему за это проголосовали -1? Конечно, жадный алгоритм не оптимален, но ... - person ShreevatsaR; 13.05.2009
comment
бьет меня. Я тоже был удивлен. - person Sven Hecht; 19.05.2009
comment
Поскольку неправильно говорить, что легко написать эффективный алгоритм для этой работы, даже если вы игнорируете расстановку переносов, нетривиально. Также сложно создать любую версию, которая была бы эффективной как для шрифтов фиксированной, так и для переменной ширины. Легко неверно, отсюда и голосование "против". - person mjaggard; 12.08.2013

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

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

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

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

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

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

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

person Aaron Digulla    schedule 13.05.2009

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

Вот мой, над которым я сегодня ради развлечения работал на 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 и 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 и пустые строки.

person Philippe Carphin    schedule 10.06.2016

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

}
person Jeff Y    schedule 04.12.2015

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

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

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

person Johan Andersson    schedule 03.11.2010