TOP > 国内特許検索 > 構文解析装置、方法、及びプログラム > 明細書

明細書 :構文解析装置、方法、及びプログラム

発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2018-081505 (P2018-081505A)
公開日 平成30年5月24日(2018.5.24)
発明の名称または考案の名称 構文解析装置、方法、及びプログラム
国際特許分類 G06F  17/27        (2006.01)
G06N   5/04        (2006.01)
FI G06F 17/27 610
G06N 5/04
G06F 17/27 615
請求項の数または発明の数 5
出願形態 OL
全頁数 14
出願番号 特願2016-223547 (P2016-223547)
出願日 平成28年11月16日(2016.11.16)
発明者または考案者 【氏名】西野 正彬
【氏名】山本 章博
出願人 【識別番号】000004226
【氏名又は名称】日本電信電話株式会社
【識別番号】504132272
【氏名又は名称】国立大学法人京都大学
個別代理人の代理人 【識別番号】110001519、【氏名又は名称】特許業務法人太陽国際特許事務所
審査請求 未請求
テーマコード 5B091
Fターム 5B091CA05
要約 【課題】生成規則に関する任意の制約条件を考慮した構文解析を行うことができる。
【解決手段】BDD構築部30が、入力された生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築する。構文解析部32が、予め与えられた生成規則の集合と、終端記号の系列とに基づいて、可能な導出の集合を求め、求められた可能な導出の集合に基づいて、導出において各生成規則が利用されることを、命題変数を用いて表現し、命題変数を用いて終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義し、定義された論理関数に対応する二分決定グラフを構築し、構築された二分決定グラフと、定義された論理関数に対応する二分決定グラフとの論理積となる二分決定グラフを用いて、制約条件を満たし、かつ、確率が最大となる導出を求める。
【選択図】図2
特許請求の範囲 【請求項1】
終端記号の系列に対して、確率文脈自由文法に基づいた構文解析を行う構文解析装置であって、
入力された、確率文脈自由文法における非終端記号を書き換えるための生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築するBDD構築部と、
予め与えられた生成規則の集合と、前記終端記号の系列とに基づいて、予め定められた開始記号から前記終端記号の系列を得るまでの、前記生成規則の列を導出とし、前記終端記号の系列に対して可能な導出の集合を求め、
前記求められた前記可能な導出の集合に基づいて、前記導出において各生成規則が利用されることを、命題変数を用いて表現し、
前記命題変数を用いて前記終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義し、
前記定義された論理関数に対応する二分決定グラフを構築し、
前記BDD構築部によって構築された前記二分決定グラフと、前記定義された論理関数に対応する前記二分決定グラフとの論理積となる前記二分決定グラフを用いて、前記制約条件を満たし、かつ、確率が最大となる導出を求める構文解析部と、
を含む構文解析装置。
【請求項2】
前記構文解析部は、前記終端記号の系列に含まれる前記終端記号の各々について、非終端記号を前記終端記号に書き換える生成規則が、前記導出において利用されることを表す命題変数と、前記終端記号の系列に含まれる部分系列の各々について、前記部分系列に対応して前記生成規則が、前記導出において利用されることを表す命題変数とを用いて、前記論理関数を定義する請求項1に記載の構文解析装置。
【請求項3】
終端記号の系列に対して、確率文脈自由文法に基づいた構文解析を行う構文解析装置における構文解析方法であって、
BDD構築部が、入力された、確率文脈自由文法における非終端記号を書き換えるための生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築するステップと、
構文解析部が、予め与えられた生成規則の集合と、前記終端記号の系列とに基づいて、予め定められた開始記号から前記終端記号の系列を得るまでの、前記生成規則の列を導出とし、前記終端記号の系列に対して可能な導出の集合を求めるステップと、
前記構文解析部が、前記求められた前記可能な導出の集合に基づいて、前記導出において各生成規則が利用されることを、命題変数を用いて表現するステップと、
前記構文解析部が、前記命題変数を用いて前記終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義するステップと、
前記構文解析部が、前記定義された論理関数に対応する二分決定グラフを構築するステップと、
前記構文解析部が、前記BDD構築部によって構築された前記二分決定グラフと、前記定義された論理関数に対応する前記二分決定グラフとの論理積となる前記二分決定グラフを用いて、前記制約条件を満たし、かつ、確率が最大となる導出を求めるステップと、
を含む構文解析方法。
【請求項4】
前記構文解析部が定義するステップは、前記終端記号の系列に含まれる前記終端記号の各々について、非終端記号を前記終端記号に書き換える生成規則が、前記導出において利用されることを表す命題変数と、前記終端記号の系列に含まれる部分系列の各々について、前記部分系列に対応して前記生成規則が、前記導出において利用されることを表す命題変数とを用いて、前記論理関数を定義する請求項3に記載の構文解析方法。
【請求項5】
コンピュータを、請求項1又は請求項2に記載の構文解析装置の各部として機能させるためのプログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、構文解析装置、方法、及びプログラムに係り、特に、終端記号の系列に対して、構文解析を行うための構文解析装置、方法、及びプログラムに関する。
【背景技術】
【0002】
確率文脈自由文法は自然言語文の構文解析に用いられる基礎的な技術である。確率文脈自由文法Gは、G=(M,T,R,S,P)からなる5つ組として定義される。ここでMは非終端記号の集合、Tは終端記号の集合、Rは生成規則の集合、Sは開始記号、Pは生成規則に付与された確率値の集合である。確率文脈自由文法がチョムスキー標準形であるとすれば、生成規則は以下(1)~(3)式のいずれかである。
【0003】
【数1】
JP2018081505A_000003t.gif

