Breaking Paragraphs into Lines

Breaking Paragraphs into Lines は、Donald E. Knuth と Michael F. Plass の行分割に関する論文で、40年近く前のものです。ここで示されているアルゴリズムは、パラグラフ全体を Box/Glue/Penalty という要素（Paragraph Item）でモデル化して、行分割位置を決定するものです。処理の流れは次のようになります。

アプリケーションが、文書から Paragraph Items を構築する。
分割可能位置に対して、そこで行分割したときの不具合度を示すデメリット値と呼ばれる値を計算する。
もっともデメリット値の合計の少ない位置を選択し、行分割位置とする。

Paragraph Item の要素 Box/Glue/Penalty は、それぞれが幅を持っています。

Box は常に幅が確保される。伸縮性はない。
Glue も幅が確保されるが、そこで分割が起こったとき幅がなくなる。Glue には伸縮性がある。
Penalty はその逆で、通常は幅が確保されないが、そこで分割が起こったとき前の行末にその幅が確保される。Penalty に伸縮性はない。また、行分割の起こり易さを調整するペナルティ値という値を持っており、分割不可では ∞ を、分割必須では −∞ を与えることになっている。ハイフネーションは Penalty を利用して実現されている（通常の Penalty と区別するために Flagged Penalty と呼ばれる）。

次のような文書（論文に出てくるグリム童話）を例に、このアルゴリズムがどのように行分割位置を決定するのかをざっと見てみましょう。

fig-12

これから次のような Paragraph Items が構築されます。
x は要素、t は要素の種別、w は要素の幅、y は伸ばせる幅、z は縮められる幅、p はペナルティ値を示しています。

