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

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

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

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

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

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

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

1. x_b が Penalty であり p_b < ∞ である x_b
2. 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 です。
パラグラフ全体にこれを繰り返すと、次のようなネットワークができ上がります（パスのいくつかは省略されています）。数値は、下に示された語の後で分割したときのデメリット値を示しています。この例では、太い枠の語で分割するのが最良となっています。

現在の 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 にこのアルゴリズムを導入することが検討されています。

Tweet