・・・(1)
JP2018081505A_000004t.gif
・・・(2)
JP2018081505A_000005t.gif
・・・(3)
【0004】
ここでA、B、及びCは非終端記号、αは終端記号、Sは開始記号、εは空列を表すものとする。
【0005】
各規則は、規則の左辺(以下では頭部とよぶ)の非終端記号Aを右辺の記号列に書き換えることを表している。ある規則A→BCを適用するとは、非終端記号Aを含む系列において、Aを非終端記号の列BCに書き換えることを表す。
【0006】
各規則に対してはその規則が適用される確率が付与されている。与えられた確率文脈自由文法において、規則の頭部が非終端記号Aであるような規則の集合をr,...,rとすると、各規則rには出現確率wが与えられる。ここで確率w
【0007】
【数2】
JP2018081505A_000006t.gif

【0008】
を満たす。各確率は、非終端記号Aが与えられたときに確率wで生成規則rを適用することを表している。
【0009】
ある確率文脈自由文法Gが与えられると、それを用いた構文解析が可能となる。すなわち、与えられた終端記号の列α,α,...,αに対して、開始記号Sから当該終端記号の列を導出するための生成規則の適用による非終端記号の書き換えの列を得ることができる。ある構文解析は、開始記号に対して適用した生成規則の列として表現することができる。この列を導出ともよぶ。また、生成規則の列に含まれる各規則に付与された確率の積として、その解析が得られる確率が定義される。
【0010】
確率文脈自由文法を用いることで自然言語文のように曖昧さのある対象に対する構文解析を行うことができるため、自然言語文の解析や、RNA(リボ核酸)の二次構造予測などに用いられてきた。また、確率文脈自由文法が与えられたときに、ある系列に対する構文解析のうち、確率が最大となるものを発見する問題は、系列の長さをNとするとO(N)の動的計画法を用いることで解くことができる。
【先行技術文献】
【0011】

