返回资讯中心
外部精选
软件工程
#开发者实时流

A page looks innocent: the algorithms behind a typeset page

Footnotes look like the easiest thing on a page, but they are among the hardest. A footnote must be on the same page as its reference. But the footnote takes space from the main text, so maybe the line with the referenc…

Hacker News 最新patrickg2026/10/18 · 2026/10/1814 分钟阅读

以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。

Footnotes look like the easiest thing on a page, but they are among the hardest. A footnote must be on the same page as its reference. But the footnote takes space from the main text, so maybe the line with the reference does not fit on the page anymore. Then the reference moves to the next page, and the footnote has to move with it. A long footnote sometimes has to be split across two pages, while the reference stays on the first one.

TeX solves this with insertions. This is a separate mechanism next to the page builder that keeps track of the space the inserted material needs.

In boxes and glue, footnotes are done in htmlbag, the HTML layer. There, the footnote is tied to the line with its number. If the line and the footnote don’t fit on the page together, both move to the next page. Splitting a long footnote across two pages is not possible yet.

Now let’s look at one paragraph. Where should the lines break?

The simple way is to fill a line until the next word does not fit, and then start a new line. Word processors do it like this. The result is that some lines are tight and others have big gaps between the words.

In 1981 Donald Knuth and Michael Plass published a different method. It does not look at one line at a time, but at the whole paragraph. Each possible break point gets a cost: the badness of the line that ends there, plus penalties for hyphens and for hyphens in consecutive lines. Then the algorithm searches for the break points with the lowest total cost, the demerits. So a decision in the first line can depend on the last line.

Knuth and Plass describe this as a graph. Each feasible break is a node, and each possible line between two breaks is an edge. The edge has the demerits of this line as its weight. The best paragraph is the cheapest path from the start to the end. Here is the graph for the first sentence of “The Frog King”, the fairy tale that is also used in their paper. boxes and glue computed the numbers:

Feasible breaks for a 190 pt column in Latin Modern 10 pt. The cheapest path has a loose fifth line (107,969 demerits), because all other paths start with worse lines.

You can try it yourself. Change the width of the column and see how the line breaks move. Sometimes a line far away from the end changes:

The full version of the demo shows more of what the algorithm sees: for each line the adjustment ratio (how much the spaces are stretched or shrunk), the badness and the demerits. You can also change all the parameters that TeX uses for the decision.

Two more things make the result even better:

Now we go to a single word at the end of a line. Can it be hyphenated, and where?

A dictionary with all hyphenations would be huge. TeX uses patterns instead. This idea is from Frank Liang (1983). A pattern is a small part of a word with numbers between the letters. Odd numbers allow a break, even numbers forbid it, and the highest number wins. A few thousand patterns per language are enough for almost every word, even for words that did not exist when the patterns were made.

Here is an example: the word hyphenation with the US English patterns. Nine patterns match some part of the word. Each one puts its numbers into the gaps between the letters, and for each gap the highest number counts:

. h y p h e n a t i o n . 0 0 3 0 0 | | | | | | | hy3ph | | | 0 0 2 0 | | | | | he2n | | | 0 0 0 0 4 | | | | hena4 | | | 0 0 0 5 0 0 | | | hen5at | | | | | 1 0 0 | | | | 1na | | | | | 0 2 0 0 | | | n2at | | | | | | | 1 0 0 0 | 1tio | | | | | | | | 2 0 0 | 2io | | | | | | | | | 0 2 0 o2n max: 0 0 3 0 0 2 5 4 2 0 2 0 final: h y - p h e n - a t i o n

Only two gaps have an odd number, so the word can be broken as hy-phen-ation. The gap between “a” and “t” is interesting: 1tio would allow a break before “tion”, but hena4 has a higher, even number at the same place and so forbids the break. The patterns are careful on purpose. They miss some correct hyphens, but they almost never allow a wrong one.

boxes and glue uses the same pattern files as TeX. The table above is the debug output of hyphenation, the Go port of the TeX algorithm that boxes and glue uses.

Now we are inside a line. The text is a sequence of Unicode characters. But a PDF does not contain characters, it contains glyphs, the shapes from the font. The step from characters to glyphs is called shaping, and it is much more than a simple table lookup:

All these rules are in the font itself, in the OpenType tables GSUB (substitution) and GPOS (positioning). The program that reads these tables and applies them is the shaper. The reference is HarfBuzz. It is used by browsers, LibreOffice and nowadays also by LuaTeX, and so by the speedata Publisher. boxes and glue uses a Go port of HarfBuzz, so everything stays in Go.

Here you can watch a shaper at work. The demo runs HarfBuzz in your browser and draws each glyph from its outline in the font. So you see exactly what the shaper decided. With the slider you go through the shaping step by step: first the Unicode characters, then the glyph IDs from the cmap table, then each lookup that changed something. Look how “f”, “f” and “i” become one glyph, and how “A” and “V” move closer together. You can switch features on and off, or drop your own font on the box, for example an Arabic one.

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →