(57)【特許請求の範囲】
【請求項１】
ノード、及び０以上のノードと０以上のノードとを結ぶ超辺からなる有向グラフであって、前記有向グラフは無閉路であって、前記ノードの各々に入力される超辺の数が１以下であり、前記ノードの各々から出力される超辺の数が１以下であり、かつ、全ての前記ノードの各々について、前記ノードの始点となるノードの数が０よりも多い有向グラフである、意味構造を表すＤＡＧグラフを、ノード及び超辺からなる有向グラフであって、前記ノードの各々に入力される超辺の数が０以上であり、前記ノードの各々から出力される超辺の数が０以上である有向グラフである、前記意味構造を表す超グラフに変換するグラフ変換装置において、
１つの超辺と前記１つの超辺の始点となる各ノードからなるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力された前記ＤＡＧグラフに含まれる前記１つの超辺を超グラフに置換する処理を繰り返すことにより、前記超グラフに変換する変換部
を含む、グラフ変換装置。
【請求項２】
ノード、及び０以上のノードと０以上のノードとを結ぶ超辺からなる有向グラフであって、前記有向グラフは無閉路であって、前記ノードの各々に入力される超辺の数が１以下であり、前記ノードの各々から出力される超辺の数が１以下であり、かつ、全ての前記ノードの各々について、前記ノードの始点となるノードの数が０よりも多い有向グラフである、意味構造を表すＤＡＧグラフを、ノード及び超辺からなる有向グラフであって、前記ノードの各々に入力される超辺の数が０以上であり、前記ノードの各々から出力される超辺の数が０以上である有向グラフである、前記意味構造を表す超グラフに変換するグラフ変換装置において、
１つのＤＡＧグラフと前記１つのＤＡＧグラフの始点となる各ノードからなるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力された前記ＤＡＧグラフに含まれる前記１つのＤＡＧグラフを超グラフに置換する処理を繰り返すことにより、前記超グラフに変換する変換部
を有する、グラフ変換装置。
【請求項３】
変換部を含む、ノード、及び０以上のノードと０以上のノードとを結ぶ超辺からなる有向グラフであって、前記有向グラフは無閉路であって、前記ノードの各々に入力される超辺の数が１以下であり、前記ノードの各々から出力される超辺の数が１以下であり、かつ、全ての前記ノードの各々について、前記ノードの始点となるノードの数が０よりも多い有向グラフである、意味構造を表すＤＡＧグラフを、ノード及び超辺からなる有向グラフであって、前記ノードの各々に入力される超辺の数が０以上であり、前記ノードの各々から出力される超辺の数が０以上である有向グラフである、前記意味構造を表す超グラフに変換するグラフ変換装置における、グラフ変換方法であって、
前記変換部は、１つの超辺と前記１つの超辺の始点となる各ノードからなるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力された前記ＤＡＧグラフに含まれる前記１つの超辺を超グラフに置換する処理を繰り返すことにより、前記超グラフに変換する
グラフ変換方法。
【請求項４】
変換部を含む、ノード、及び０以上のノードと０以上のノードとを結ぶ超辺からなる有向グラフであって、前記有向グラフは無閉路であって、前記ノードの各々に入力される超辺の数が１以下であり、前記ノードの各々から出力される超辺の数が１以下であり、かつ、全ての前記ノードの各々について、前記ノードの始点となるノードの数が０よりも多い有向グラフである、意味構造を表すＤＡＧグラフを、ノード及び超辺からなる有向グラフであって、前記ノードの各々に入力される超辺の数が０以上であり、前記ノードの各々から出力される超辺の数が０以上である有向グラフである、前記意味構造を表す超グラフに変換するグラフ変換装置における、グラフ変換方法であって、
前記変換部は、１つのＤＡＧグラフと前記１つのＤＡＧグラフの始点となる各ノードからなるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力された前記ＤＡＧグラフに含まれる前記１つのＤＡＧグラフを超グラフに置換する処理を繰り返すことにより、前記超グラフに変換する
グラフ変換方法。
【請求項５】
コンピュータを、請求項１又は２記載のグラフ変換装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力された閉路無し有向超グラフをより一般的な有向超グラフへと変換するためのグラフ変換装置、方法、及びプログラムに関するものである。
【背景技術】
【０００２】
従来、木構造から木構造への変換を行う木トランスデューサ（非特許文献１）、閉路無し有向超グラフ（ＤＡＧ：Ｄｉｒｅｃｔｅｄ  ａｃｙｃｌｉｃ  ｇｒａｐｈ）から木構造への変換を行うＤＡＧトランスデューサ（非特許文献２）、及び木構造からより一般的な有向超グラフ（以下、Ｇｒａｐｈとも称する）への変換を行う木‐ｔо‐Ｇｒａｐｈトランスデューサ（非特許文献３）が知られている。なお、図１３左に、自然言語構文木（ＤＡＧの一種）、図１３中央に、自然言語文の簡単化された意味構造（ＤＡＧ）、及び図１３右に、自然言語文の完全な意味構造（Ｇｒａｐｈ）の各々の例を示す。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Andreas Maletti. Survey: Tree transducers in machine translation. In NCMA, pages 11−32. Citeseer, 2010.
【非特許文献２】Tsutomu Kamimura and Giora Slutzki. Parallel and two-way automata on directed ordered acyclic graphs. Information and Control, 49(1):10−51, 1981.
【非特許文献３】Joost Engelfriet and Heiko Vogler. The translation power of top-down tree-to-graph transducers. Journal of Computer and System Sciences, 49(2):258−305, 1994.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、上述した従来の方法では、ＤＡＧからＧｒａｐｈへの変換が行えるより一般化されたトランスデューサが存在しない（従来の３つの独立した方法を統一する枠組みがない）という問題がある。
【０００５】
また、ＤＡＧトランスデューサは自然言語処理などの実課題に対して、表現力が乏しい（モデル化できない言語現象などがある）という問題がある。
【０００６】
本発明では、上記問題点を解決するために成されたものであり、木トランスデューサ、ＤＡＧトランスデューサ、及び木‐ｔо‐Ｇｒａｐｈトランスデューサでモデル化することができる問題を全て解くことができる統一的な枠組みの提供をすることができるグラフ変換装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、第１の発明に係るグラフ変換装置は、ノード、及び０以上のノードと０以上のノードとを結ぶ超辺からなる有向グラフであって、前記有向グラフは無閉路であって、前記ノードの各々に入力される超辺の数が１以下であり、前記ノードの各々から出力される超辺の数が１以下であり、かつ、全ての前記ノードの各々について、前記ノードの始点となるノードの数が０よりも多い有向グラフである、意味構造を表すＤＡＧグラフを、ノード及び超辺からなる有向グラフであって、前記ノードの各々に入力される超辺の数が０以上であり、前記ノードの各々から出力される超辺の数が０以上である有向グラフである、前記意味構造を表す超グラフに変換するグラフ変換装置において、１つの超辺と前記１つの超辺の始点となるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力された前記ＤＡＧグラフに含まれる前記超辺を置換する処理を繰り返すことにより、前記超グラフに変換する変換部、を含んで構成されている。
【０００８】
第２の発明に係るグラフ変換方法は、変換部を含む、ノード、及び０以上のノードと０以上のノードとを結ぶ超辺からなる有向グラフであって、前記有向グラフは無閉路であって、前記ノードの各々に入力される超辺の数が１以下であり、前記ノードの各々から出力される超辺の数が１以下であり、かつ、全ての前記ノードの各々について、前記ノードの始点となるノードの数が０よりも多い有向グラフである、意味構造を表すＤＡＧグラフを、ノード及び超辺からなる有向グラフであって、前記ノードの各々に入力される超辺の数が０以上であり、前記ノードの各々から出力される超辺の数が０以上である有向グラフである、前記意味構造を表す超グラフに変換するグラフ変換装置における、グラフ変換方法であって、前記変換部は、１つの超辺と前記１つの超辺の始点となるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力された前記ＤＡＧグラフに含まれる前記超辺を置換する処理を繰り返すことにより、前記超グラフに変換する。
【０００９】
第１及び第２の発明によれば、変換部により、１つの超辺と１つの超辺の始点となるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力されたＤＡＧグラフに含まれる超辺を置換する処理を繰り返すことにより、超グラフに変換する。
【００１０】
このように、１つの超辺と１つの超辺の始点となるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力されたＤＡＧグラフに含まれる超辺を置換する処理を繰り返すことにより、超グラフに変換することにより、木トランスデューサ、ＤＡＧトランスデューサ、及び木‐ｔо‐Ｇｒａｐｈトランスデューサでモデル化することができる問題を全て解くことができる統一的な枠組みの提供をすることができる。
【００１１】
第３の発明に係るグラフ変換装置は、ノード、及び０以上のノードと０以上のノードとを結ぶ超辺からなる有向グラフであって、前記有向グラフは無閉路であって、前記ノードの各々に入力される超辺の数が１以下であり、前記ノードの各々から出力される超辺の数が１以下であり、かつ、全ての前記ノードの各々について、前記ノードの始点となるノードの数が０よりも多い有向グラフである、意味構造を表すＤＡＧグラフを、ノード及び超辺からなる有向グラフであって、前記ノードの各々に入力される超辺の数が０以上であり、前記ノードの各々から出力される超辺の数が０以上である有向グラフである、前記意味構造を表す超グラフに変換するグラフ変換装置において、１つのＤＡＧグラフと前記１つのＤＡＧグラフの始点となるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力された前記ＤＡＧグラフに含まれる前記ＤＡＧグラフを置換する処理を繰り返すことにより、前記超グラフに変換する変換部、を含んで構成されている。
【００１２】
第４の発明に係るグラフ変換方法は、変換部を含む、ノード、及び０以上のノードと０以上のノードとを結ぶ超辺からなる有向グラフであって、前記有向グラフは無閉路であって、前記ノードの各々に入力される超辺の数が１以下であり、前記ノードの各々から出力される超辺の数が１以下であり、かつ、全ての前記ノードの各々について、前記ノードの始点となるノードの数が０よりも多い有向グラフである、意味構造を表すＤＡＧグラフを、ノード及び超辺からなる有向グラフであって、前記ノードの各々に入力される超辺の数が０以上であり、前記ノードの各々から出力される超辺の数が０以上である有向グラフである、前記意味構造を表す超グラフに変換するグラフ変換装置における、グラフ変換方法であって、前記変換部は、１つのＤＡＧグラフと前記１つのＤＡＧグラフの始点となるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力された前記ＤＡＧグラフに含まれる前記ＤＡＧグラフを置換する処理を繰り返すことにより、前記超グラフに変換する。
【００１３】
第３及び第４の発明によれば、変換部により、１つのＤＡＧグラフと１つのＤＡＧグラフの始点となるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力されたＤＡＧグラフに含まれるＤＡＧグラフを置換する処理を繰り返すことにより、超グラフに変換する。
【００１４】
このように、１つのＤＡＧグラフと１つのＤＡＧグラフの始点となるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力されたＤＡＧグラフに含まれるＤＡＧグラフを置換する処理を繰り返すことにより、超グラフに変換することにより、木トランスデューサ、ＤＡＧトランスデューサ、及び木‐ｔо‐Ｇｒａｐｈトランスデューサでモデル化することができる問題を全て解くことができる統一的な枠組みの提供をすることができる。
【００１５】
また、本発明のプログラムは、コンピュータを、上記のグラフ変換装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１６】
以上説明したように、本発明のグラフ変換装置、方法、及びプログラムによれば、１つの超辺と１つの超辺の始点となるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力されたＤＡＧグラフに含まれる超辺を置換する処理を繰り返すことにより、超グラフに変換することにより、木トランスデューサ、ＤＡＧトランスデューサ、及び木‐ｔо‐Ｇｒａｐｈトランスデューサでモデル化することができる問題を全て解くことができる統一的な枠組みの提供をすることができる。
【００１７】
また、１つのＤＡＧグラフと１つのＤＡＧグラフの始点となるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力されたＤＡＧグラフに含まれるＤＡＧグラフを置換する処理を繰り返すことにより、超グラフに変換することにより、木トランスデューサ、ＤＡＧトランスデューサ、及び木‐ｔо‐Ｇｒａｐｈトランスデューサでモデル化することができる問題を全て解くことができる統一的な枠組みの提供をすることができる。
【図面の簡単な説明】
【００１８】
【図１】超辺置換操作の一例を示す図である。
【図２】本発明の第１の実施形態に係るグラフ変換装置の機能的構成を示すブロック図である。
【図３】本発明の第１の実施形態に係るグラフ変換装置におけるグラフ変換処理ルーチンのフローチャート図である。
【図４】英語の簡単化された意味構造から日本語の構文木への非構成的変換の一例を示す図である。
【図５】アルゴリズムの一例を示す図である。
【図６】アルゴリズムの一例を示す図である。
【図７】本発明の第２の実施形態に係るグラフ変換装置の機能的構成を示すブロック図である。
【図８】モデルＭ１の一例を示す図である。
【図９】構文木から完全な意味構造への重み付き変換の過程の一例を示す図である。
【図１０】モデルＭ２の一例を示す図である。
【図１１】簡単化された意味構造から構文木への重み付き変換の過程の一例を示す図である。
【図１２】本発明の第２の実施形態に係るグラフ変換装置におけるグラフ変換処理ルーチンのフローチャート図である。
【図１３】ＤＡＧ、及びＧｒａｐｈの一例を示す図である。
【発明を実施するための形態】
【００１９】
以下、図面を参照して本発明の実施形態を詳細に説明する。
【００２０】
＜本発明の実施形態の概要＞
まず、本発明の実施形態の原理について説明する。後述する本実施形態に係るグラフ変換装置は、入力となる閉路無し有向超グラフ（ＤＡＧ）をより一般的な有向超グラフ（超グラフ）へと変換するための形式的な装置である。
【００２１】
ＤＡＧの構造は自然言語処理の構文木（根付き木）や簡単化された意味構造などを表現できる。また、超グラフはＤＡＧ構造を包含し、より一般的で複雑な構造（自然言語文の完全な意味構造など）も表現できる。
【００２２】
後述する、グラフ変換装置では、構文木から構文木への変換による構文構造に基づく機械翻訳、簡単化された意味構造から構文木への変換による意味構造に基づく機械翻訳、及び構文木から完全な意味構造への変換による意味構造解析等をモデル化し、解くことができる。また、自然言語処理以外のＤＡＧ構造から超グラフ構造への変換問題に対しても応用可能である。
【００２３】
＜定義＞
本実施形態においては、系列、未定義シンボル、及び変数を定義する。以下説明する。
【００２４】
集合Ｖに対して、Ｖ＊はＶ上の要素＊個から成る系列の集合であり、空列
【００２５】
【数１】
0006517630.tif 000002
【００２６】
を含む。ある系列
【００２７】
【数２】
0006517630.tif 000003
【００２８】
は全ての
【００２９】
【数３】
0006517630.tif 000004
【００３０】
に対して、ｖｉ∈Ｖである。なお、系列を表す記号は、ｂоｌｄフォントで表現する。
【００３１】
系列
【００３２】
【数４】
0006517630.tif 000005
【００３３】
の長さは
【００３４】
【数５】
0006517630.tif 000006
【００３５】
と表し、全ての
【００３６】
【数６】
0006517630.tif 000007
【００３７】
に対して、そのｉ番目の要素を
【００３８】
【数７】
0006517630.tif 000008
【００３９】
と表現する。ある２つの系列
【００４０】
【数８】
0006517630.tif 000009
【００４１】
に対して、その結合
【００４２】
【数９】
0006517630.tif 000010
【００４３】
は、＜ｖ１１,...,ｖ１ｎ,ｖ２１,...,ｖ２ｍ＞となる。
【００４４】
ｎｉｌは集合の要素や系列を表す記号が未定義の場合に用いる特殊なシンボルである。Ｘ＝｛ｘ１,ｘ２,....｝を変数の無限集合と定義し、
【００４５】
【数１０】
0006517630.tif 000011
【００４６】
に対して、Ｘｋ＝｛ｘ１,...,ｘｋ｝はその有限集合とする。
【００４７】
また、本実施形態においては、２重階層化アルファベットを定義する。２重階層化アルファベットは組
【００４８】
【数１１】
0006517630.tif 000012
【００４９】
であり、有限集合
【００５０】
【数１２】
0006517630.tif 000013
【００５１】
と関数
【００５２】
【数１３】
0006517630.tif 000014
【００５３】
から成る。
【００５４】
【数１４】
0006517630.tif 000015
【００５５】
は自然数を表す。２重階層化アルファベットを表示するときは省略して、その
【００５６】
【数１５】
0006517630.tif 000016
【００５７】
のみを表示する。関数ｄｒｋは、
【００５８】
【数１６】
0006517630.tif 000017
【００５９】
の要素に２重ランクを割り当てる関数である。全ての
【００６０】
【数１７】
0006517630.tif 000018
【００６１】
に対して、
【００６２】
【数１８】
0006517630.tif 000019
【００６３】
は、その各要素
【００６４】
【数１９】
0006517630.tif 000020
【００６５】
が、
【００６６】
【数２０】
0006517630.tif 000021
【００６７】
となるような
【００６８】
【数２１】
0006517630.tif 000022
【００６９】
の補集合である。その要素
【００７０】
【数２２】
0006517630.tif 000023
【００７１】
は、
【００７２】
【数２３】
0006517630.tif 000024
【００７３】
と表現する。
【００７４】
また、本実施形態においては、超グラフ（Ｇｒａｐｈ）を定義する。２重階層化アルファベット
【００７５】
【数２４】
0006517630.tif 000025
【００７６】
上において、超グラフｈは組ｈ＝（Ｖ,Ｅ,ｓ,ｔ,ｌ,ｂｅｇｉｎ,ｅｎｄ）から成る。なお、それぞれの要素を以下に説明する。
【００７７】
・Ｖはノードの有限集合を表す。
・Ｅは超辺の有限集合を表す。
・ｓ：Ｅ→Ｖ＊はソースノード関数を表す。
・ｔ：Ｅ→Ｖ＊はターゲットノード関数を表す。
・ｌ：Ｅ→Δはラベル付け関数で、全ての超辺ｅ∈Ｅに対して、ｄｒｋ（ｌ（ｅ））＝（｜ｓ（ｅ）｜,｜ｔ（ｅ）｜）となる２重階層化されたシンボルｌ（ｅ）をラベル付けする関数を表す。
・ｂｅｇｉｎ∈Ｖ＊はｈの始点となるノード系列を表す。
・ｅｎｄ∈Ｖ＊はｈの終点となるノード系列を返す関数を表す。
【００７８】
【数２５】
0006517630.tif 000026
【００７９】
上で定義される全ての超グラフの集合（クラス）を
【００８０】
【数２６】
0006517630.tif 000027
【００８１】
として表現する。ある
【００８２】
【数２７】
0006517630.tif 000028
【００８３】
に対して、その要素をＶｈ、Ｅｈ、ｓｈ、ｔｈ、ｌｈ、ｂｅｇｉｎ（ｈ）、ｅｎｄ（ｈ）と表現する。各ｖ∈Ｖｈに対して、ｉｎｄｅｇ（ｖ）はｖに入る超辺の数、оｕｔｄｅｇ（ｖ）はｖから出る超辺の数を表現する。
【００８４】
｜ｂｅｇｉｎ（ｈ）｜＝ｍ、かつ、｜ｅｎｄ（ｈ）｜＝ｎのとき、ｈは（ｍ,ｎ）‐ｈｙｐｅｒｇｒａｐｈと表現し、超グラフｈのランクをｄｒｋ（ｈ）＝（ｍ,ｎ）と表現する。同様に、各超辺ｅ∈Ｅｈがｄｒｋ（ｌ（ｅ））＝（ｍ,ｎ）のとき、ｅを（ｍ,ｎ）‐ｈｙｐｅｒｅｄｇｅと表現する。Δで定義される全ての（ｍ,ｎ）‐ｈｙｐｅｒｇｒａｐｈのクラスを（ｍ,ｎ）‐ＨＧＲ（Δ）として表現する。
【００８５】
また、本実施形態においては、無閉路を定義する。ある超グラフｈにおいて、そのノードｖからノードｕへの経路とは、３つ組の有限系列＜（ｋ１,ｅ１,ｊ１）,...,（ｋｎ,ｅｎ,ｊｎ）＞で表される。ここで、
【００８６】
【数２８】
0006517630.tif 000029
【００８７】
は自然数で、全てのｅｉ∈Ｅｈはｓ（ｅ１）（ｋ１）＝ｖ、かつ、ｔ（ｅｎ）（ｊｎ）＝ｕとなり、全ての
【００８８】
【数２９】
0006517630.tif 000030
【００８９】
に対して、ｔ（ｅｉ）（ｊｉ）＝ｓ（ｅｉ＋１）（ｊｉ＋１）となる。超グラフｈが無閉路とは、各ノードに対して、そのノード自身への空列でない経路が存在しない場合をいう。
【００９０】
また、本実施形態においては、アトムを定義する。
【００９１】
【数３０】
0006517630.tif 000031
【００９２】
となる２重階層化シンボル
【００９３】
【数３１】
0006517630.tif 000032
【００９４】
に対して、
【００９５】
【数３２】
0006517630.tif 000033
【００９６】
とはランク（ｍ,ｎ）の超グラフｇであり、ノード集合
【００９７】
【数３３】
0006517630.tif 000034
【００９８】
となるｅを持つ超辺集合Ｅｇ＝｛ｅ｝、ｂｅｇｉｎ（ｇ）＝ｓ（ｅ）＝＜ａ１,...,ａｍ＞、ｅｎｄ（ｅ）＝ｔ（ｅ）＝＜ｂ１,...,ｂｎ＞、から構成される。
【００９９】
また、本実施形態においては、超辺置換操作を定義する。図１に、図１左の超グラフが持つｘでラベル付けされた超辺を図１中央にある超グラフで置換したとき、図１右の超グラフが作成される。ｈを超グラフ、Ｒ⊆Ｖｈ×Ｖｈをｈのノード間の関係とする。あるノードａ∈Ｖｈに対して、［ａ］Ｒはそれと等価なノードを表す。あるノード補集合Ｖ⊆Ｖｈに対して、Ｖ／Ｒ＝｛［ａ］Ｒ｜ａ∈Ｖ｝と表現する。ノード系列
【０１００】
【数３４】
0006517630.tif 000035
【０１０１】
に対して、
【０１０２】
【数３５】
0006517630.tif 000036
【０１０３】
と表現する。更に、超グラフｈ／Ｒをｈ／Ｒ＝（Ｖｈ／Ｒ,Ｅｈ,ｓ,ｔ,ｌｈ,［ｂｅｇｉｎ（ｈ）］Ｒ,［ｅｎｄ（ｈ）］Ｒ）として表現し、ここでは全てのｅ∈Ｅｈに対して、ｓ（ｅ）＝［ｓｈ（ｅ）］Ｒ、かつ、ｔ（ｅ）＝［ｔｈ（ｅ）］Ｒを満たす。
【０１０４】
ｇを超グラフ、ｅをＥｇ中の（ｍ,ｎ）‐ｈｙｐｅｒｅｄｇｅ、ｈを（ｍ,ｎ）‐ｈｙｐｅｒｇｒａｐｈとしたとき、ｇからｅを取り除き、ｈを加えると、ｇ´＝（Ｖｇ∪Ｖｈ,（Ｅｇ−｛ｅ｝）∪Ｅｈ,ｓ,ｔ,ｌ,ｂｅｇｉｎ（ｇ）,ｅｎｄ（ｇ））が取得できる。
【０１０５】
ここで、ｅ∈（Ｅｇ−｛ｅ｝）に対して、ｓ（ｅ）＝ｓｇ（ｅ）、ｅ∈Ｅｈに対して、ｓ（ｅ）＝ｓｈ（ｅ）であり、ｔとｌも同様である。このとき、ｇ中の超辺ｅに対するｈの置換とは、ｇ［ｅ／ｈ］で表現され、超グラフｇ´／Ｒとなる。ここで、
【０１０６】
【数３６】
0006517630.tif 000037
【０１０７】
となる。
【０１０８】
ＡとＢとを２重階層化アルファベット、φ：Ａ→ＨＧＲ（Ｂ）を置換関数と呼び、全ての
【０１０９】
【数３７】
0006517630.tif 000038
【０１１０】
に対して、
【０１１１】
【数３８】
0006517630.tif 000039
【０１１２】
となる。φを拡張し、関数
【０１１３】
【数３９】
0006517630.tif 000040
【０１１４】
を、下記の様に定義する。
【０１１５】
・
【０１１６】
【数４０】
0006517630.tif 000041
【０１１７】
に対して、
【０１１８】
【数４１】
0006517630.tif 000042
【０１１９】
となる。
【０１２０】
・
【０１２１】
【数４２】
0006517630.tif 000043
【０１２２】
と
【０１２３】
【数４３】
0006517630.tif 000044
【０１２４】
に対して、
【０１２５】
【数４４】
0006517630.tif 000045
【０１２６】
となり、ここで、Ｅｇ＝｛ｅ１,...,ｅｋ｝となる。この拡張された関数
【０１２７】
【数４５】
0006517630.tif 000046
【０１２８】
はｇ中で
【０１２９】
【数４６】
0006517630.tif 000047
【０１３０】
となる全ての超辺ｅを
【０１３１】
【数４７】
0006517630.tif 000048
【０１３２】
で置き換える関数である。
【０１３３】
また、本実施形態においては、木、及びＤＡＧを定義する。２重階層化アルファベット
【０１３４】
【数４８】
0006517630.tif 000049
【０１３５】
上で定義されたＤＡＧ  ｄ＝（Ｖ,Ｅ,ｓ,ｔ,ｌ,ｂｅｇｉｎ,ｅｎｄ）は、ｄは無閉路であり、各ノードｖ∈Ｖに対して、
【０１３６】
【数４９】
0006517630.tif 000050
【０１３７】
、各ノードｖ∈Ｖに対して、
【０１３８】
【数５０】
0006517630.tif 000051
【０１３９】
、及び全てのｅ∈Ｅｊに対して、｜ｓ（ｅ）｜＞０の条件を満たす超グラフである。
【０１４０】
あるＤＡＧ  ｄに対して、各要素をＶｄ、Ｅｄ、ｓｄ、ｔｄ、ｌｄ、ｂｅｇｉｎ（ｄ）、ｅｎｄ（ｄ）と表現する。
【０１４１】
【数５１】
0006517630.tif 000052
【０１４２】
上で定義される全てのＤＡＧのクラスを
【０１４３】
【数５２】
0006517630.tif 000053
【０１４４】
と表現する。｜ｂｅｇｉｎ（ｄ）｜＝ｍ、かつ｜ｅｎｄ（ｄ）｜＝ｎのとき、当該ＤＡＧを（ｍ,ｎ）‐ｄａｇと表現する。全ての（ｍ,ｎ）‐ｄａｇから成るクラスを
【０１４５】
【数５３】
0006517630.tif 000054
【０１４６】
と表現する。
【０１４７】
クラス
【０１４８】
【数５４】
0006517630.tif 000055
【０１４９】
に属するＤＡＧを根付きＤＡＧと表現し、そのクラスに、全てのｅ∈Ｅｄに対して、｜ｓ（ｅ）｜＝１を加えたクラスに属するＤＡＧを木と表現する。
【０１５０】
ＤＡＧや木は、あるノードから出る超辺が１つ以下という制約がある。そのため、あるノードｖ∈Ｖｄに対して、оｕｔ‐ｅ（ｖ）をそのノードから超辺を返す関数とする。もし、出る超辺が無い場合には、ｎｉｌを返す。
【０１５１】
また、本実施形態においては、重み付きＤＡＧ−ｔо−Ｇｒａｐｈトランスデューサを定義する。これを（重み付き）ＤＡＧ−ｔо−Ｇｒａｐｈトランスデューサと表現する。
【０１５２】
重み付きＤＡＧトランスデューサＭは５つ組
【０１５３】
【数５５】
0006517630.tif 000056
【０１５４】
から成る。
【０１５５】
なお、Ｑは状態集合であり、状態は２重階層化アルファベットの要素をとり、Σは入力シンボルの２重階層化アルファベットであり、
【０１５６】
【数５６】
0006517630.tif 000057
【０１５７】
は出力シンボルの２重階層化アルファベットをとり、Ｉ⊆Ｑ（１,０）１は初期状態系列の集合であり、初期状態系列は状態集合Ｑの補集合Ｑ（１,０）から１つだけ要素をとり、Ｒは組（Ｒ´,π）から成り、Ｒ´は規則の有限集合で、各規則ｒは
【０１５８】
【数５７】
0006517630.tif 000058
【０１５９】
で定義される。
【０１６０】
ここで、
【０１６１】
【数５８】
0006517630.tif 000059
【０１６２】
は状態系列、ｅは（ｍ,ｎ）超辺、
【０１６３】
【数５９】
0006517630.tif 000060
【０１６４】
は、ｎ個の変数から成る系列、
【０１６５】
【数６０】
0006517630.tif 000061
【０１６６】
はｍ個の超グラフから成る系列であり、各超グラフは全ての
【０１６７】
【数６１】
0006517630.tif 000062
【０１６８】
に対して、
【０１６９】
【数６２】
0006517630.tif 000063
【０１７０】
が成り立つ。
【０１７１】
【数６３】
0006517630.tif 000064
【０１７２】
は各規則に重みを割り当てる関数である。重み付きの規則は、
【０１７３】
【数６４】
0006517630.tif 000065
【０１７４】
として定義される。
【０１７５】
＜第１の実施形態の原理＞
次に、第１の実施形態に係るグラフ変換装置における、ＤＡＧから超グラフへの変換を行う過程を説明する。当該過程は、規則を入力ＤＡＧは１つずつ提供することで進んでいく。
【０１７６】
状態系列
【０１７７】
【数６５】
0006517630.tif 000066
【０１７８】
とし、
【０１７９】
【数６６】
0006517630.tif 000067
【０１８０】
となるような規則ｒ∈Ｒを考え、ｄｒｋ（ｌ（ｅ））＝（ｍ,ｎ）、かつ、
【０１８１】
【数６７】
0006517630.tif 000068
【０１８２】
、かつ、
【０１８３】
【数６８】
0006517630.tif 000069
【０１８４】
とする。ここで、ｄ∈（１,０）‐ＤＡＧ（Σ）を入力ＤＡＧとし、
【０１８５】
【数６９】
0006517630.tif 000070
【０１８６】
を２つの超グラフとすると、導出の１ステップは
【０１８７】
【数７０】
0006517630.tif 000071
【０１８８】
として表現でき、下記条件を満たすｍ個の超辺
【０１８９】
【数７１】
0006517630.tif 000072
【０１９０】
と超辺ｅｄ∈Ｅｄとが存在する場合に動作する。
【０１９１】
条件１：ｌ（ｅｄ）＝ｌ（ｅ）
条件２：ｓ（ｅｄ）＝＜ｖ１,...,ｖｍ＞
条件３：全ての
【０１９２】
【数７２】
0006517630.tif 000073
【０１９３】
に対して、
【０１９４】
【数７３】
0006517630.tif 000074
【０１９５】
条件４：
【０１９６】
【数７４】
0006517630.tif 000075
【０１９７】
が成り立つ。ここで、
【０１９８】
【数７５】
0006517630.tif 000076
【０１９９】
は、
【０２００】
【数７６】
0006517630.tif 000077
【０２０１】
となる関数で、超辺置換関数
【０２０２】
【数７７】
0006517630.tif 000078
【０２０３】
と拡張したものである。超辺置換関数φは、全ての
【０２０４】
【数７８】
0006517630.tif 000079
【０２０５】
に対して、
【０２０６】
【数７９】
0006517630.tif 000080
【０２０７】
が成り立つような関数である。
【０２０８】
【数８０】
0006517630.tif 000081
【０２０９】
をある自然数、全ての
【０２１０】
【数８１】
0006517630.tif 000082
【０２１１】
に対して、
【０２１２】
【数８２】
0006517630.tif 000083
【０２１３】
を超グラフとする。ここで、
【０２１４】
【数８３】
0006517630.tif 000084
【０２１５】
となるような系列
【０２１６】
【数８４】
0006517630.tif 000085
【０２１７】
をＭにおける
【０２１８】
【数８５】
0006517630.tif 000086
【０２１９】
の導出と表現する。
【０２２０】
導出
【０２２１】
【数８６】
0006517630.tif 000087
【０２２２】
の重み
【０２２３】
【数８７】
0006517630.tif 000088
【０２２４】
は、各規則の重みの積
【０２２５】
【数８８】
0006517630.tif 000089
【０２２６】
で定義される。
【０２２７】
全ての
【０２２８】
【数８９】
0006517630.tif 000090
【０２２９】
に対して、重み付きＤＡＧ‐ｔо‐Ｇｒａｐｈ変換とは、写像
【０２３０】
【数９０】
0006517630.tif 000091
【０２３１】
であり、
【０２３２】
【数９１】
0006517630.tif 000092
【０２３３】
のように定義される。ここで、ｒ１,...,ｒｌ∈Ｒ´は規則である。
【０２３４】
Ｍの意味τＭとは、全ての
【０２３５】
【数９２】
0006517630.tif 000093
【０２３６】
と
【０２３７】
【数９３】
0006517630.tif 000094
【０２３８】
に対して、重み付きＤＡＧ‐ｔо‐Ｇｒａｐｈ変換
【０２３９】
【数９４】
0006517630.tif 000095
【０２４０】
であり、
【０２４１】
【数９５】
0006517630.tif 000096
【０２４２】
として定義される。
【０２４３】
＜本発明の第１の実施形態に係るグラフ変換装置の構成＞
次に、本発明の第１の実施形態に係るグラフ変換装置の構成について説明する。図２に示すように、本発明の本実施形態に係るグラフ変換装置１００は、ＣＰＵと、ＲＡＭと、後述するグラフ変換処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このグラフ変換装置１００は、機能的には図２に示すように入力部１０と、演算部２０と、出力部９０とを含んで構成されている。なお、第１の実施形態においては、上述した第１の実施形態の原理に基づいて、入力されたＤＡＧを変換する。
【０２４４】
入力部１０は、変換対象のＤＡＧを受け付ける。なお、変換対象のＤＡＧの各ノードには状態ｑが付加されているものとする。
【０２４５】
演算部２０は、変換部２２と、ルール記憶部２４とを含んで構成されている。
【０２４６】
変換部２２は、入力部１０において受け付けたＤＡＧに含まれる超辺と状態系列との組み合わせに対応する規則を、ルール記憶部２４から取得し、当該規則を当該ＤＡＧに適用することにより、変換対象となる超辺を超グラフに置換する処理を繰り返すことにより、取得したＤＡＧを超グラフに変換する。また、変換部２２は、取得した超グラフを出力部９０から出力する。
【０２４７】
ルール記憶部２４には、１つの超辺を、当該超辺と当該超辺の始点となるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則が記憶されている。
【０２４８】
＜本発明の第１の実施形態に係るグラフ変換装置の作用＞
次に、本発明の第１の実施形態に係るグラフ変換装置１００の作用について説明する。グラフ変換装置１００は、入力部１０によって、ＤＡＧを受け付けると、グラフ変換装置１００によって、図３に示すグラフ変換処理ルーチンが実行される。
【０２４９】
まず、図３に示すグラフ変換処理ルーチンのステップＳ１００で、ルール記憶部２４に記憶されている規則を読み込む。
【０２５０】
次に、ステップＳ１０２で、ステップＳ１００において取得した規則と、入力部１０において取得したＤＡＧとに基づいて、取得したＤＡＧに含まれる超辺を１つずつ置換し、規則が適用できなくなるまで処理を繰り返し、当該ＤＡＧを超グラフに変換する。
【０２５１】
次に、ステップＳ１０４で、ステップＳ１０２において取得した超グラフを出力部９０から出力して、グラフ変換処理ルーチンを終了する。
【０２５２】
以上説明したように、本発明の本実施形態に係るグラフ変換装置によれば、１つの超辺と１つの超辺の始点となるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力されたＤＡＧグラフに含まれる超辺を置換する処理を繰り返すことにより、超グラフに変換することにより、木トランスデューサ、ＤＡＧトランスデューサ、及び木‐ｔо‐Ｇｒａｐｈトランスデューサでモデル化することができる問題を全て解くことができる統一的な枠組みの提供をすることができる。
【０２５３】
また、従来の木トランスデューサ、ＤＡＧトランスデューサ、及び木‐ｔо‐Ｇｒａｐｈトランスデューサでモデル化することができる問題を全て解くことができる統一的な枠組みを提供することができる。
【０２５４】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０２５５】
次に、第２の実施形態に係るグラフ変換装置について説明する。第２の実施形態においては、ＤＡＧ‐ｔо‐Ｇｒａｐｈトランスデューサの規則の左辺に、任意のＤＡＧを取れるようにトランスデューサを拡張した点が第１の実施形態と異なる。なお、第１の実施形態に係るグラフ変換装置と同様の構成及び作用については、同一の符号を付して、説明を省略する。
【０２５６】
＜第２の実施形態の原理＞
図４左に示すような英語の簡単化された意味構造を、図４右に示すような日本語の構文木へ非構成的変換を行う場合、英語側において、ｇｉｒｌ´はｗоｒｋ´の下にあり、日本語側ではｓｈｅｊとｗоｒｋｊとが同列となることから、上述した第１の実施形態に係るＤＡＧ‐ｔо‐Ｇｒａｐｈトランスデューサに基づいて行うことはできない。
【０２５７】
これは、第１の実施形態に係るＤＡＧ‐ｔо‐Ｇｒａｐｈトランスデューサにおいては、規則の左辺に超辺を１つしかとることができず、入力されたＤＡＧの超辺を１つずつしか処理できないため、英語側のｇｉｒｌ´を日本語側のｓｈｅｊに変換することができないからである。
【０２５８】
そこで、第２の実施形態においては、図４に示した場合についても変換を行えるようにするため、ＤＡＧ‐ｔо‐Ｇｒａｐｈトランスデューサの規則の左辺に、任意のＤＡＧを取れるように拡張する。このような拡張は、非特許文献２のＤＡＧトランスデューサでは記載されていない新しい拡張である。
【０２５９】
重み付き拡張型ＤＡＧ‐ｔо‐Ｇｒａｐｈトランスデューサは、組
【０２６０】
【数９６】
0006517630.tif 000097
【０２６１】
で表現される。上述した第１の実施形態に係るＤＡＧ‐ｔо‐Ｇｒａｐｈとの違いは、規則の左辺に超辺ではなく、ＤＡＧを取れる点である。
【０２６２】
Ｒは組（Ｒ´,π）であり、Ｒ´は規則の有限集合で、各規則ｒは、
【０２６３】
【数９７】
0006517630.tif 000098
【０２６４】
と表現される。ここで、
【０２６５】
【数９８】
0006517630.tif 000099
【０２６６】
は状態系列、ｄは（ｍ,ｎ）‐ｄａｇ、
【０２６７】
【数９９】
0006517630.tif 000100
【０２６８】
はｎ個の変数から成る系列、
【０２６９】
【数１００】
0006517630.tif 000101
【０２７０】
は全ての
【０２７１】
【数１０１】
0006517630.tif 000102
【０２７２】
に対して、
【０２７３】
【数１０２】
0006517630.tif 000103
【０２７４】
となるｎ個の超グラフから成る系列である。
【０２７５】
【数１０３】
0006517630.tif 000104
【０２７６】
は規則の重み関数で、重み付き規則は
【０２７７】
【数１０４】
0006517630.tif 000105
【０２７８】
という形式をとる。
【０２７９】
＜定義＞
また、第２の実施形態においては、ＤＡＧマッチングアルゴリズムを定義する。重み付き拡張型ＤＡＧ‐ｔо‐Ｇｒａｐｈトランスデューサでは、規則の左辺に（ｍ,ｎ）‐ｄａｇをとることができるため、導出を定義するためには、入力されたＤＡＧの任意のｍ個のノードから始まる部分ＤＡＧに、規則の左辺のＤＡＧが一致するか否かを調べる必要がある。
【０２８０】
調べることが行うためのアルゴリズムを図５に示す。ｇを（ｍ,ｎ）−ｄａｇ、ｈをＤＡＧとする。また、
【０２８１】
【数１０５】
0006517630.tif 000106
【０２８２】
をｈの任意のｍ個のノードから成る系列とすると、
【０２８３】
【数１０６】
0006517630.tif 000107
【０２８４】
は、ｈのノード系列
【０２８５】
【数１０７】
0006517630.tif 000108
【０２８６】
を始点とする部分ＤＡＧにｇがマッチするかを判定する。もし、ｇがｈのノード系列
【０２８７】
【数１０８】
0006517630.tif 000109
【０２８８】
を始点とする部分ＤＡＧｈ´にマッチすると、このアルゴリズムはｈ´の終点からなる系列を返す。
【０２８９】
このようなｈ´を探すため、図５に示すアルゴリズムは、ペアＲ＝（ＲＶ,ＲＥ）が存在するかを検査する。当該要素ＲＶ：Ｖｇ→Ｖｈ´とＲＥ：Ｅｇ→Ｅｈ´は、どちらも全単射の関係集合であり、全ての超辺ｅ∈Ｅｇに対して、
【０２９０】
【数１０９】
0006517630.tif 000110
【０２９１】
、かつ、
【０２９２】
【数１１０】
0006517630.tif 000111
【０２９３】
、かつ、
【０２９４】
【数１１１】
0006517630.tif 000112
【０２９５】
が成り立つ。そのようなペアがｇとｈ´の間で存在するとき、ｇはｈ´にマッチし、そうでない場合、ｇはｈ´にマッチしない。図５に示すアルゴリズムでは、ノードに対する関数集合ＲＶは直接構築するが、超辺に対する関係集合ＲＥは構築しない。代わりに、ＲＶに含まれる全てのノードペアに対し、それらのノードから出る超辺ｅ∈Ｅｇとｅ´∈Ｅｈ´の間で
【０２９６】
【数１１２】
0006517630.tif 000113
【０２９７】
、かつ、
【０２９８】
【数１１３】
0006517630.tif 000114
【０２９９】
、かつ、
【０３００】
【数１１４】
0006517630.tif 000115
【０３０１】
が成り立つかを、図６に示すアルゴリズムに基づいて検査する。
【０３０２】
次に、第２の実施形態における導出を定義する。
【０３０３】
【数１１５】
0006517630.tif 000116
【０３０４】
を入力となるＤＡＧ、
【０３０５】
【数１１６】
0006517630.tif 000117
【０３０６】
を２つの超グラフ、
【０３０７】
【数１１７】
0006517630.tif 000118
【０３０８】
を状態系列、ｒ∈Ｒを
【０３０９】
【数１１８】
0006517630.tif 000119
【０３１０】
という形式の規則とし、ここでｄｒｋ（ｄ）＝（ｍ,ｎ）、かつ、
【０３１１】
【数１１９】
0006517630.tif 000120
【０３１２】
、かつ、
【０３１３】
【数１２０】
0006517630.tif 000121
【０３１４】
とする。
【０３１５】
導出の１ステップは、
【０３１６】
【数１２１】
0006517630.tif 000122
【０３１７】
として表現し、次の条件を満たすようなｍ個の超辺
【０３１８】
【数１２２】
0006517630.tif 000123
【０３１９】
が存在するならば動作する。
【０３２０】
条件１：全ての
【０３２１】
【数１２３】
0006517630.tif 000124
【０３２２】
に対して、
【０３２３】
【数１２４】
0006517630.tif 000125
【０３２４】
条件２：
【０３２５】
【数１２５】
0006517630.tif 000126
【０３２６】
条件３：
【０３２７】
【数１２６】
0006517630.tif 000127
【０３２８】
であり、ここで、
【０３２９】
【数１２７】
0006517630.tif 000128
【０３３０】
は関数
【０３３１】
【数１２８】
0006517630.tif 000129
【０３３２】
で、置換関数
【０３３３】
【数１２９】
0006517630.tif 000130
【０３３４】
を拡張したものである。
【０３３５】
この置換関数は全ての
【０３３６】
【数１３０】
0006517630.tif 000131
【０３３７】
に対して、
【０３３８】
【数１３１】
0006517630.tif 000132
【０３３９】
を満たす
【０３４０】
【数１３２】
0006517630.tif 000133
【０３４１】
である。
【０３４２】
＜本発明の第２の実施形態にグラフ変換装置の構成＞
次に、本発明の第２の実施形態に係るグラフ変換装置の構成について説明する。図７に示すように、第２の実施形態に係るグラフ変換装置２００は、ＣＰＵと、ＲＡＭと、後述するグラフ変換処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このグラフ変換装置２００は、機能的には図７に示すように入力部１０と、演算部２２０と、出力部９０とを含んで構成されている。
【０３４３】
演算部２２０は、変換部２２２と、ルール記憶部２２４とを含んで構成されている。
【０３４４】
変換部２２２は、入力部１０において受け付けたＤＡＧに含まれる部分ＤＡＧと状態系列との組み合わせに対応する規則を、ルール記憶部２２４から取得し、当該規則を当該ＤＡＧに適用することにより、変換対象となる部分ＤＡＧを超グラフに置換する処理を繰り返すことにより、取得したＤＡＧを超グラフに変換する。また、変換部２２２は、取得した超グラフを出力部９０から出力する。
【０３４５】
図８に、入力部１０において自然言語文の構文木から完全な意味構造への重み付き変換をモデル化する例を示す。図８に示すモデルＭ１はその規則集合Ｒにｒ１とｒ２との２つの規則を持つ。なお、当該規則集合Ｒは、ルール記憶部２２４に記憶されている規則である。具体的には、例えば、入力部１０において、図１左に示した構文木を受け付けた場合、変換部２２２は、当該構文木に対応する規則ｒ１をルール記憶部２２４から取得し、当該規則に対応するラベルが付加されている図９左の左側の超辺を、規則ｒ１の変換規則に従って、超グラフに置換する。これにより、図９左から図９中央へと遷移する。
【０３４６】
次に、図９中央のＤＡＧに対応する規則ｒ２を、ルール記憶部２２４から取得し、当該規則に対応するラベルが付加されている部分ＤＡＧを、規則ｒ２の変換規則に従って、超グラフに置換する。これにより、図９中央から図９右へと遷移する。このように、規則を繰り返し適用することにより、入力された自然言語文の構文木を、完全な意味構造へと変換させることができる。
【０３４７】
また、図１０に、入力部１０において自然言語文の簡単化された意味構造から自然言語構文木への重み付き変換をモデル化する例を示す。図１０に示すモデルＭ２はその規則集合Ｒにｒ１とｒ２との２つの規則を持つ。なお、当該規則集合Ｒは、ルール記憶部２２４に記憶されている規則である。具体的には、例えば、入力部１０において、図１中央に示した意味構造を受け付けた場合、変換部２２２は、当該意味構造に対応する規則ｒ１をルール記憶部２２４から取得し、当該規則に対応するラベルが付加されている図１１左の左側の超辺を、規則ｒ１の変換規則に従って、超グラフに置換する。これにより、図１１左から図１１中央へと遷移する。
【０３４８】
次に、図１１中央のＤＡＧに対応する規則ｒ２を、ルール記憶部２２４から取得し、当該規則に対応するラベルが付加されている部分ＤＡＧを、規則ｒ２の変換規則に従って、超グラフに置換する。これにより、図１１中央から図１１右へと遷移する。このように、規則を繰り返し適用することにより、入力された簡単化された意味構造から構文木へと変換させることができる。なお、図１１右に示す構文木は、図１左に示した英語構文木に対応する日本語の構文木の例である。
【０３４９】
ルール記憶部２２４には、１つのＤＡＧを、当該ＤＡＧと当該ＤＡＧの始点となるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則が記憶されている。
【０３５０】
＜本発明の第２の実施形態に係るグラフ変換装置の作用＞
次に、第２の本実施形態に係るグラフ変換装置２００の作用について説明する。グラフ変換装置２００は、入力部１０によって、ＤＡＧを受け付けると、グラフ変換装置２００によって、図１２に示すグラフ変換処理ルーチンが実行される。なお、第１の実施形態に係るグラフ変換装置１００と同様の作用については、同一の符号を付して説明を省略する。
【０３５１】
まず、図１２に示すグラフ変換処理ルーチンのステップＳ２００で、ステップＳ１００において取得した規則と、入力部１０において取得したＤＡＧとに基づいて、取得したＤＡＧに含まれる部分ＤＡＧを置換し、規則が適用できなくなるまで処理を繰り返し、当該ＤＡＧを超グラフに変換する。
【０３５２】
以上説明したように、本発明の本実施形態に係るグラフ変換装置によれば、１つのＤＡＧと１つのＤＡＧの始点となるノード系列に対応する状態系列との組み合わせに対応した超グラフに置換するための予め定義された規則に基づいて、入力されたＤＡＧグラフに含まれるＤＡＧを置換する処理を繰り返すことにより、超グラフに変換することにより、木トランスデューサ、ＤＡＧトランスデューサ、及び木‐ｔо‐Ｇｒａｐｈトランスデューサでモデル化することができる問題を全て解くことができる統一的な枠組みの提供をすることができる。
【０３５３】
また、規格拡張化による変換表現力を向上させることができる。
【０３５４】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０３５５】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能であるし、ネットワークを介して提供することも可能である。
【符号の説明】
【０３５６】
１０   入力部
２０,２２０   演算部
２２,２２２   変換部
２４,２２４   ルール記憶部
９０   出力部
１００,２００ グラフ変換装置
【図１】
0006517630.tif 000134
【図２】
0006517630.tif 000135
【図３】
0006517630.tif 000136
【図４】
0006517630.tif 000137
【図５】
0006517630.tif 000138
【図６】
0006517630.tif 000139
【図７】
0006517630.tif 000140
【図８】
0006517630.tif 000141
【図９】
0006517630.tif 000142
【図１０】
0006517630.tif 000143
【図１１】
0006517630.tif 000144
【図１２】
0006517630.tif 000145
【図１３】
0006517630.tif 000146