【非特許文献1】Bryant, Randal E. "Graph-based algorithms for boolean function manipulation." Computers, IEEE Transactions on 100.8 (1986): 677-691.
【非特許文献2】Knuth, D. E. (2009). The Art of Computer Programming: Bitwise Tricks & Techniques;Binary Decision Diagrams, volume 4, fascicle 1.
【発明の概要】
【発明が解決しようとする課題】
【0012】
確率文脈自由文法を用いた構文解析には動的計画法を用いた効率的なアルゴリズムが存在し、系列の要素間の関係性を考慮した解析が可能であることから、様々な問題に利用される。一方で、既存の動的計画法に基づく構文解析アルゴリズムでは、適用される規則の間の制約条件を考慮することができなかった。ここで制約条件とは、例えばある規則r∈Rが導出中に出現する回数に制限を加えたり、規則r,s∈Rが導出中で同時に出現することを禁止したりするものである。
【0013】
本発明は、上記事情を鑑みて成されたものであり、生成規則に関する任意の制約条件を考慮した構文解析を行うことができる構文解析装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【0014】
上記目的を達成するために、第1の発明に係る構文解析装置は、終端記号の系列に対して、確率文脈自由文法に基づいた構文解析を行う構文解析装置であって、入力された、確率文脈自由文法における非終端記号を書き換えるための生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築するBDD構築部と、予め与えられた生成規則の集合と、前記終端記号の系列とに基づいて、予め定められた開始記号から前記終端記号の系列を得るまでの、前記生成規則の列を導出とし、前記終端記号の系列に対して可能な導出の集合を求め、前記求められた前記可能な導出の集合に基づいて、前記導出において各生成規則が利用されることを、命題変数を用いて表現し、前記命題変数を用いて前記終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義し、前記定義された論理関数に対応する二分決定グラフを構築し、前記BDD構築部によって構築された前記二分決定グラフと、前記定義された論理関数に対応する前記二分決定グラフとの論理積となる前記二分決定グラフを用いて、前記制約条件を満たし、かつ、確率が最大となる導出を求める構文解析部と、を含んで構成されている。
【0015】
また、第1の発明に係る構文解析装置において、前記構文解析部は、前記終端記号の系列に含まれる前記終端記号の各々について、非終端記号を前記終端記号に書き換える生成規則が、前記導出において利用されることを表す命題変数と、前記終端記号の系列に含まれる部分系列の各々について、前記部分系列に対応して前記生成規則が、前記導出において利用されることを表す命題変数とを用いて、前記論理関数を定義するようにしてもよい。
【0016】
第2の発明に係る構文解析方法は、終端記号の系列に対して、確率文脈自由文法に基づいた構文解析を行う構文解析装置における構文解析方法であって、BDD構築部が、入力された、確率文脈自由文法における非終端記号を書き換えるための生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築するステップと、構文解析部が、予め与えられた生成規則の集合と、前記終端記号の系列とに基づいて、予め定められた開始記号から前記終端記号の系列を得るまでの、前記生成規則の列を導出とし、前記終端記号の系列に対して可能な導出の集合を求めるステップと、前記構文解析部が、前記求められた前記可能な導出の集合に基づいて、前記導出において各生成規則が利用されることを、命題変数を用いて表現するステップと、前記構文解析部が、前記命題変数を用いて前記終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義するステップと、前記構文解析部が、前記定義された論理関数に対応する二分決定グラフを構築するステップと、前記構文解析部が、前記BDD構築部によって構築された前記二分決定グラフと、前記定義された論理関数に対応する前記二分決定グラフとの論理積となる前記二分決定グラフを用いて、前記制約条件を満たし、かつ、確率が最大となる導出を求めるステップと、を含んで実行することを特徴とする。
【0017】
また、第2の発明に係る構文解析方法において、前記構文解析部が定義するステップは、前記終端記号の系列に含まれる前記終端記号の各々について、非終端記号を前記終端記号に書き換える生成規則が、前記導出において利用されることを表す命題変数と、前記終端記号の系列に含まれる部分系列の各々について、前記部分系列に対応して前記生成規則が、前記導出において利用されることを表す命題変数とを用いて、前記論理関数を定義するようにしてもよい。
【0018】
また、第3の発明に係るプログラムは、コンピュータを、第1の発明に係る構文解析装置の各部として機能させるためのプログラムである。
【発明の効果】
【0019】
本発明の構文解析装置、方法、及びプログラムによれば、生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築し、予め与えられた生成規則の集合と、終端記号の系列とに基づいて、予め定められた開始記号から終端記号の系列を得るまでの、生成規則の列を導出とし、終端記号の系列に対して可能な導出の集合を求め、求められた可能な導出の集合に基づいて、導出において各生成規則が利用されることを、命題変数を用いて表現し、命題変数を用いて終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義し、定義された論理関数に対応する二分決定グラフを構築し、構築された二分決定グラフと、定義された論理関数に対応する二分決定グラフとの論理積となる二分決定グラフを用いて、制約条件を満たし、かつ、確率が最大となる導出を求めることにより、生成規則に関する任意の制約条件を考慮した構文解析を行うことができる、という効果が得られる。
【図面の簡単な説明】
【0020】
【図1】二分決定グラフ(BDD)の一例を示す図である。
【図2】本発明の実施の形態に係る構文解析装置の構成を示すブロック図である。
【図3】本発明の実施の形態に係る構文解析装置における構文解析処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【0021】
以下、図面を参照して本発明の実施の形態を詳細に説明する。

