(57)【要約】【課題】生成規則に関する任意の制約条件を考慮した構文解析を行うことができる。【解決手段】ＢＤＤ構築部３０が、入力された生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築する。構文解析部３２が、予め与えられた生成規則の集合と、終端記号の系列とに基づいて、可能な導出の集合を求め、求められた可能な導出の集合に基づいて、導出において各生成規則が利用されることを、命題変数を用いて表現し、命題変数を用いて終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義し、定義された論理関数に対応する二分決定グラフを構築し、構築された二分決定グラフと、定義された論理関数に対応する二分決定グラフとの論理積となる二分決定グラフを用いて、制約条件を満たし、かつ、確率が最大となる導出を求める。【選択図】図２
2018081505.tif 000002
【特許請求の範囲】
【請求項１】
終端記号の系列に対して、確率文脈自由文法に基づいた構文解析を行う構文解析装置であって、
入力された、確率文脈自由文法における非終端記号を書き換えるための生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築するＢＤＤ構築部と、
予め与えられた生成規則の集合と、前記終端記号の系列とに基づいて、予め定められた開始記号から前記終端記号の系列を得るまでの、前記生成規則の列を導出とし、前記終端記号の系列に対して可能な導出の集合を求め、
前記求められた前記可能な導出の集合に基づいて、前記導出において各生成規則が利用されることを、命題変数を用いて表現し、
前記命題変数を用いて前記終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義し、
前記定義された論理関数に対応する二分決定グラフを構築し、
前記ＢＤＤ構築部によって構築された前記二分決定グラフと、前記定義された論理関数に対応する前記二分決定グラフとの論理積となる前記二分決定グラフを用いて、前記制約条件を満たし、かつ、確率が最大となる導出を求める構文解析部と、
を含む構文解析装置。
【請求項２】
前記構文解析部は、前記終端記号の系列に含まれる前記終端記号の各々について、非終端記号を前記終端記号に書き換える生成規則が、前記導出において利用されることを表す命題変数と、前記終端記号の系列に含まれる部分系列の各々について、前記部分系列に対応して前記生成規則が、前記導出において利用されることを表す命題変数とを用いて、前記論理関数を定義する請求項１に記載の構文解析装置。
【請求項３】
終端記号の系列に対して、確率文脈自由文法に基づいた構文解析を行う構文解析装置における構文解析方法であって、
ＢＤＤ構築部が、入力された、確率文脈自由文法における非終端記号を書き換えるための生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築するステップと、
構文解析部が、予め与えられた生成規則の集合と、前記終端記号の系列とに基づいて、予め定められた開始記号から前記終端記号の系列を得るまでの、前記生成規則の列を導出とし、前記終端記号の系列に対して可能な導出の集合を求めるステップと、
前記構文解析部が、前記求められた前記可能な導出の集合に基づいて、前記導出において各生成規則が利用されることを、命題変数を用いて表現するステップと、
前記構文解析部が、前記命題変数を用いて前記終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義するステップと、
前記構文解析部が、前記定義された論理関数に対応する二分決定グラフを構築するステップと、
前記構文解析部が、前記ＢＤＤ構築部によって構築された前記二分決定グラフと、前記定義された論理関数に対応する前記二分決定グラフとの論理積となる前記二分決定グラフを用いて、前記制約条件を満たし、かつ、確率が最大となる導出を求めるステップと、
を含む構文解析方法。
【請求項４】
前記構文解析部が定義するステップは、前記終端記号の系列に含まれる前記終端記号の各々について、非終端記号を前記終端記号に書き換える生成規則が、前記導出において利用されることを表す命題変数と、前記終端記号の系列に含まれる部分系列の各々について、前記部分系列に対応して前記生成規則が、前記導出において利用されることを表す命題変数とを用いて、前記論理関数を定義する請求項３に記載の構文解析方法。
【請求項５】
コンピュータを、請求項１又は請求項２に記載の構文解析装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、構文解析装置、方法、及びプログラムに係り、特に、終端記号の系列に対して、構文解析を行うための構文解析装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
確率文脈自由文法は自然言語文の構文解析に用いられる基礎的な技術である。確率文脈自由文法Ｇは、Ｇ＝（Ｍ，Ｔ，Ｒ，Ｓ，Ｐ）からなる５つ組として定義される。ここでＭは非終端記号の集合、Ｔは終端記号の集合、Ｒは生成規則の集合、Ｓは開始記号、Ｐは生成規則に付与された確率値の集合である。確率文脈自由文法がチョムスキー標準形であるとすれば、生成規則は以下（１）〜（３）式のいずれかである。
【０００３】
【数１】
2018081505.tif 000003
・・・（１）
2018081505.tif 000004
・・・（２）
2018081505.tif 000005
・・・（３）
【０００４】
ここでＡ、Ｂ、及びＣは非終端記号、αは終端記号、Ｓは開始記号、εは空列を表すものとする。
【０００５】
各規則は、規則の左辺（以下では頭部とよぶ）の非終端記号Ａを右辺の記号列に書き換えることを表している。ある規則Ａ→ＢＣを適用するとは、非終端記号Ａを含む系列において、Ａを非終端記号の列ＢＣに書き換えることを表す。
【０００６】
各規則に対してはその規則が適用される確率が付与されている。与えられた確率文脈自由文法において、規則の頭部が非終端記号Ａであるような規則の集合をｒ１，．．．，ｒｍとすると、各規則ｒｉには出現確率ｗｉが与えられる。ここで確率ｗｉは
【０００７】
【数２】
2018081505.tif 000006
【０００８】
を満たす。各確率は、非終端記号Ａが与えられたときに確率ｗｉで生成規則ｒｉを適用することを表している。
【０００９】
ある確率文脈自由文法Ｇが与えられると、それを用いた構文解析が可能となる。すなわち、与えられた終端記号の列α１，α２，．．．，αｎに対して、開始記号Ｓから当該終端記号の列を導出するための生成規則の適用による非終端記号の書き換えの列を得ることができる。ある構文解析は、開始記号に対して適用した生成規則の列として表現することができる。この列を導出ともよぶ。また、生成規則の列に含まれる各規則に付与された確率の積として、その解析が得られる確率が定義される。
【００１０】
確率文脈自由文法を用いることで自然言語文のように曖昧さのある対象に対する構文解析を行うことができるため、自然言語文の解析や、ＲＮＡ（リボ核酸）の二次構造予測などに用いられてきた。また、確率文脈自由文法が与えられたときに、ある系列に対する構文解析のうち、確率が最大となるものを発見する問題は、系列の長さをＮとするとＯ（Ｎ３）の動的計画法を用いることで解くことができる。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Bryant, Randal E. "Graph-based algorithms for boolean function manipulation." Computers, IEEE Transactions on 100.8 (1986): 677-691.
【非特許文献２】Knuth, D. E. (2009). The Art of Computer Programming: Bitwise Tricks & Techniques;Binary Decision Diagrams, volume 4, fascicle 1.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
確率文脈自由文法を用いた構文解析には動的計画法を用いた効率的なアルゴリズムが存在し、系列の要素間の関係性を考慮した解析が可能であることから、様々な問題に利用される。一方で、既存の動的計画法に基づく構文解析アルゴリズムでは、適用される規則の間の制約条件を考慮することができなかった。ここで制約条件とは、例えばある規則ｒ∈Ｒが導出中に出現する回数に制限を加えたり、規則ｒ，ｓ∈Ｒが導出中で同時に出現することを禁止したりするものである。
【００１３】
本発明は、上記事情を鑑みて成されたものであり、生成規則に関する任意の制約条件を考慮した構文解析を行うことができる構文解析装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するために、第１の発明に係る構文解析装置は、終端記号の系列に対して、確率文脈自由文法に基づいた構文解析を行う構文解析装置であって、入力された、確率文脈自由文法における非終端記号を書き換えるための生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築するＢＤＤ構築部と、予め与えられた生成規則の集合と、前記終端記号の系列とに基づいて、予め定められた開始記号から前記終端記号の系列を得るまでの、前記生成規則の列を導出とし、前記終端記号の系列に対して可能な導出の集合を求め、前記求められた前記可能な導出の集合に基づいて、前記導出において各生成規則が利用されることを、命題変数を用いて表現し、前記命題変数を用いて前記終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義し、前記定義された論理関数に対応する二分決定グラフを構築し、前記ＢＤＤ構築部によって構築された前記二分決定グラフと、前記定義された論理関数に対応する前記二分決定グラフとの論理積となる前記二分決定グラフを用いて、前記制約条件を満たし、かつ、確率が最大となる導出を求める構文解析部と、を含んで構成されている。
【００１５】
また、第１の発明に係る構文解析装置において、前記構文解析部は、前記終端記号の系列に含まれる前記終端記号の各々について、非終端記号を前記終端記号に書き換える生成規則が、前記導出において利用されることを表す命題変数と、前記終端記号の系列に含まれる部分系列の各々について、前記部分系列に対応して前記生成規則が、前記導出において利用されることを表す命題変数とを用いて、前記論理関数を定義するようにしてもよい。
【００１６】
第２の発明に係る構文解析方法は、終端記号の系列に対して、確率文脈自由文法に基づいた構文解析を行う構文解析装置における構文解析方法であって、ＢＤＤ構築部が、入力された、確率文脈自由文法における非終端記号を書き換えるための生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築するステップと、構文解析部が、予め与えられた生成規則の集合と、前記終端記号の系列とに基づいて、予め定められた開始記号から前記終端記号の系列を得るまでの、前記生成規則の列を導出とし、前記終端記号の系列に対して可能な導出の集合を求めるステップと、前記構文解析部が、前記求められた前記可能な導出の集合に基づいて、前記導出において各生成規則が利用されることを、命題変数を用いて表現するステップと、前記構文解析部が、前記命題変数を用いて前記終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義するステップと、前記構文解析部が、前記定義された論理関数に対応する二分決定グラフを構築するステップと、前記構文解析部が、前記ＢＤＤ構築部によって構築された前記二分決定グラフと、前記定義された論理関数に対応する前記二分決定グラフとの論理積となる前記二分決定グラフを用いて、前記制約条件を満たし、かつ、確率が最大となる導出を求めるステップと、を含んで実行することを特徴とする。
【００１７】
また、第２の発明に係る構文解析方法において、前記構文解析部が定義するステップは、前記終端記号の系列に含まれる前記終端記号の各々について、非終端記号を前記終端記号に書き換える生成規則が、前記導出において利用されることを表す命題変数と、前記終端記号の系列に含まれる部分系列の各々について、前記部分系列に対応して前記生成規則が、前記導出において利用されることを表す命題変数とを用いて、前記論理関数を定義するようにしてもよい。
【００１８】
また、第３の発明に係るプログラムは、コンピュータを、第１の発明に係る構文解析装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１９】
本発明の構文解析装置、方法、及びプログラムによれば、生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築し、予め与えられた生成規則の集合と、終端記号の系列とに基づいて、予め定められた開始記号から終端記号の系列を得るまでの、生成規則の列を導出とし、終端記号の系列に対して可能な導出の集合を求め、求められた可能な導出の集合に基づいて、導出において各生成規則が利用されることを、命題変数を用いて表現し、命題変数を用いて終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義し、定義された論理関数に対応する二分決定グラフを構築し、構築された二分決定グラフと、定義された論理関数に対応する二分決定グラフとの論理積となる二分決定グラフを用いて、制約条件を満たし、かつ、確率が最大となる導出を求めることにより、生成規則に関する任意の制約条件を考慮した構文解析を行うことができる、という効果が得られる。
【図面の簡単な説明】
【００２０】
【図１】二分決定グラフ（ＢＤＤ）の一例を示す図である。
【図２】本発明の実施の形態に係る構文解析装置の構成を示すブロック図である。
【図３】本発明の実施の形態に係る構文解析装置における構文解析処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２２】
＜本発明の実施の形態に係る概要＞
【００２３】
まず、本発明の実施の形態における概要を説明する。
【００２４】
本実施の形態で提案する、論理制約が存在するもとでの確率文脈自由文法に基づく構文解析の特徴は、まず確率文脈自由文法における各生成規則を命題変数に置き換えて、可能な導出の集合を、論理関数を用いて表現し、論理関数を二分決定グラフ(ＢＤＤ)とよばれるデータ構造を用いて表現することにある。二分決定グラフを用いて論理関数を表現することによって、可能な導出の集合のうち制約条件を満たし、かつ確率最大となる導出の検索を行うことができるようになる。
【００２５】
＜本発明の実施の形態に係る原理＞
【００２６】
次に、本発明の実施の形態における二分決定グラフ（ＢＤＤ）の原理を説明する。
【００２７】
二分決定グラフ（ＢＤＤ）は論理関数を有向非巡回グラフとして表現するデータ構造である。Ｎ引数の論理関数
【００２８】
【数３】
2018081505.tif 000007
【００２９】
は、Ｎ個の命題変数ｘ１，．．．，ｘＮを引数として受け取り、０または１を出力する関数である。論理関数は命題変数と論理演算子を用いて記述することができる。例えばｘ１，ｘ２を引数として受け取り、ｘ１＝１かつｘ２＝１のときに１、それ以外のときに０を返すような論理関数は、
【００３０】
【数４】
2018081505.tif 000008
【００３１】
として表現することができる。３引数の論理関数
【００３２】
【数５】
2018081505.tif 000009
【００３３】
を表現するＢＤＤを図１に示す。ＢＤＤは２種類のノードからなる。
【００３４】
そのノードを親とするようなアークが存在しないノードを終端ノードとよび、図中では四角で表現する。それ以外のノードを分岐ノードとよび、図中では丸で表現する。ＢＤＤは必ず記号
【００３５】
【数６】
2018081505.tif 000010
【００３６】
が付与された２種類の終端ノードを含む。また、分岐ノードは必ずそのノードを親とする２つのアークを持つ。それぞれのアークは区別され、０枝、１枝とよばれる。図１中では０枝は破線、１枝は実線で表現される。各分岐ノードは論理関数のいずれかの引数である命題変数に対応しており、対応している変数は図１中では分岐ノードの丸の中に書かれた記号で表現されている。対応している変数をＢＤＤの分岐ノードのラベルとよぶ。また、最上位の分岐ノードをＢＤＤの根とよぶ。
【００３７】
ＢＤＤ上で最上位のノードから、入力に応じた枝を辿ることによって、ある引数の値に対する論理関数の出力を得ることができる。例で挙げた論理関数に入力としてｘ＝１，ｙ＝１，ｚ＝１が与えられたときに図１のＢＤＤを用いて関数を評価する方法を示す。まず、根のラベルはｘであり、入力ではｘ＝１であることから、根から１枝を辿って図中で根の直下にある分岐ノードに遷移する。辿った先のノードのラベルはｙであり、入力はｙ＝１であることから、ノードから１枝を辿って
【数７】
2018081505.tif 000011
終端ノードに遷移する。
【数８】
2018081505.tif 000012
終端ノードに遷移した場合、関数は与えられた入力に対して１を返すことを示すため、入力ｘ＝１，ｙ＝１，ｚ＝１に対する出力は１であることが分かる。同様に、入力としてｘ＝１，ｙ＝０，ｚ＝０が与えられたとすると、ＢＤＤを根から順番に辿るとこの場合は
【００３８】
【数９】
2018081505.tif 000013
【００３９】
終端ノードに到達する。
【００４０】
【数１０】
2018081505.tif 000014
【００４１】
終端ノードに到達したときには関数は０を返すことを示すため、入力ｘ＝１，ｙ＝０，ｚ＝０に対する出力は０であることが分かる。
【００４２】
ＢＤＤを用いて論理関数を表現することで、上述した関数の評価のほかにも論理関数間の演算を行うことができたり、関数のモデル（関数が１を返すような引数の値の組合せの個数）を数えるなどの演算を高速に実行することが可能となる。
【００４３】
＜本発明の実施の形態に係る構文解析装置の構成＞
【００４４】
次に、本発明の実施の形態に係る構文解析装置の構成について説明する。図２に示すように、本発明の実施の形態に係る構文解析装置１００は、ＣＰＵと、ＲＡＭと、後述する構文解析処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この構文解析装置１００は、機能的には図２に示すように文入力部１０と、論理制約入力部１２と、生成規則入力部１４と、演算部２０と、出力部５０とを備えている。
【００４５】
文入力部１０は、解析の対象となる終端記号の系列（例えば、自然言語文）の入力を受け付ける。
【００４６】
論理制約入力部１２は、確率文脈自由文法における非終端記号を書き換えるための生成規則に関する制約条件である論理制約を表す論理関数を受け付ける。論理関数の引数については後述する。
【００４７】
生成規則入力部１４は、チョムスキー標準形で与えられる生成規則の集合を入力として受け取る。
【００４８】
演算部２０は、生成規則記憶部２８と、ＢＤＤ構築部３０と、構文解析部３２とを含んで構成されている。
【００４９】
生成規則記憶部２８は、生成規則入力部１４で受け付けた生成規則の集合を記憶している。
【００５０】
ＢＤＤ構築部３０は、論理制約入力部１２で受け付けた論理関数に対応する二分決定グラフを構築する。
【００５１】
構文解析部３２は、生成規則記憶部２８に記憶されている生成規則の集合と、文入力部１０で受け付けた終端記号の系列とに基づいて、予め定められた開始記号Ｓから当該終端記号の系列を得るまでに適用される生成規則の列を導出とし、終端記号の系列に対して可能な導出の集合を求め、求められた可能な導出の集合に基づいて、導出において各生成規則が利用されることを、命題変数を用いて表現し、命題変数を用いて終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義する。構文解析部３２は、定義された論理関数に対応する二分決定グラフを構築し、ＢＤＤ構築部３０によって構築された二分決定グラフと、定義された論理関数に対応する二分決定グラフとの論理積となる二分決定グラフを用いて、可能な導出の集合のうち、論理制約入力部１２で受け付けた論理関数が表す制約条件を満たし、かつ、確率が最大となる導出を求める。ここで、論理関数を定義する際には、終端記号の系列に含まれる終端記号αｉの各々について、非終端記号を終端記号αｉに書き換える生成規則ｒｊが、導出において利用されることを表す命題変数ｄｉｊと、終端記号の系列に含まれる部分系列αｉｊの各々について、部分系列αｉｊに対応して生成規則ｒｌが、導出において利用されることを表す命題変数ｂｉｊｌとを用いる。
【００５２】
＜本発明の実施の形態に係る構文解析装置の作用＞
【００５３】
次に、本発明の実施の形態に係る構文解析装置１００の作用について説明する。生成規則入力部１４が生成規則の集合を受け付けると、生成規則記憶部２８に生成規則の集合が記憶される。そして、構文解析装置１００は、図３に示す構文解析処理ルーチンを実行する。
【００５４】
まず、ステップＳ１００では、文入力部１０が終端記号の系列を受け付け、論理制約入力部１２が論理制約を表す論理関数を受け付ける。受け付けた長さＮの終端記号の列をα１，α２，．．．，αＮとする。Ｔを終端記号の集合とすると、各αｉはαｉ∈Ｔであるとする。また、生成規則記憶部２８に記憶されている生成規則の集合をＲとする。Ｒに含まれる生成規則のうち、非終端記号を終端記号に置き換える規則、すなわちＡ→αの形をしている規則をｑ１，．．．，ｑＫとし，非終端記号を非終端記号のペアに置き換える規則、すなわちＡ→ＢＣの形をしている規則をｒ１，．．．，ｒＭとする。論理制約は、後述する命題変数ｄｉ，ｂｉを引数とする任意の論理関数として表現されるものとする。
【００５５】
次に、ステップＳ１０２では、ステップＳ１００で受け付けた論理制約を表す論理関数に対応する二分決定グラフを構築する。二分決定グラフの構築には、例えば非特許文献１に記載されているような二分決定グラフ構築のための既存手法を用いる。
【００５６】
ステップＳ１０４では、ステップＳ１００で受け付けた生成規則の集合と、終端記号の系列とに基づいて、予め定められた開始記号Ｘから終端記号の系列を得るまでの、生成規則の列を導出とし、終端記号の系列に対して可能な導出の集合を求める。ここでは、Cocke-Younger-Kasami(CYK)アルゴリズムを実行して、生成規則の集合による可能な導出の集合を求める。CYKアルゴリズムは動的計画法によって文脈自由文法の構文解析を行うアルゴリズムである。終端記号の系列のｉ文字目からｊ文字目までからなる部分系列をαｉｊとすると、CYKアルゴリズムは任意の非終端記号を開始記号とする各部分系列への導出を再帰的に求める。すなわち、Ｓｉｊ（Ｘ）を、部分系列αｉｊに対する、非終端記号Ｘを開始記号とする導出において、最初に利用された生成規則のインデックスの集合であるとすると、(ｉ＜ｊ)であるときのＳｉｊ（Ｘ）は以下（４）式のように再帰的に求められる。
【００５７】
【数１１】
2018081505.tif 000015
・・・（４）
【００５８】
また、Ｓｉｉ（Ｘ）は、導出において利用される、非終端記号Ｘを終端記号αｉに書き換える生成規則のインデックスの集合であり、以下（５）式のように定義される。
【００５９】
【数１２】
2018081505.tif 000016
・・・（５）
【００６０】
すべてのＳｉｊ（Ｘ）の計算はＯ(Ｎ３)時間で実行することができる。
【００６１】
ステップＳ１０６では、求められた可能な導出の集合に基づいて、導出において各生成規則が利用されることを、命題変数を用いて表現する。命題変数は、終端記号の系列に含まれる終端記号αｉの各々について、非終端記号を終端記号αｉに書き換える生成規則ｒｊが、導出において利用されることを表す命題変数ｄｉｊと、終端記号の系列に含まれる部分系列αｉｊの各々について、部分系列αｉｊに対応して生成規則ｒｌが、導出において利用されることを表す命題変数ｂｉｊｌとを用いる。すなわち、命題変数ｄｉｊは、終端記号αｉの各々ついて、
【００６２】
【数１３】
2018081505.tif 000017
【００６３】
であるような生成規則のインデックス
【００６４】
【数１４】
2018081505.tif 000018
【００６５】
に対して定義される。
【００６６】
また、命題変数ｂｉｊｌは、終端記号αｉからαｊについて、ｉ≠ｊであり各
【００６７】
【数１５】
2018081505.tif 000019
【００６８】
である場合において、生成規則のインデックスｌ∈Ｓｉｊ（Ｘ）に対応する生成規則ｒｌ＝（Ｘ→ＹＺ）と、あるｋ：i≦ｋ≦ｊ−１について、
【００６９】
【数１６】
2018081505.tif 000020
【００７０】
である生成規則のインデックスｌに対して定義される。
【００７１】
ステップＳ１０８では、ステップＳ１０６で得られた各命題変数ｄｉｊ、ｂｉｊｌを用いて、終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義する。ここでは、論理式間が満たすべき制約の条件をそれぞれ以下（６）〜（１１）のように設定することで、正しい導出を表現する論理関数を構成する。まず、各命題変数dｉ＊のうち、二つ以上が同時に真とならない制約を以下（６）式とする。
【００７２】
【数１７】
2018081505.tif 000021
・・・（６）
【００７３】
同様に、各命題変数ｂｉｊ＊のうち、二つ以上が同時に真とならない制約を以下（７）式のように表す。
【００７４】
【数１８】
2018081505.tif 000022
・・・（７）
【００７５】
次に、各集合Ｓｉｊ（Ｘ）にインデックスが含まれる生成規則のうちいずれかが真となる制約を、以下（８）式のように表す。
【００７６】
【数１９】
2018081505.tif 000023
・・・（８）
【００７７】
同様にＳｉｉ（Ｘ）にインデックスが含まれる生成規則のうちいずれかが真となる制約を、以下（９）式のように表す。
【００７８】
【数２０】
2018081505.tif 000024
・・・（９）
【００７９】
また、命題変数ｂｉｊｋに対し、ｒｋ＝(Ｘ→ＹＺ)であるならば、以下（１０）式の制約を設定する。
【００８０】
【数２１】
2018081505.tif 000025
・・・（１０）
【００８１】
最後に、ｉ＜ｋ≦ｊ＜ｌであるような全てのｂｉｊｍ，ｂｋｌｎに対して、以下（１１）式の制約を設定する。
【００８２】
【数２２】
2018081505.tif 000026
・・・（１１）
【００８３】
上記（６）〜（１１）式を用いると、正しい導出に対応する規則の集合が与えられたときに真を返す論理関数は、命題変数ｄｉｊ，ｂｉｊｋを引数とする関数として以下（１２）のように表現できる。
【００８４】
【数２３】
2018081505.tif 000027
・・・（１２）
【００８５】
ステップＳ１１０では、ステップＳ１０８で定義された論理関数に対応する二分決定グラフを構築する。二分決定グラフの構築は、ステップＳ１０２と同様に非特許文献１に記載の既存手法を用いる。
【００８６】
ステップＳ１１２では、ステップＳ１０２で構築された二分決定グラフと、ステップＳ１１０で構築された二分決定グラフとの論理積となる二分決定グラフを計算する。
【００８７】
ステップＳ１１４では、ステップＳ１１２で構築された二分決定グラフを用いて、可能な導出のうち、ステップＳ１００で受け付けた論理関数が表す制約条件を満たし、かつ、確率が最大となる導出を求める。ステップＳ１１２で計算した二分決定グラフを用いることで、導出確率を最大とする導出は二分決定グラフのサイズに比例する動的計画法で求めることができる。このとき、Ｎ引数ｘ１，．．．，ｘＮの論理関数ｆ(ｘ１，．．．，ｘｎ)が二分決定グラフで表されているとする。また、各ｘｉについて重みｕｉが定められているとすると、二分決定グラフを用いた、非特許文献２に記載されているアルゴリズム(非特許文献２の７ページに記載されている”AlgorithmB”を参照)を用いることで、以下（１３）〜（１５）式を解くことができる。
【００８８】
【数２４】
2018081505.tif 000028
・・・（１３）
2018081505.tif 000029
・・・（１４）
2018081505.tif 000030
・・・（１５）
【００８９】
本実施の形態の問題では、各命題変数ｘｉについて対応する生成規則ｒｊが定まるので、その生成規則の出現確率ｗｊの対数をとり、出現確率ｗｊの対数を命題変数ｘｉに対応する重みｕｉとして設定することによって、上記の定式化によって確率最大かつ制約条件を満たす導出を得ることが可能となる。
【００９０】
以上説明したように、本発明の実施の形態に係る構文解析装置によれば、入力された生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築し、予め与えられた生成規則の集合と、終端記号の系列とに基づいて、予め定められた開始記号から終端記号の系列を得るまでの、生成規則の列を導出とし、終端記号の系列に対して可能な導出の集合を求め、求められた可能な導出の集合に基づいて、導出において各生成規則が利用されることを、命題変数を用いて表現し、命題変数を用いて終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義し、定義された論理関数に対応する二分決定グラフを構築し、構築された二分決定グラフと、定義された論理関数に対応する二分決定グラフとの論理積となる二分決定グラフを用いて、制約条件を満たし、かつ、確率が最大となる導出を求めることにより、生成規則に関する任意の制約条件を考慮した構文解析を行うことができる。
【００９１】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００９２】
例えば、上述した実施の形態における構文解析装置は、自然言語文に対して、構文解析を行う場合について説明したが、これに限定されるものではなく、自然言語文以外の終端記号の列を受け付けて、構文解析を行うようにしてもよい。例えば、ＲＮＡなどの二次構造予測など、何らかの構造に対して、構文解析を行うようにしてもよい。
【符号の説明】
【００９３】
１０   文入力部
１２   論理制約入力部
１４   生成規則入力部
２０   演算部
２８   生成規則記憶部
３０   ＢＤＤ構築部
３２   構文解析部
５０   出力部
１００ 構文解析装置
【図１】
2018081505.tif 000031
【図２】
2018081505.tif 000032
【図３】
2018081505.tif 000033