グラフ統合装置及びそのプログラム
【課題】本発明は、複数の統合グラフを扱うことができ、演算量が少なく、簡易な構成のグラフ統合装置を提供することを目的とする。
【解決手段】グラフ統合装置１は、入力要素を示すノードとノード間において分岐及び合流が可能な示すエッジとで構成された入力グラフＧが複数入力され、入力グラフＧを統合するものであって、グラフ入力手段１１と、入力グラフ記憶手段１２と、ＤＰマッチング法によって、入力グラフＧの類似度を算出する類似度算出手段１３と、類似度に基づいて、入力グラフＧが類似するか否かを判定する類似判定手段１４と、入力グラフＧが類似する場合、入力グラフＧを統合するグラフ統合手段１５と、入力グラフＧが類似しない場合、入力グラフＧを新たな統合グラフとして追加するグラフ追加手段１６と、統合グラフ記憶手段１７と、を備える。
【解決手段】グラフ統合装置１は、入力要素を示すノードとノード間において分岐及び合流が可能な示すエッジとで構成された入力グラフＧが複数入力され、入力グラフＧを統合するものであって、グラフ入力手段１１と、入力グラフ記憶手段１２と、ＤＰマッチング法によって、入力グラフＧの類似度を算出する類似度算出手段１３と、類似度に基づいて、入力グラフＧが類似するか否かを判定する類似判定手段１４と、入力グラフＧが類似する場合、入力グラフＧを統合するグラフ統合手段１５と、入力グラフＧが類似しない場合、入力グラフＧを新たな統合グラフとして追加するグラフ追加手段１６と、統合グラフ記憶手段１７と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力要素を示すノードと、ノード間の接続、ノード間の分岐又はノード間の合流を示すエッジとで構成された入力グラフを統合するグラフ統合装置及びそのプログラムに関する。
【背景技術】
【０００２】
従来から、例えば、音声認識の際、音声信号を音素、単語等の認識候補のグラフとしたときに、このグラフを複数の言語モデルに基づいて認識することで、音声認識の精度を向上させることが行われている。
【０００３】
ここで、複数の言語モデルからより適切な認識結果を生成するために、このグラフを統合することが行われている（特許文献１参照）。例えば、特許文献１に記載の発明は、このグラフから不要な経路を減らして、このグラフを統合するものである。
【特許文献１】特開２００３−１５６８５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、特許文献１に記載の発明は、３個以上のグラフを統合する場合、これらグラフを組み合わせた回数、グラフを比較する必要があり、演算量が多くなってしまう。例えば、特許文献１に記載の発明では、ｎ個のグラフを統合するために、ｎ×（ｎ−１）／２回、グラフを比較する必要があり、利便性に欠ける。また、従来技術では、複数のグラフを１個のグラフに統合するのみで、２以上のグラフに統合することができなかった。
【０００５】
そこで、本発明は、複数の統合グラフを扱うことができ、演算量が少なく、簡易な構成のグラフ統合装置及びそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
前記した課題を解決するため、請求項１に係るグラフ統合装置は、入力要素を示すノードとノードにおいて分岐及び合流が可能なエッジとで構成された入力グラフが複数入力され、これら入力グラフを統合するグラフ統合装置において、類似度算出手段と、類似判定手段と、グラフ統合手段と、グラフ追加手段と、を備える構成とした。
【０００７】
かかる構成において、グラフ統合装置は、類似度算出手段によって、ＤＰマッチング法を用いて、入力された複数の入力グラフのノードの一致と挿入誤りと欠落誤りと代替誤りとをＤＰマッチングの結果として求める。そして、グラフ統合装置は、類似度算出手段によって、このＤＰマッチングの結果を予め設定された関数に代入して入力グラフ同士の類似度を算出し、求めたＤＰマッチングの結果と、算出した入力グラフ同士の類似度を出力する。
【０００８】
また、グラフ統合装置は、類似判定手段によって、類似度算出手段から入力された入力グラフ同士の類似度が予め設定された閾値以上の場合、入力グラフ同士が類似すると判定する。さらに、グラフ統合装置は、類似判定手段によって、類似度算出手段から入力された入力グラフ同士の類似度が閾値未満の場合、入力グラフ同士が類似しないと判定し、この類似判定結果を出力する。これによって、グラフ統合装置は、類似性の低い入力グラフ同士を統合してしまう事態を低減できる。
【０００９】
類似判定手段から入力された類似判定結果において、入力グラフ同士が類似する場合、グラフ統合装置は、グラフ統合手段によって、類似度算出手段から入力されたＤＰマッチングの結果に基づいて、入力グラフ同士を統合グラフに統合する。また、類似判定手段から入力された類似判定結果において、入力グラフ同士が類似しない場合、グラフ統合装置は、グラフ追加手段によって、入力グラフのそれぞれを新たな統合グラフとして追加する。
【００１０】
次に、グラフ統合装置は、類似度算出手段によって、ＤＰマッチング法を用いて、入力グラフと、グラフ統合手段が統合した統合グラフ又はグラフ追加手段が追加した統合グラフとのノードの一致と挿入誤りと欠落誤りと代替誤りとをＤＰマッチングの結果として求める。そして、グラフ統合装置は、このＤＰマッチングの結果を関数に代入して入力グラフと統合グラフとの類似度を算出し、求めたＤＰマッチングの結果と、算出した入力グラフと統合グラフとの類似度を出力する。
【００１１】
また、グラフ統合装置は、類似判定手段によって、類似度算出手段から入力された入力グラフと統合グラフとの類似度が閾値以上の場合、入力グラフと統合グラフとが類似すると判定する。さらに、グラフ統合装置は、類似判定手段によって、類似度算出手段から入力された類似度が閾値未満の場合、入力グラフと統合グラフとが類似しないと判定し、この類似判定結果を出力する。これによって、グラフ統合装置は、類似性の低い入力グラフと統合グラフとを統合してしまう事態を低減できる。
【００１２】
類似判定手段から入力された類似判定結果において、入力グラフと統合グラフとが類似する場合、グラフ統合装置は、グラフ統合手段によって、類似度算出手段から入力されたＤＰマッチングの結果に基づいて、入力グラフと統合グラフとを統合する。
【００１３】
類似判定手段から入力された類似判定結果において、入力グラフと統合グラフとが類似しない場合、グラフ統合装置は、グラフ追加手段によって、入力グラフを新たな統合グラフとして追加する。これによって、グラフ統合装置は、入力グラフと統合グラフとを統合でき、入力グラフを組み合わせた回数分の類似判定を行う必要がなくなると共に、複数の統合グラフを扱うことを可能とする。
【００１４】
また、前記した課題を解決するため、請求項２に係るグラフ統合プログラムは、入力要素を示すノードとノードにおいて分岐及び合流が可能なエッジとで構成された入力グラフが複数入力され、これら入力グラフを統合するために、コンピュータを、類似度算出手段と、類似判定手段と、グラフ統合手段と、グラフ追加手段と、として機能させる構成とした。
【００１５】
かかる構成において、グラフ統合プログラムは、類似度算出手段によって、ＤＰマッチング法を用いて、入力された複数の入力グラフのノードの一致と挿入誤りと欠落誤りと代替誤りとを求める。そして、グラフ統合プログラムは、このＤＰマッチングの結果を予め設定された関数に代入して入力グラフ同士の類似度を算出し、求めたＤＰマッチングの結果と、算出した入力グラフ同士の類似度を出力する。
【００１６】
また、グラフ統合プログラムは、類似判定手段によって、類似度算出手段から入力された入力グラフ同士の類似度が予め設定された閾値以上の場合、入力グラフ同士が類似すると判定する。さらに、グラフ統合プログラムは、類似判定手段によって、類似度算出手段から入力された入力グラフ同士の類似度が閾値未満の場合、入力グラフ同士が類似しないと判定する。これによって、グラフ統合プログラムは、類似性の低い入力グラフ同士を統合してしまう事態を低減できる。
【００１７】
類似判定手段から入力された類似判定結果において、入力グラフ同士が類似する場合、グラフ統合プログラムは、グラフ統合手段によって、類似度算出手段から入力されたＤＰマッチングの結果に基づいて、入力グラフ同士を統合グラフに統合する。また、類似判定手段から入力された類似判定結果において、入力グラフ同士が類似しない場合、グラフ統合プログラムは、グラフ追加手段によって、入力グラフのそれぞれを新たな統合グラフとして追加する。
【００１８】
次に、グラフ統合プログラムは、類似度算出手段によって、ＤＰマッチング法を用いて、入力グラフと、グラフ統合手段が統合した統合グラフ又はグラフ追加手段が追加した統合グラフとのノードの一致と挿入誤りと欠落誤りと代替誤りとを求める。そして、グラフ統合プログラムは、このＤＰマッチングの結果を関数に代入して入力グラフと統合グラフとの類似度を算出し、求めたＤＰマッチングの結果と、算出した入力グラフと統合グラフとの類似度を出力する。
【００１９】
また、グラフ統合プログラムは、類似判定手段によって、類似度算出手段から入力された入力グラフと統合グラフとの類似度が閾値以上の場合、入力グラフと統合グラフとが類似すると判定する。さらに、グラフ統合プログラムは、類似判定手段によって、類似度算出手段から入力された類似度が閾値未満の場合、入力グラフと統合グラフとが類似しないと判定する。これによって、グラフ統合プログラムは、類似性の低い入力グラフと統合グラフとを統合してしまう事態を低減できる。
【００２０】
類似判定手段から入力された類似判定結果において、入力グラフと統合グラフとが類似する場合、グラフ統合プログラムは、グラフ統合手段によって、類似度算出手段から入力されたＤＰマッチングの結果に基づいて、入力グラフと統合グラフとを統合する。
【００２１】
類似判定手段から入力された類似判定結果において、入力グラフと統合グラフとが類似しない場合、グラフ統合プログラムは、グラフ追加手段によって、入力グラフを新たな統合グラフとして追加する。これによって、グラフ統合プログラムは、入力グラフと統合グラフとを統合でき、入力グラフを組み合わせた回数分の類似判定を行う必要がなくなると共に、複数の統合グラフを扱うことを可能とする。
【発明の効果】
【００２２】
本発明によれば、以下のような優れた効果を奏する。
請求項１，２に係る発明によれば、入力グラフを組み合わせた回数分の類似判定を行う必要がなくなると共に、複数の統合グラフを扱うことを可能とするため、演算量を少なくでき、グラフ統合装置を簡易な構成とすることができる。また、請求項１，２に係る発明によれば、類似性の低い入力グラフ同士及び入力グラフと統合グラフとを統合してしまう事態を低減できるため、グラフの統合がより正確になる。
【発明を実施するための最良の形態】
【００２３】
［グラフ統合装置の構成］
以下、本発明の実施形態について、適宜図面を参照しながら詳細に説明する。
図１を参照して、本発明の本実施形態に係るグラフ統合装置の構成について説明する。図１は、本発明の本実施形態に係るグラフ統合装置の構成を示すブロック図である。
【００２４】
図１のグラフ統合装置１は、入力要素を示すノードと、ノード間において分岐及び合流が可能なエッジとで構成されたエッジとで構成された入力グラフＧが複数入力され、入力グラフＧを統合するものであって、グラフ入力手段１１と、入力グラフ記憶手段１２と、類似度算出手段１３と、類似判定手段１４と、グラフ統合手段１５と、グラフ追加手段１６と、統合グラフ記憶手段１７と、を備える。なお、図１では、入力グラフを符号Ｇ、統合グラフを符号Ｔで示した。
【００２５】
グラフ入力手段１１は、図２の複数の入力グラフＧ１，Ｇ２，Ｇ３，Ｇ４（Ｇ）が入力されるものである。例えば、グラフ入力手段１１としては、入力グラフＧ１，Ｇ２，Ｇ３，Ｇ４（Ｇ）を外部から受信する通信ポート、又は、磁気ディスク等の記憶媒体に記憶された入力グラフＧを読み取る読取装置がある。以下、入力グラフＧ１，Ｇ２，Ｇ３，Ｇ４を区別しないで説明する場合、単に入力グラフＧとする。なお、入力グラフＧの詳細は、後記する。
【００２６】
入力グラフ記憶手段１２は、グラフ入力手段１１に入力された入力グラフＧを記憶する、例えば、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）等の記憶手段である。
【００２７】
類似度算出手段１３は、例えば、後記する統合グラフ記憶手段１７が統合グラフＴを記憶してなければ、ＤＰマッチング法を用いて、入力グラフ記憶手段１２が記憶する複数の入力グラフＧ同士（例えば、図２（ａ）の入力グラフＧ１と図２（ｂ）の入力グラフＧ２）におけるノードの一致と挿入誤りと欠落誤りと代替誤りとをＤＰマッチングの結果として求める。そして、類似度算出手段１３は、このＤＰマッチングの結果を予め設定された関数に代入し、入力グラフＧのそれぞれの類似度を算出するものである。
【００２８】
ここで、入力グラフ記憶手段１２は、入力グラフＧ毎に、その入力グラフＧの類似度を算出したか否かを示す算出フラグをあわせて記憶しても良い。この場合、算出フラグは、類似度を未算出（例えば、「０」）が初期値として設定される。そして、類似度算出手段１３は、類似度を算出した入力グラフＧについて、算出フラグを算出済み（例えば、「１」）に設定しても良い。
【００２９】
また、類似度算出手段１３は、例えば、統合グラフ記憶手段１７が統合グラフＴを記憶していれば、ＤＰマッチング法を用いて、入力グラフ記憶手段１２が記憶する入力グラフＧと、統合グラフ記憶手段１７が記憶する統合グラフＴとのノードの一致と挿入誤りと欠落誤りと代替誤りとをＤＰマッチングの結果として求め、このＤＰマッチングの結果を関数に代入して入力グラフＧと統合グラフＴとの類似度を算出するものである。また、類似度算出手段１３は、求めたＤＰマッチングの結果と、算出した類似度とを類似判定手段１４、及び、類似判定手段１４を介してグラフ統合手段１５に出力する。
【００３０】
ここで、後記する統合グラフ記憶手段１７は、統合グラフＴ毎に、その統合グラフＴの類似度を算出したか否かを示す統合フラグをあわせて記憶しても良い。この場合、統合フラグは、類似度を未算出（例えば、「０」）が初期値として設定される。そして、類似度算出手段１３は、類似度を算出した統合グラフＴについて、統合フラグを算出済み（例えば、「１」）に設定しても良い。
【００３１】
類似判定手段１４は、例えば、統合グラフ記憶手段１７が統合グラフＴを記憶してなければ、入力グラフＧのそれぞれの類似度が予め設定された閾値以上の場合、入力グラフ記憶手段１２が記憶する入力グラフＧのそれぞれが類似すると判定し、入力グラフＧのそれぞれの類似度が閾値未満の場合、入力グラフ記憶手段１２が記憶する入力グラフＧのそれぞれが類似しないと判定するものである。
【００３２】
また、類似判定手段１４は、例えば、統合グラフ記憶手段１７が統合グラフＴを記憶していれば、入力グラフ記憶手段１２が記憶する入力グラフＧと統合グラフ記憶手段１７が記憶する統合グラフＴとが類似するか否かを判定する。なお、類似度の算出及び類似判定の詳細は、後記する。また、類似判定手段１４は、類似するか否かの類似判定結果をグラフ統合手段１５及びグラフ追加手段１６に出力する。
【００３３】
グラフ統合手段１５は、類似判定手段１４が出力した類似判定結果において、入力グラフＧのそれぞれが類似する場合、ＤＰマッチングの結果に基づいて、入力グラフＧのそれぞれを統合グラフＴに統合するものである。また、グラフ統合手段１５は、類似判定手段１４が出力した類似判定結果において、入力グラフＧと統合グラフＴとが類似する場合、ＤＰマッチング法の結果に基づいて、入力グラフＧと統合グラフＴとを統合し、統合グラフ記憶手段１７に記憶させる。
【００３４】
グラフ追加手段１６は、類似判定手段１４が出力した類似判定結果において、入力グラフＧのそれぞれが類似しない場合、入力グラフＧのそれぞれを新たな統合グラフＴとして追加するものである。また、グラフ追加手段１６は、類似判定手段１４が出力した類似判定結果において、入力グラフＧと統合グラフＴとが類似しない場合、入力グラフＧを新たな統合グラフＴとして追加し、統合グラフ記憶手段１７に記憶させる。
【００３５】
統合グラフ記憶手段１７は、グラフ統合手段１５が統合した統合グラフＴ又はグラフ追加手段１６が追加した統合グラフＴを記憶するものである。ここで、グラフ統合装置１は、統合グラフ記憶手段１７が記憶する統合グラフＴを、外部の音声認識装置（不図示）からの要求に応じて出力しても良い。なお、図１では、説明のために、入力グラフ記憶手段１２と統合グラフ記憶手段１７とを別々に図示したが、これらを１個の記憶手段で構成しても良い（不図示）。
【００３６】
＜入力グラフの詳細＞
以下、図２，３を参照して、入力グラフの詳細について説明する（適宜図１参照）。図２は図１のグラフ入力手段に入力された入力グラフを説明する図であり、（ａ）〜（ｄ）がそれぞれ入力グラフの第１例〜第４例である。また、図３は図１のグラフ入力手段に入力された入力グラフを説明する図であり、（ａ）〜（ｃ）がそれぞれ入力グラフの第１例、第５例及び第６例である。なお、図２（ａ）と図３（ａ）に示す入力グラフは、同じものである。
【００３７】
図２では、入力グラフＧの先頭を「先頭」、及び、入力グラフＧの終了を「終了」として図示した。また、ノードは、長方形で図示し、そのノード名を長方形の内部に示した。以下、ノードを特定して説明する場合、そのノード名を記す（例えば、ノードＡ１、ノードＣ６等と記す）。さらに、エッジは、ノード間の接続、ノード間の合流及びノード間の分岐を示すものであり、ノード間を接続する矢印、及び、入力グラフＧの先頭や終了とノードとを接続する矢印で図示した。この矢印の方向がエッジの接続方向を示すことからも明らかなように、入力グラフＧは、ノードとエッジとで構成される有向グラフである。
【００３８】
図２（ａ）に示すように、入力グラフＧ１は、その先頭から終了まで、ノードＡ１、ノードＡ２、ノードＡ３、ノードＡ４、ノードＡ５及びノードＡ６が順にエッジで接続されている。また、図２（ｂ）に示すように、入力グラフＧ２は、ノードＡ１・・・ノードＡ４、ノードＢ５及びノードＡ６が順にエッジで接続されている。
【００３９】
また、図２（ｃ）に示すように、入力グラフＧ３は、ノードＡ１・・・ノードＡ４、ノードＢ５及びノードＣ６が順にエッジで接続されている。さらに、図２（ｄ）に示すように、入力グラフＧ４は、ノードＡ１、ノードＤ２、ノードＤ３、ノードＡ４、ノードＢ５及びノードＣ６が順にエッジで接続されている。
【００４０】
図３（ｂ）に示すように、入力グラフＧ５は、ノードＡ１・・・ノードＡ４及びノードＢ５が順にエッジで接続されている。また、図３（ｃ）に示すように、入力グラフＧ６は、ノードＡ１・・・ノードＢ５、ノードＡ６及びノードＡ７が順にエッジで接続されている。
【００４１】
＜類似度の算出及び類似判定の詳細：第１例＞
以下、図４を参照して、類似度の算出及び類似判定の詳細について説明する（適宜図１，図２参照）。図４は図１のグラフ統合手段が統合した統合グラフを説明する図であり、（ａ）〜（ｃ）がそれぞれ統合グラフの第１例〜第３例である。ここでは、図２に示す４個の入力グラフＧの類似度を算出して類似判定する例を説明する。
【００４２】
まず、類似度算出手段１３は、ＤＰマッチング法を用いて、図２の入力グラフＧ１，Ｇ２の類似度を算出する。具体的には、類似度算出手段１３は、入力グラフＧ１，Ｇ２のノードの一致（Ｈ）、挿入誤り（Ｉ）、欠落誤り（Ｄ）又は代替誤り（Ｓ）を結果として求め、このＤＰマッチングの結果を下記式（１）に代入して類似度を算出する。ここで、式（１）が、請求項に記載の関数に相当する。
【００４３】
類似度＝（Ｈ−Ｉ）／（Ｈ＋Ｓ＋Ｄ）・・・式（１）
【００４４】
この場合、類似度算出手段１３は、入力グラフＧ１のノードＡ５と入力グラフＧ２のノードＢ５のみが代替誤りとなり、他のノードが一致するという結果「ＨＨＨＨＳＨ」を得ることができる。そして、類似度算出手段１３は、このＤＰマッチングの結果を式（１）に代入し、類似度を５／６と算出する。なお、類似度算出手段１３は、入力グラフＧ１，Ｇ２の算出フラグを算出済みに設定しても良い。
【００４５】
類似判定手段１４は、入力グラフＧ１，Ｇ２の類似度（例えば、５／６）と、予め設定された閾値（例えば、１／２）とを比較し、この類似度が閾値以上なので入力グラフＧ１，Ｇ２が類似すると判定する。
【００４６】
入力グラフＧ１，Ｇ２が類似するので、グラフ統合手段１５は、ＤＰマッチング法の結果に基づいて、入力グラフＧ１，Ｇ２を図４（ａ）の統合グラフＴに統合する。ここで、グラフ統合手段１５は、ＤＰマッチングの結果が一致となるノードについては、統合グラフＴにおいて、そのノードをそのまま配置しても良い。また、グラフ統合手段１５は、ＤＰマッチングの結果が挿入誤りとなるノードについては、そのノードを統合グラフＴに挿入しても良い。さらに、グラフ統合手段１５は、ＤＰマッチングの結果が欠落誤りとなるノードについては、そのノードをスキップするように、そのノードに前後するノード同士を直接接続するエッジを追加しても良い。そして、グラフ統合手段１５は、ＤＰマッチングの結果が代替誤りとなるノードについては、統合グラフＴにおいて、代替え関係となるノードを並列に配置しても良い。
【００４７】
具体的には、入力グラフＧ１，Ｇ２において、ノードＡ１〜ノードＡ４及びノードＡ６が一致するので、グラフ統合手段１５は、「先頭」からノードＡ１・・・ノードＡ４を順にし、ノードＡ６を「終点」の直前とする。また、入力グラフＧ１，Ｇ２において、ノードＡ５とノードＢ５とが代替誤りとなるので、グラフ統合手段１５は、ノードＡ５とノードＢ５とを並列にする。そして、グラフ統合手段１５は、代替誤りとなるノードＡ５，Ｂ５の直前に位置するノードＡ４から、代替誤りとなるノードＡ５，Ｂ５にエッジを分岐させる。さらに、グラフ統合手段１５は、代替誤りとなるノードＡ５，Ｂ５の直後に位置するノードＡ６に、代替誤りとなるノードＡ５，Ｂ５からエッジを合流させる。
【００４８】
なお、入力グラフＧ１，Ｇ２が類似しない場合、グラフ追加手段１６は、入力グラフＧ１，２をそれぞれ、新たな統合グラフＴとして統合グラフ記憶手段１７に記憶させる。この場合、グラフ統合装置１は、複数の統合グラフＴを用いて類似判定を行うことができる。
【００４９】
次に、類似度算出手段１３は、ＤＰマッチング法を用いて、算出フラグが未算出である、図２（ｃ）の入力グラフＧ３と、図４（ａ）の統合グラフＴとの類似度を算出する。なお、類似度算出手段１３は、入力グラフＧ３の算出フラグを算出済みに設定し、統合グラフＴの統合フラグを算出済みに設定しても良い。
【００５０】
ここでは、ノードＡ１・・・ノードＡ４までのＤＰマッチングが終了している場合を例に説明する。類似度算出手段１３は、ノードＡ５とノードＢ５とが分岐するので、（１）統合グラフＴにおけるノードＡ５に対する「ＨＨＨＨＤ」、（２）統合グラフＴにおけるノードＡ５に対する「ＨＨＨＨＳ」、（３）統合グラフＴにおけるノードＢ５に対する「ＨＨＨＨＤ」、（４）統合グラフＴにおけるノードＢ５に対する「ＨＨＨＨＨ」、及び、（５）入力グラフＧ３におけるノードＢ５に対する「ＨＨＨＨＩ」という５個の仮説を生成する。
【００５１】
また、類似度算出手段１３は、ノードＡ６で合流するので、（１）統合グラフＴにおけるノードＡ５の欠落誤り、（２）統合グラフＴにおけるノードＡ５の代替誤り、（３）統合グラフＴにおけるノードＢ５の欠落誤り、（４）統合グラフＴにおけるノードＢ５の一致、及び、（５）入力グラフＧ３におけるノードＢ５の挿入誤りという、前記した仮説をマージする。
【００５２】
ここでは、類似度算出手段１３は、上記（４）の仮説が最小となるので、ノードＢ５が一致という結果を用いて、類似度を算出する。従って、類似度算出手段１３は、統合グラフＴのノードＡ６と入力グラフＧ３のノードＣ６のみが代替誤りとなり、他のノードが一致するという結果「ＨＨＨＨＨ（Ｂ５）Ｓ」を用いて、類似度を５／６と算出する。
【００５３】
類似判定手段１４は、統合グラフＴと入力グラフＧ３との類似度（例えば、５／６）と、閾値（例えば、１／２）とを比較し、この類似度が閾値以上なので統合グラフＴと入力グラフＧ３とが類似すると判定する。
【００５４】
統合グラフＴと入力グラフＧ３とが類似するので、グラフ統合手段１５は、ＤＰマッチングの結果に基づいて、統合グラフＴと入力グラフＧ３とを図４（ｂ）の統合グラフＴ´（Ｔ）に統合する。ここで、統合グラフＴと入力グラフＧ３において、ノードＡ１〜ノードＡ５，Ｂ５が一致するので、グラフ統合手段１５は、統合グラフＴのノードＡ１〜ノードＡ５，Ｂ５をそのままの順とする。
【００５５】
具体的には、統合グラフＴと入力グラフＧ３において、ノードＡ６とノードＣ６が代替誤りとなるため、グラフ統合手段１５は、ノードＡ６とノードＣ６とを並列に追加する。そして、グラフ統合手段１５は、ノードＡ５とノードＡ６とを接続し、ノードＢ５からノードＡ６，Ｃ６にエッジを分岐させる。
【００５６】
最後に、類似度算出手段１３は、ＤＰマッチング法を用いて、図２（ｄ）の入力グラフＧ４と、図４（ｂ）統合グラフＴ´との類似度を算出する。なお、類似度算出手段１３は、入力グラフＧ４の算出フラグを算出済みに設定し、統合グラフＴ´の統合フラグを算出済みに設定しても良い。
【００５７】
このとき、前記と同様に、類似度算出手段１３は、ノードＢ５及びノードＣ６を用いて類似度を算出する。この場合、類似度算出手段１３は、統合グラフＴ´のノードＡ６と入力グラフＧ３のノードＣ６のみが代替誤りとなり、他のノードが一致するという結果「ＨＳＳＨ（Ｂ５）Ｈ（Ｃ６）」を用いて、類似度を２／３と算出する。
【００５８】
類似判定手段１４は、統合グラフＴ´と入力グラフＧ４との類似度（例えば、２／３）と、閾値（例えば、１／２）とを比較し、この類似度が閾値以上なので統合グラフＴ´と入力グラフＧ４とが類似すると判定する。
【００５９】
統合グラフＴ´と入力グラフＧ４とが類似するので、グラフ統合手段１５は、ＤＰマッチングの結果に基づいて、統合グラフＴ´と入力グラフＧ４とを図４（ｃ）の統合グラフＴ´´（Ｔ）に統合する。
【００６０】
具体的には、統合グラフＴ´と入力グラフＧ４において、ノードＡ１，Ａ４が一致するので、グラフ統合手段１５は、統合グラフＴのノードＡ１，Ａ４をそのままの順とする。また、統合グラフＴ´と入力グラフＧ４において、ノードＡ２とノードＤ２、ノードＡ３とノードＤ３、ノードＡ５とノードＢ５、及び、ノードＡ６とノードＣ６が代替誤りとなる。ここで、グラフ統合手段１５は、ノードＡ２とノードＤ２とを並行にし、ノードＡ３とノードＤ３とを並列にする。さらに、グラフ統合手段１５は、代替誤りとなるノードＡ２，Ｄ２の直前に位置するノードＡ１から代替誤りとなるノードＡ２，Ｄ２にエッジを分岐させる。
【００６１】
また、グラフ統合手段１５は、代替誤りとなるノードＡ２，Ｄ２とノードＡ３，Ｄ３とが連続するので、ノードＡ２からノードＡ３にエッジを接続し、ノードＤ２からノードＤ３にエッジを接続する。そして、グラフ統合手段１５は、代替誤りとなるノードＡ３，Ｄ３の直後に位置するノードＡ４に、代替誤りとなるノードＡ３，Ｄ３からエッジを合流させる。なお、ノードＡ５，Ｂ５及びノードＡ６，Ｃ６については、統合グラフＴ´と同様のため、説明を省略する。
【００６２】
このように、類似度算出手段１３が、並行となるノードＮのうち、入力グラフＧのノードＮと一致する経路で類似度を算出することで、従来ではｎ×（ｎ−１）／２回行っていたグラフの比較回数を、ｎ回に低減することができる。
【００６３】
なお、統合グラフＴ´と入力グラフＧ４とが類似しない場合、グラフ追加手段１６は、入力グラフＧ４を新たな統合グラフＴとして統合グラフ記憶手段１７に記憶させる。この場合、グラフ統合装置１は、複数の統合グラフＴを用いて類似判定を行うことができる。
【００６４】
＜類似度の算出及び類似判定の詳細：第２例＞
以下、図３に戻り、欠落誤り及び挿入誤りが発生した場合における類似度の算出を説明する（適宜図１参照）。
【００６５】
例えば、図３（ａ）の入力グラフＧ１と、図３（ｂ）の入力グラフＧ５と比較すると、類似度算出手段１３は、ノードＡ６が欠落誤りとなる結果「ＨＨＨＨＳＤ」を得ることができる。また、類似度算出手段１３は、このＤＰマッチングの結果を式（１）に代入して類似度を４／６と算出する。そして、前記と同様に、類似判定手段１４は、この類似度が所定の閾値以上であるか否かにより、類似判定を行う。ここでは、この類似度が閾値（例えば、１／２）以上なので、類似判定手段１４は、入力グラフＧ１，Ｇ５を類似すると判定する。
【００６６】
また、図３（ａ）の入力グラフＧ１と、図３（ｃ）の入力グラフＧ６と比較すると、類似度算出手段１３は、ノードＡ７が挿入誤りとなる結果「ＨＨＨＨＳＨＩ」を得ることができる。また、類似度算出手段１３は、このＤＰマッチングの結果を式（１）に代入して類似度を４／６と算出する。そして、前記と同様に、類似判定手段１４は、この類似度が所定の閾値以上であるか否かにより、類似判定を行う。ここでは、この類似度が閾値（例えば、１／２）以上なので、類似判定手段１４は、入力グラフＧ１，Ｇ６を類似すると判定する。
【００６７】
［グラフ統合装置の動作］
以下、図５を参照して、本発明の本実施形態に係るグラフ統合装置の動作について説明する（適宜図１参照）。図５は、図１のグラフ統合装置の動作を示すフローチャートである。ここでは、入力グラフＧが入力グラフ記憶手段１２に記憶され、統合グラフＴが統合グラフ記憶手段１７に記憶されているものとして説明する。
【００６８】
グラフ統合装置１は、類似度算出手段１３によって、入力グラフ記憶手段１２に記憶された算出フラグを参照し、類似度が未計算の入力グラフＧが有るか否かを判定する（ステップＳ１）。類似度が未計算の入力グラフＧが有る場合（ステップＳ１でＹｅｓ）、グラフ統合装置１は、類似度算出手段１３によって、類似度の最大値を初期化（例えば、０に初期化）する（ステップＳ２）。
【００６９】
ステップＳ２に続いて、グラフ統合装置１は、類似度算出手段１３によって、統合グラフ記憶手段１７に記憶された統合フラグを参照し、類似度が未計算の統合グラフＴが有るか否かを判定する（ステップＳ３）。
【００７０】
類似度が未計算の統合グラフＴが有る場合（ステップＳ３でＹｅｓ）、グラフ統合装置１は、類似度算出手段１３によって、ＤＰマッチング法を用いて、統合グラフＴと入力グラフＧとの類似度を算出する（ステップＳ４）。そして、グラフ統合装置１は、類似度算出手段１３によって、算出した類似度が、類似度の最大値以上であるか否かを判定する（ステップＳ５）。
【００７１】
算出した類似度が最大値以上の場合（ステップＳ５でＹｅｓ）、グラフ統合装置１は、類似度算出手段１３によって、算出した類似度で類似度の最大値を更新し（ステップＳ６）、ステップＳ３の処理に戻る。一方、類似度が最大値未満の場合（ステップＳ５でＮｏ）、グラフ統合装置１は、類似度の最大値を更新せずに、ステップＳ３の処理に戻る。
【００７２】
類似度が未計算の統合グラフＴが無い場合（ステップＳ３でＮｏ）、グラフ統合装置１は、類似判定手段１４によって、統合グラフＴと入力グラフＧとの類似度が閾値以上の場合、統合グラフＴと入力グラフＧとが類似すると判定し、統合グラフＴと入力グラフＧとの類似度が閾値未満の場合、統合グラフＴと入力グラフＧとが類似しないと判定する（ステップＳ７）。
【００７３】
統合グラフＴと入力グラフＧとが類似する場合（ステップＳ７でＹｅｓ）、グラフ統合装置１は、グラフ統合手段１５によって、ＤＰマッチング法の結果に基づいて、統合グラフＴと入力グラフＧとを統合する（ステップＳ８）。一方、統合グラフＴと入力グラフＧとが類似しない場合（ステップＳ７でＮｏ）、グラフ統合装置１は、グラフ追加手段１６によって、入力グラフＧを新たな統合グラフＴとして追加する（ステップＳ９）。
【００７４】
その後、グラフ統合装置１は、ステップＳ１の処理に戻り、入力グラフ記憶手段１２に記憶された算出フラグを参照し、類似度が未計算の入力グラフＧが有るか否かを判定する。ここで、類似度が未計算の入力グラフＧが有る場合、グラフ統合装置１は、類似度が未計算の入力グラフＧが無くなるまで、前記した処理を繰り返す。また、類似度が未計算の入力グラフＧが無い場合（ステップＳ１でＮｏ）、グラフ統合装置１は、処理を終了する。
【００７５】
なお、本実施形態では、本発明に係るグラフ統合装置を独立した装置として説明したが、本発明では、一般的なコンピュータを、前記した各手段として機能させるプログラムによって動作させることもできる。このプログラムは、通信回線を介して配布しても良く、ＣＤ−ＲＯＭやフラッシュメモリ等の記録媒体に書き込んで配布しても良い。
【図面の簡単な説明】
【００７６】
【図１】本発明の本実施形態に係るグラフ統合装置の構成を示すブロック図である。
【図２】図１のグラフ入力手段に入力された入力グラフを説明する図であり、（ａ）〜（ｄ）がそれぞれ入力グラフの第１例〜第４例である。
【図３】図１のグラフ入力手段に入力された入力グラフを説明する図であり、（ａ）〜（ｃ）がそれぞれ入力グラフの第１例、第５例及び第６例である。
【図４】図１のグラフ統合手段が統合した統合グラフを説明する図であり、（ａ）〜（ｃ）がそれぞれ統合グラフの第１例〜第３例である。
【図５】図１のグラフ統合装置の動作を示すフローチャートである。
【符号の説明】
【００７７】
１ グラフ統合装置
１１ グラフ入力手段
１２ 入力グラフ記憶手段
１３ 類似度算出手段
１４ 類似判定手段
１５ グラフ統合手段
１６ グラフ追加手段
１７ 統合グラフ記憶手段
【技術分野】
【０００１】
本発明は、入力要素を示すノードと、ノード間の接続、ノード間の分岐又はノード間の合流を示すエッジとで構成された入力グラフを統合するグラフ統合装置及びそのプログラムに関する。
【背景技術】
【０００２】
従来から、例えば、音声認識の際、音声信号を音素、単語等の認識候補のグラフとしたときに、このグラフを複数の言語モデルに基づいて認識することで、音声認識の精度を向上させることが行われている。
【０００３】
ここで、複数の言語モデルからより適切な認識結果を生成するために、このグラフを統合することが行われている（特許文献１参照）。例えば、特許文献１に記載の発明は、このグラフから不要な経路を減らして、このグラフを統合するものである。
【特許文献１】特開２００３−１５６８５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、特許文献１に記載の発明は、３個以上のグラフを統合する場合、これらグラフを組み合わせた回数、グラフを比較する必要があり、演算量が多くなってしまう。例えば、特許文献１に記載の発明では、ｎ個のグラフを統合するために、ｎ×（ｎ−１）／２回、グラフを比較する必要があり、利便性に欠ける。また、従来技術では、複数のグラフを１個のグラフに統合するのみで、２以上のグラフに統合することができなかった。
【０００５】
そこで、本発明は、複数の統合グラフを扱うことができ、演算量が少なく、簡易な構成のグラフ統合装置及びそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
前記した課題を解決するため、請求項１に係るグラフ統合装置は、入力要素を示すノードとノードにおいて分岐及び合流が可能なエッジとで構成された入力グラフが複数入力され、これら入力グラフを統合するグラフ統合装置において、類似度算出手段と、類似判定手段と、グラフ統合手段と、グラフ追加手段と、を備える構成とした。
【０００７】
かかる構成において、グラフ統合装置は、類似度算出手段によって、ＤＰマッチング法を用いて、入力された複数の入力グラフのノードの一致と挿入誤りと欠落誤りと代替誤りとをＤＰマッチングの結果として求める。そして、グラフ統合装置は、類似度算出手段によって、このＤＰマッチングの結果を予め設定された関数に代入して入力グラフ同士の類似度を算出し、求めたＤＰマッチングの結果と、算出した入力グラフ同士の類似度を出力する。
【０００８】
また、グラフ統合装置は、類似判定手段によって、類似度算出手段から入力された入力グラフ同士の類似度が予め設定された閾値以上の場合、入力グラフ同士が類似すると判定する。さらに、グラフ統合装置は、類似判定手段によって、類似度算出手段から入力された入力グラフ同士の類似度が閾値未満の場合、入力グラフ同士が類似しないと判定し、この類似判定結果を出力する。これによって、グラフ統合装置は、類似性の低い入力グラフ同士を統合してしまう事態を低減できる。
【０００９】
類似判定手段から入力された類似判定結果において、入力グラフ同士が類似する場合、グラフ統合装置は、グラフ統合手段によって、類似度算出手段から入力されたＤＰマッチングの結果に基づいて、入力グラフ同士を統合グラフに統合する。また、類似判定手段から入力された類似判定結果において、入力グラフ同士が類似しない場合、グラフ統合装置は、グラフ追加手段によって、入力グラフのそれぞれを新たな統合グラフとして追加する。
【００１０】
次に、グラフ統合装置は、類似度算出手段によって、ＤＰマッチング法を用いて、入力グラフと、グラフ統合手段が統合した統合グラフ又はグラフ追加手段が追加した統合グラフとのノードの一致と挿入誤りと欠落誤りと代替誤りとをＤＰマッチングの結果として求める。そして、グラフ統合装置は、このＤＰマッチングの結果を関数に代入して入力グラフと統合グラフとの類似度を算出し、求めたＤＰマッチングの結果と、算出した入力グラフと統合グラフとの類似度を出力する。
【００１１】
また、グラフ統合装置は、類似判定手段によって、類似度算出手段から入力された入力グラフと統合グラフとの類似度が閾値以上の場合、入力グラフと統合グラフとが類似すると判定する。さらに、グラフ統合装置は、類似判定手段によって、類似度算出手段から入力された類似度が閾値未満の場合、入力グラフと統合グラフとが類似しないと判定し、この類似判定結果を出力する。これによって、グラフ統合装置は、類似性の低い入力グラフと統合グラフとを統合してしまう事態を低減できる。
【００１２】
類似判定手段から入力された類似判定結果において、入力グラフと統合グラフとが類似する場合、グラフ統合装置は、グラフ統合手段によって、類似度算出手段から入力されたＤＰマッチングの結果に基づいて、入力グラフと統合グラフとを統合する。
【００１３】
類似判定手段から入力された類似判定結果において、入力グラフと統合グラフとが類似しない場合、グラフ統合装置は、グラフ追加手段によって、入力グラフを新たな統合グラフとして追加する。これによって、グラフ統合装置は、入力グラフと統合グラフとを統合でき、入力グラフを組み合わせた回数分の類似判定を行う必要がなくなると共に、複数の統合グラフを扱うことを可能とする。
【００１４】
また、前記した課題を解決するため、請求項２に係るグラフ統合プログラムは、入力要素を示すノードとノードにおいて分岐及び合流が可能なエッジとで構成された入力グラフが複数入力され、これら入力グラフを統合するために、コンピュータを、類似度算出手段と、類似判定手段と、グラフ統合手段と、グラフ追加手段と、として機能させる構成とした。
【００１５】
かかる構成において、グラフ統合プログラムは、類似度算出手段によって、ＤＰマッチング法を用いて、入力された複数の入力グラフのノードの一致と挿入誤りと欠落誤りと代替誤りとを求める。そして、グラフ統合プログラムは、このＤＰマッチングの結果を予め設定された関数に代入して入力グラフ同士の類似度を算出し、求めたＤＰマッチングの結果と、算出した入力グラフ同士の類似度を出力する。
【００１６】
また、グラフ統合プログラムは、類似判定手段によって、類似度算出手段から入力された入力グラフ同士の類似度が予め設定された閾値以上の場合、入力グラフ同士が類似すると判定する。さらに、グラフ統合プログラムは、類似判定手段によって、類似度算出手段から入力された入力グラフ同士の類似度が閾値未満の場合、入力グラフ同士が類似しないと判定する。これによって、グラフ統合プログラムは、類似性の低い入力グラフ同士を統合してしまう事態を低減できる。
【００１７】
類似判定手段から入力された類似判定結果において、入力グラフ同士が類似する場合、グラフ統合プログラムは、グラフ統合手段によって、類似度算出手段から入力されたＤＰマッチングの結果に基づいて、入力グラフ同士を統合グラフに統合する。また、類似判定手段から入力された類似判定結果において、入力グラフ同士が類似しない場合、グラフ統合プログラムは、グラフ追加手段によって、入力グラフのそれぞれを新たな統合グラフとして追加する。
【００１８】
次に、グラフ統合プログラムは、類似度算出手段によって、ＤＰマッチング法を用いて、入力グラフと、グラフ統合手段が統合した統合グラフ又はグラフ追加手段が追加した統合グラフとのノードの一致と挿入誤りと欠落誤りと代替誤りとを求める。そして、グラフ統合プログラムは、このＤＰマッチングの結果を関数に代入して入力グラフと統合グラフとの類似度を算出し、求めたＤＰマッチングの結果と、算出した入力グラフと統合グラフとの類似度を出力する。
【００１９】
また、グラフ統合プログラムは、類似判定手段によって、類似度算出手段から入力された入力グラフと統合グラフとの類似度が閾値以上の場合、入力グラフと統合グラフとが類似すると判定する。さらに、グラフ統合プログラムは、類似判定手段によって、類似度算出手段から入力された類似度が閾値未満の場合、入力グラフと統合グラフとが類似しないと判定する。これによって、グラフ統合プログラムは、類似性の低い入力グラフと統合グラフとを統合してしまう事態を低減できる。
【００２０】
類似判定手段から入力された類似判定結果において、入力グラフと統合グラフとが類似する場合、グラフ統合プログラムは、グラフ統合手段によって、類似度算出手段から入力されたＤＰマッチングの結果に基づいて、入力グラフと統合グラフとを統合する。
【００２１】
類似判定手段から入力された類似判定結果において、入力グラフと統合グラフとが類似しない場合、グラフ統合プログラムは、グラフ追加手段によって、入力グラフを新たな統合グラフとして追加する。これによって、グラフ統合プログラムは、入力グラフと統合グラフとを統合でき、入力グラフを組み合わせた回数分の類似判定を行う必要がなくなると共に、複数の統合グラフを扱うことを可能とする。
【発明の効果】
【００２２】
本発明によれば、以下のような優れた効果を奏する。
請求項１，２に係る発明によれば、入力グラフを組み合わせた回数分の類似判定を行う必要がなくなると共に、複数の統合グラフを扱うことを可能とするため、演算量を少なくでき、グラフ統合装置を簡易な構成とすることができる。また、請求項１，２に係る発明によれば、類似性の低い入力グラフ同士及び入力グラフと統合グラフとを統合してしまう事態を低減できるため、グラフの統合がより正確になる。
【発明を実施するための最良の形態】
【００２３】
［グラフ統合装置の構成］
以下、本発明の実施形態について、適宜図面を参照しながら詳細に説明する。
図１を参照して、本発明の本実施形態に係るグラフ統合装置の構成について説明する。図１は、本発明の本実施形態に係るグラフ統合装置の構成を示すブロック図である。
【００２４】
図１のグラフ統合装置１は、入力要素を示すノードと、ノード間において分岐及び合流が可能なエッジとで構成されたエッジとで構成された入力グラフＧが複数入力され、入力グラフＧを統合するものであって、グラフ入力手段１１と、入力グラフ記憶手段１２と、類似度算出手段１３と、類似判定手段１４と、グラフ統合手段１５と、グラフ追加手段１６と、統合グラフ記憶手段１７と、を備える。なお、図１では、入力グラフを符号Ｇ、統合グラフを符号Ｔで示した。
【００２５】
グラフ入力手段１１は、図２の複数の入力グラフＧ１，Ｇ２，Ｇ３，Ｇ４（Ｇ）が入力されるものである。例えば、グラフ入力手段１１としては、入力グラフＧ１，Ｇ２，Ｇ３，Ｇ４（Ｇ）を外部から受信する通信ポート、又は、磁気ディスク等の記憶媒体に記憶された入力グラフＧを読み取る読取装置がある。以下、入力グラフＧ１，Ｇ２，Ｇ３，Ｇ４を区別しないで説明する場合、単に入力グラフＧとする。なお、入力グラフＧの詳細は、後記する。
【００２６】
入力グラフ記憶手段１２は、グラフ入力手段１１に入力された入力グラフＧを記憶する、例えば、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）等の記憶手段である。
【００２７】
類似度算出手段１３は、例えば、後記する統合グラフ記憶手段１７が統合グラフＴを記憶してなければ、ＤＰマッチング法を用いて、入力グラフ記憶手段１２が記憶する複数の入力グラフＧ同士（例えば、図２（ａ）の入力グラフＧ１と図２（ｂ）の入力グラフＧ２）におけるノードの一致と挿入誤りと欠落誤りと代替誤りとをＤＰマッチングの結果として求める。そして、類似度算出手段１３は、このＤＰマッチングの結果を予め設定された関数に代入し、入力グラフＧのそれぞれの類似度を算出するものである。
【００２８】
ここで、入力グラフ記憶手段１２は、入力グラフＧ毎に、その入力グラフＧの類似度を算出したか否かを示す算出フラグをあわせて記憶しても良い。この場合、算出フラグは、類似度を未算出（例えば、「０」）が初期値として設定される。そして、類似度算出手段１３は、類似度を算出した入力グラフＧについて、算出フラグを算出済み（例えば、「１」）に設定しても良い。
【００２９】
また、類似度算出手段１３は、例えば、統合グラフ記憶手段１７が統合グラフＴを記憶していれば、ＤＰマッチング法を用いて、入力グラフ記憶手段１２が記憶する入力グラフＧと、統合グラフ記憶手段１７が記憶する統合グラフＴとのノードの一致と挿入誤りと欠落誤りと代替誤りとをＤＰマッチングの結果として求め、このＤＰマッチングの結果を関数に代入して入力グラフＧと統合グラフＴとの類似度を算出するものである。また、類似度算出手段１３は、求めたＤＰマッチングの結果と、算出した類似度とを類似判定手段１４、及び、類似判定手段１４を介してグラフ統合手段１５に出力する。
【００３０】
ここで、後記する統合グラフ記憶手段１７は、統合グラフＴ毎に、その統合グラフＴの類似度を算出したか否かを示す統合フラグをあわせて記憶しても良い。この場合、統合フラグは、類似度を未算出（例えば、「０」）が初期値として設定される。そして、類似度算出手段１３は、類似度を算出した統合グラフＴについて、統合フラグを算出済み（例えば、「１」）に設定しても良い。
【００３１】
類似判定手段１４は、例えば、統合グラフ記憶手段１７が統合グラフＴを記憶してなければ、入力グラフＧのそれぞれの類似度が予め設定された閾値以上の場合、入力グラフ記憶手段１２が記憶する入力グラフＧのそれぞれが類似すると判定し、入力グラフＧのそれぞれの類似度が閾値未満の場合、入力グラフ記憶手段１２が記憶する入力グラフＧのそれぞれが類似しないと判定するものである。
【００３２】
また、類似判定手段１４は、例えば、統合グラフ記憶手段１７が統合グラフＴを記憶していれば、入力グラフ記憶手段１２が記憶する入力グラフＧと統合グラフ記憶手段１７が記憶する統合グラフＴとが類似するか否かを判定する。なお、類似度の算出及び類似判定の詳細は、後記する。また、類似判定手段１４は、類似するか否かの類似判定結果をグラフ統合手段１５及びグラフ追加手段１６に出力する。
【００３３】
グラフ統合手段１５は、類似判定手段１４が出力した類似判定結果において、入力グラフＧのそれぞれが類似する場合、ＤＰマッチングの結果に基づいて、入力グラフＧのそれぞれを統合グラフＴに統合するものである。また、グラフ統合手段１５は、類似判定手段１４が出力した類似判定結果において、入力グラフＧと統合グラフＴとが類似する場合、ＤＰマッチング法の結果に基づいて、入力グラフＧと統合グラフＴとを統合し、統合グラフ記憶手段１７に記憶させる。
【００３４】
グラフ追加手段１６は、類似判定手段１４が出力した類似判定結果において、入力グラフＧのそれぞれが類似しない場合、入力グラフＧのそれぞれを新たな統合グラフＴとして追加するものである。また、グラフ追加手段１６は、類似判定手段１４が出力した類似判定結果において、入力グラフＧと統合グラフＴとが類似しない場合、入力グラフＧを新たな統合グラフＴとして追加し、統合グラフ記憶手段１７に記憶させる。
【００３５】
統合グラフ記憶手段１７は、グラフ統合手段１５が統合した統合グラフＴ又はグラフ追加手段１６が追加した統合グラフＴを記憶するものである。ここで、グラフ統合装置１は、統合グラフ記憶手段１７が記憶する統合グラフＴを、外部の音声認識装置（不図示）からの要求に応じて出力しても良い。なお、図１では、説明のために、入力グラフ記憶手段１２と統合グラフ記憶手段１７とを別々に図示したが、これらを１個の記憶手段で構成しても良い（不図示）。
【００３６】
＜入力グラフの詳細＞
以下、図２，３を参照して、入力グラフの詳細について説明する（適宜図１参照）。図２は図１のグラフ入力手段に入力された入力グラフを説明する図であり、（ａ）〜（ｄ）がそれぞれ入力グラフの第１例〜第４例である。また、図３は図１のグラフ入力手段に入力された入力グラフを説明する図であり、（ａ）〜（ｃ）がそれぞれ入力グラフの第１例、第５例及び第６例である。なお、図２（ａ）と図３（ａ）に示す入力グラフは、同じものである。
【００３７】
図２では、入力グラフＧの先頭を「先頭」、及び、入力グラフＧの終了を「終了」として図示した。また、ノードは、長方形で図示し、そのノード名を長方形の内部に示した。以下、ノードを特定して説明する場合、そのノード名を記す（例えば、ノードＡ１、ノードＣ６等と記す）。さらに、エッジは、ノード間の接続、ノード間の合流及びノード間の分岐を示すものであり、ノード間を接続する矢印、及び、入力グラフＧの先頭や終了とノードとを接続する矢印で図示した。この矢印の方向がエッジの接続方向を示すことからも明らかなように、入力グラフＧは、ノードとエッジとで構成される有向グラフである。
【００３８】
図２（ａ）に示すように、入力グラフＧ１は、その先頭から終了まで、ノードＡ１、ノードＡ２、ノードＡ３、ノードＡ４、ノードＡ５及びノードＡ６が順にエッジで接続されている。また、図２（ｂ）に示すように、入力グラフＧ２は、ノードＡ１・・・ノードＡ４、ノードＢ５及びノードＡ６が順にエッジで接続されている。
【００３９】
また、図２（ｃ）に示すように、入力グラフＧ３は、ノードＡ１・・・ノードＡ４、ノードＢ５及びノードＣ６が順にエッジで接続されている。さらに、図２（ｄ）に示すように、入力グラフＧ４は、ノードＡ１、ノードＤ２、ノードＤ３、ノードＡ４、ノードＢ５及びノードＣ６が順にエッジで接続されている。
【００４０】
図３（ｂ）に示すように、入力グラフＧ５は、ノードＡ１・・・ノードＡ４及びノードＢ５が順にエッジで接続されている。また、図３（ｃ）に示すように、入力グラフＧ６は、ノードＡ１・・・ノードＢ５、ノードＡ６及びノードＡ７が順にエッジで接続されている。
【００４１】
＜類似度の算出及び類似判定の詳細：第１例＞
以下、図４を参照して、類似度の算出及び類似判定の詳細について説明する（適宜図１，図２参照）。図４は図１のグラフ統合手段が統合した統合グラフを説明する図であり、（ａ）〜（ｃ）がそれぞれ統合グラフの第１例〜第３例である。ここでは、図２に示す４個の入力グラフＧの類似度を算出して類似判定する例を説明する。
【００４２】
まず、類似度算出手段１３は、ＤＰマッチング法を用いて、図２の入力グラフＧ１，Ｇ２の類似度を算出する。具体的には、類似度算出手段１３は、入力グラフＧ１，Ｇ２のノードの一致（Ｈ）、挿入誤り（Ｉ）、欠落誤り（Ｄ）又は代替誤り（Ｓ）を結果として求め、このＤＰマッチングの結果を下記式（１）に代入して類似度を算出する。ここで、式（１）が、請求項に記載の関数に相当する。
【００４３】
類似度＝（Ｈ−Ｉ）／（Ｈ＋Ｓ＋Ｄ）・・・式（１）
【００４４】
この場合、類似度算出手段１３は、入力グラフＧ１のノードＡ５と入力グラフＧ２のノードＢ５のみが代替誤りとなり、他のノードが一致するという結果「ＨＨＨＨＳＨ」を得ることができる。そして、類似度算出手段１３は、このＤＰマッチングの結果を式（１）に代入し、類似度を５／６と算出する。なお、類似度算出手段１３は、入力グラフＧ１，Ｇ２の算出フラグを算出済みに設定しても良い。
【００４５】
類似判定手段１４は、入力グラフＧ１，Ｇ２の類似度（例えば、５／６）と、予め設定された閾値（例えば、１／２）とを比較し、この類似度が閾値以上なので入力グラフＧ１，Ｇ２が類似すると判定する。
【００４６】
入力グラフＧ１，Ｇ２が類似するので、グラフ統合手段１５は、ＤＰマッチング法の結果に基づいて、入力グラフＧ１，Ｇ２を図４（ａ）の統合グラフＴに統合する。ここで、グラフ統合手段１５は、ＤＰマッチングの結果が一致となるノードについては、統合グラフＴにおいて、そのノードをそのまま配置しても良い。また、グラフ統合手段１５は、ＤＰマッチングの結果が挿入誤りとなるノードについては、そのノードを統合グラフＴに挿入しても良い。さらに、グラフ統合手段１５は、ＤＰマッチングの結果が欠落誤りとなるノードについては、そのノードをスキップするように、そのノードに前後するノード同士を直接接続するエッジを追加しても良い。そして、グラフ統合手段１５は、ＤＰマッチングの結果が代替誤りとなるノードについては、統合グラフＴにおいて、代替え関係となるノードを並列に配置しても良い。
【００４７】
具体的には、入力グラフＧ１，Ｇ２において、ノードＡ１〜ノードＡ４及びノードＡ６が一致するので、グラフ統合手段１５は、「先頭」からノードＡ１・・・ノードＡ４を順にし、ノードＡ６を「終点」の直前とする。また、入力グラフＧ１，Ｇ２において、ノードＡ５とノードＢ５とが代替誤りとなるので、グラフ統合手段１５は、ノードＡ５とノードＢ５とを並列にする。そして、グラフ統合手段１５は、代替誤りとなるノードＡ５，Ｂ５の直前に位置するノードＡ４から、代替誤りとなるノードＡ５，Ｂ５にエッジを分岐させる。さらに、グラフ統合手段１５は、代替誤りとなるノードＡ５，Ｂ５の直後に位置するノードＡ６に、代替誤りとなるノードＡ５，Ｂ５からエッジを合流させる。
【００４８】
なお、入力グラフＧ１，Ｇ２が類似しない場合、グラフ追加手段１６は、入力グラフＧ１，２をそれぞれ、新たな統合グラフＴとして統合グラフ記憶手段１７に記憶させる。この場合、グラフ統合装置１は、複数の統合グラフＴを用いて類似判定を行うことができる。
【００４９】
次に、類似度算出手段１３は、ＤＰマッチング法を用いて、算出フラグが未算出である、図２（ｃ）の入力グラフＧ３と、図４（ａ）の統合グラフＴとの類似度を算出する。なお、類似度算出手段１３は、入力グラフＧ３の算出フラグを算出済みに設定し、統合グラフＴの統合フラグを算出済みに設定しても良い。
【００５０】
ここでは、ノードＡ１・・・ノードＡ４までのＤＰマッチングが終了している場合を例に説明する。類似度算出手段１３は、ノードＡ５とノードＢ５とが分岐するので、（１）統合グラフＴにおけるノードＡ５に対する「ＨＨＨＨＤ」、（２）統合グラフＴにおけるノードＡ５に対する「ＨＨＨＨＳ」、（３）統合グラフＴにおけるノードＢ５に対する「ＨＨＨＨＤ」、（４）統合グラフＴにおけるノードＢ５に対する「ＨＨＨＨＨ」、及び、（５）入力グラフＧ３におけるノードＢ５に対する「ＨＨＨＨＩ」という５個の仮説を生成する。
【００５１】
また、類似度算出手段１３は、ノードＡ６で合流するので、（１）統合グラフＴにおけるノードＡ５の欠落誤り、（２）統合グラフＴにおけるノードＡ５の代替誤り、（３）統合グラフＴにおけるノードＢ５の欠落誤り、（４）統合グラフＴにおけるノードＢ５の一致、及び、（５）入力グラフＧ３におけるノードＢ５の挿入誤りという、前記した仮説をマージする。
【００５２】
ここでは、類似度算出手段１３は、上記（４）の仮説が最小となるので、ノードＢ５が一致という結果を用いて、類似度を算出する。従って、類似度算出手段１３は、統合グラフＴのノードＡ６と入力グラフＧ３のノードＣ６のみが代替誤りとなり、他のノードが一致するという結果「ＨＨＨＨＨ（Ｂ５）Ｓ」を用いて、類似度を５／６と算出する。
【００５３】
類似判定手段１４は、統合グラフＴと入力グラフＧ３との類似度（例えば、５／６）と、閾値（例えば、１／２）とを比較し、この類似度が閾値以上なので統合グラフＴと入力グラフＧ３とが類似すると判定する。
【００５４】
統合グラフＴと入力グラフＧ３とが類似するので、グラフ統合手段１５は、ＤＰマッチングの結果に基づいて、統合グラフＴと入力グラフＧ３とを図４（ｂ）の統合グラフＴ´（Ｔ）に統合する。ここで、統合グラフＴと入力グラフＧ３において、ノードＡ１〜ノードＡ５，Ｂ５が一致するので、グラフ統合手段１５は、統合グラフＴのノードＡ１〜ノードＡ５，Ｂ５をそのままの順とする。
【００５５】
具体的には、統合グラフＴと入力グラフＧ３において、ノードＡ６とノードＣ６が代替誤りとなるため、グラフ統合手段１５は、ノードＡ６とノードＣ６とを並列に追加する。そして、グラフ統合手段１５は、ノードＡ５とノードＡ６とを接続し、ノードＢ５からノードＡ６，Ｃ６にエッジを分岐させる。
【００５６】
最後に、類似度算出手段１３は、ＤＰマッチング法を用いて、図２（ｄ）の入力グラフＧ４と、図４（ｂ）統合グラフＴ´との類似度を算出する。なお、類似度算出手段１３は、入力グラフＧ４の算出フラグを算出済みに設定し、統合グラフＴ´の統合フラグを算出済みに設定しても良い。
【００５７】
このとき、前記と同様に、類似度算出手段１３は、ノードＢ５及びノードＣ６を用いて類似度を算出する。この場合、類似度算出手段１３は、統合グラフＴ´のノードＡ６と入力グラフＧ３のノードＣ６のみが代替誤りとなり、他のノードが一致するという結果「ＨＳＳＨ（Ｂ５）Ｈ（Ｃ６）」を用いて、類似度を２／３と算出する。
【００５８】
類似判定手段１４は、統合グラフＴ´と入力グラフＧ４との類似度（例えば、２／３）と、閾値（例えば、１／２）とを比較し、この類似度が閾値以上なので統合グラフＴ´と入力グラフＧ４とが類似すると判定する。
【００５９】
統合グラフＴ´と入力グラフＧ４とが類似するので、グラフ統合手段１５は、ＤＰマッチングの結果に基づいて、統合グラフＴ´と入力グラフＧ４とを図４（ｃ）の統合グラフＴ´´（Ｔ）に統合する。
【００６０】
具体的には、統合グラフＴ´と入力グラフＧ４において、ノードＡ１，Ａ４が一致するので、グラフ統合手段１５は、統合グラフＴのノードＡ１，Ａ４をそのままの順とする。また、統合グラフＴ´と入力グラフＧ４において、ノードＡ２とノードＤ２、ノードＡ３とノードＤ３、ノードＡ５とノードＢ５、及び、ノードＡ６とノードＣ６が代替誤りとなる。ここで、グラフ統合手段１５は、ノードＡ２とノードＤ２とを並行にし、ノードＡ３とノードＤ３とを並列にする。さらに、グラフ統合手段１５は、代替誤りとなるノードＡ２，Ｄ２の直前に位置するノードＡ１から代替誤りとなるノードＡ２，Ｄ２にエッジを分岐させる。
【００６１】
また、グラフ統合手段１５は、代替誤りとなるノードＡ２，Ｄ２とノードＡ３，Ｄ３とが連続するので、ノードＡ２からノードＡ３にエッジを接続し、ノードＤ２からノードＤ３にエッジを接続する。そして、グラフ統合手段１５は、代替誤りとなるノードＡ３，Ｄ３の直後に位置するノードＡ４に、代替誤りとなるノードＡ３，Ｄ３からエッジを合流させる。なお、ノードＡ５，Ｂ５及びノードＡ６，Ｃ６については、統合グラフＴ´と同様のため、説明を省略する。
【００６２】
このように、類似度算出手段１３が、並行となるノードＮのうち、入力グラフＧのノードＮと一致する経路で類似度を算出することで、従来ではｎ×（ｎ−１）／２回行っていたグラフの比較回数を、ｎ回に低減することができる。
【００６３】
なお、統合グラフＴ´と入力グラフＧ４とが類似しない場合、グラフ追加手段１６は、入力グラフＧ４を新たな統合グラフＴとして統合グラフ記憶手段１７に記憶させる。この場合、グラフ統合装置１は、複数の統合グラフＴを用いて類似判定を行うことができる。
【００６４】
＜類似度の算出及び類似判定の詳細：第２例＞
以下、図３に戻り、欠落誤り及び挿入誤りが発生した場合における類似度の算出を説明する（適宜図１参照）。
【００６５】
例えば、図３（ａ）の入力グラフＧ１と、図３（ｂ）の入力グラフＧ５と比較すると、類似度算出手段１３は、ノードＡ６が欠落誤りとなる結果「ＨＨＨＨＳＤ」を得ることができる。また、類似度算出手段１３は、このＤＰマッチングの結果を式（１）に代入して類似度を４／６と算出する。そして、前記と同様に、類似判定手段１４は、この類似度が所定の閾値以上であるか否かにより、類似判定を行う。ここでは、この類似度が閾値（例えば、１／２）以上なので、類似判定手段１４は、入力グラフＧ１，Ｇ５を類似すると判定する。
【００６６】
また、図３（ａ）の入力グラフＧ１と、図３（ｃ）の入力グラフＧ６と比較すると、類似度算出手段１３は、ノードＡ７が挿入誤りとなる結果「ＨＨＨＨＳＨＩ」を得ることができる。また、類似度算出手段１３は、このＤＰマッチングの結果を式（１）に代入して類似度を４／６と算出する。そして、前記と同様に、類似判定手段１４は、この類似度が所定の閾値以上であるか否かにより、類似判定を行う。ここでは、この類似度が閾値（例えば、１／２）以上なので、類似判定手段１４は、入力グラフＧ１，Ｇ６を類似すると判定する。
【００６７】
［グラフ統合装置の動作］
以下、図５を参照して、本発明の本実施形態に係るグラフ統合装置の動作について説明する（適宜図１参照）。図５は、図１のグラフ統合装置の動作を示すフローチャートである。ここでは、入力グラフＧが入力グラフ記憶手段１２に記憶され、統合グラフＴが統合グラフ記憶手段１７に記憶されているものとして説明する。
【００６８】
グラフ統合装置１は、類似度算出手段１３によって、入力グラフ記憶手段１２に記憶された算出フラグを参照し、類似度が未計算の入力グラフＧが有るか否かを判定する（ステップＳ１）。類似度が未計算の入力グラフＧが有る場合（ステップＳ１でＹｅｓ）、グラフ統合装置１は、類似度算出手段１３によって、類似度の最大値を初期化（例えば、０に初期化）する（ステップＳ２）。
【００６９】
ステップＳ２に続いて、グラフ統合装置１は、類似度算出手段１３によって、統合グラフ記憶手段１７に記憶された統合フラグを参照し、類似度が未計算の統合グラフＴが有るか否かを判定する（ステップＳ３）。
【００７０】
類似度が未計算の統合グラフＴが有る場合（ステップＳ３でＹｅｓ）、グラフ統合装置１は、類似度算出手段１３によって、ＤＰマッチング法を用いて、統合グラフＴと入力グラフＧとの類似度を算出する（ステップＳ４）。そして、グラフ統合装置１は、類似度算出手段１３によって、算出した類似度が、類似度の最大値以上であるか否かを判定する（ステップＳ５）。
【００７１】
算出した類似度が最大値以上の場合（ステップＳ５でＹｅｓ）、グラフ統合装置１は、類似度算出手段１３によって、算出した類似度で類似度の最大値を更新し（ステップＳ６）、ステップＳ３の処理に戻る。一方、類似度が最大値未満の場合（ステップＳ５でＮｏ）、グラフ統合装置１は、類似度の最大値を更新せずに、ステップＳ３の処理に戻る。
【００７２】
類似度が未計算の統合グラフＴが無い場合（ステップＳ３でＮｏ）、グラフ統合装置１は、類似判定手段１４によって、統合グラフＴと入力グラフＧとの類似度が閾値以上の場合、統合グラフＴと入力グラフＧとが類似すると判定し、統合グラフＴと入力グラフＧとの類似度が閾値未満の場合、統合グラフＴと入力グラフＧとが類似しないと判定する（ステップＳ７）。
【００７３】
統合グラフＴと入力グラフＧとが類似する場合（ステップＳ７でＹｅｓ）、グラフ統合装置１は、グラフ統合手段１５によって、ＤＰマッチング法の結果に基づいて、統合グラフＴと入力グラフＧとを統合する（ステップＳ８）。一方、統合グラフＴと入力グラフＧとが類似しない場合（ステップＳ７でＮｏ）、グラフ統合装置１は、グラフ追加手段１６によって、入力グラフＧを新たな統合グラフＴとして追加する（ステップＳ９）。
【００７４】
その後、グラフ統合装置１は、ステップＳ１の処理に戻り、入力グラフ記憶手段１２に記憶された算出フラグを参照し、類似度が未計算の入力グラフＧが有るか否かを判定する。ここで、類似度が未計算の入力グラフＧが有る場合、グラフ統合装置１は、類似度が未計算の入力グラフＧが無くなるまで、前記した処理を繰り返す。また、類似度が未計算の入力グラフＧが無い場合（ステップＳ１でＮｏ）、グラフ統合装置１は、処理を終了する。
【００７５】
なお、本実施形態では、本発明に係るグラフ統合装置を独立した装置として説明したが、本発明では、一般的なコンピュータを、前記した各手段として機能させるプログラムによって動作させることもできる。このプログラムは、通信回線を介して配布しても良く、ＣＤ−ＲＯＭやフラッシュメモリ等の記録媒体に書き込んで配布しても良い。
【図面の簡単な説明】
【００７６】
【図１】本発明の本実施形態に係るグラフ統合装置の構成を示すブロック図である。
【図２】図１のグラフ入力手段に入力された入力グラフを説明する図であり、（ａ）〜（ｄ）がそれぞれ入力グラフの第１例〜第４例である。
【図３】図１のグラフ入力手段に入力された入力グラフを説明する図であり、（ａ）〜（ｃ）がそれぞれ入力グラフの第１例、第５例及び第６例である。
【図４】図１のグラフ統合手段が統合した統合グラフを説明する図であり、（ａ）〜（ｃ）がそれぞれ統合グラフの第１例〜第３例である。
【図５】図１のグラフ統合装置の動作を示すフローチャートである。
【符号の説明】
【００７７】
１ グラフ統合装置
１１ グラフ入力手段
１２ 入力グラフ記憶手段
１３ 類似度算出手段
１４ 類似判定手段
１５ グラフ統合手段
１６ グラフ追加手段
１７ 統合グラフ記憶手段
【特許請求の範囲】
【請求項１】
入力要素を示すノードと前記ノードにおいて分岐及び合流が可能なエッジとで構成された入力グラフが複数入力され、前記入力グラフを統合するグラフ統合装置において、
ＤＰマッチング法を用いて、前記複数の入力グラフの前記ノードの一致と挿入誤りと欠落誤りと代替誤りとを求め、当該ＤＰマッチングの結果を予め設定された関数に代入して前記入力グラフ同士の類似度を算出する類似度算出手段と、
前記入力グラフ同士の類似度が予め設定された閾値以上の場合、前記入力グラフ同士が類似すると判定し、前記類似度が前記閾値未満の場合、前記入力グラフ同士が類似しないと判定する類似判定手段と、
前記ＤＰマッチングの結果に基づいて、前記入力グラフ同士が類似する場合、前記入力グラフ同士を統合グラフに統合するグラフ統合手段と、
前記入力グラフ同士が類似しない場合、前記入力グラフのそれぞれを新たな前記統合グラフとして追加するグラフ追加手段と、を備え、
前記類似度算出手段は、前記入力グラフと、前記グラフ統合手段が統合した統合グラフ又は前記グラフ追加手段が追加した統合グラフとの類似度を算出し、
前記類似判定手段は、前記入力グラフと前記統合グラフとの類似度が前記閾値以上の場合、前記入力グラフと前記統合グラフとが類似すると判定し、前記類似度が前記閾値未満の場合、前記入力グラフと前記統合グラフとが類似しないと判定し、
前記グラフ統合手段は、前記入力グラフと前記統合グラフとが類似する場合、前記入力グラフと前記統合グラフとを統合し、
前記グラフ追加手段は、前記入力グラフと前記統合グラフとが類似しない場合、前記入力グラフを新たな前記統合グラフとして追加することを特徴とするグラフ統合装置。
【請求項２】
入力要素を示すノードと前記ノードにおいて分岐及び合流が可能なエッジとで構成された入力グラフが複数入力され、前記入力グラフを統合するために、コンピュータを、
ＤＰマッチング法を用いて、前記複数の入力グラフの前記ノードの一致と挿入誤りと欠落誤りと代替誤りとを求め、当該ＤＰマッチングの結果を予め設定された関数に代入して前記入力グラフ同士の類似度を算出する類似度算出手段、
前記入力グラフ同士の類似度が予め設定された閾値以上の場合、前記入力グラフ同士が類似すると判定し、前記類似度が前記閾値未満の場合、前記入力グラフ同士が類似しないと判定する類似判定手段、
前記ＤＰマッチングの結果に基づいて、前記入力グラフ同士が類似する場合、前記入力グラフ同士を統合グラフに統合するグラフ統合手段、
前記入力グラフ同士が類似しない場合、前記入力グラフのそれぞれを新たな前記統合グラフとして追加するグラフ追加手段、として機能させ、
前記類似度算出手段は、前記入力グラフと、前記グラフ統合手段が統合した統合グラフ又は前記グラフ追加手段が追加した統合グラフとの類似度を算出し、
前記類似判定手段は、前記入力グラフと前記統合グラフとの類似度が前記閾値以上の場合、前記入力グラフと前記統合グラフとが類似すると判定し、前記類似度が前記閾値未満の場合、前記入力グラフと前記統合グラフとが類似しないと判定し、
前記グラフ統合手段は、前記入力グラフと前記統合グラフとが類似する場合、前記入力グラフと前記統合グラフとを統合し、
前記グラフ追加手段は、前記入力グラフと前記統合グラフとが類似しない場合、前記入力グラフを新たな前記統合グラフとして追加することを特徴とするグラフ統合プログラム。
【請求項１】
入力要素を示すノードと前記ノードにおいて分岐及び合流が可能なエッジとで構成された入力グラフが複数入力され、前記入力グラフを統合するグラフ統合装置において、
ＤＰマッチング法を用いて、前記複数の入力グラフの前記ノードの一致と挿入誤りと欠落誤りと代替誤りとを求め、当該ＤＰマッチングの結果を予め設定された関数に代入して前記入力グラフ同士の類似度を算出する類似度算出手段と、
前記入力グラフ同士の類似度が予め設定された閾値以上の場合、前記入力グラフ同士が類似すると判定し、前記類似度が前記閾値未満の場合、前記入力グラフ同士が類似しないと判定する類似判定手段と、
前記ＤＰマッチングの結果に基づいて、前記入力グラフ同士が類似する場合、前記入力グラフ同士を統合グラフに統合するグラフ統合手段と、
前記入力グラフ同士が類似しない場合、前記入力グラフのそれぞれを新たな前記統合グラフとして追加するグラフ追加手段と、を備え、
前記類似度算出手段は、前記入力グラフと、前記グラフ統合手段が統合した統合グラフ又は前記グラフ追加手段が追加した統合グラフとの類似度を算出し、
前記類似判定手段は、前記入力グラフと前記統合グラフとの類似度が前記閾値以上の場合、前記入力グラフと前記統合グラフとが類似すると判定し、前記類似度が前記閾値未満の場合、前記入力グラフと前記統合グラフとが類似しないと判定し、
前記グラフ統合手段は、前記入力グラフと前記統合グラフとが類似する場合、前記入力グラフと前記統合グラフとを統合し、
前記グラフ追加手段は、前記入力グラフと前記統合グラフとが類似しない場合、前記入力グラフを新たな前記統合グラフとして追加することを特徴とするグラフ統合装置。
【請求項２】
入力要素を示すノードと前記ノードにおいて分岐及び合流が可能なエッジとで構成された入力グラフが複数入力され、前記入力グラフを統合するために、コンピュータを、
ＤＰマッチング法を用いて、前記複数の入力グラフの前記ノードの一致と挿入誤りと欠落誤りと代替誤りとを求め、当該ＤＰマッチングの結果を予め設定された関数に代入して前記入力グラフ同士の類似度を算出する類似度算出手段、
前記入力グラフ同士の類似度が予め設定された閾値以上の場合、前記入力グラフ同士が類似すると判定し、前記類似度が前記閾値未満の場合、前記入力グラフ同士が類似しないと判定する類似判定手段、
前記ＤＰマッチングの結果に基づいて、前記入力グラフ同士が類似する場合、前記入力グラフ同士を統合グラフに統合するグラフ統合手段、
前記入力グラフ同士が類似しない場合、前記入力グラフのそれぞれを新たな前記統合グラフとして追加するグラフ追加手段、として機能させ、
前記類似度算出手段は、前記入力グラフと、前記グラフ統合手段が統合した統合グラフ又は前記グラフ追加手段が追加した統合グラフとの類似度を算出し、
前記類似判定手段は、前記入力グラフと前記統合グラフとの類似度が前記閾値以上の場合、前記入力グラフと前記統合グラフとが類似すると判定し、前記類似度が前記閾値未満の場合、前記入力グラフと前記統合グラフとが類似しないと判定し、
前記グラフ統合手段は、前記入力グラフと前記統合グラフとが類似する場合、前記入力グラフと前記統合グラフとを統合し、
前記グラフ追加手段は、前記入力グラフと前記統合グラフとが類似しない場合、前記入力グラフを新たな前記統合グラフとして追加することを特徴とするグラフ統合プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１０−３２９１９（Ｐ２０１０−３２９１９Ａ）
【公開日】平成２２年２月１２日（２０１０．２．１２）
【国際特許分類】
【出願番号】特願２００８−１９６９５５（Ｐ２００８−１９６９５５）
【出願日】平成２０年７月３０日（２００８．７．３０）
【出願人】（０００００４３５２）日本放送協会 (2,206)
【出願人】（５９１０５３９２６）財団法人エヌエイチケイエンジニアリングサービス (169)
【Ｆターム（参考）】
【公開日】平成２２年２月１２日（２０１０．２．１２）
【国際特許分類】
【出願日】平成２０年７月３０日（２００８．７．３０）
【出願人】（０００００４３５２）日本放送協会 (2,206)
【出願人】（５９１０５３９２６）財団法人エヌエイチケイエンジニアリングサービス (169)
【Ｆターム（参考）】
[ Back to top ]