x₀	empty box for indentation	t₀	= box	w₀	= 20
x₁	box for ‘In’	t₁	= box	w₁	= 17.44
x₂	glue for space U+0020	t₂	= glue	w₂	= 4.54	y₂	= 5	z₂	= 2
x₃	box for ‘old’	t₃	= box	w₃	= 25.68
x₄	penalty for hyphenation	t₄	= flagged-penalty	w₄	= 7.12	p₄	= 100
x₅	box for ‘en’	t₅	= box	w₅	= 19.44
x₆	glue for space U+0020	t₆	= glue	w₆	= 4.54	y₆	= 5	z₆	= 2
x₇	box for ‘times’	t₇	= box	w₇	= 43.7
x₈	glue for space U+0020	t₈	= glue	w₈	= 4.54	y₈	= 5	z₈	= 2
x₉	box for ‘when’	t₉	= box	w₉	= 43.88
`......`
x₂₄	glue for space U+0020	t₂₄	= glue	w₂₄	= 4.54	y₂₄	= 5	z₂₄	= 2
x₂₅	box for ‘lived’	t₂₅	= box	w₂₅	= 38.54
x₂₆	glue for space U+0020	t₂₆	= glue	w₂₆	= 4.54	y₂₆	= 5	z₂₆	= 2
x₂₇	box for ‘a’	t₂₇	= box	w₂₇	= 8.78
x₂₈	glue for space U+0020	t₂₈	= glue	w₂₈	= 4.54	y₂₈	= 5	z₂₈	= 2
x₂₉	box for ‘king’	t₂₉	= box	w₂₉	= 35.5
x₃₀	glue for space U+0020	t₃₀	= glue	w₃₀	= 4.54	y₃₀	= 5	z₃₀	= 2
x₃₁	box for ‘whose’	t₃₁	= box	w₃₁	= 50.64
`......`
x₅₁	box for ‘young’	t₅₁	= box	w₅₁	= 49.76
x₅₂	penalty for hyphenation	t₅₂	= flagged-penalty	w₅₂	= 7.12	p₅₂	= 100
x₅₃	box for ‘est’	t₅₃	= box	w₅₃	= 21.84
x₅₄	glue for space U+0020	t₅₄	= glue	w₅₄	= 4.54	y₅₄	= 5	z₅₄	= 2
x₅₅	box for ‘was’	t₅₅	= box	w₅₅	= 29.82
x₅₆	glue for space U+0020	t₅₆	= glue	w₅₆	= 4.54	y₅₆	= 5	z₅₆	= 2
x₅₇	box for ‘so’	t₅₇	= box	w₅₇	= 17.7
x₅₈	glue for space U+0020	t₅₈	= glue	w₅₈	= 4.54	y₅₈	= 5	z₅₈	= 2
x₅₉	box for ‘beau’	t₅₉	= box	w₅₉	= 38.36
x₆₀	penalty for hyphenation	t₆₀	= flagged-penalty	w₆₀	= 7.12	p₆₀	= 100
x₆₁	box for ‘ti’	t₆₁	= box	w₆₁	= 11.56
x₆₂	penalty for hyphenation	t₆₂	= flagged-penalty	w₆₂	= 7.12	p₆₂	= 100
x₆₃	box for ‘ful’	t₆₃	= box	w₆₃	= 21.82
`......`
x₁₄₃	box for ‘old’	t₁₄₃	= box	w₁₄₃	= 25.68
x₁₄₄	glue for space U+0020	t₁₄₄	= glue	w₁₄₄	= 4.54	y₁₄₄	= 5	z₁₄₄	= 2
x₁₄₅	box for ‘lime-‘	t₁₄₅	= box	w₁₄₅	= 42.34
x₁₄₆	penalty for inter-word	t₁₄₆	= flagged-penalty	w₁₄₆	= 0	p₁₄₆	= 100
x₁₄₇	box for ‘tree’	t₁₄₇	= box	w₁₄₇	= 30.46
x₁₄₈	glue for space U+0020	t₁₄₈	= glue	w₁₄₈	= 4.54	y₁₄₈	= 5	z₁₄₈	= 2
x₁₄₉	box for ‘in’	t₁₄₉	= box	w₁₄₉	= 16.3
`......`
x₂₆₇	box for ‘her’	t₂₆₇	= box	w₂₆₇	= 26.52
x₂₆₈	glue for space U+0020	t₂₆₈	= glue	w₂₆₈	= 4.54	y₂₆₈	= 5	z₂₆₈	= 2
x₂₆₉	box for ‘fa’	t₂₆₉	= box	w₂₆₉	= 14.7
x₂₇₀	penalty for hyphenation	t₂₇₀	= flagged-penalty	w₂₇₀	= 7.12	p₂₇₀	= 100
x₂₇₁	box for ‘vor’	t₂₇₁	= box	w₂₇₁	= 26.48
x₂₇₂	penalty for hyphenation	t₂₇₂	= flagged-penalty	w₂₇₂	= 7.12	p₂₇₂	= 100
x₂₇₃	box for ‘ite’	t₂₇₃	= box	w₂₇₃	= 19.6
x₂₇₄	glue for space U+0020	t₂₇₄	= glue	w₂₇₄	= 4.54	y₂₇₄	= 5	z₂₇₄	= 2
x₂₇₅	box for ‘play’	t₂₇₅	= box	w₂₇₅	= 33.42
x₂₇₆	penalty for hyphenation	t₂₇₆	= flagged-penalty	w₂₇₆	= 7.12	p₂₇₆	= 100
x₂₇₇	box for ‘thing.’	t₂₇₇	= box	w₂₇₇	= 47.02
x₂₇₈	finishing glue	t₂₇₈	= glue	w₂₇₈	= 0	y₂₇₈	= ∞	z₂₇₈	= 0
x₂₇₉	forced break	t₂₇₉	= flagged-penalty	w₂₇₉	= 0	p₂₇₉	= −∞

次の位置が分割可能位置となります。上の例では、x₂、x₄ などです。

x_b が Penalty であり p_b < ∞ である x_b
x_b が Glue であり x_b-1 が Box である x_b

デメリット値は、そこで行分割するとどの程度よろしくないのかを示す値であり、この値が小さいほどよい分割位置と判断されます。あまりに大きなデメリット値のときは分割位置の候補から除外されます。デメリット値の算出方法の詳細はここでは触れませんが、外部から与えるいくつかのパラメタによって、デメリット値を調整できるようになっています。

上の例では、x₂ や x₄ のデメリット値は非常に大きく、候補から除外されます。最初（1行目）の分割位置候補となるのは x₂₆ と x₂₈ で、デメリット値を d とすると、d₂₆ = 975.065、d₂₈ = 23.5004 となっています。
x₂₆ で行分割したとき、次の行（2行目）の分割位置候補は、x₅₂ と x₅₄ で、d₅₂ = 29412.2、d₅₄ = 1288.3 です。
x₂₈ で行分割したときは、x₅₆ と x₅₈ が次の候補となり、d₅₆ = 24.6185、d₅₈ = 6446.52 です。
パラグラフ全体にこれを繰り返すと、次のようなネットワークができ上がります（パスのいくつかは省略されています）。数値は、下に示された語の後で分割したときのデメリット値を示しています。この例では、太い枠の語で分割するのが最良となっています。

