全局优化分页框架
在 DocEng ‘16 ACM 文档工程研讨会上，Frank 发表了一篇关于“全局优化分页框架”的论文，讨论了一种使用动态规划方法的全局优化分页算法及其理论基础。该论文荣获会议“ACM 最佳论文奖”。
完整论文可以从 ACM 数字图书馆下载，链接位于出版物页面。
论文摘要
分页问题处理的是关于将源文本流转换为格式化文档的问题，方法是将其划分为单独的列和页，包括添加与源流数据有一定关系但可能允许在位置上有所变化的辅助元素（例如，图或脚注）。
传统上，分页问题是通过将其分为微观排版（例如，将文本分解为段落，也称为 h&j）和宏观排版（例如，获取已格式化段落的清样并将其分解为列和页）来解决的，两者之间没有太多互动。
虽然早期针对这两个问题空间的解决方案都使用了简单的贪婪算法，但 Knuth 和 Plass 在 80 年代引入了一种全局拟合算法用于断行，该算法优化了整个段落的断行 [1]。该算法在 TeX’82 [2] 中实现，并且自那时以来一直保持着其作为该领域最佳可用解决方案的桂冠。然而，对于宏观排版，一直没有（成功）尝试提供全局优化的页面布局：迄今为止的所有系统（包括 TeX）都使用贪婪算法进行分页。该领域的各种问题都得到了研究（例如，[3,4,5,6]），并且文献记录了一些原型开发。但是，这些原型都没有广泛提供给研究界，也没有进入通用且公开可用的系统。
本文提出了一个基于 Knuth/Plass 思想的页面断行全局拟合算法框架。它的实现方式使其可以直接使用，而无需额外的可执行文件，即可与任何现代 TeX 安装一起使用。因此，它可以作为未来在该领域进行实验和扩展的试验台。同时，当前原型的清理版本有可能成为全球大量 TeX 用户的生产工具。
本文还讨论了两个已经实现的扩展，它们增加了分页过程的灵活性：自动考虑段落长度中现有灵活性的能力（通过考虑具有不同行数的段落变体 [7]）以及在跨页上运行长或短一行的列的概念。最后，它讨论了总体方法、其固有的局限性以及未来研究的方向。
[1] D. E. Knuth and M. F. Plass. Breaking Paragraphs into Lines. Software-Practice and Experience, 11(11):1119-1184, Nov. 1981.
[2] D. E. Knuth. TeX: The Program, volume B of Computers and Typesetting. Addison-Wesley, Reading, MA, USA, 1986.
[3] A. Brüggemann-Klein, R. Klein, and S. Wohlfeil. Computer science in perspective. Chapter On the Pagination of Complex Documents, pages 49-68. Springer-Verlag New York, Inc., New York, NY, USA, 2003.
[4] C. Jacobs, W. Li, and D. H. Salesin. Adaptive document layout via manifold content. In Second International Workshop on Web Document Analysis (wda2003), Liverpool, UK, 2003, 2003.
[5] A. Holkner. Global multiple objective line breaking. Master’s thesis, School of Computer Science and Information Technology, RMIT University, Melbourne, Victoria, Australia, 2006.
[6] P. Ciancarini, A. Di Iorio, L. Furini, and F. Vitali. High-quality pagination for publishing. Software-Practice and Experience, 42(6):733-751, June 2012.
[7] T. Hassan and A. Hunter. Knuth-Plass revisited: Flexible line-breaking for automatic document layout. In Proceedings of the 2015 ACM Symposium on Document Engineering, DocEng ‘15, pages 17-20, New York, NY, USA, 2015.