ページは無害に見える：組版されたページの背後にあるアルゴリズム

ページは無害に見える：組版されたページの背後にあるアルゴリズム

よく組版された書籍やカタログのページを見ると、通常は特別なことは何も気づきません。テキスト、表、画像、脚注などがあります。しかし、そのようなページ上の各行は、多くの小さな決定の結果です。それらの背後にあるアルゴリズムは数十年前から発明されており、人々は今日でもそれに取り組んでいます。

この記事では、ページ上で何が起こるかを示したいと思います。ページ全体から始め、ステップバイステップで下に降りていき、PDFファイルのバイトに至るまで説明します。各レベルで、speedata Publisherがどのように行っているか（バックグラウンドでLuaTeXを使用）、そしてboxes and glueがどのように行っているかを示します。boxes and glueは、私が将来の基盤として書いているGoライブラリです。どちらもオープンソースで、GitHubで見つけることができます：speedata/publisherとboxesandglue。

［画像: 見出し、2つの段落、脚注のあるサンプルページ。6つの番号付きマーカーが脚注、最初の段落、ハイフンでつながれた単語、fi合字、文字g、最初の単語を指しており、各レベルを説明する凡例が付いています。］
A page typeset with boxes and glue. The numbers are the sections of this post.

2つのエンジン、1組の問題

まず、2つのエンジンについて簡単に説明します。

speedata Publisherは、ほとんどの組版作業をLuaTeXに任せています。Publisherはどこに要素を配置するかを決定し、LuaTeXは段落をどのように行に分割するかを決定し、PDFを書き出します。PublisherはLuaコールバックを使用してLuaTeXにフックします。これはうまく機能しており、そのためPublisherは最初から非常に優れた組版を実現しています。しかし、LuaTeXは巨大なプログラムです。一部が期待通りに機能しない場合、回避策を見つける必要があります。

boxes and glueは、個別のGoモジュールで同じ作業を行います。この記事の各レベルは独自のパッケージであり、それぞれを単独で使用、テスト、または置き換えることができます。

ほとんどのアルゴリズムは両方のシステムで同じです。違いはアーキテクチャであり、これは見た目以上に重要です。

最初で最大の疑問：どの要素がどのページに配置されるか？

TeXにはページビルダーがあります。これは、ページがいっぱいになるまで行を収集し、出力ルーチンを呼び出します。これは、マテリアルを取得して何をするかを決定するコードの一部です。非常に強力ですが、使用も非常に困難です。speedata Publisherはこれを使用したことがありません。独自のページモデルを持ち、グリッド、領域、明示的な位置を持っています。

このレベルでのいくつかの問題：

• 寡婦（widows）と孤児（orphans）：段落の1行だけがページの上部または下部にあると、見た目が悪くなります。これを避けるために、行は次のページに移動する必要があり、現在のページにはギャップができます。
• ページをまたぐ表：表が収まらない場合、2つの行に分割されます。ヘッダーは次のページで繰り返され、おそらく「次ページに続く」のようなフッターが表示されます。分割によって単一行だけが残されるべきではありません。
• フロート：画像は参照元のテキストの近くにあるべきですが、必ずしもその正確な場所にある必要はありません。

脚注

脚注はページ上で最も簡単なもののように見えますが、最も難しいものの1つです。脚注はその参照元と同じページになければなりません。しかし、脚注は本文のスペースを占めるため、参照元の行がページに収まらなくなる可能性があります。その場合、参照元は次のページに移動し、脚注もそれに伴って移動する必要があります。長い脚注は、参照元が最初のページに残ったまま、2つのページに分割されることがあります。

TeXはこれを挿入物（insertions）で解決します。これはページビルダーとは別のメカニズムで、挿入されたマテリアルが必要とするスペースを追跡します。

boxes and glueでは、脚注はhtmlbag、HTMLレイヤーで行われます。そこでは、脚注はその番号の行に結び付けられます。行と脚注が一緒にページに収まらない場合、両方とも次のページに移動します。長い脚注を2つのページに分割することは、まだできません。

2. 段落

次に1つの段落を見てみましょう。行はどこで分割されるべきでしょうか？

簡単な方法は、次の単語が収まるまで行を埋め、新しい行を開始することです。ワードプロセッサはこれを行います。その結果、一部の行はきつく、他の行は単語間に大きなギャップができます。

1981年にDonald KnuthとMichael Plassは異なる方法を発表しました。これは一度に1行を見るのではなく、段落全体を見ます。各可能な区切り点にはコストが割り当てられます。それは、そこで終わる行の悪さ（badness）に、ハイフンと連続する行のハイフンに対するペナルティを加えたものです。その後、アルゴリズムは最も低い総コスト、つまりデメリッツ（demerits）を持つ区切り点を検索します。したがって、最初の行の決定は最後の行に依存する可能性があります。

