将文本从左对齐转换为对齐的算法

Question

最近，在一次采访中，我被要求设计一种算法，将左对齐(每一行末尾有空格)的输入字符串转换为对齐(整行末尾没有空白)，类似于MS Word中的输入字符串。我提出了一些基本的解决方案，包括计算每行的单词数和空格数，然后在所有空间中平均分配它们(他要求我假设小数空间可以在单词之间分布)。但后来，他让我考虑整个段落，然后修改文本，使文字的美不会失去时，文字之间的不平等空间分配是不可避免的。

当时我想不出任何适当的解决办法。后来他告诉我，这是通过动态编程完成的。我不确定这方面是否已经有一些标准的算法。如果是，请分享一些有用的链接。

PS:我提出的解决方案是非常抽象的想法，因此我没有任何代码来显示我已经尝试过的所有内容。理由：(排版)

Answer 1

将段落分解成行的标准算法可能仍然是Knuth & Plass的算法，Knuth的排字系统TeX使用它。该算法“通过明智地使用动态规划技术避免回溯”将在

DonaldE.Knuth和MichaelF.Plass，软件-实践和经验11 (1981) 1119-1184 DOI: 10.1002/spe.4380111102，也可在数字排版，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上可以找到一个有插图的描述

各种语言的实现可在网络上获得，例如Bram在Javascript中的实现：http://www.bramstein.com/projects/typeset/

Answer 2

这可能是一条旧线。

但还是想分享解决方案以防有帮助。

文本校正算法

Answer 3

我做了一个空格插入函数:)

但是，只需插入一个空格，直到线宽小于所需宽度。

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

希望能帮上忙！