【0022】
<本発明の実施の形態に係る概要>

【0023】
まず、本発明の実施の形態における概要を説明する。

【0024】
本実施の形態で提案する、論理制約が存在するもとでの確率文脈自由文法に基づく構文解析の特徴は、まず確率文脈自由文法における各生成規則を命題変数に置き換えて、可能な導出の集合を、論理関数を用いて表現し、論理関数を二分決定グラフ(BDD)とよばれるデータ構造を用いて表現することにある。二分決定グラフを用いて論理関数を表現することによって、可能な導出の集合のうち制約条件を満たし、かつ確率最大となる導出の検索を行うことができるようになる。

【0025】
<本発明の実施の形態に係る原理>

【0026】
次に、本発明の実施の形態における二分決定グラフ(BDD)の原理を説明する。

【0027】
二分決定グラフ(BDD)は論理関数を有向非巡回グラフとして表現するデータ構造である。N引数の論理関数

【0028】
【数3】
JP2018081505A_000007t.gif

【0029】
は、N個の命題変数x,...,xを引数として受け取り、0または1を出力する関数である。論理関数は命題変数と論理演算子を用いて記述することができる。例えばx,xを引数として受け取り、x1=1かつx2=1のときに1、それ以外のときに0を返すような論理関数は、

【0030】
【数4】
JP2018081505A_000008t.gif

【0031】
として表現することができる。3引数の論理関数

【0032】
【数5】
JP2018081505A_000009t.gif

【0033】
を表現するBDDを図1に示す。BDDは2種類のノードからなる。

【0034】
そのノードを親とするようなアークが存在しないノードを終端ノードとよび、図中では四角で表現する。それ以外のノードを分岐ノードとよび、図中では丸で表現する。BDDは必ず記号

【0035】
【数6】
JP2018081505A_000010t.gif

【0036】
が付与された2種類の終端ノードを含む。また、分岐ノードは必ずそのノードを親とする2つのアークを持つ。それぞれのアークは区別され、0枝、1枝とよばれる。図1中では0枝は破線、1枝は実線で表現される。各分岐ノードは論理関数のいずれかの引数である命題変数に対応しており、対応している変数は図1中では分岐ノードの丸の中に書かれた記号で表現されている。対応している変数をBDDの分岐ノードのラベルとよぶ。また、最上位の分岐ノードをBDDの根とよぶ。

【0037】
BDD上で最上位のノードから、入力に応じた枝を辿ることによって、ある引数の値に対する論理関数の出力を得ることができる。例で挙げた論理関数に入力としてx=1,y=1,z=1が与えられたときに図1のBDDを用いて関数を評価する方法を示す。まず、根のラベルはxであり、入力ではx=1であることから、根から1枝を辿って図中で根の直下にある分岐ノードに遷移する。辿った先のノードのラベルはyであり、入力はy=1であることから、ノードから1枝を辿って
【数7】
JP2018081505A_000011t.gif

終端ノードに遷移する。
【数8】
JP2018081505A_000012t.gif

