(57)【要約】【課題】ＧＰＵ（グラフィカルプロセッシングユニット）が自然言語処理に有効活用されていないこと。【解決手段】入力単語系列を解析して形態素系列を生成する形態素解析部と、形態素系列を解析して、係り元の文節と係り先の文節との組み合わせから構成される係り受け候補のリストを生成する係り受け候補生成部と、図形どうしの交差の有無を判定する機能を有するＧＰＵと、文節毎に円周上のそれぞれ異なる空間位置を割り当て、係り元の文節に割り当てられた空間位置と係り先の文節に割り当てられた空間位置とを接続する図形データをＧＰＵに出力し、ＧＰＵから出力される図形データどうしの交差判定結果に基づいて、係り受け候補どうしの交差の有無を表す交差情報を生成する交差情報生成部と、交差情報と係り受け候補のリストとから、非交差条件を満たす入力単語系列全体の係り受け構造を決定する係り受け構造決定部とを有する。【選択図】図１
2013171381.tif 000002
【特許請求の範囲】
【請求項１】
入力単語系列を解析して形態素系列を生成する形態素解析部と、
前記形態素系列を解析して、係り元の文節と係り先の文節との組み合わせから構成される係り受け候補のリストを生成する係り受け候補生成部と、
図形どうしの交差の有無を判定する機能を有するＧＰＵ（グラフィカルプロセッシングユニット）と、
前記文節毎に円周上のそれぞれ異なる空間位置を割り当て、前記係り元の文節に割り当てられた前記空間位置と前記係り先の文節に割り当てられた前記空間位置とを接続する図形データを前記ＧＰＵに出力し、前記ＧＰＵから出力される前記図形データどうしの交差判定結果に基づいて、前記係り受け候補どうしの交差の有無を表す交差情報を生成する交差情報生成部と、
前記交差情報と前記係り受け候補のリストとから、非交差条件を満たす前記入力単語系列全体の係り受け構造を決定する係り受け構造決定部と
を有する自然言語解析装置。
【請求項２】
前記図形データは、線分データである
請求項１に記載の自然言語解析装置。
【請求項３】
前記入力単語系列は日本語文である
請求項１または２に記載の自然言語解析装置。
【請求項４】
形態素解析部と、係り受け候補生成部と、ＧＰＵ（グラフィカルプロセッシングユニット）と、交差情報生成部と、係り受け構造決定部とを有する自然言語解析装置が実行する自然言語解析方法であって、
前記形態素解析部が、入力単語系列を解析して形態素系列を生成し、
前記係り受け候補生成部が、前記形態素系列を解析して、係り元の文節と係り先の文節との組み合わせから構成される係り受け候補のリストを生成し、
前記交差情報生成部が、前記文節毎に円周上のそれぞれ異なる空間位置を割り当て、前記係り元の文節に割り当てられた前記空間位置と前記係り先の文節に割り当てられた前記空間位置とを接続する図形データを前記ＧＰＵに出力し、
前記ＧＰＵが、図形どうしの交差の有無を判定し、
前記交差情報生成部が、前記ＧＰＵから出力される前記図形データどうしの交差判定結果に基づいて、前記係り受け候補どうしの交差の有無を表す交差情報を生成し、
前記係り受け構造決定部が、前記交差情報と前記係り受け候補のリストとから、非交差条件を満たす前記入力単語系列全体の係り受け構造を決定する
自然言語解析方法。
【請求項５】
図形どうしの交差の有無を判定する機能を有するＧＰＵ（グラフィカルプロセッシングユニット）に接続されたコンピュータを、
入力単語系列を解析して形態素系列を生成する形態素解析部と、
前記形態素系列を解析して、係り元の文節と係り先の文節との組み合わせから構成される係り受け候補のリストを生成する係り受け候補生成部と、
前記文節毎に円周上のそれぞれ異なる空間位置を割り当て、前記係り元の文節に割り当てられた前記空間位置と前記係り先の文節に割り当てられた前記空間位置とを接続する図形データを前記ＧＰＵに出力し、前記ＧＰＵから出力される前記図形データどうしの交差判定結果に基づいて、前記係り受け候補どうしの交差の有無を表す交差情報を生成する交差情報生成部と、
前記交差情報と前記係り受け候補のリストとから、非交差条件を満たす前記入力単語系列全体の係り受け構造を決定する係り受け構造決定部と
して機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は自然言語解析装置に関し、特に文節間の係り受けを解析する技術に関する。
【背景技術】
【０００２】
近年のＩＴ産業の急速な発展に伴い、大量の文書から目的の文書を検索したり、検索した文書を要約したり、翻訳したりする自然言語解析技術の必要性がますます高まっている。自然言語の文を解説する技術の中で構文解析技術は、上述した自然言語解析技術の基盤となる要素技術の一つである。
【０００３】
構文解析の目的は、入力文の構文構造、とりわけ文節間の係り受け構造を特定することである。文節間の係り受けを解析する方法としては、各種の方法が提案ないし実用化されている。例えば特許文献１には、文節間の係り受け関係は交差しないという条件（非交差条件）と、前の文節は後ろの文節に係るという条件とを拘束条件として、入力文の係り受け構造を決定している。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００８−２４２６０７号公報
【特許文献２】特開２００４−１１８５５９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、表示機能の高度化の要求に応じてＧＰＵを搭載するコンピュータ端末が増加している。ＧＰＵは、Graphics Processing Unitの略称であり、主に３次元グラフィックスの表示に必要な計算処理を行うプロセッサのことである。例えば特許文献２では、Ｚバッファ法等による陰面消去を含む画像処理をＧＰＵが実行するようにしている。
【０００６】
ＧＰＵは、高い並列処理能力を持っていることもあって、計算の種類にもよるが、ＣＰＵに比べて高速な計算が可能である。しかしながら、ＧＰＵは画像処理に適用が限定されているのが現状であり、自然言語処理、特に構文解析に活用した事例は見当たらない。若し、ＧＰＵを自然言語処理に利用できれば、その分、ＣＰＵの負荷が軽減されると同時に自然言語処理の高速化が可能になると考えらえる。
【０００７】
本発明の目的は、上述したような課題、すなわちＧＰＵが自然言語処理に有効活用されていない、という課題を解決することにある。
【課題を解決するための手段】
【０００８】
本発明の一形態にかかる自然言語解析装置は、
入力単語系列を解析して形態素系列を生成する形態素解析部と、
前記形態素系列を解析して、係り元の文節と係り先の文節との組み合わせから構成される係り受け候補のリストを生成する係り受け候補生成部と、
図形どうしの交差の有無を判定する機能を有するＧＰＵ（グラフィカルプロセッシングユニット）と、
前記文節に対応する空間位置を語順に従って円周上に割り当て、前記係り元の文節に割り当てられた前記空間位置と前記係り先の文節に割り当てられた前記空間位置とを接続する図形データを前記ＧＰＵに出力し、前記ＧＰＵから出力される前記図形データどうしの交差判定結果に基づいて、前記係り受け候補どうしの交差の有無を表す交差情報を生成する交差情報生成部と、
前記交差情報と前記係り受け候補のリストとから、非交差条件を満たす前記入力単語系列全体の係り受け構造を決定する係り受け構造決定部と
を有する。
【発明の効果】
【０００９】
本発明は上述したような構成を有するため、自然言語処理にＧＰＵを有効に活用することが可能になる。
【図面の簡単な説明】
【００１０】
【図１】本発明の第１の実施形態にかかる自然言語解析装置のブロック図である。
【図２】本発明の第１の実施形態にかかる自然言語解析装置の処理の一例を示すフローチャートである。
【図３】本発明の第１の実施形態における自然言語解析装置の処理過程で生成される係り受け候補リストの一例を示す図である。
【図４】本発明の第１の実施形態における自然言語解析装置の構成要素である交差情報生成部が生成する図形データの説明図である。
【図５】本発明の第１の実施形態における自然言語解析装置が出力する係り受け構造の一例を示す図である。
【図６】本発明を第２の実施形態の構成を示す構成図である。
【図７】本発明を第２の実施形態における形態素解析の例を示す図である。
【図８】本発明を第２の実施形態における係り受けリストの例である。
【図９】本発明を第２の実施形態における係り受けチャート構造の例である。
【図１０】本発明を第２の実施形態における空間配置の例である。
【図１１】本発明を第２の実施形態における空間配置の例である。
【図１２】本発明を第２の実施形態における処理手順を示すフローチャートである。
【発明を実施するための形態】
【００１１】
次に本発明の実施の形態について図面を参照して詳細に説明する。
[第１の実施形態]
図１を参照すると、本発明の第１の実施形態にかかる自然言語解析装置１００は、ハードウェアとして、通信インターフェース部（以下、通信Ｉ／Ｆ部という）１０１、操作入力部１０２、画面表示部１０３、ＧＰＵ１０４、記憶部１０５、およびプロセッサ１０６を有する。
【００１２】
通信Ｉ／Ｆ部１０１は、専用のデータ通信回路からなり、通信回線を介して接続された各種装置との間でデータ通信を行う機能を有している。操作入力部１０２は、キーボードやマウスなどの操作入力装置からなり、利用者の操作を検出してプロセッサ１０６に出力する機能を有している。画面表示部１０３は、ＬＣＤやＰＤＰなどの画面表示装置からなり、プロセッサ１０６からの指示に応じて、各種のメニューや構文解析結果などの各種情報を画面表示する機能を有している。
【００１３】
ＧＰＵ１０４は、画面表示部１０３の表示に必要な計算処理を行うユニットである。画面表示部１０３に３Ｄ画像を表示する場合、ＧＰＵ１０４は、３Ｄ座標から２Ｄ座標への座標変換処理やレンダリング処理などの計算を行う。但し、本実施形態では、ＧＰＵ１０４を利用して図形データの交差判定の計算を行わせる。そのため、ＧＰＵ１０４は、通常の機能に加えて、プロセッサ１０６から与えられる複数の図形データ間の交差判定を行うようにプログラミングされている。
【００１４】
記憶部１０５は、ハードディスクやメモリなどの記憶装置からなり、プロセッサ１０６での各種処理に必要な処理情報やプログラム１０５Ｐを記憶する機能を有している。プログラム１０５Ｐは、プロセッサ１０６に読み込まれて実行されることにより各種処理部を実現するプログラムであり、通信Ｉ／Ｆ部１０１などのデータ入出力機能を介して外部装置（図示せず）やコンピュータ可読記憶媒体（図示せず）から予め読み込まれて記憶部１０５に保存される。記憶部１０５で記憶される主な処理情報として、入力単語系列１０５Ａ、形態素系列１０５Ｂ、係り受け候補リスト１０５Ｃ、交差情報１０５Ｄ、係り受け構造１０５Ｅ、および辞書１０５Ｆがある。
【００１５】
入力単語系列１０５Ａは、構文解析の対象となる文である。形態素系列１０５Ｂは、入力単語系列１０５Ａに対して形態素解析を行った結果得られるデータである。係り受け候補リスト１０５Ｃは、係り元の文節と係り先の文節との組み合わせから構成される係り受け候補のリストであり、形態素系列１０５Ｂから生成されたものである。交差情報１０５Ｄは、係り受け候補どうしの交差の有無を表す交差情報である。係り受け構造１０５Ｅは、交差情報１０５Ｄと係り受け候補リスト１０５Ｃとから求められた、非交差条件を満たす、入力単語系列１０５Ａ全体の係り受け構造を表すデータである。
【００１６】
辞書１０５Ｆは、形態素解析および構文解析に必要な辞書情報および文法的知識である。辞書情報としては、例えば、単語とその単語の品詞やカテゴリ（自律語や付属語など）との対応情報などがある。また、文法的知識としては、文節構成規則、文節間係り受け可能性検出規則、文節間係り受け制約がある。文節構成規則は、文節を構成する品詞情報とそれに由来する文節に付加する文節属性とに基づいて、文節の構成を記述した規則である。文節間係り受け可能性検出規則は、係り元の文節の文節属性と係り先の文節の文節属性との対応関係を記述した規則である。文節間係り受け制約としては、いわゆる非交差条件がある。
【００１７】
プロセッサ１０６は、ＣＰＵなどのマイクロプロセッサとその周辺回路を有し、記憶部１０５からプログラム１０５Ｐを読み込んで実行することにより、上記ハードウェアとプログラム１０５Ｐとを協働させて各種処理部を実現する機能を有している。プロセッサ１０６で実現される主な処理部として、入力部１０６Ａ、形態素解析部１０６Ｂ、係り受け候補生成部１０６Ｃ、交差情報生成部１０６Ｄ、係り受け構造決定部１０６Ｅ、および出力部１０６Ｆがある。
【００１８】
入力部１０６Ａは、通信Ｉ／Ｆ部１０１あるいは操作入力部１０２から、処理の対象となる文を入力し、入力単語系列１０５Ａとして記憶部１０５に記憶する機能を有する。
【００１９】
形態素解析部１０６Ｂは、記憶部１０５から入力単語系列１０５Ａと辞書１０５Ｆとを読み出し、辞書１０５Ｆの辞書情報に基づいて入力単語系列１０５Ａを解析し、解析結果を形態素系列１０５Ｂとして記憶部１０５に記憶する機能を有する。
【００２０】
係り受け候補生成部１０６Ｃは、記憶部１０５から形態素系列１０５Ｂと辞書１０５Ｆを読み出し、辞書１０５Ｆの文節構成規則に基づいて形態素系列１０５Ｂを文節に分割し、さらに辞書１０５Ｆの文節間係り受け可能性検出規則に基づいて、係り元の文節と係り先の文節との組み合わせから構成される係り受け候補のリスト１０５Ｃを生成し、記憶部１０５に記憶する機能を有する。
【００２１】
交差情報生成部１０６Ｄは、記憶部１０５から係り受け候補のリスト１０５Ｃを読み出し、当該リストに含まれる文節に対応する空間位置を語順に従って予め定められた円周上に割り当て、係り元の文節に割り当てられた空間位置と係り先の文節に割り当てられた空間位置とを接続する図形データをＧＰＵ１０４に出力し、交差判定を指令する機能を有する。円周の代わりに楕円の周を用いてもよい。また、交差情報生成部１０６Ｄは、ＧＰＵ１０４から出力される図形データどうしの交差判定結果に基づいて、係り受け候補どうしの交差の有無を表す交差情報を生成し、記憶装置１０５に記憶する機能を有する。
【００２２】
係り受け構造決定部１０６Ｅは、記憶部１０５から交差情報１０５Ｄと係り受け候補リスト１０５Ｃと辞書１０５Ｆとを読み出し、交差情報１０５Ｄと係り受け候補リスト１０５Ｃとから、辞書１０５Ｆの文節間係り受け制約を満たす、入力単語系列１０５Ａ全体の係り受け構造１０５Ｅを決定し、記憶部１０５に記憶する機能を有する。
【００２３】
出力部１０６Ｆは、記憶部１０５から係り受け構造１０５Ｅを読み出し、通信Ｉ／Ｆ部１０１から外部へ出力し、あるいは画面表示部１０３に表示する機能を有する。
【００２４】
次に本実施形態の動作を説明する。
【００２５】
まず、入力部１０６Ａは、通信Ｉ／Ｆ部１０１あるいは操作入力部１０２から、処理の対象となる文を入力し、入力単語系列１０５Ａとして記憶部１０５に記憶する（図２のＳ１）。
【００２６】
次に、形態素解析部１０６Ｂは、辞書情報に基づいて入力単語系列１０５Ａを解析し、その解析結果である形態素系列１０５Ｂを生成する（Ｓ２）。
【００２７】
次に、係り受け候補生成部１０６Ｃは、文節構成規則に基づいて形態素系列１０５Ｂを文節に分割し、さらに文節間係り受け可能性検出規則に基づいて、係り元の文節と係り先の文節との組み合わせから構成される係り受け候補のリスト１０５Ｃを生成する（Ｓ３）。
【００２８】
次に、交差情報生成部１０６Ｄは、交差情報を生成する（Ｓ４）。即ち、以下の処理を行う。まず、係り受け候補のリスト１０５Ｃに含まれる各文節に対して、円周上のそれぞれ異なる空間位置を割り当てる。その際、語順と同じ順に、文節に対応する空間位置が円周上に並ぶようにする。次に、係り元の文節に割り当てた空間位置と係り先の文節に割り当てた空間位置とを接続する図形データをＧＰＵ１０４に出力し、交差判定を指令する。ＧＰＵ１０４は、プロセッサ１０６から与えられた図形データ間の交差の有無を計算し、その結果をプロセッサ１０６に返却する。交差情報生成部１０６Ｄは、ＧＰＵ１０４から出力される図形データどうしの交差判定結果を受け取り、それに基づいて係り受け候補どうしの交差の有無を表す交差情報１０５Ｄを生成する。
【００２９】
次に、係り受け構造決定部１０６Ｅは、交差情報１０５Ｄと係り受け候補リスト１０５Ｃとに基づいて、文節間係り受け制約を満たす、入力単語系列１０５Ａ全体の係り受け構造１０５Ｅを決定する（Ｓ５）。
【００３０】
最後に出力部１０６Ｆは、係り受け構造１０５Ｅを通信Ｉ／Ｆ部１０１から外部へ出力し、あるいは画面表示部１０３に表示する（Ｓ６）。
【００３１】
次に、日本語文「美しい黒い髪の少女」という入力単語系列１０５Ａを例に挙げて、本実施形態の動作をより詳細に説明する。
【００３２】
形態素解析部１０６Ｂでは、上記入力単語系列１０５Ａを解析し、「美しい」（形容詞）、「黒い」（形容詞）、「髪」（名詞）、「の」（格助詞）、「少女」（名詞）という、品詞情報を付加した形態素系列１０５Ｂを生成する。
【００３３】
係り受け候補生成部１０６Ｃでは、上記形態素系列を解析し、「美しい」（形容詞句）、「黒い」（形容詞句）、「髪の」（体言句）、「少女」（名詞句）という、文節属性を付加した文節系列を生成する。続いて係り受け候補生成部１０６Ｃでは、形容詞句は体言句の係り元になる、体言句は形容詞句の係り先になる、前の文節は後ろの文節に係る、といった文節間係り受け可能性検出規則に基づいて、図３に示すような係り受け候補のリストを生成する。
【００３４】
次に、交差情報生成部１０６Ｄは、例えば図４に示すように、ＸＹ平面上に設定した円周Ｃを文節の総数である４で分割した各分割点を空間位置Ｋ１〜Ｋ４とし、語順に従って文節に対して空間位置を割り当てる。図４に示す例では、「美しい」にＫ１を、「黒い」にＫ２を、「髪の」にＫ３を、「少女」にＫ４を、それぞれ割り当てている。
【００３５】
次に交差情報生成部１０６Ｄは、係り元の文節に割り当てられた空間位置と係り先の文節に割り当てられた空間位置とを接続する図形データを生成する。図４に示す例では、図形の種類として線分を使用し、図３に示す文節間の係り受け関係に従って、Ｋ１とＫ３とを接続する線分Ｌ１３、Ｋ１とＫ４を接続する線分Ｌ１４、Ｋ２とＫ３を接続する線分Ｌ２３、Ｋ２とＫ４を接続する線分Ｌ２４、Ｋ３とＫ４を接続する線分Ｌ３４の合計５本の線分のデータを生成している。線分のデータは、例えば、線分ＩＤと両端点のＸＹ座標値とから構成される。そして、交差情報生成部１０６Ｄは、上記生成した線分のデータをＧＰＵ１０４に出力し、その交差判定を指定する。
【００３６】
ＧＰＵ１０４は、プロセッサ１０６から与えられた線分どうしの交差を判定し、その判定結果をプロセッサ１０６に返却する。図４の例の場合、線分Ｌ１３と線分Ｌ２４とが交差し、これ以外の線分どうしは交差しないという判定結果が返される。
【００３７】
交差情報生成部１０６Ｄは、上記の交差判定結果に従って、線分Ｌ１３に対応する係り受け候補（係り元文節「美しい」、係り先文節「髪の」）と線分Ｌ２４に対応する係り受け候補（係り元文節「黒い」、係り先文節「少女」）とは交差し、それ以外の係り受け候補どうしは交差しないとする交差情報１０５Ｄを生成する。
【００３８】
係り受け構造決定部１０６Ｅは、係り受け候補リスト１０５Ｃに基づいて、入力単語系列１０５Ａ全体の係り受け構造１０５Ｅを決定する。その決定過程において係り受け構造決定部１０６Ｅは、交差情報１０５Ｄを参照し、既に決定した係り受け関係と交差する係り受け関係を抑止する。これによって、本例の場合、図５に示される３通りの係り受け構造が決定される。
【００３９】
このように本実施形態によれば、自然言語処理にＧＰＵ１０４を有効に活用することが可能になる。その理由は、文節に対応する空間位置を語順に従って円周上に割り当て、係り元の文節に割り当てられた空間位置と係り先の文節に割り当てられた空間位置とを接続する図形データ間の交差判定をＧＰＵ１０４によって実行し、その結果に基づいて、係り受け候補どうしの交差の有無を判断するようにしているためである。
【００４０】
本実施形態では、交差判定に使用する図形として線分を使用したが、交差の判定を行える他の種類の図形でよい。例えば直線であっても良い。また２次元の図形である必要はなく、３次元の図形とすることもできる。
【００４１】
[第２の実施形態]
本実施形態は、構文解析に関する分野に属し、特に構文解析を並列処理にて行う方式において、非交差条件を利用して高速に解析を行う装置に関するものである。
【００４２】
[本実施形態の背景技術]
従来より、全文検索、機械翻訳、テキストマイニング、特許解析などの分野において、構文を解析する装置が利用されてきた。構文を解析する手法は各種あるが、一般的に利用されるものは、以下の通りである。
(1)1型言語「文脈依存言語」を対象とするもので、形式的文法規則を利用するもの
(2)2型言語「文脈依存言語」を対象とするもので、構文解析に意味制約を組み合わせたものなど。
(3)3型言語「文脈自由言語」を対象とするもので、従来の自然言語を処理する装置の多くが属するものであり、よく利用される解析手法としては、(A)チャート(chart)法,(B)アーリー(Earley)法,(c)一般化LR(GLR)法などがある。
【００４３】
本実施形態においては、（Ａ）のチャート法を改良し、画像処理の陰面処理を利用可能な形式に変換することにより、高速に構文解析を実施する装置を実現した。
【００４４】
[本実施形態が解決しようとする課題]
第１の問題点は、従来の方式では、並列化が困難であった点である。
第２の問題点は、従来の方式では、計算量を抑えるため、セグメントの分割を行うため精度上の問題があった点である。
【００４５】
［本実施形態の目的］
本実施形態の目的は、利用者に対し、「構文解析の高速化を行う機能」と「構文解析の精度向上を行う機能」と、これらの機能を有する「構文解析装置」を提供することである。
【００４６】
[本実施形態の課題を解決するための手段]
本実施形態の訳語選択装置は、図６に示されるような構成をとり、文書入力装置１と、形態素解析装置２と、辞書３と、チャート構造作成装置４と、空間配置装置５と、構文解析管理装置６と、陰面計算装置７と、フィルタ８と、解析結果出力装置９とを備えている装置である。
【００４７】
文書入力装置１は、構文解析の対象となる文を入力するための装置である。
【００４８】
形態素解析装置２は、「文書入力装置」に入力された文をかかり受けの単位（形態素）に分解するための装置である。かかり受けの単位を作成するためには、一般に辞書に記載されたデータが利用される。日本語の場合、通常、文節が形態素の単位となる。本装置により、形態素に分解された文を図７に示す。
【００４９】
辞書３は、単語のつづり、語形変化の情報、品詞情報、左右間の接続情報などを記載したデータベースである。本実施形態の場合、形態素解析装置２で利用される他にチャート構造を作成する際の統語情報を作成するためにも利用される。ただし、必要な情報は、形態素解析装置が動作するときに辞書から取得するため、構成図上では、チャート構造作成装置４と直接つながる形態にはなっていない。
【００５０】
チャート構造作成装置４は、構文解析チャートを作成する装置である。構文解析チャートとは、構文的な係り受け構造の可能性を連結グラフで表現したものである。図８にチャートの例を示す。またこのチャート上でのノードが形態素に対応する。
【００５１】
空間配置装置５は、連結グラフであるチャートを空間上に配置するための装置である。まず円周上に、形態素が語順に従って配置される。次に、有向グラフの組み合わせを連結したものを生成する。
【００５２】
構文解析管理装置６は、空間配置装置によって配置されたデータを陰面計算装置に送出したり、その結果を受けとったりするための管理装置である。
【００５３】
陰面計算装置７は、特定の視点から３次元の空間上の物体を見た場合に、隠蔽される面を計算するための装置である。陰面を計算する手法として、著名なものにa)ペインタアルゴリズム、b)法線ベクトル法、c)Ｚバッファ法などがあるが、本実施形態においては、その手法は特定しない。一般にチャートの計算を空間に配置し、陰面計算を行う場合、計算量が大幅に増加する。しかしながら、Graphics Processing Unit（ＧＰＵ）の発達により、物体の回転、陰面消去などの画像処理は、ハード的にパラレル処理されることが多く、高速に解を得ることが可能になっている。また、言語的には、非交差条件と言われる拘束条件が知られている。この条件は、かかり受けのリンク同士は交差しないとの条件である。この拘束条件は、陰面処理では、交差する面が存在する（陰面できない部分）として検出される。この装置では、有向グラフを各ノードで１つ固定し、ノード方向に視点を回転させ、交差する面があるものを取り除く。視点を回転させて得られる結果は、フィルタ装置に送出される。
【００５４】
また、視点は、複数あってよく、各ノードごとに視点を割り振り、同時に回転を行ってもよい。
【００５５】
さらに、空間上に配置される物体は、視点の数だけ（ノードの数だけ）配置し、それぞれの物体に対し、視点を付与し、陰面処理を行ってもよい。
【００５６】
フィルタ８は、陰面計算装置７の計算結果からリンク先が無くなったものを除去するものである。
【００５７】
解析結果出力装置９は、解析の結果を他の装置に出力するための装置である。
【００５８】
[本実施形態の構成]
図６を参照すると、本実施形態は、図６に示されるような構成をとり、文書入力装置１と、形態素解析装置２と、辞書３と、チャート構造作成装置４と、空間配置装置５と、構文解析管理装置６と、陰面計算装置７と、フィルタ８8と、解析結果出力装置９とを備えている装置である。
【００５９】
文書入力装置１は、構文解析の対象となる文を入力するための装置である。
【００６０】
形態素解析装置２は、文書入力装置に入力された文をかかり受けの単位（形態素）に分解するための装置である。かかり受けの単位を作成するためには、一般に辞書に記載されたデータが利用される。日本語の場合、通常、文節が形態素の単位となる。本装置により、形態素に分解された文を図７に示す。
【００６１】
辞書３は、単語のつづり、語形変化の情報、品詞情報、左右間の接続情報などを記載したデータベースである。本実施形態の場合、形態素解析装置２で利用される他にチャート構造を作成する際の統語情報を作成するためにも利用される。ただし、必要な情報は、形態素解析装置が動作するときに辞書から取得するため、構成図上では、チャート構造作成装置４と直接つながる形態にはなっていない。
【００６２】
チャート構造作成装置４は、構文解析チャートを作成する装置である。構文解析チャートとは、構文的な係り受け構造の可能性を連結グラフで表現したものである。図８にチャートの例を示す。またこのチャート上でのノードが形態素に対応する。
【００６３】
空間配置装置５は、連結グラフであるチャートを空間上に配置するための装置である。まず円周上に、形態素が語順に従って配置される。次に、有向グラフの組み合わせを最短に連結したものを成する。
【００６４】
構文解析管理装置６は、空間配置装置によって配置されたデータを陰面計算装置に送出したり、その結果を受けとったりするための管理装置である。
【００６５】
陰面計算装置７は、特定の視点から３次元の空間上の物体を見た場合に、隠蔽される面を計算するための装置である。陰面を計算する手法として、著名なものにa)ペインタアルゴリズム、b)法線ベクトル法、c)Ｚバッファ法などがあるが、本実施形態においては、その手法は特定しない。一般にチャートの計算を空間に配置し、陰面計算を行う場合、計算量が大幅に増加する。しかしながら、Graphics Processing Unit（ＧＰＵ）の発達により、物体の回転、陰面消去などの画像処理は、ハード的にパラレル処理されることが多く、高速に解を得ることが可能になっている。また、言語的には、非交差条件と言われる拘束条件が知られている。この条件は、かかり受けのリンク同士は交差しないとの条件である。この拘束条件は、陰面処理では、交差する面が存在する（陰面できない部分）として検出される。
【００６６】
この装置では、有向グラフを各ノードで１つ固定し、ノード方向に視点を回転させ、交差する面があるものを取り除く。視点を回転させて得られる結果は、フィルタ装置に送出される。
【００６７】
ここで、有向グラフを各ノードで一つ固定しとは、文章のかかりうけ状態計算するための視点を特定するために、ノードをひとつ取り出すことを意味する。すなわち、視点の状態により、空間上のノードの配置状態は変わる。前面に壁があり、後方にオブジェクトがある場合、そのオブジェクトは、見えなくなる。逆に視点から見て、オブジェクトの後ろ側に壁がある場合、その壁により、オブジェクトが見えなくなることはない。
【００６８】
また、ノード方向に視点を回転させる理由は、視点して特定したノードから視点を回転させると、他のノードの相対的な位置により、ノードがノード間のリンクの前方にあるか後方にあるか計算できるためである。
【００６９】
また、視点は、複数あってよく、各ノードごとに視点を割り振り、同時に回転を行ってもよい。さらに、空間上に配置される物体は、視点の数だけ（ノードの数だけ）配置し、それぞれの物体に対し、視点を付与し、陰面処理を行ってもよい。すなわち、陰面の計算のために、上記した処理（有向グラフを各ノードで１つ固定し、ノード方向に視点を回転させ、交差する面があるものを取り除く処理）を行うわけであるが、複数のノードを固定し、それぞれの視点の計算を同時にすることを意味する。例えば、ABCDの４つのノードが存在する場合、Aから見て見えるノードがCと計算する場合、同時にBやCでも計算し、そこから見えるノードがBやAであると計算することを意味する。
【００７０】
フィルタ８は、陰面計算装置７の計算結果からリンク先が無くなったものを除去するものである。すなわち、文章の解析上、係り先がなくなった場合は文章の解析は失敗である。上記のように非交差条件により（陰面と処理される結果）リンクが失われる場合は解析が失敗したと判断して、それ以上の処理は行わない。
【００７１】
解析結果出力装置９は、解析の結果を他の装置に出力するための装置である。
【００７２】
次に、図６及び図１２のフローチャートを参照して本実施形態の動作について説明する。
【００７３】
[ステップ１]  文書入力装置から文章が入力される。
[ステップ２]  形態素解析を行う。
[ステップ３]  文法情報からかかり受け構造を作りだす。
[ステップ４]  ノードをひとつ取り出す。
[ステップ５]  ノードの係り先候補をひとつ取り出し、空間に配置する。
[ステップ６]  係り先候補はまだあるか？。あればステップ５へ、無ければステップ７へ。
[ステップ７]  未調査のノードはあるか？
あればステップ４へ、無ければステップ８へ
[ステップ８]  空間に配置された複数のチャート構造それぞれに対し、陰面処理を実施。
[ステップ９]  リンクがすべて失われたノードを持つものを削除。
[ステップ１０]  残ったチャート構造を出力。
[ステップ１２]終了。
【００７４】
ステップ８で言う、空間に配置された複数のチャート構造は、「美しい黒い髪の少女」という文の場合、以下のようになる。
美しい  →  黒い
美しい  →  髪
美しい  →  少女
黒い    →  髪
黒い  →  少女
髪の  →  少女
【００７５】
ステップ９で言う、リンクがすべて失われたノードを持つものを削除は、「美しい黒い髪の少女」という文の場合、以下のようになる。
(1)美しい  →  髪
(2)黒い  →  少女
すなわち、(1)の場合、(2)の係り（解析）は存在しなくなる。
【００７６】
このように本実施形態は、図１０に示されるように円周上に形態素を語順に従って配置し、係り受け関係にある形態素間を矢印で結ぶと、係り受け関係が互いに交差している箇所では矢印が交差することになるため、陰面処理で交差する面を検出すれば、互いに交差している係り受け関係を見つけることができる。そして、陰面処理で交差する面を検出することはハード的にパラレル処理できるので、結果的に高速に解を求めることができる。
【００７７】
また、ノード間の係りを１つ決定すると、非交差条件により、係り先候補が減少する。さらに、ノード間の係りを１つ決定すると、さらに係り先候補が減少する。一般には、これを繰り返すことにより、解析木を作り上げるのであるが、ノード間の係りを１つ決定するという部分を並列化することを、本実施形態は陰面処理装置を利用して行っている。
【００７８】
本システムの実装上の形態として、各構成要素１〜９を実現する手段として、電子回路やコンピュータなどが想定される。これら１〜９のモジュールを別々の部品としても、全部を１つの装置として作成することも可能である。また、１〜９のモジュールは、PCなどに代表されるひとつの装置内部に格納することも可能である。また、それぞれをソフトウエアと、コンピュータという構成で実施することも可能である。また、それぞれの機能をネットワークを介した形での構成も可能である。また、それぞれの機能あるいは装置全体を  複数台用意し、性能を向上する構成をとることも可能である。さらに、本装置を他の装置に組み合わせたり、ソフトウエアの形で実施する場合は、他のソフトウエアから呼ばれる形での構成も可能である。
【００７９】
[本実施形態の効果]
第一の効果は、「構文解析の高速化を行う機能」を実現できることである。その理由は、構文解析のためのチャート構造を画像処理の陰面処理を利用可能な形式に変換することが可能になったためである。
【００８０】
第二の効果は、「構文解析の精度向上を行う機能」を実現できることである。その理由は、計算量を縮小させるためにセグメントで分割する必要がなくなるためである。
【００８１】
[本実施形態の産業上の利用可能性]
本実施形態は、（１）「構文解析の高速化を行う機能」、（２）「構文解析の精度向上を行う機能」を有することを特徴に持つ「構文解析装置」である。構文解析に関しては、機械翻訳装置への利用が第一義として想定されるが、検索装置でのランキング機構、テキストマイニングにおける計算時間の圧縮などへの利用も想定される。
【符号の説明】
【００８２】
１--文書入力装置
２--形態素解析装置
３--辞書
４--チャート構造作成装置
５--空間配置装置
６--構文解析管理装置
７--陰面計算装置
８--フィルタ
９--解析結果出力装置
【図１】
2013171381.tif 000003
【図２】
2013171381.tif 000004
【図３】
2013171381.tif 000005
【図４】
2013171381.tif 000006
【図５】
2013171381.tif 000007
【図６】
2013171381.tif 000008
【図７】
2013171381.tif 000009
【図８】
2013171381.tif 000010
【図９】
2013171381.tif 000011
【図１０】
2013171381.tif 000012
【図１１】
2013171381.tif 000013
【図１２】
2013171381.tif 000014