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

構文解析装置、方法、及びプログラム NEW

国内特許コード P180015650
整理番号 5470
掲載日 2018年11月22日
出願番号 特願2016-223547
公開番号 特開2018-081505
出願日 平成28年11月16日(2016.11.16)
公開日 平成30年5月24日(2018.5.24)
発明者
  • 西野 正彬
  • 山本 章博
出願人
  • 日本電信電話株式会社
  • 国立大学法人京都大学
発明の名称 構文解析装置、方法、及びプログラム NEW
発明の概要 【課題】生成規則に関する任意の制約条件を考慮した構文解析を行うことができる。
【解決手段】BDD構築部30が、入力された生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築する。構文解析部32が、予め与えられた生成規則の集合と、終端記号の系列とに基づいて、可能な導出の集合を求め、求められた可能な導出の集合に基づいて、導出において各生成規則が利用されることを、命題変数を用いて表現し、命題変数を用いて終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義し、定義された論理関数に対応する二分決定グラフを構築し、構築された二分決定グラフと、定義された論理関数に対応する二分決定グラフとの論理積となる二分決定グラフを用いて、制約条件を満たし、かつ、確率が最大となる導出を求める。
【選択図】図2
従来技術、競合技術の概要


確率文脈自由文法は自然言語文の構文解析に用いられる基礎的な技術である。確率文脈自由文法Gは、G=(M,T,R,S,P)からなる5つ組として定義される。ここでMは非終端記号の集合、Tは終端記号の集合、Rは生成規則の集合、Sは開始記号、Pは生成規則に付与された確率値の集合である。確率文脈自由文法がチョムスキー標準形であるとすれば、生成規則は以下(1)~(3)式のいずれかである。



【数1】



・・・(1)



・・・(2)



・・・(3)



ここでA、B、及びCは非終端記号、αは終端記号、Sは開始記号、εは空列を表すものとする。



各規則は、規則の左辺(以下では頭部とよぶ)の非終端記号Aを右辺の記号列に書き換えることを表している。ある規則A→BCを適用するとは、非終端記号Aを含む系列において、Aを非終端記号の列BCに書き換えることを表す。



各規則に対してはその規則が適用される確率が付与されている。与えられた確率文脈自由文法において、規則の頭部が非終端記号Aであるような規則の集合をr,...,rとすると、各規則rには出現確率wが与えられる。ここで確率w



【数2】





を満たす。各確率は、非終端記号Aが与えられたときに確率wで生成規則rを適用することを表している。



ある確率文脈自由文法Gが与えられると、それを用いた構文解析が可能となる。すなわち、与えられた終端記号の列α,α,...,αに対して、開始記号Sから当該終端記号の列を導出するための生成規則の適用による非終端記号の書き換えの列を得ることができる。ある構文解析は、開始記号に対して適用した生成規則の列として表現することができる。この列を導出ともよぶ。また、生成規則の列に含まれる各規則に付与された確率の積として、その解析が得られる確率が定義される。



確率文脈自由文法を用いることで自然言語文のように曖昧さのある対象に対する構文解析を行うことができるため、自然言語文の解析や、RNA(リボ核酸)の二次構造予測などに用いられてきた。また、確率文脈自由文法が与えられたときに、ある系列に対する構文解析のうち、確率が最大となるものを発見する問題は、系列の長さをNとするとO(N)の動的計画法を用いることで解くことができる。

産業上の利用分野


本発明は、構文解析装置、方法、及びプログラムに係り、特に、終端記号の系列に対して、構文解析を行うための構文解析装置、方法、及びプログラムに関する。

特許請求の範囲 【請求項1】
終端記号の系列に対して、確率文脈自由文法に基づいた構文解析を行う構文解析装置であって、
入力された、確率文脈自由文法における非終端記号を書き換えるための生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築するBDD構築部と、
予め与えられた生成規則の集合と、前記終端記号の系列とに基づいて、予め定められた開始記号から前記終端記号の系列を得るまでの、前記生成規則の列を導出とし、前記終端記号の系列に対して可能な導出の集合を求め、
前記求められた前記可能な導出の集合に基づいて、前記導出において各生成規則が利用されることを、命題変数を用いて表現し、
前記命題変数を用いて前記終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義し、
前記定義された論理関数に対応する二分決定グラフを構築し、
前記BDD構築部によって構築された前記二分決定グラフと、前記定義された論理関数に対応する前記二分決定グラフとの論理積となる前記二分決定グラフを用いて、前記制約条件を満たし、かつ、確率が最大となる導出を求める構文解析部と、
を含む構文解析装置。

【請求項2】
前記構文解析部は、前記終端記号の系列に含まれる前記終端記号の各々について、非終端記号を前記終端記号に書き換える生成規則が、前記導出において利用されることを表す命題変数と、前記終端記号の系列に含まれる部分系列の各々について、前記部分系列に対応して前記生成規則が、前記導出において利用されることを表す命題変数とを用いて、前記論理関数を定義する請求項1に記載の構文解析装置。

【請求項3】
終端記号の系列に対して、確率文脈自由文法に基づいた構文解析を行う構文解析装置における構文解析方法であって、
BDD構築部が、入力された、確率文脈自由文法における非終端記号を書き換えるための生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築するステップと、
構文解析部が、予め与えられた生成規則の集合と、前記終端記号の系列とに基づいて、予め定められた開始記号から前記終端記号の系列を得るまでの、前記生成規則の列を導出とし、前記終端記号の系列に対して可能な導出の集合を求めるステップと、
前記構文解析部が、前記求められた前記可能な導出の集合に基づいて、前記導出において各生成規則が利用されることを、命題変数を用いて表現するステップと、
前記構文解析部が、前記命題変数を用いて前記終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義するステップと、
前記構文解析部が、前記定義された論理関数に対応する二分決定グラフを構築するステップと、
前記構文解析部が、前記BDD構築部によって構築された前記二分決定グラフと、前記定義された論理関数に対応する前記二分決定グラフとの論理積となる前記二分決定グラフを用いて、前記制約条件を満たし、かつ、確率が最大となる導出を求めるステップと、
を含む構文解析方法。

【請求項4】
前記構文解析部が定義するステップは、前記終端記号の系列に含まれる前記終端記号の各々について、非終端記号を前記終端記号に書き換える生成規則が、前記導出において利用されることを表す命題変数と、前記終端記号の系列に含まれる部分系列の各々について、前記部分系列に対応して前記生成規則が、前記導出において利用されることを表す命題変数とを用いて、前記論理関数を定義する請求項3に記載の構文解析方法。

【請求項5】
コンピュータを、請求項1又は請求項2に記載の構文解析装置の各部として機能させるためのプログラム。
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2016223547thum.jpg
出願権利状態 公開
ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記までご連絡ください。


PAGE TOP

close
close
close
close
close
close
close