超並列制約伝播プロジェクトで開発されたアルゴリズムの 単一化文法パーザーでの使用実験 Abstract:グラフの単一化は単一化を利用した自然言語処理において計算時間のボトルネックになっている。本稿では準破壊型単一化にデータ構造レベルでの表現内容の共有化を利用したグラフの複製手法を導入する方法について述べる。この単一化手法は超並列制約伝播解析における制約処理手法として当初開発されたが、ループを扱える一般化された単一化手法であり、通常の単一化文法パーザ等で利用可能であり、HPSGベースの日本語文法のアーレーのアルゴリズムを利用した解析ではWroblewskiの手法の3倍から5倍程度の実行速度を確認した。
Graph unification remains the most expensive part of unification-based natural language constraint processing. We focus on one speed-up element in the design of unification algorithms: avoidance of copying of unmodified subgraphs. We propose a method of attaining such a design through a method of structure-sharing which avoids log(d) overheads often associated with structure-sharing of graphs without any use of costly dependency pointers. The proposed scheme eliminates redundant copying while maintaining the quasi-destructive scheme's ability to avoid over copying and early copying combined with its ability to handle cyclic structures without algorithmic additions. This algorithm was originally developed by the author as a fast graph-unification method in the joint ATR/CMU massively-parallel constraint propagation natural language processing project and is now used in the conventional unification-based grammar parsing at ATR and at CMU.