KnuthとPlassはこれをグラフとして説明しています。各可能な区切り点はノードであり、2つの区切り点間の各可能な行はエッジです。エッジはその行のデメリッツを重みとして持ちます。最適な段落は、開始から終了までの最も安いパスです。これは、「カエルの王様」の最初の文のグラフです。この物語は彼らの論文でも使用されています。boxes and glueが数値を計算しました：

［画像: 実現可能な行区切りのグラフ。開始から、パスは単語 helped, one, daughters, all, beautiful を経て、終了地点 face に至ります。最も安いパスがハイライトされており、その隣には設定された段落の6行が表示されています。］
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.

自分で試すことができます。列の幅を変更して、行区切りがどのように移動するかを確認してください。場合によっては、遠くの行が変更されることがあります。

デモのフルバージョンは、アルゴリズムが何を見ているかをより多く示しています。各行について、調整比率（スペースがどれだけ伸縮したか）、悪さ、デメリッツが表示されます。TeXが決定に使用するすべてのパラメータを変更することもできます。

結果をさらに良くする2つのことがあります：

• フォント拡張：グリフはわずかに幅を広げたり狭めたりできるため、行分割器はより自由になります。これについてはMicrotypography and font expansionで書きました。
• ぶら下がり句読点：行末のハイフンや引用符は、余白に少し突き出ているため、端が目にまっすぐに見えます。

3. 単語

次に、行末の単語に注目します。ハイフンで分割できますか、そしてどこで？

すべてのハイフネーションを含む辞書は巨大になります。TeXは代わりにパターンを使用します。このアイデアはFrank Liang（1983年）によるものです。パターンは単語の一部で、文字の間に数字があります。奇数は分割を許可し、偶数は禁止し、最も高い数字が優先されます。言語ごとに数千のパターンがあれば、ほとんどすべての単語に対応できます。存在しない単語にも対応できます。

例を見てみましょう：hyphenationという単語をUS英語のパターンで分割します。9つのパターンが単語の一部に一致します。それぞれが数字を文字の間のギャップに入力し、各ギャップで最も高い数字がカウントされます：

   .   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

奇数は2つのギャップにしかないので、単語はhy-phen-ationと分割できます。“a”と“t”の間のギャップが興味深いです：1tioは“tion”の前に分割を許可しますが、hena4は同じ場所でより高い偶数を持っており、分割を禁止します。パターンは意図的に慎重に作られています。いくつかの正しいハイフンを見逃しますが、間違ったハイフンを許可することはほとんどありません。

boxes and glueはTeXと同じパターンファイルを使用しています。上記の表は、boxes and glueが使用するTeXアルゴリズムのGoポートであるhyphenationのデバッグ出力です。

4. テキストラン

今、行の中にいます。テキストはUnicode文字のシーケンスです。しかし、PDFは文字を含んでおらず、フォントの形状であるグリフを含んでいます。文字からグリフへのステップはシェーピング（shaping）と呼ばれ、単純なテーブルルックアップ以上のものです：

• 合字（Ligatures）： "f" の後に "i" が続くと、1つのグリフ "fi" になることがあります。
• カーニング（Kerning）：ペア "AV" は "AH" よりも近くに配置されます。
• 文脈依存の形状：アラビア語では、文字は単語の先頭、中間、末尾で異なる形状を持ちます。
• 並べ替え：デーヴァナーガリー文字では、母音記号はテキストでの順序とは異なり、子音の前に書かれることがあります。
• 方向：ヘブライ語とアラビア語は右から左に流れますが、その中の数字は左から右に流れます（bidiアルゴリズム）。

これらのルールはすべてフォント自体、OpenTypeテーブルのGSUB（置換）とGPOS（配置）に含まれています。これらのテーブルを読み取り、適用するプログラムがシェイパーです。参照はHarfBuzzです。これはブラウザ、LibreOffice、そして最近ではLuaTeX、つまりspeedata Publisherによって使用されています。boxes and glueはHarfBuzzのGoポートを使用しているため、すべてGo内で完結します。

ここでシェイパーの動作を見ることができます。デモはブラウザでHarfBuzzを実行し、フォントのアウトラインから各グリフを描画します。これにより、シェイパーが決定したことが正確にわかります。スライダーを動かすと、シェーピングステップを段階的に進めることができます。まずUnicode文字、次にcmapテーブルからのグリフID、次に何かを変更した各ルックアップです。“f”、“f”、“i”が1つのグリフになり、“A”と“V”がどのように近づくかを見てください。フィーチャーをオン/オフしたり、たとえばアラビア語のフォントをボックスにドロップしたりできます。

Text

Loading HarfBuzz…

More features of this font (0)

Font:

そして、アラビア語の場合も同様です。cmapステップでは、すべての文字はまだ孤立した形状を持っています。次に、init、medi、finaフィーチャーが各文字に単語内での位置に応じた形状を与え、文字が接続されます：

Text

Loading HarfBuzz…

More features of this font (0)

Font:

5. グリフ

さらに一歩進んで、フォントファイルです。OpenTypeフォントは小さなデータベースのようなものです。cmapテーブルは文字をグリフIDにマッピングし、hmtxは幅を持ち、glyfまたはCFFはアウトラインを持ち、GSUB/GPOSは前のセクションのルールを持ちます。可変フォントは、ウェイトや幅のような軸を追加し、カラーフォントは絵文字用の独自のテーブルを持ちます。

