Pagination of Complex Documents

Abstract

This work investigates the pagination problem of complex documents. The problem is in placing text and floating objects on pages in such a way that each object appears close to, but not before, its text reference. Current electronic formatting systems do not offer the pagination quality provided by human experts in the traditional bookprinting process.

For the sake of efficiency, it would be desirable to employ an online pagination algorithm that computes a good placement of text and floating objects during a single pass over the input. We prove that this is only possible in a restricted document model. But in a more realistic model no competitive online algorithm exists.

The algorithmic difficulty of the pagination problem also depends on the measure of quality used. In this work we propose, as a measure of quality, the total number of page turns necessary for reading the document and looking up all referenced objects. We show that this weighted objective function can be optimized by a dynamic programming approach, in time proportional to the product of the numbers of text blocks and floating objects.

We have implemented a prototype document formatter based on this pagination algorithm. Tests on real-world documents that were previously formatted by Word, FrameMaker, or LaTeX, and fine-tuned by expert users, have produced considerable improvements. In addition to the features mentioned above, our formatter can cope with additional pagination constraints commonly used in professional printing.

Table of Contents

• Introduction (21K, HTML)
• Document Models
• Pagination Problem
• Online Pagination Algorithms
• Pagination by Dynamic Programming
• Implementation of XFormatter
• Practical Results
• Conclusions (22K, HTML)

Note: As this work has been published as a book (see [Woh98]) we only summarize it on the WWW. A technical report (PDF, 138K) that contains the first results of this work is available online. Another technical report (PDF, 540K) summarizes the results of the book and is available online, too.

Bibliography

• [Ash90] G. Asher. Type&Set: TeX as the engine of a friendly publishing system. In M. Clark, editor, TeX: Applications, Uses, Methods, pages 91-100, Chichester, UK 1990. Ellis Horwood Publishers. Proceedings of the TeX88 Confernece.
• [BKKW95] A. Brüggemann-Klein, R. Klein, S. Wohlfeil. Pagination Reconsiderd. Electronic Publishing: Origination, Dissemination, and Design. 8(2/3):139-152, 1995.
• [BKKW96] A. Brüggemann-Klein, R. Klein, S. Wohlfeil. Pagination Reconsidered. Technical Report, Fernuniversität Hagen, Germany, 1996.
• [BKKW98] A. Brüggemann-Klein, R. Klein, S. Wohlfeil. On the Pagination of Complex Documents. Technical Report, Fernuniversität Hagen, Germany, 1998.
• [Eva90] David R. Evans. An Investigation of Parallelism in Document Processing. PhD thesis, University of Nottingham, UK, 1990.
• [GB93] Michael J. Groves and David F. Bailsford. Separate compilation of structured documents. Electronic Publishing-Origination, Dissemination, and Design. 6(4):315-326, December 1993.
• [HH88] Wilfred J. Hansen and Christina Haas. Reading and Writing with Computers: A Framework for Explaining Differences in Performance. Communications of the ACM, 31(9):1080-1089, September 1988.
• [Knu86] Donald E. Knuth. The TeXbook, volume A of Computer & Typesetting. Addison Wesley Publishing Company, Reading, MA, 1986.
• [KW89] B. W. Kernighan and Ch. J. Van Wyk. Page makeup by postprocessing text formatter output. Computing Systems, 2(2):103-132, 1998.
• [Lag95] Krista Lagus. Automated pagination of the generalized newspaper using simulated annealing. Master's thesis, Helsinki University of Technology, Helsinky, Finland, 1995.
• [Pla81] M. F. Plass. Optimal pagination techniques for automatic typesetting systems. Technical Report STAN-CS-81-870, Department of Computer Science, Stanford University, 1981.
• [SR94] Norman E. Spear and David C. Riccio. Memory - Phenomena and Principles. Allyn & Bacon, Needham Heights, MA, 1994.
• [Woh98] Stefan Wohlfeil. On the Pagination of Complex, Book-Like Documents ; (ISBN 3-8265-3304-6); Shaker Verlag; Germany; 1998.