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

Question

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

当时我想不出任何合适的解决方案。后来他告诉我这是用动态规划做的。我不确定是否已经有一些标准算法。如果是，请分享一些有用的链接。

PS: 我提出的解决方案是非常抽象的想法，因此我没有任何代码来展示我已经尝试过的所有内容。理由:http://en.wikipedia.org/wiki/Justification_(typesetting)

Answer 1

将段落分成行的标准算法可能仍然是 Knuth 的排版系统 TeX 使用的 Knuth & Plass 算法。

中描述了 “通过明智地使用动态规划技术避免回溯”的算法

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/