ヒンティング（hinting）はどうでしょうか？画面上では、各グリフはピクセルで描画されます。emあたりのピクセル数が多い場合、形状は良好です。ピクセル数が少ない場合、形状が崩れます。1つのステムが1ピクセルになり、次のステムが2ピクセルになり、ボウルが閉じます。

［画像: 2つのピクセルグリッドの上に文字aが表示されています。細かいグリッドでは、塗りつぶされたピクセルがアウトラインに従っています。emあたり12ピクセルの粗いグリッドでは、塗りつぶされたピクセルは認識可能なaの形をほとんど形成していません。］
The a of Crimson Pro. A pixel is black when its center is inside the outline. At 12 pixels per em and without hints, the letter breaks apart.

自分で試してみてください。スライダーを動かして、文字がいつ崩れるかを確認してください。他の文字を入力することもできます。たとえば、emあたり13ピクセルでは、“m”の中央のステムが完全に失われます。またはアンチエイリアスをオンにしてください。すると、ピクセルはアウトラインがカバーする部分に対してグレースケール値を取得します。これはピクセル問題へのもう1つの答えであり、macOSがヒントをほとんど無視する理由です。

Text Pixels per em

Anti-aliasing (gray levels) Show the outline

Font:

ヒントはフォント内の命令です。これらは、小サイズでアウトラインをピクセルグリッドにどのように移動させるかをラスタライザーに指示し、すべてのステムが同じ幅を持ち、xハイトが完全なピクセルになるようにします。組版エンジンはこれを使用しません。デザイン単位ですべてを計算し、これらはデバイスに依存しません。画面上でPDFを見ると、PDFビューアはヒントを使用できます。紙の上では、これらはまったく重要ではありません。したがって、これはこの記事のレベルの中で、組版者が気にする必要のない唯一のレベルです。

6. PDF

これで最下層に到達しました。テキストの1行はPDF内でどのように見えるでしょうか？

これは、冒頭のサンプルページの最初の行の開始部分です。PDFから取得したもので、省略記号「…」で示されている部分以外は展開されています：

BT
/F2 10 Tf
1 0 0 1 34.02 350.2 Tm
[<0051015f0271> -154 <016a015401110118015f0271> -154
 <01a4013d015d011801980271> -154 ... <01a4013801180190> 21 <01180271> ...] TJ
ET

BTとETはテキストオブジェクトの開始と終了を示します。/F2 10 TfはフォントF2（Crimson Pro）を10ポイントで選択し、Tmは行の開始位置をページ左から34.02ポイント、下から350.2ポイントに設定します。次にTJが行を描画します。山括弧内のテキストは「In olden times」ではなく、それぞれ4桁の16進数を持つグリフIDです。「I」は0051、「n」は015f、「スペース」は0271です。文字列間の数値は、フォントサイズの1000分の1単位で次のグリフを移動させます。-154は右に1.54ポイント移動させます。これは行揃えによる追加スペースです。“there”の中の21は、最後の“e”を0.21ポイント左に移動させ、“r”に近づけます。これはフォントからのカーニングです。

フォントは埋め込まれていますが、使用されているグリフのみ（サブセット）です。テキストは文字ではなく、グリフIDとして書き込まれます。このため、一部のPDFからテキストをコピーするとゴミになることがあります。ToUnicodeテーブルがないと、グリフから文字への逆マッピング方法がありません。合字はさらに難しくします。単一のグリフ「fi」は、2つの文字にマッピングし直す必要があります。

アクセシブルPDF（PDF/UA）では、すべてのテキストピースに、ドキュメント内での役割（見出し、段落、表セル、脚注など）を示すタグも必要です。結果を確認する方法については、Checking PDF/UA without firing up a Windows VMで説明されています。

このレベルをさらに詳しく見たい場合は、「What is PDF?」シリーズでPDFファイルを手書きで作成しています。パート2はテキストとTJ演算子、カーニングについて、パート6はタグ付きPDFについてです。

再びズームアウト

それでは、最初に戻ってページを見てみましょう。ページからバイトまでの6つのレベルがあり、それぞれに独自のアルゴリズムがあります。それらのいくつかはPDFフォーマットよりも古いものです。読者はこれらのどれも認識せず、それが正しいあり方です。

しかし、レベルは実際には分離されていません。シェイパーからの合字は、単語がハイフンで分割できる場所を変更します。行の途中の色の変更は、PDF内のテキストからスペースを削除する可能性があります。私の経験では、最も興味深いバグはレベル間の境界にあります。これが、boxes and glueが各レベルを独自のパッケージに分けている理由の1つです。問題が発生した場合、一度に1つのレベルを調べることができます。

これらの各レベルは、独自の投稿を持つ可能性があります。どれを最初に読みたいですか？ Mastodon (speedata@typo.social)で連絡してください。