終端ノードに遷移した場合、関数は与えられた入力に対して1を返すことを示すため、入力x=1,y=1,z=1に対する出力は1であることが分かる。同様に、入力としてx=1,y=0,z=0が与えられたとすると、BDDを根から順番に辿るとこの場合は

【0038】
【数9】
JP2018081505A_000013t.gif

【0039】
終端ノードに到達する。

【0040】
【数10】
JP2018081505A_000014t.gif

【0041】
終端ノードに到達したときには関数は0を返すことを示すため、入力x=1,y=0,z=0に対する出力は0であることが分かる。

【0042】
BDDを用いて論理関数を表現することで、上述した関数の評価のほかにも論理関数間の演算を行うことができたり、関数のモデル(関数が1を返すような引数の値の組合せの個数)を数えるなどの演算を高速に実行することが可能となる。

【0043】
<本発明の実施の形態に係る構文解析装置の構成>

【0044】
次に、本発明の実施の形態に係る構文解析装置の構成について説明する。図2に示すように、本発明の実施の形態に係る構文解析装置100は、CPUと、RAMと、後述する構文解析処理ルーチンを実行するためのプログラムや各種データを記憶したROMと、を含むコンピュータで構成することが出来る。この構文解析装置100は、機能的には図2に示すように文入力部10と、論理制約入力部12と、生成規則入力部14と、演算部20と、出力部50とを備えている。

【0045】
文入力部10は、解析の対象となる終端記号の系列(例えば、自然言語文)の入力を受け付ける。

【0046】
論理制約入力部12は、確率文脈自由文法における非終端記号を書き換えるための生成規則に関する制約条件である論理制約を表す論理関数を受け付ける。論理関数の引数については後述する。

【0047】
生成規則入力部14は、チョムスキー標準形で与えられる生成規則の集合を入力として受け取る。

【0048】
演算部20は、生成規則記憶部28と、BDD構築部30と、構文解析部32とを含んで構成されている。

【0049】
生成規則記憶部28は、生成規則入力部14で受け付けた生成規則の集合を記憶している。

【0050】
BDD構築部30は、論理制約入力部12で受け付けた論理関数に対応する二分決定グラフを構築する。

【0051】
構文解析部32は、生成規則記憶部28に記憶されている生成規則の集合と、文入力部10で受け付けた終端記号の系列とに基づいて、予め定められた開始記号Sから当該終端記号の系列を得るまでに適用される生成規則の列を導出とし、終端記号の系列に対して可能な導出の集合を求め、求められた可能な導出の集合に基づいて、導出において各生成規則が利用されることを、命題変数を用いて表現し、命題変数を用いて終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義する。構文解析部32は、定義された論理関数に対応する二分決定グラフを構築し、BDD構築部30によって構築された二分決定グラフと、定義された論理関数に対応する二分決定グラフとの論理積となる二分決定グラフを用いて、可能な導出の集合のうち、論理制約入力部12で受け付けた論理関数が表す制約条件を満たし、かつ、確率が最大となる導出を求める。ここで、論理関数を定義する際には、終端記号の系列に含まれる終端記号αの各々について、非終端記号を終端記号αに書き換える生成規則rが、導出において利用されることを表す命題変数dijと、終端記号の系列に含まれる部分系列αijの各々について、部分系列αijに対応して生成規則rが、導出において利用されることを表す命題変数bijlとを用いる。

【0052】
<本発明の実施の形態に係る構文解析装置の作用>

【0053】
次に、本発明の実施の形態に係る構文解析装置100の作用について説明する。生成規則入力部14が生成規則の集合を受け付けると、生成規則記憶部28に生成規則の集合が記憶される。そして、構文解析装置100は、図3に示す構文解析処理ルーチンを実行する。

