BLOG 
Carl McTague

How to Optimize a Codex
The best way to print a book is in signatures—that is, as a sequence of nested bifolia to be sewn together through their folds to form a codex. (See Wikipedia for definitions of these terms.)
Traditionally, a book is printed with the same number of bifolia in each signature. This is because a signature is traditionally made by folding a single large sheet of paper in half repeatedly and then trimming.
However, if one prints bifolia individually then there is a priori no reason for the number of bifolia in each signature to be the same. In fact, there is good reason for them not to be.
Indeed, in many forms of bookbinding (e.g. Coptic binding), great prominence is given to pages at the beginnings, middles & ends of signatures. The presentation of a book can therefore be greatly enhanced by varying the number of bifolia in each signature to place landmark pages of the book (e.g. beginnings of chapters) in these prominent positions.
This isn’t entirely straightforward to do, so I’ve written a program to do it—the Signature Optimizer.
I’ve been using it myself for some time and am very pleased with the results.
I even use it when printing short papers I don’t intend to sew. (I usually trim margins first using Briss so that the text in the resulting A5 booklet isn’t much smaller than the intended fullsized A4 sheets, saving lots of paper.)
I wrote the Signature Optimizer in JavaScript so it can easily be used by anyone with a web browser. The source code is all inline so you can simply save the page source to your disk to use it offline. (In fact, it’s easy to install as a standalone app on an iPhone or iPad: just navigate to the Signature Optimizer in Safari, tap the bookmark button and then tap “Add to Home Screen”.)
The Signature Optimizer also generates a LaTeX script which transforms a given PDF file into a PDF file which, when printed, produces bifolia which are ready to fold and sew. To do this, simply save the generated LaTeX script as a file, replace yourfile.pdf with the name of the PDF file you want to print, and run pdflatex. You may want to experiment with the scaling factor and the value of delta (the distance between pages within a bifolium).
How did the signature optimizer come about? How does it work?
In October 2011 I found myself couch surfing in London. I was taking the tube a lot so was thinking a lot about shortest paths through its famous topological map (compare Harry Beck’s radical original 1933 topological tube map, and his early sketch, on which the current map is based and which Beck completed as an uncommissioned spare time project, as well as GH Davis’s 1927 threedimensional drawings of the London Underground and the London Sound Survey’s Soundmap of London Canals and Minor Rivers). One day while gazing mesmerized at the stunning modeltrainsetlike view of tangled roads & railways from some friends’ 17th story apartment, it struck me that arranging a book into signatures is quite like finding a short path through the underground. The stations are all the pages divisible by 4 and the underground links are all imaginable signatures linking these pages. The nicer a signature—the more landmark pages it exhibits and the closer the number of its bifolia to the ideal number for a given paper weight—the shorter the link. Finding a good sequence of signatures, then, is the same as finding a short path from the first page to the last through this network. I read about Dijkstra’s algorithm (see also Dijkstra’s original 1959 paper) for finding a “shortest path tree” within a directed metric graph, but I eventually realized that the situation is far simpler since the graph in question is acyclic and the page numbers in fact give a topological sorting of the graph’s nodes. This topological sorting makes it easy to inductively construct a shortest path tree. The main task, then, is to define the length of a signature in this graph. I took this to be the sum:
length(signature) = λ · ( #{ landmark pages in signature } – #{ landmark pages given prominence } ) + (1λ) · p ( #{ bifolia in signature } )
where 0 ≤ λ ≤ 1 is a constant and p is a polynomial with various properties. Specifically, I wanted p(4) < p(3), p(6) < 2·p(3) and p(3) + p(4) < p(7) < p(2). To find such a polynomial, I fit a degree2 polynomial to the points (2,4), (3,2), (4,1), (5,1), (6,2), (7,7/2). This gave:
p(x) = 10.4643 – 4.16964 x + 0.455357 x^{2}
Experimenting then showed that taking λ=½ strikes a good balance between fitting landmark pages into prominent positions and using reasonable signature lengths. (Taking λ=1 gives signature arrangements with most landmark pages in prominent positions but with impractical signature lengths. Taking λ=0 gives signature arrangements indifferent to the placement of landmark pages.)
Afterword
I later realized I had essentially rediscovered the Knuth–Plass algorithm for breaking lines in TeX, which was itself first developed for typesetting music:
“The idea of applying dynamic programming to line breaking occurred to DE Knuth in 1976, when Professor Leland Smith of Stanford’s music department raised a related question that arises in connection with the layout of music on a page. During a subsequent discussion with students in a problemsolving seminar, someone pointed out that essentially the same idea would apply to the texts of paragraphs as well as to music.” —Knuth & Plass, Breaking Paragraphs into Lines, 1981.
All this suggests implementing the optimizer as a TeX package which, when loaded in the preamble of a TeX document, would result in a PDF of optimized bifolia, the landmark pages having been determined automatically by TeX. Even better, it could be integrated into TeX’s layout engine so that, for example, a document otherwise typeset on just over 16 pages would be squeezed onto 4 bifolia.