Алгоритм для преобразования текста по левому краю для выравнивания

Question

Недавно меня попросили в интервью разработать алгоритм для преобразования входной строки с выравниванием по левому краю (с пробелами в конце каждой строки) в Justify (без пробелов в конце полной строки), аналогично тому, что в MS Word. Я предложил ему какое-то базовое решение, которое включало подсчет количества слов и количества пробелов в каждой строке, а затем равномерное распределение их по всем пробелам (он попросил меня предположить, что дробное пространство можно распределить между словами). Но позже он попросил меня рассмотреть весь абзац, а затем изменить текст, чтобы красота текста не терялась, когда неравномерное распределение пробелов между словами неизбежно.

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

PS: решение, которое я предложил, было очень абстрактной идеей, поэтому у меня нет кода, чтобы показать все, что я уже пробовал. Обоснование: http://en.wikipedia.org/wiki/Justification_(typesetting)

Answer 1

Стандартным алгоритмом разбиения абзацев на строки, вероятно, все еще остается алгоритм Кнута и Пласса, используемый системой набора текста Кнута. TeX, Алгоритм, который "избегает обратного отслеживания путем разумного использования методов динамического программирования ", описан в

Дональд Э. Кнут и Майкл Ф. Пласс, Программное обеспечение - практика и опыт 11 (1981) 1119-1184 http://dx.doi.org/10.1002/spe.4380111102, также доступный в Digital Typography, Ch. 3, с. 67–155.

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

Упрощенная версия алгоритма (например, без переносов) может быть описана так:

Add start of paragraph to list of active breakpoints
For each possible breakpoint (space) B_n, starting from the beginning:
   For each breakpoint in active list as B_a:
      If B_a is too far away from B_n:
          Delete B_a from active list
      else
          Calculate badness of line from B_a to B_n
          Add B_n to active list
          If using B_a minimizes cumulative badness from start to B_n:
             Record B_a and cumulative badness as best path to B_n

The result is a linked list of breakpoints to use.

The badness of lines under consideration can be calculated like this:

Each space is assigned a nominal width, a strechability, and a shrinkability.
The badness is then calculated as the ratio of stretching or shrinking used,
relative to what is allowed, raised e.g. to the third power (in order to
ensure that several slightly bad lines are prefered over one really bad one)

Иллюстрированное описание можно найти по адресу http://defoe.sourceforge.net/folio/knuth-plass.html

Реализации на разных языках доступны в Интернете, например, реализация Брэма Стейна в Javascript: http://www.bramstein.com/projects/typeset/

Answer 2

Это может быть старая тема.

Но все равно хотел поделиться решением в случае, если оно поможет.

Алгоритм выравнивания текста

Answer 3

Я бы посоветовал всем, кто хочет вдаваться в подробности и разобраться в этой проблеме, посмотреть курс MIT 6.006 - Лекция №20.

Вот ссылка на него.

https://www.youtube.com/watch?v=ENyox7kNKeY

Answer 4

Я сделал функцию Space-Inserter:)

Но просто вставьте пробел, пока ширина линии не станет меньше желаемой ширины.

    public static List<string> GetText(string text, int width)
    {
        string[] palabras = text.Split(' ');
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        int length = palabras.Length;
        List<string> resultado = new List<string>();
        for (int i = 0; i < length; i++)
        {
            sb1.AppendFormat("{0} ", palabras[i]);
            if (sb1.ToString().Length > width)
            {
                resultado.Add(sb2.ToString());
                sb1 = new StringBuilder();
                sb2 = new StringBuilder();
                sb1.AppendFormat("{0} ", palabras[i]);
            }
            else
            {
                sb2.AppendFormat("{0} ", palabras[i]);
            }
        }
        resultado.Add(sb2.ToString());

        List<string> resultado2 = new List<string>();
        string temp;

        int index1, index2, salto;
        string target;
        int limite = resultado.Count;
        foreach (var item in resultado)
        {
            target = " ";
            temp = item.ToString().Trim();
            index1 = 0; index2 = 0; salto = 2;

            if (limite <= 1)
            {
                resultado2.Add(temp);
                break;
            }
            while (temp.Length <= width)
            {
                if (temp.IndexOf(target, index2) < 0)
                {
                    index1 = 0; index2 = 0;
                    target = target + " ";
                    salto++;
                }
                index1 = temp.IndexOf(target, index2);
                temp = temp.Insert(temp.IndexOf(target, index2), " ");
                index2 = index1 + salto;

            }
            limite--;
            resultado2.Add(temp);
        }
        return resultado2;
    }

Надеюсь, поможет!