読者です 読者をやめる 読者になる 読者になる

FIELD NOTES: 書を持って街へ出よう

合同会社フィールドワークス プログラマ兼代表のブログ

TeXで使用しているハイフネーションアルゴリズムについて

技術調査

TeXで欧文文書を成形する際に必要に応じて単語のハイフネーション処理を行なっている。TeXの解説書などによると,F. M. Liangさんの考案したパターンマッチングによりハイフンを入れる箇所を求める方式を使っているらしい。
現在作成している帳票ソフトでハイフネーション処理が必要になってきたので,このアルゴリズムの詳細を調べ,OCamlで実装した。

パターン辞書の準備

まず,パターンマッチングに使用する辞書を準備する。
これには,以下のような形式の辞書を用意する。

".aft" → [0, 0, 0, 1, 0]
".alt" → [0, 0, 0, 3, 0]
"ama" → [4, 0, 0, 0]
"by." → [5, 0, 0, 0]
...

矢印をはさんで左側がキーワード,右側がハイフンの挿入位置を示す。
キーワード中の“.”は,単語の始めと終わりにマッチする文字である。
右側の数字が奇数の場合,ハイフンを挿入すべき位置であることを示す。反対に偶数であれば,ハイフンを挿入すべきでないことを示す。また,数値が大きいほど積極的にハイフンを挿入すべき/挿入すべきでないことを表現している。

ハイフネーション処理

ハイフネーション処理は,以下の順で行う。

  1. 単語の最初と最後に“.”を付ける。
  2. 1文字目から始めて,マッチするパターンが持つ数列をすべて抽出する。
  3. 以降,1文字づつずらしながらマッチするパターンが持つ数列をすべて抽出する。
  4. 文字位置ごとに,得られた数値の最大値を求める。
  5. 最終的に得られた最大値の数列において,奇数の数字の位置をハイフンを挿入すべき位置とみなす。

実装

http://nedbatchelder.com/code/modules/hyphenate.htmlに公開されているPythonコードを参考にOcamlで実装した。
Pythonコードは非常にコンパクトに実装してあるが,OCamlで実装したら3倍ぐらいに膨らんでしまった。特に,圧縮して保持しているパターン辞書を展開する処理で手間取った。Pythonコードでは正規表現を使っているが,OcamlのStrモジュールの正規表現Pythonとは振る舞いが異なり使えなかった。また,副作用を利用しない形にこだわったので,最終的にはオリジナルとはまったく異なるコードとなった。

今回は,他のモジュールとの結合度の高いプログラムになってしまったので,コードは非公開とする。