【0054】
まず、ステップS100では、文入力部10が終端記号の系列を受け付け、論理制約入力部12が論理制約を表す論理関数を受け付ける。受け付けた長さNの終端記号の列をα,α,...,αとする。Tを終端記号の集合とすると、各αはα∈Tであるとする。また、生成規則記憶部28に記憶されている生成規則の集合をRとする。Rに含まれる生成規則のうち、非終端記号を終端記号に置き換える規則、すなわちA→αの形をしている規則をq,...,qとし,非終端記号を非終端記号のペアに置き換える規則、すなわちA→BCの形をしている規則をr,...,rとする。論理制約は、後述する命題変数d,bを引数とする任意の論理関数として表現されるものとする。

【0055】
次に、ステップS102では、ステップS100で受け付けた論理制約を表す論理関数に対応する二分決定グラフを構築する。二分決定グラフの構築には、例えば非特許文献1に記載されているような二分決定グラフ構築のための既存手法を用いる。

【0056】
ステップS104では、ステップS100で受け付けた生成規則の集合と、終端記号の系列とに基づいて、予め定められた開始記号Xから終端記号の系列を得るまでの、生成規則の列を導出とし、終端記号の系列に対して可能な導出の集合を求める。ここでは、Cocke-Younger-Kasami(CYK)アルゴリズムを実行して、生成規則の集合による可能な導出の集合を求める。CYKアルゴリズムは動的計画法によって文脈自由文法の構文解析を行うアルゴリズムである。終端記号の系列のi文字目からj文字目までからなる部分系列をαijとすると、CYKアルゴリズムは任意の非終端記号を開始記号とする各部分系列への導出を再帰的に求める。すなわち、Sij(X)を、部分系列αijに対する、非終端記号Xを開始記号とする導出において、最初に利用された生成規則のインデックスの集合であるとすると、(i<j)であるときのSij(X)は以下(4)式のように再帰的に求められる。

【0057】
【数11】
JP2018081505A_000015t.gif

・・・(4)

【0058】
また、Sii(X)は、導出において利用される、非終端記号Xを終端記号αに書き換える生成規則のインデックスの集合であり、以下(5)式のように定義される。

【0059】
【数12】
JP2018081505A_000016t.gif

・・・(5)

【0060】
すべてのSij(X)の計算はO(N)時間で実行することができる。

【0061】
ステップS106では、求められた可能な導出の集合に基づいて、導出において各生成規則が利用されることを、命題変数を用いて表現する。命題変数は、終端記号の系列に含まれる終端記号αの各々について、非終端記号を終端記号αに書き換える生成規則rが、導出において利用されることを表す命題変数dijと、終端記号の系列に含まれる部分系列αijの各々について、部分系列αijに対応して生成規則rが、導出において利用されることを表す命題変数bijlとを用いる。すなわち、命題変数dijは、終端記号αの各々ついて、

【0062】
【数13】
JP2018081505A_000017t.gif

【0063】
であるような生成規則のインデックス

【0064】
【数14】
JP2018081505A_000018t.gif

【0065】
に対して定義される。

【0066】
また、命題変数bijlは、終端記号αからαについて、i≠jであり各

【0067】
【数15】
JP2018081505A_000019t.gif

【0068】
である場合において、生成規則のインデックスl∈Sij(X)に対応する生成規則r=(X→YZ)と、あるk:i≦k≦j-1について、

【0069】
【数16】
JP2018081505A_000020t.gif

【0070】
である生成規則のインデックスlに対して定義される。

【0071】
ステップS108では、ステップS106で得られた各命題変数dij、bijlを用いて、終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義する。ここでは、論理式間が満たすべき制約の条件をそれぞれ以下(6)~(11)のように設定することで、正しい導出を表現する論理関数を構成する。まず、各命題変数di*のうち、二つ以上が同時に真とならない制約を以下(6)式とする。

【0072】
【数17】
JP2018081505A_000021t.gif

・・・(6)

【0073】
同様に、各命題変数bij*のうち、二つ以上が同時に真とならない制約を以下(7)式のように表す。

【0074】
【数18】
JP2018081505A_000022t.gif

・・・(7)

【0075】

次に、各集合Sij(X)にインデックスが含まれる生成規則のうちいずれかが真となる制約を、以下(8)式のように表す。

