PDFページ順序に関する付随する解説では、表示順序はオブジェクト番号からではなく、/Pagesツリーの/Kids配列の深さ優先の左から右へのウォークから導出されるという基本ルールについて説明しています。この記事では、このツリーを別の角度から、つまりその形状について見ていきます。完全に合法的な単一のフラットな配列でも問題ないのに、なぜ成熟したPDFライターは中間ノードの階層を出力するのでしょうか？ツールがツリーをフラット化したり再構築したりすると、実際に何が変わるのでしょうか？そして、構造全体を高速化する/Countの簿記が真実を語らなくなると何が起こるのでしょうか
ファンアウトはパフォーマンス上の決定事項です
ライターにネストを強制するものはありません。1つのルート/Pagesノードと1つの/Kids配列に10,000個のリーフ参照を持つ10,000ページのドキュメントは、仕様に準拠しています。それでも、PDFリファレンスは大規模なドキュメントにバランスの取れたツリーを推奨しており、主流のジェネレーターはそのアドバイスに従って、通常は中間ノードごとに数十個の子供を持つ適度なファンアウトで出力します
その理由は、ビューアーが何かを表示する前に読み取る必要があるためです。その10,000ページのファイルの8,214ページに直接ジャンプする場合を考えてみてください。フラットツリーの場合、ビューアーはまずルートノードを解析する必要があります。そのルートノードは1つの巨大な配列です。間接参照あたり約8バイトの場合、エントリ8,213を解決する前に、端から端までトークン化する必要がある80 KBのオブジェクトになります。ファンアウト32のバランスの取れたツリーの場合、同じジャンプでルートを読み取り、実行中の/Countの合計を比較して正しい子を選択し、下降します。合計で3つまたは4つの小さな辞書があり、それぞれ数百バイトです。これはツリーが提供するように設計されたO(log n)のランダムアクセスであり、これが中間ノードに/Countが存在する理由のすべてです。これにより、リーダーは内部の単一のオブジェクトを開くことなく、サブツリー全体をスキップできます
ツリーの形状によっても編集のコストが決まります。1ページを挿入する増分更新では、/Kidsまたは/Countが変更されたすべてのノード、つまり新しいリーフの親からルートまでのパスを書き換える必要があります。バランスの取れたツリーでは、そのパスはファイルに追加される一握りの小さな辞書です。フラットなツリーでは、「パス」は単一の巨大なルート配列であり、すべてのリビジョンで完全に複製されます。30回のレビューと注釈のサイクルを経るコントラクトは、結果的にバイトストリームに同じ80 KBの配列の30個の置き換えられたコピーを保持することになる可能性があります
内部ノードは継承された属性を持ちます
中間ノードは単なるルーティングではありません。継承可能な4つのページ属性（/Resources、/MediaBox、/CropBox、および/Rotate）は、任意の/Pagesノードにホイストでき、そこで子孫がそれらをオーバーライドしない限り、その下のすべてのリーフに適用されます。横向きの付録を含むレポートを生成するライターは、ツリー自体でそのレイアウトを表現できます：
5 0 obj % document root
<< /Type /Pages /Count 6 /Kids [6 0 R 7 0 R] >>
endobj
6 0 obj % report body: portrait A4, body font
<< /Type /Pages /Parent 5 0 R /Count 3
/Kids [30 0 R 31 0 R 32 0 R]
/MediaBox [0 0 595 842]
/Resources << /Font << /F1 8 0 R >> >> >>
endobj
7 0 obj % appendix: landscape A4, rotated, its own font
<< /Type /Pages /Parent 5 0 R /Count 3
/Kids [40 0 R 41 0 R 42 0 R]
/MediaBox [0 0 842 595] /Rotate 90
/Resources << /Font << /F2 9 0 R >> >> >>
endobj
40 0 obj % appendix page: inherits size, rotation, fonts
<< /Type /Page /Parent 7 0 R /Contents 43 0 R >>
endobjオブジェクト40〜42はほぼ空です。それらのページサイズ、回転、およびフォントリソースはすべてノード7からの継承によって到着するため、ファイルはコンパクトで自己保守性を保ちます。付録ノードの下に4ページ目を追加すると、自動的に横向きで出力されます
同じメカニズムにより、典型的なページ移動の危険が生じます。ツールが2つの/Kids配列を編集し、/Parentをノード6に変更することで、オブジェクト40をレポート本文に移動するとします。この移動は構造的に有効ですが、オブジェクト40は縦向きの/MediaBox、回転なし、およびフォント/F1を継承するようになります。一方、そのコンテンツストリームは引き続き/F2を選択しますが、これはもはや解決されません。ページは縮小し、回転が解除され、1回の編集でテキストが失われます。したがって、堅牢な並べ替えコードは、ページを親に再設定する前に、継承可能な4つの属性すべての解決された値をページ辞書に具体化します。エディタでページをドラッグして、そのサイズや向きが変わるのを見たことがあるなら、これがあなたが目撃したメカニズムです
フラット化：合法、一般的、場合によっては高コスト
多くのツールは逆の方向に進みます。最小限のライターは、それが単純であるため単一レベルのツリーを出力します。また、多くのマージおよび分割ユーティリティは、読み取ったツリーを1つのフラットな/Kids配列に再構築します。なぜなら、バランスの取れた構造を生成することは余分な作業であり、フラットな出力は常に準拠しているからです。正しい再構築では、継承も同時に解決する必要があります。リーフが継承していたすべての属性は、リーフにコピーするか、ドキュメント全体で均一である場合は新しいルートにホイストする必要があります。そうしないと、ページの移動の場合とまったく同じように出力のジオメトリが変更されます
一般的なドキュメントの場合、フラット化しても害はありません。すでに説明した2つの点で規模が大きくなると問題が生じます。ルート配列が1つの大きなオブジェクトになり、すべてのオープンとすべてのページジャンプで完全に解析する必要があり、すべての構造編集で配列全体を書き換えることになります。フラット化しても破壊されないのは、間接参照による共有です。10,000ページすべてが同じ/Resources辞書オブジェクトを指すフラットツリーは、依然として重複が排除されています。失われるのは、エントリをページから除外し、先祖にそれを提供させるオプションだけです
/Countが嘘をつくとき
/Countは純粋な簿記です。これはノードのサブツリー内のリーフページの数と等しくなければならず、ファイル形式にはそれを強制するものはありません。野生で見られる嘘のカウントの大部分は、2つの破損パターンで説明できます
1つ目は、増分更新によって残された古いカウントです。エディタはページを挿入し、新しい/Kidsと更新された/Countで直近の親を書き換え、両方をファイルに追加しますが、先祖にはまったく触れません：
% Original revision
12 0 obj
<< /Type /Pages /Count 9 /Kids [13 0 R 14 0 R 15 0 R] >>
endobj
14 0 obj
<< /Type /Pages /Parent 12 0 R /Count 3
/Kids [50 0 R 51 0 R 52 0 R] >>
endobj
% Appended revision: one page inserted into the middle branch.
% Object 14 is superseded; object 12 is never rewritten
14 0 obj
<< /Type /Pages /Parent 12 0 R /Count 4
/Kids [50 0 R 51 0 R 90 0 R 52 0 R] >>
endobjツリーには現在10個のリーフが含まれていますが、ルートは依然として9つと表示しています。ルートを信頼するビューアーは、ページカウンターで9ページを報告します。内部カウントを使用してページジャンプをバイナリ検索するビューアーは、挿入ポイント以降のすべてのページについて誤ったインデックスを計算します。完全なトラバーサルでは10個見つかります。3つの異なる答え、1つのファイルです
2番目のパターンは、決して正しくないカウントです。負数、入力済みノードでゼロ、またはとてつもなく巨大な数値です。これらは、ファジング、送信中の損傷、および場合によってはエディタの算術バグに起因します。これらは、割り当てのために/Countを信頼するコードにとって特に危険です。-3の/Countから配列のサイズを設定すると、せいぜい範囲エラーが発生し、20億の/Countから配列のサイズを設定すると、サービス拒否の割り当てになります。この値は、ファイル内の他のすべての数値と同様に、信頼できない入力です
パーサーは、これらすべてをめぐって2つの陣営に分かれます。プリフライトツール、PDF/A検証ツール、アーカイブパイプラインなどの厳密なコンシューマーは、/Countをトラバーサルの結果と比較し、ファイルを拒否するかフラグを立てます。インタラクティブなビューアーはほぼ普遍的に寛容です。トラバースし、実際のカウントを導き出し、保存されているカウントを静かに無視します。古いカウントのファイルが、自動化されたワークフロー内でより厳密なパーサーに出会うまで、何年もの間文句を言われずに循環できるのはまさにこのためです。ライブラリコードの防御的な妥協点は、/Countをヒント（事前割り当て、および検証後のサブツリーのスキップに役立つ）として扱いながら、トラバーサルを引き続き真実のソースとすることです
トラバーサルアルゴリズム自体、継承検索ルール、カタログからリーフへのウォークについては、ページ順序の解説から始めてください。実際の顧客のドキュメントが本番コードに到達したときにこれらの障害モードがどのようになるかについては、症状から根本原因までのシャッフルされたページのインシデントを追跡するページ順序のデバッグのケーススタディをお読みください
HotPDF コンポーネントは、これらすべてを内部的に処理します。任意の深さのネストされたツリーをトラバースし、ページがコピーまたは移動されたときに継承された属性を解決し、/Countを信頼する代わりに実際のリーフカウントと照合して検証するため、API内のページインデックスは常に論理ページを意味します