fig-12-network

現在の AH Formatter はこのアルゴリズムを利用していません。そこで、このアルゴリズムを利用すると、どのように行分割位置が変化するのかを見てみます。

AH Formatter の結果 — ハイフネーションなし

Knuth-Plass アルゴリズムの結果 — ハイフネーションなし

これは、行あたりの単語数の少ない文書です。つまり、分割可能位置が少ない。行末のアキの幅がより均等に近いのは、Knuth-Plass アルゴリズムの方であるのが見て取れます。

ハイフネーションをしたときは次のようになります。

AH Formatter の結果 — ハイフネーションあり

Knuth-Plass アルゴリズムの結果 — ハイフネーションあり

AH Formatter はハイフネーションが多く発生しています。
Knuth-Plass アルゴリズムは、ハイフネーションの発生を少なく抑えるように作られていますが、パラメタを調整して、もう少しハイフネーションが起こり易くすると、次のようにもなります。

Knuth-Plass アルゴリズムの結果 — ハイフネーション多め

行あたりの単語数が多いときは分割可能位置も多いので、結果に差はなくなってきます。

AH Formatter の結果 — ハイフネーションなし

Knuth-Plass アルゴリズムの結果 — ハイフネーションなし

Knuth-Plass アルゴリズムには、いろいろ制約があることがわかっています。例えば以下のようなものです。

空白によって分かち書きされる英語などの文書を想定しているので、日本語のように分かち書きせず、ほとんどの文字間で分割可能な言語のことは考慮されていない。
非矩形の領域を扱えるが、そのとき行の高さが一定であることが仮定されている。つまり、途中で大きな文字が入っていたりすると処理できない。
ドロップキャップ、letter-spacing、カーニング、リガチャ、綴りの変化するハイフネーション、ルビなどは考慮されていない。
ページ分割は処理しないので、widows/orphans は処理できない。

AH Formatter にこのアルゴリズムを導入することが検討されています。

投票をお願いいたします

瞬簡PDF 変換 2024
PDFをOffice文書へ高精度変換

アウトライナー
PDFを解析してしおり・目次を自動生成

『Antenna House PDF Tool API』（PDF Tool API）でページ単位に分割してみる(2)

『Antenna House PDF Tool API』（PDF Tool API）は、PDFファイルの情報取得やPDFファイルの加工・編集を行うライブラリです。
PDFに関するさまざまな処理機能を搭載しています。
文書情報やページ数などの情報取得、ページの挿入や削除、透かしの挿入、セキュリティ設定などのファイル加工、ページコンテンツのテキストや画像の削除、画像の最適化（ダウンサンプリング）といったページ編集処理が可能です。

今回は『Antenna House PDF Tool API』（PDF Tool API）を使用して、複数ページのPDFを、１ページ単位に分割しながら、リンク注釈を設定します。
設定されたリンク注釈をクリックすると、前後のページのPDFを呼び出します。

Javaサンプルコード

Javaサンプルコード（ExtractPageAndLink）のダウンロード(ZIP)

入力元PDFから１ページ単位で取り出し、出力先PDFを生成します。
この時、入力PDFの文書情報を、出力先PDFに設定しています。
更に、前後ページのPDFファイルへリンク注釈を設定しています。

入力サンプルPDF(総ページ数3)

出力サンプルPDF(1ページ目)

次ページのPDFファイル(output_page_2.pdf)へのリンク注釈です。

出力サンプルPDF(2ページ目)

前ページのPDFファイル(output_page_1.pdf)へのリンク注釈です。

次ページのPDFファイル(output_page_3.pdf)へのリンク注釈です。

出力サンプルPDF(3ページ目)

前ページのPDFファイル(output_page_2.pdf)へのリンク注釈です。

索引用のPDFファイルを作成して、分割したPDFファイルへリンク注釈を設定するなども可能です。

投票をお願いいたします

瞬簡PDF 変換 2024
PDFをOffice文書へ高精度変換

瞬簡PDF 編集 2024
かんたん操作でPDFを自由自在に編集