【0076】
【数19】
JP2018081505A_000023t.gif

・・・(8)

【0077】
同様にSii(X)にインデックスが含まれる生成規則のうちいずれかが真となる制約を、以下(9)式のように表す。

【0078】
【数20】
JP2018081505A_000024t.gif

・・・(9)

【0079】
また、命題変数bijkに対し、r=(X→YZ)であるならば、以下(10)式の制約を設定する。

【0080】
【数21】
JP2018081505A_000025t.gif

・・・(10)

【0081】
最後に、i<k≦j<lであるような全てのbijm,bklnに対して、以下(11)式の制約を設定する。

【0082】
【数22】
JP2018081505A_000026t.gif

・・・(11)

【0083】
上記(6)~(11)式を用いると、正しい導出に対応する規則の集合が与えられたときに真を返す論理関数は、命題変数dij,bijkを引数とする関数として以下(12)のように表現できる。

【0084】
【数23】
JP2018081505A_000027t.gif

・・・(12)

【0085】
ステップS110では、ステップS108で定義された論理関数に対応する二分決定グラフを構築する。二分決定グラフの構築は、ステップS102と同様に非特許文献1に記載の既存手法を用いる。

【0086】
ステップS112では、ステップS102で構築された二分決定グラフと、ステップS110で構築された二分決定グラフとの論理積となる二分決定グラフを計算する。

【0087】
ステップS114では、ステップS112で構築された二分決定グラフを用いて、可能な導出のうち、ステップS100で受け付けた論理関数が表す制約条件を満たし、かつ、確率が最大となる導出を求める。ステップS112で計算した二分決定グラフを用いることで、導出確率を最大とする導出は二分決定グラフのサイズに比例する動的計画法で求めることができる。このとき、N引数x,...,xの論理関数f(x,...,x)が二分決定グラフで表されているとする。また、各xについて重みuが定められているとすると、二分決定グラフを用いた、非特許文献2に記載されているアルゴリズム(非特許文献2の7ページに記載されている”AlgorithmB”を参照)を用いることで、以下(13)~(15)式を解くことができる。

【0088】
【数24】
JP2018081505A_000028t.gif

・・・(13)
JP2018081505A_000029t.gif
・・・(14)
JP2018081505A_000030t.gif
・・・(15)

【0089】
本実施の形態の問題では、各命題変数xについて対応する生成規則rが定まるので、その生成規則の出現確率wの対数をとり、出現確率wの対数を命題変数xに対応する重みuとして設定することによって、上記の定式化によって確率最大かつ制約条件を満たす導出を得ることが可能となる。

【0090】
以上説明したように、本発明の実施の形態に係る構文解析装置によれば、入力された生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築し、予め与えられた生成規則の集合と、終端記号の系列とに基づいて、予め定められた開始記号から終端記号の系列を得るまでの、生成規則の列を導出とし、終端記号の系列に対して可能な導出の集合を求め、求められた可能な導出の集合に基づいて、導出において各生成規則が利用されることを、命題変数を用いて表現し、命題変数を用いて終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義し、定義された論理関数に対応する二分決定グラフを構築し、構築された二分決定グラフと、定義された論理関数に対応する二分決定グラフとの論理積となる二分決定グラフを用いて、制約条件を満たし、かつ、確率が最大となる導出を求めることにより、生成規則に関する任意の制約条件を考慮した構文解析を行うことができる。

【0091】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。

【0092】
例えば、上述した実施の形態における構文解析装置は、自然言語文に対して、構文解析を行う場合について説明したが、これに限定されるものではなく、自然言語文以外の終端記号の列を受け付けて、構文解析を行うようにしてもよい。例えば、RNAなどの二次構造予測など、何らかの構造に対して、構文解析を行うようにしてもよい。
【符号の説明】
【0093】
10 文入力部
12 論理制約入力部
14 生成規則入力部
20 演算部
28 生成規則記憶部
30 BDD構築部
32 構文解析部
50 出力部
100 構文解析装置
図面
【図1】
0
【図2】
1
【図3】
2