組版では段落内での改行位置を適切に決めていく必要がある。
一番単純なのは、単語が一行に入り切らなくなったら直前に改行を入れるというもの。 ただ、それだと場当たり的な組み方になってしまうので、段落全体で見たときに酷い見た目になってしまう可能性がある。 そこで、TeXなどの組版システムではもっと賢いアルゴリズムが使われていて、見た目の悪さが最小になるような工夫がされている。 これは数理最適化の応用の一例とも言える。
ここでは欧文組版でTeXが使っているアルゴリズムを整理してみたい。
これは数理最適化 Advent Calendar 2024およびTeX ＆ LaTeX Advent Calendar 2024の16日目の記事です。
空白の伸び縮み
欧文組版では行頭と行末がキレイに揃うように単語の間の空白を伸び縮みさせて調整する。 この伸び縮みする空白のことをTeXでは「グルー（glue, 「糊」という意味）」と呼んでいる。 ちなみに、単語を繋ぎ合わせてるから「糊」なんだと思うけど、『TeXブック』では実際には「バネ」に近いかもとも書かれている。
グルーには「自然な幅」「伸長度」「縮小度」という3つの長さを設定できる。 「自然な幅」というのは伸び縮みしなかったときのサイズで、「伸長度」は伸ばせる長さの最大値（※1）、「縮小度」は縮められる長さの最大値を意味している。
たとえば、自然な幅が10、伸長度が3、縮小度が2のグルーは、伸び縮みしなければ10、縮めば最小で8（=10-2）、伸びれば最大（※1）で13（=10+3）というサイズの空白になる。
そして、グルーの伸びが必要な場合には伸長度の比率、縮みが必要な場合には縮小度の比率に応じて、伸び縮みが計算される。
たとえば、次の一連の単語と空白を一行に並べるとする：
- 幅が20の単語
- 自然な幅が10、伸長度が5、縮小度が4のグルー
- 幅が15の単語
- 自然な幅が10、伸長度が10、縮小度が2のグルー
- 幅が10の単語
- 自然な幅が15、伸長度が0、縮小度が0のグルー
- 幅が20の単語
グルーが伸び縮みしない場合、これらの幅の合計は100（＝20+10+15+10+10+15+20）。 なので、もし一行の幅がちょうど100なら、伸び縮みしないでOKとなる。
ここで、一行の幅が106だったとする。 すると、6伸ばしてやらないと行末が揃わなくなるので、グルーを伸ばすことになる。 グルーは全体で15（＝5+10+0）伸ばすことができるので、伸長度の比率に応じて、1つ目のグルーは6x(5/15)=2、2つ目のグルーは6x(10/15)=4、3つ目のグルーは6x(0/15)=0伸ばすことになる。 そして、結果として、幅が20の単語、幅が12（=10+2）の空白、幅が15の単語、幅が14（=10+4）の空白、幅が10の単語、幅が15（=15+0）の空白、幅が20の単語が一行に並び、一行の幅は106となる。
逆に、一行の幅が97だったとする。 すると、3縮めてやらないと行末が飛び出てしまうので、グルーを縮めることになる。 グルーは全体で6（＝4+2+0）縮めることができるので、縮小度の比率に応じて、1つ目のグルーは3x(4/6)=2、2つ目のグルーは3x(2/6)=1、3つ目のグルーは3x(0/6)=0縮めることになる。 そして、結果として、幅が20の単語、幅が8（=10-2）の空白、幅が15の単語、幅が9（=10-1）の空白、幅が10の単語、幅が15（=15+0）の空白、幅が20の単語が一行に並び、一行の幅は97となる。
ちなみに、伸長度が無限のグルーも存在する。 この場合は伸びが必要な分をすべて伸長度無限のグルーが引き受けることになる。 これは右寄せや左寄せ、センタリングなどに使われる。
※1：実際には伸長度を超えて伸びることができるので「最大値」ではないんだけど、表現が難しいのでとりあえず「最大値」と呼ぶことにする
行の評価値
改行位置に応じて、こうやってグルーを使えば行末を揃えられるけど、空白が詰まりすぎてたり、逆に開きすぎてたりすると、見栄えが悪い。 そこで、何かしらの評価値を用意して、その評価値が最小（もしくは最大）になるように、改行位置を決められるといい。
TeXでは段落内の各行について「行の見た目の悪さ（badness）」と「改行位置の悪さ（penalty）」、および「行のペナルティ（line penalty）」を使って「行のデメリット（demerit）」を計算し、その合計（※2）を「段落のデメリット」としている。 そして、「段落のデメリット」が最小になるように改行位置を決める。
まず、行の見た目の悪さ $b$ は、次の式で計算される（※3）：
$$ b = \min\left\{10000, 100\times \left(\frac{\text{実際の伸ばす（もしくは縮める）長さ}}{\text{伸長度（もしくは縮小度）の合計}}\right)^{3}\right\} $$
たとえばさっきの例を使うと、一行の幅が106で伸ばさないといけない場合、伸長度の合計が15、実際に伸ばす長さが6なので、$100\times \left(\frac{6}{15}\right)^{3} \fallingdotseq 6.4$、逆に一行の幅が97で縮めないといけない場合、縮小度の合計が6、実際に縮める長さが3なので、$100\times\left(\frac{3}{6}\right)^{3} \fallingdotseq 12.5$となる（※3）。
ちなみに、与えられた伸長度（もしくは縮小度）の半分のサイズまで伸びる（もしくは縮む）とbadnessの値は12.5となる。 なので、12以下の行は標準的な行、13以上の行は伸びすぎ（もしくは縮みすぎ）な行という感じに捉えられる。 また、用意された伸長度（もしくは縮小度）を使い切るまで伸びる（もしくは縮む）とbadnessの値は100となる。 さらに、伸びる方向については伸長度を超えて伸びることができ、その場合、badnessは100より急激に大きくなって、最大で10,000まで大きくなるようになっている。
次に、段落の中には改行したら困る部分や、逆に改行してほしい位置があったりする。 そういうのを表現するために用意されているのが「改行位置の悪さ（penalty）」。 これは、改行しては困る部分に正の値（最大で10,000で、それ以上なら改行禁止）、改行してほしい位置に負の値（最小で-10,000で、それ以下なら強制改行）を指定する。 そして、その位置で改行することになった場合には、指定された値をpenaltyとする（それ以外の位置で改行する場合、penaltyの値は0）。
あと、段落としてできるだけ行数を少なくしないとか多くても構わないとかがある。 それを調整するために「行のペナルティ（line penalty）」という設定値も用意されている。 これは「行のデメリット」に常に追加される値で、大きいとできるだけ行数を少なくしようとするし、逆に小さくすれば行数が多くても構わないとなる。 plain TeXでのデフォルト値は10とのこと。
以上の要素を使って、行の見た目の悪さを $b$、改行位置の悪さを $p$、行のペナルティを $l$ とすると、行のデメリット $d$ は次のように計算される：
$$ d = \begin{cases} (l + b)^{2} + p^{2} & (0 \le p < 10000) \\ (l + b)^{2} - p^{2} & (-10000 < p < 0) \\ (l + b)^{2} & (p \le -10000) \\ \end{cases} $$
（ちなみにpenaltyとして10,000以上が指定された位置では改行されないので、$d$ の計算で $p$ の値が10,000以上になることはないことに注意）
あとは各行のデメリットを足し合わせれば段落のデメリットとなるので、その値が最小になるように改行位置を決めていけばいい。
※2：この記事ではハイフネーションについて扱ってないけど、実際にはハイフネーションに関連したデメリットなども追加した値
※3：実際にはこれに近い値を計算する式が使われていて、値は整数になるとのこと
動的計画法
さて、これで最小化すべき評価値（つまり目的関数）は用意できたわけだけど、問題はどうやってそれを最小化する改行位置を見つければいいのか。
ここで一つ重要な観察がある。
仮に段落内のある空白で改行して、$n$ 行の部分的な段落を作ったとする。 このとき、その部分的な段落の評価値は、その空白よりも前で改行した $n-1$ 行の部分的な段落の評価値に、その $n$ 行目の評価値を加えたものになる。
数式で表現してみると、$j$ 番目の空白で改行して $n$ 行の部分的な段落を作ったときの段落のデメリットを $D(j, n)$、$i$ 番目の空白から $j$ 番目の空白までを1行としたときの行のデメリットを $L(i, j)$ と表すことにすれば、
$$ D(j, n) = D(i, n-1) + L(i, j),\quad(\text{ただし } i < j) $$
そして、この $D(j, n)$ を最小にしようと思った場合、それより前の改行位置 $i$ はいくつか考えられるけど、いずれの $i$ であっても $D(i, n-1)$ も最小になっている必要があるので、最適値を $D^\ast$ で表すことにすれば、次の関係が成り立つ：
$$ D^\ast(j, n) = \min_{i < j} \left\{D^\ast(i, n-1) + L(i, j) \right\} $$
つまり、$D^\ast(j, n)$ を求める問題を解こうと思った場合、部分問題の $D^\ast(i, n-1)$ を求める問題を解くという再帰的な構造をこの問題は持っていることが分かる。
これは最適性原理と呼ばれるもので、最適化しようとしている問題をある部分問題にしたとき、元の問題の最適解はその部分問題の最適解を含んでいるという性質。 そして、この最適性原理が成り立っている問題に対しては、動的計画法を使うことができる。
もう一つ重要な観察として、上記では $i < j$ となる $i$ をすべて動かして最小値を与える $i$ を探すとしてたけど、行のデメリット $L(i, j)$ を見てみると、$i$ と $j$ が近い場合は入る空白の数が少ないので、グルーをめちゃくちゃ伸ばす必要があって、$L(i, j)$ の値はとても大きくなる。 そういった大きなデメリットになる改行位置を考慮するのは無駄になる。 そこで、見た目の悪さ $b$ に関して閾値を与え（toleranceという値）、それを超える改行位置は考慮しないとした方がいい。
また、$i$ と $j$ が離れすぎた場合、今度はグルーを最大限縮めても一行に収まらないということが出てくる。 そういった場所も改行位置としては相応しくないので、それ以上離れた改行位置は考慮しないとした方がいい（※4）。
以上を踏まえて、次のようなアルゴリズムが組み立てられる：
- データ構造の用意
- 「改行位置、そこまでの部分的な段落のデメリット値、直前の最適な改行位置」を保持する「改行情報」というデータ構造を用意する
- 改行情報のリストで、最小のデメリット値が確定したものを入れる「確定済み改行情報リスト」を用意する
- 改行情報のリストで、最小のデメリット値が未確定のものを入れる「未確定な改行情報リスト」を用意する
- 「未確定な改行情報リスト」の先頭に、「改行位置=段落の最初、そこまでの部分的な段落のデメリット値=0、直前の最適な改行位置=なし」という改行情報を追加しておく
- 以下を繰り返す
- 「未確定な改行情報リスト」から先頭の要素を取り出し、「確定済み改行情報リスト」の最後に追加する
- 取り出した改行情報の改行位置を $i$、そこまでの部分的な段落のデメリット値を $D(i)$ とする
- もし改行位置 $i$ が段落の最後なら、繰り返し終了
- 改行位置 $i$ よりあとの改行位置 $j$ について、順に以下を処理する
- $i$ と $j$ で決まる一行について、見た目の悪さ $b$ を計算する
- $b$ が閾値（tolerance）以上なら次の繰り返しへ
- 逆にグルーを縮める必要があって $b$ が100となるなら、繰り返し終了（※5）
- いずれでもない場合、$i$ と $j$ で決まる一行のデメリット $d$ を計算し、$j$ までの部分的な段落の暫定的なデメリット値を $D'(j) = D(i) + d$ と計算する
- 改行位置 $j$ に関する改行情報が「未確定な改行情報リスト」に含まれる場合、
- その改行情報での部分的な段落のデメリット値を $D(j)$ とする
- $D'(j) < D(j)$ であれば、$i$ で改行した上で $j$ で改行した方がデメリットを小さくできるので、$D(j)$ の値を $D'(j)$ で更新し、直前の最適な改行位置を $i$ に更新する
- 含まれない場合、「改行位置=$j$、そこまでの部分的な段落のデメリット値=$D'(j)$、直前の最適な改行位置=$i$」という改行情報を「未確定な改行情報リスト」に追加する（改行位置が順に並ぶようにしておくこと）
- 「確定済み改行情報リスト」の最後の改行情報（＝改行位置が段落の最後となっている改行情報）を取り出し、直前の最適な改行位置を順に辿っていくことで、最適な改行位置のリストを作成する
ちなみに、これは最短経路を求めるダイクストラ法とほとんど同じになっている。 最短経路といえば乗換案内とかでも使われているわけだけど、乗換案内のアルゴリズムと行分割のアルゴリズムがほとんど同じものになるというのは、ちょっと面白いかも。
あとはこれを実際に実装してみようとも思ったんだけど、時間切れ。 また何か別の機会で実装してみたい。
※4：ただ、参考文献だと明言されてる場所を見つけられなかったので、間違ってるかも；当たり前すぎて言及されてないだけだと思うけど
※5：結果としてこの繰り返しが1回も回らない可能性がある；その場合はオーバーフルボックスになるはず（このあたり理解がまだ怪しい）
参考文献は以下：
今日はここまで！
