Apache FOPを使ってみる～Knuthの分割アルゴリズム

はじめに

　Apache FOPの改行および改ページのために用いられているのは、　Knuth分割アルゴリズム　と呼ばれるものです。このアルゴリズムの設計者は、「文芸的プログラミング（Literate Programming）」のコンセプトで有名なDonald Knuth（ドナルド・クヌース）さんで、TeXの開発者でもあるんです。TeXもこの分割アルゴリズムを使っているので、非常に実績のあるアルゴリズムです。

　Knuthの分割アルゴリズムについての詳細な説明は、書籍　“Digital Typography ”　（ISBN 1-57586-010-4）の中の論文“Breaking Paragraphs into Lines”に見つけることができます。

※　この本は当然全部英語なので　^^;　^^;、、、日本語のよい資料はないかと探してみたところ、概念的に分かりやすい資料として、http://www.tom.sfc.keio.ac.jp/~hagino/sa07/04.pdf を見つけました。これはTeXについて説明したものですが、Knuthアルゴリズムについての概念的な説明が含まれているので、こちらもご一読ください。

　Apache FOPでのKnuthモデルについて説明がされているWikiのページ（http://wiki.apache.org/xmlgraphics-fop/KnuthsModel）をベース（コピペじゃないですよ　^^;）にして、Knuthアルゴリズムの基本的な考え方を説明していきます。今回の解説の範囲では、段落の行分割に関する問題で、用語もそれに沿った「段落」「行」「単語」などとしていますが、コンセプトはページ分割についても当てはめて考えることができるものです。実際に、FOPでは行分割、ページ分割ともにKnuthアルゴリズムを使用しています。

段落モデリング

段落は、要素の列としてモデル化することができます。

　　　　X₁　X₂　X₃　…　X_n

それぞれの　X_i　要素は、box要素、glue要素、penalty要素のいずれかの要素とすることができます。

すべての要素は、幅w　を持っているものとします。もし、　X_i　が　i　番目の要素である場合、その要素の幅はw_iとします。

Box要素

　box要素は、固定幅を持つ分割できないピースを表します。たとえば、文字、音節、インライン画像などです 。

Glue要素

　glue要素は、box要素間の間隔などを表現します。たとえば、二つの単語の間のスペース文字などです。

　glue要素　x_i　がある場合、それは最適幅　w_i　と共に、伸張可能量y_iと縮小可能量　z_i　を持っています。つまり、分割アルゴリズムは、この要素の実際の幅として　[　w_i　–　z_i　,　 w_i　+　y_i　]　のうちのいずれの値も指定できる、ということになります。当然、可能な限りw_iの近くの値を取ろうとするはずです 。

Penalty要素

　penalty要素は、分割点などの情報を表現します。純粋に情報を指定するための要素で、特定の文字や文字列を表現することはありません。

　penalty要素　x_i　の幅　w_i　は、分割アルゴリズムがそのpenalty要素を分割点として選ぶ場合にのみ考慮されます。たとえば、改行について考える場合、単語にハイフンを入れなければならないときに限って、ハイフン“-”の幅を考慮することになるのです。

　penalty要素　x_i　は、分割点としての非推奨値を表すpenalty値　p_i　を持っています。それが正の値である場合、分割アルゴリズムに対してそこを分割点として使用しないように推奨していることになります。しかし、負の値である場合は、そこを分割点として使用するのに魅力的な位置であることを示めしています。特に、p_i　が　+infinity（無限大）の場合は分割を禁止していることになり、逆に、piが-infinity（無限小）の場合は分割を強制していることになります。

　さらに、penalty要素は、flaggedというbool値を持っています。この値は、連続する行の終わりとして選ばれるべきではないことを示します。たとえば、行分割において、単語内のハイフン分割点はflaggedとして表現されますので、分割アルゴリズムはハイフンで終わる行が連続しないように努力することになります。

分割点に関する処理

　段落を行に分割するとき、通常は行内の文字の間隔が開きすぎていたり、逆に狭すぎたりすることのない点を分割点として選ぶはずです。これから、その適切な分割点をどのようにして決定するかについて解説します。

　まず、文字列の中にはそこで分割することができない場所と分割できる場所があります。たとえば、アルファベット言語であれば単語の音節の途中で分割することは基本的にできませんが、単語の間にあるスペースでは分割することができます。この、文字列の中で分割できる箇所、それを　Legal Breakpoint　と呼びます。

Apache FOPにおけるLegal Breakpointの採用条件（いずれか）

　しかし、分割点としてすべての　Legal Breakpoint　が採用されるわけではなく、行分割位置としてふさわしいと思われる　Legal Breakpoint　が候補としてあげられることになります。この分割候補としてあげられる分割点のことを　Feasible Breakpoint　と呼ばれます。これには、算出された美的コスト（demerits）がしきい値を下回っている　Legal Breakpoint　が選ばれることになります。

Apache FOPにおけるdemeritsの大まかな算出基準

• ・与えられた幅に対してどれほどの調整（伸び縮み）を行う必要があるか
• ・分割点がPenalty要素の場合、そのpenalty値
• ・前回採用された分割点がPenalty要素で、今回考慮している分割点もPenaltyである場合、flagged指定が連続していないかどうか



　ある　Feasible Breakpoint（F1とする）が行分割の候補として選ばれた場合、そのF1の後に始まる行の終わりにも　Feasible Breakpoint　が存在することが期待されます。もし、そのような　Feasible Breakpoint　が存在しないのであれば、F1は行分割の候補としては使用できないことになります。その場合、F1はDeactivatedされることになるのです。逆に、もしF1の後に始まる行の終わりにFeasible Breakpointが存在する場合、F1はActive Breakpointとなります。

次回は実装の詳細解説

今回はこの辺で。。。ちょっと難しかったでしょうか。うまく説明できたか、、、不安ですが・・

事業推進　事業企画担当　遊撃手　吉田晃伸