ループを含む素性構造単一化における構造共有手法

概要

論文の詳細を見る
ATRでは、素性構造の複製を逐次的に行なう「非破壊的グラフ単一化アルゴリズム」を元にして、これを遅延複製と構造共有が実現できるように改良した「構造共有型準破壊的グラフ単一化アルゴリズム(Quasi-Destructive Graph Unification with Data Structure Sharing、以下QDSS)」を開発し、音声言語翻訳実験システム(SL-TRANS)の日本語構文解析部で用いている。QDSSは、単一化操作を無矛盾性検査と出力素性構造作成の二つの段階に分けることによって過剰複製、早期複製を排除し、さらに、構造共有により冗長複製を回避するアルゴリズムである。QDSSの問題点は、(1)素性構造がループを含む場合、ループ上の全てのノードが、たとえ変更されなくても単一化の度に複製されること、(2)Bottom型(変数)のノードを構造共有した場合、ある条件下では単一化結果が論理的の不適切なものになること、である。そこで本稿では、(1)の問題に焦点を当てたQDSSの拡張として、ループを含む素性構造の構造共有を行なう方法について紹介する。
一般社団法人情報処理学会の論文
1992-09-28