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

Question

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

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

PS：我提出的解决方案是一个非常抽象的想法，因此我没有任何代码可以显示我已经尝试过的一切。理由：http : //en.wikipedia.org/wiki/Justification_（排版）

Answer 1

将段落分成几行的标准算法可能仍然是Knuth排版系统使用的Knuth＆Plass算法TeX。该算法描述为“避免通过明智地使用动态编程技术来回溯 ”。

Donald E. Knuth和Michael F. Plass，软件-实践与经验 11（1981）1119-1184 DOI：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找到插图说明。

Web上提供了各种语言的实现，例如 Bram Stein用Javascript实现：http : //www.bramstein.com/projects/typeset/