プログラム及び情報抽出装置
【課題】複数の木構造情報に頻出する木構造パターンを伸張しながら探索する過程でその木構造パターンの内部に要素を追加した場合に冗長な探索を招く木構造パターンを判定する。
【解決手段】情報抽出装置１０は、複数の木構造情報に共通して含まれる木構造のパターンを保持し、保持された木構造のパターンから予め定められた条件に基づいて選択されたパスに要素を追加して木構造のパターンを伸張する伸張箇所を選択し、木構造のパターンにおける検査対象要素と伸張箇所とに基づいて定められる検査範囲から、木構造のパターンにおける検査対象要素とその子要素との間に要素を追加した共通のパターンが検出される場合に、木構造のパターンの伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する。
【解決手段】情報抽出装置１０は、複数の木構造情報に共通して含まれる木構造のパターンを保持し、保持された木構造のパターンから予め定められた条件に基づいて選択されたパスに要素を追加して木構造のパターンを伸張する伸張箇所を選択し、木構造のパターンにおける検査対象要素と伸張箇所とに基づいて定められる検査範囲から、木構造のパターンにおける検査対象要素とその子要素との間に要素を追加した共通のパターンが検出される場合に、木構造のパターンの伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム及び情報抽出装置に関する。
【背景技術】
【０００２】
多量のデータを分析して有意な情報を引き出すデータマイニングという技術がある。こうしたデータマイニングでは扱うデータ量が増加すると計算コストが指数関数的に増加するため、冗長な処理を省略することが行われている。例えば下記の特許文献１には、冗長となるパターンを省略して処理する枝刈処理が記載されている。
【０００３】
また、ＸＭＬ等の木構造情報（ツリーデータ）群に頻出する木構造のパターンを抽出するサブツリーマイニングに関し、要素の親子関係が厳密に一致する木構造のパターンを得るＩｎｄｕｃｅｄ Ｓｕｂｔｒｅｅ Ｍｉｎｉｎｇでは、木構造のパターンを伸張する際に既に探索した範囲から木構造のパターンの末端に共通する要素を追加できる場合（すなわち、新たなリーフノードを追加できる場合）には、上記木構造のパターンの伸張探索処理を省略しているものがある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１０−３０１９４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
要素間の親子関係が厳密に保たれていなくとも先祖子孫関係が保たれていれば同じ木構造のパターンとして抽出するＥｍｂｅｄｄｅｄ Ｓｕｂｔｒｅｅ Ｍｉｎｉｎｇでは、木構造のパターンの末端だけではなく内部にも要素が追加された場合を考慮して冗長な探索を招くか否かを判定する必要がある。
【０００６】
本発明の目的は、複数の木構造情報に頻出する木構造パターンを伸張しながら探索する過程でその木構造パターンの内部に要素を追加した場合に冗長な探索を招く木構造パターンを判定するプログラム及び情報抽出装置を提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、請求項１に記載の発明は、コンピュータを、複数の木構造情報の中から予め定められた数の木構造情報に共通して含まれる木構造のパターンを保持する保持手段、前記保持手段に保持された木構造のパターンから予め定められた条件に基づいてパスを選択するとともに、当該選択されたパスに要素を追加して前記木構造のパターンを伸張する伸張箇所を選択する選択手段、及び、前記木構造のパターンに含まれるいずれかの要素を検査対象要素とし、前記木構造のパターンにおける前記検査対象要素と前記伸張箇所とに基づいて前記複数の木構造情報のそれぞれについて定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその子要素との間に要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する判定手段として機能させるためのプログラムである。
【０００８】
また、請求項２に記載の発明は、請求項１に記載のプログラムにおいて、前記判定手段は、前記定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその１つの子要素との間に要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定することを特徴とする。
【０００９】
また、請求項３に記載の発明は、請求項１又は２に記載のプログラムにおいて、前記判定手段は、前記定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその複数の子要素とのそれぞれに接続する要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定することを特徴とする。
【００１０】
また、請求項４に記載の発明は、請求項１から３のいずれかに記載のプログラムにおいて、前記判定手段はさらに、前記定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素に新たな子要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定することを特徴とする。
【００１１】
また、請求項５に記載の発明は、請求項１から４のいずれかに記載のプログラムにおいて、前記コンピュータをさらに、前記木構造のパターンにおける前記検査対象要素と前記伸張箇所とに基づいて、前記複数の木構造情報のそれぞれについて前記検査対象要素とその子要素との間に追加された要素の候補を検出する基準位置を設定する設定手段として機能させるためのプログラムである。
【００１２】
また、請求項６に記載の発明は、請求項１から５のいずれかに記載のプログラムにおいて、前記コンピュータをさらに、前記判定手段により前記木構造のパターンの前記伸張箇所に新たな要素を追加した伸張パターンの探索を行うと判定した場合に、当該伸張パターンの候補を前記複数の木構造情報の中から探索する探索手段、前記探索手段により探索された前記伸張パターンの候補に基づいて生成した木構造のパターンを前記保持手段に保持させる手段、前記保持手段に保持された木構造のパターンを前記選択手段、前記判定手段、前記探索手段により伸張する処理を再帰的に実行する手段として機能させるためのプログラムである。
【００１３】
また、請求項７に記載の発明は、複数の木構造情報の中から予め定められた数の木構造情報に共通して含まれる木構造のパターンを保持する保持手段と、前記保持手段に保持された木構造のパターンから予め定められた条件に基づいてパスを選択するとともに、当該選択されたパスに要素を追加して前記木構造のパターンを伸張する伸張箇所を選択する選択手段と、前記木構造のパターンに含まれるいずれかの要素を検査対象要素とし、前記木構造のパターンにおける前記検査対象要素と前記伸張箇所とに基づいて前記複数の木構造情報のそれぞれについて定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその子要素との間に要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する判定手段と、を含むことを特徴とする情報抽出装置である。
【発明の効果】
【００１４】
請求項１及び７に記載の発明によれば、複数の木構造情報に頻出する木構造パターンを伸張しながら探索する過程でその木構造パターンの内部に要素を追加した場合に冗長な探索を招く木構造パターンを判定できる。
【００１５】
請求項２に記載の発明によれば、木構造パターンにおける検査対象要素とその１つの子要素との間に要素を追加したパターンと探索されるパターンが重複する場合に伸張探索を省略できる。
【００１６】
請求項３に記載の発明によれば、木構造パターンにおける検査対象要素とその複数の子要素との間に設けられる分岐要素を追加したパターンと探索されるパターンが重複する場合に伸張探索を省略できる。
【００１７】
請求項４に記載の発明によれば、木構造パターンにおける検査対象要素に新たな子要素を追加したパターンと探索されるパターンが重複する場合に伸張探索を省略できる。
【００１８】
請求項５に記載の発明によれば、本構成を有しない場合と比較して、冗長な探索となるか否かの判定を効率化できる。
【００１９】
請求項６に記載の発明によれば、複数の木構造情報に頻出する木構造パターンがより多くの要素を有するように伸張する際に冗長な伸張探索処理のステップ数を低減できる。
【図面の簡単な説明】
【００２０】
【図１】本実施形態に係る情報抽出装置の機能ブロック図である。
【図２】ツリーデータの一例を示した図である。
【図３】探索される木構造パターンの一例を示した図である。
【図４】ＲＭＰ上に設定された伸張箇所の一例を示した図である。
【図５】第１冗長性判定部における、検査対象ノードに関する検査範囲を示した図である。
【図６】第２冗長性判定部における、検査対象ノードに関する検査範囲を示した図である。
【図７】１エッジ上ノードと分岐点ノードとが共に含まれるツリーデータの一例を示す図である。
【図８】伸張箇所の上位に検査対象ノードがある場合に設定される集計基準位置の一例を示した図である。
【図９】伸張箇所、検査対象ノードが一致する場合に設定される集計基準位置の一例を示した図である。
【図１０】伸張箇所の下位に検査対象ノードが位置する場合に設定される集計基準位置の一例を示した図である。
【図１１】ツリーデータから探索されるパターンの例を示した図である。
【図１２】情報抽出処理のフローチャートである。
【図１３】伸張探索処理のフローチャートである。
【図１４】冗長性判定処理のフローチャートである。
【発明を実施するための形態】
【００２１】
以下、本発明を実施するための実施の形態（以下、実施形態という）を、図面に従って説明する。
【００２２】
図１には、本実施形態に係る情報抽出装置１０の機能ブロック図を示した。図１に示されるように、情報抽出装置１０は、ツリーデータ保持部１２、パターン候補探索部１４、パターン情報保持部１６、パターン出現情報保持部１８、パターン伸張箇所選択部２０、伸張パターン存在範囲管理部２２、及び冗長性判定部２４を含む。上記の各部の機能は、ＣＰＵ等の制御手段、メモリ等の記憶手段、外部デバイスとデータを送受信する入出力手段等を備えたコンピュータが、コンピュータ読み取り可能な情報記憶媒体に格納されたプログラムを読み込み実行することで実現されるものとしてよい。なお、プログラムは情報記憶媒体によってコンピュータたる情報抽出装置１０に供給されることとしてもよいし、インターネット等のデータ通信手段を介して供給されることとしてもよい。以下、情報抽出装置１０が有する各部の機能について詳細に説明する。
【００２３】
ツリーデータ保持部１２は、半導体メモリや磁気ディスク装置等の記憶装置を含み構成され、複数の木構造情報（以下、ツリーデータ）を保持するものである。ツリーデータは、複数の要素（以下、ノード）をその親子関係に基づいて接続したデータである。なお、ツリーデータにおいて頂点に位置するノードをルートノード、末端に位置するノードをリーフノード、ノード間を接続する線をエッジ、ルートノードからリーフノードへと辿る経路をパス、各ノードに該当する具体的情報をラベルと呼称する。ツリーデータ保持部１２に保持されるツリーデータは、図示しない入力デバイスを介してユーザーから入力されてもよいし、他のデバイスからのデータ転送により取得することとしてもよい。
【００２４】
図２には、ツリーデータ保持部１２に保持されるツリーデータの一例を示した。図２に示されたツリーデータは、ツリーデータ保持部１２に保持される複数のツリーデータの一部である。本実施形態では、ツリーデータ保持部１２に保持される複数のツリーデータのうち予め定められた条件を満たす木構造のパターンを抽出する処理を行う。上記条件は、例えば複数のツリーデータの中から予め定められた数（又は割合）のツリーデータに共通した、先祖子孫関係が一致する木構造のパターンであること（すなわちＥｍｂｅｄｄｅｄ Ｓｕｂｔｒｅｅ Ｍｉｎｉｎｇを用いる）としてよい。木構造のパターンを抽出する対象とするツリーデータは、ツリーデータ保持部１２に保持されるツリーデータのすべてとしてもよいし、その一部を選択することとしてもよい。
【００２５】
パターン候補探索部１４は、ツリーデータ保持部１２に保持される複数のツリーデータの中から指定されたパターンに合致する候補を探索するものである。具体的には、パターン候補探索部１４は、処理時点で得られている木構造のパターンに要素を加えて伸張したパターンに該当する候補を各ツリーデータから探索し、探索された候補が予め定められた条件（例えば予め定められた数以上あること）を満たせば、当該候補を上記の木構造のパターンに加えていく探索処理を行うものである。なお、パターン候補探索部１４は、伸張パターンの探索を、伸張箇所の候補となるノードを各ツリーデータから探索することにより行うこととしてよい。また、パターン候補探索部１４は、各ツリーデータに頻出する木構造のパターンについて指定された初期パターンが存在する場合には当該初期パターンに基づいて探索処理を開始することとしてよく、指定された初期パターンが存在しない場合には１ノードを初期パターンとして探索処理を開始することとしてよい。
【００２６】
パターン情報保持部１６は、パターン候補探索部１４により探索された木構造パターンを保持するものである。パターン情報保持部１６は、パターン候補探索部１４により順次探索された木構造パターンをすべて保持することとしてもよいし、その一部を選択的に保持することとしてもよい。
【００２７】
パターン出現情報保持部１８は、パターン候補探索部１４により探索された木構造パターンがツリーデータ保持部１２に保持される各ツリーデータのどこに出現しているかを示すパターン出現情報を保持するものである。
【００２８】
パターン伸張箇所選択部２０は、パターン情報保持部１６に保持される木構造パターンにノードを追加して伸張する箇所を選択するものである。本実施形態では木構造パターンを深さ優先により探索する（深さ優先探索）こととし、パターン伸張箇所選択部２０は、伸張対象とする木構造パターンの右端のパス（以下、ＲＭＰ（Right Most Path））を選択し、当該選択したＲＭＰのノード又はエッジを新たなノードを追加する伸張箇所として選択することとしてよい。なお、深さ優先探索とは、探索を開始するノードから下方向にパスを辿っていき、複数のパスに分岐するノードでは左側のノードを選択してリーフノードに至るまで探索し、リーフノードに至ると、他のパスとの分岐点まで戻り、分岐点からは当該他のパスを辿り、ここでも分岐点では左側のノードを選択してリーフノードに至るまで探索する、という処理を繰り返す探索である。
【００２９】
図３には、探索される木構造パターンの一例を、図４にはＲＭＰ上に設定された伸張箇所の一例を示した。図３は、ツリーデータに共通して含まれる木構造パターンの一例であり、右端のパスがＲＭＰとなる。
【００３０】
図４に示されるように、ＲＭＰへのノードの追加は、図４（Ａ）のようにＲＭＰの各ノードの新たな子ノードとして追加することとしてもよいし、図４（Ｂ）のようにノードとノード間のエッジ上にノードを入れ込むものも含むこととしてもよい。
【００３１】
伸張パターン存在範囲管理部２２は、パターン伸張箇所選択部２０により選択された伸張箇所にノードを追加した部分木構造が存在するツリーデータ上の存在範囲を管理するものである。伸張パターン存在範囲管理部２２は、伸張ノードを追加する前の木構造パターンのツリーデータ上における出現箇所に基づいて、上記存在範囲を特定し管理することとしてよい。伸張パターン存在範囲管理部２２において管理される情報は、伸張箇所が選択された際に伸張パターンの存在範囲を絞り込む際に用いられるとともに、伸張パターンの候補を探索する際にも用いられることとしてよい。
【００３２】
冗長性判定部２４は、検査対象ノード選択部２６、第１冗長性判定部２８、第２冗長性判定部３０、第３冗長性判定部３２、集計基準位置設定部３４を含み、パターン伸張箇所選択部２０により選択された伸張箇所にノードを追加したパターンが冗長な探索となるか否かを判定するものである。冗長な探索となると判定された場合にはそのパターンについての探索処理は省略される。以下、冗長性判定部２４による判定処理の詳細について説明する。
【００３３】
検査対象ノード選択部２６は、伸張箇所が選択されたパターンに含まれるノードの１つを検査対象ノードとして順次選択するものである。検査対象ノード選択部２６による検査対象ノードの選択順序は特に限定されるものではなく、例えば左側のパスの上位ノードから順に選択することとしてもよいし、伸張箇所の兄弟ノード、親ノード、子ノード等の周囲にあるノードから順に選択することとしてもよい。後者の方法により、ＸＭＬデータのように構造が定義されているデータにおいて伸張箇所と同じラベルが出現し易い伸張箇所の周囲のノードから検査を行うことで、他の部分から検査を行う場合に比べて枝刈処理の効率が向上する。
【００３４】
第１冗長性判定部２８は、検査対象ノード選択部２６により選択された検査対象ノードに新たなリーフノードを追加したパターンが冗長な探索となるか否かを判定するものである。具体的には、第１冗長性判定部２８は、パターン伸張箇所と、検査対象ノードとに基づいて定められた、パターンの探索がすでに行われているか、パターンを包含する他のパターンの探索範囲となる範囲に、検査対象ノードについてラベルが共通する新たなリーフノードが存在する場合には、冗長性ありと判定する。
【００３５】
図５には、第１冗長性判定部２８における、検査対象ノードに関する検査範囲を示した。図５においては、パターンにおける検査対象ノードとその子ノードをツリーデータ上で対応させた例を示している。図５に示されるように、検査対象ノードに関する検査範囲は、まず、検査対象ノードに接続する各子ノードの左側の領域が選ばれ、そして検査対象ノードがＲＭＰにあるか否か、そして伸張箇所と検査対象ノードとの位置関係に応じて右端の子ノードの右側の領域も検査範囲に選ばれる。そして、各ツリーデータについて定めた検査範囲から同じラベルのノードが検出された場合には冗長性ありと判定される。また、第１冗長性判定部２８は、検査対象ノードがルートノードである場合に、当該ルートノードに新たなルートノードを追加したパターンが冗長な探索となるか否かについても判定することとしてよい。
【００３６】
第２冗長性判定部３０は、検査対象ノード選択部２６により選択された検査対象ノードとその１つの子ノードとの間に新たなノード（１エッジ上ノード）を追加したパターンが冗長な探索となるか否かを判定するものである。具体的には、第２冗長性判定部３０は、パターン伸張箇所と、検査対象ノードとに基づいて定められた、パターンの探索がすでに行われているか、パターンを包含する他のパターンの探索範囲となる範囲に、検査対象ノードについてラベルが共通する新たな１エッジ上ノードが存在する場合には、冗長性ありと判定する。なお、検査対象ノードに子ノードがない場合には１エッジ上ノードは存在しないため、第２冗長性判定部３０による冗長性判定を省略してよい。
【００３７】
図６には、第２冗長性判定部３０における、検査対象ノードに関する検査範囲を示した。図６においては、パターンにおける検査対象ノードとその子ノードをツリーデータ上で対応させた例を示している。図６に示されるように、検査対象ノードに関する検査範囲は、検査対象ノードとその子ノードとの間の領域となる。そして、各ツリーデータについて定めた検査範囲から同じラベルのノードが検出された場合には冗長性ありと判定される。ただし、図７に例示されるように、検査対象ノードに複数の子ノードがあり、検査対象ノードとその一部の子ノードの分岐点ノードとなるノードは１エッジ上ノードには該当しないため、こうしたノードはラベルの検出対象から除外する。
【００３８】
第３冗長性判定部３２は、検査対象ノード選択部２６により選択された検査対象ノードとその複数の子ノードとの間に各ノードに接続する新たなノード（分岐点ノード）を追加したパターンが冗長な探索となるか否かを判定するものである。具体的には、第３冗長性判定部３２は、パターン伸張箇所と、検査対象ノードに基づいて定められた、パターンの探索がすでに行われているか、パターンを包含する他のパターンの探索範囲となる範囲に、検査対象ノードについてラベルが共通する新たな分岐点ノードが存在する場合には、冗長性ありと判定する。分岐点ノードは、図７におけるノードＬａに相当し、当該ノードＬａが検査範囲となる。なお、検査対象ノードに複数の子ノードがない場合には分岐点ノードは存在しないため、第３冗長性判定部３２による冗長性判定を省略してよい。
【００３９】
なお、第３冗長性判定部３２は、検査対象ノードの子ノードに関して取り得る組み合わせの各々について検査範囲を定め、ラベルが共通する分岐点ノードの存在を検査することとする。
【００４０】
集計基準位置設定部３４は、検査対象ノードと伸張箇所とに基づいて、伸張箇所を伸張させたパターンが冗長な探索となるか否かを判定する際にラベルが共通する新リーフノード、１エッジ上ノード、又は分岐点ノードの存在を集計する基準となるツリーデータ上の位置（集計基準位置）を設定するものである。集計基準位置設定部３４は、ツリーデータ上において、パターンの伸張箇所に該当するノードが複数存在する場合に、検査対象ノード、伸張箇所に基づいて、集計基準位置を設定する。例えば集計基準位置は、検査対象ノードが存在するパス上から、検査対象ノードと伸張箇所と検査対象パターンの子ノードとの関係に応じて選択した位置としてよい。この集計基準位置の設定の具体例については以下に述べる。
【００４１】
図８には、伸張箇所の上位に検査対象ノードがある場合に設定される集計基準位置の一例を示した。図８（Ａ）に示されるように、ツリーデータ上において伸張箇所に該当するノードが複数あり、さらに検査対象ノードの出現箇所も複数ある場合に、集計基準位置となり得るノードのうち最上位にあるものを集計基準位置として設定することとしてよい。
【００４２】
また、図８（Ｂ）に示されるように、ツリーデータ上において伸張箇所に該当するノードが複数あり、伸張箇所とは異なるパス上に検査対象ノードの出現箇所が複数ある場合には、伸張箇所、検査対象ノードがそれぞれ存在するパスが上位側で交わる位置を集計基準位置として設定することとしてよい。
【００４３】
図９には、伸張箇所、検査対象ノードが一致する場合に設定される集計基準位置の一例を示した。図９に例示されるように、伸張箇所と検査対象ノードが一致する場合であって、ツリーデータ上において伸張箇所に該当するノードが複数ある場合に、集計基準位置は伸張箇所の最上位の位置として設定することとしてよい。
【００４４】
図１０には、伸張箇所の下位に検査対象ノードが位置する場合に設定される集計基準位置の一例を示した。図１０に示されるように、ツリーデータ上において伸張箇所の子ノードのうちより下位に位置するものの位置に応じて集計基準位置を設定することとしてよい。
【００４５】
冗長性の判定は、各ツリーデータについて設定した集計基準位置について他のツリーデータとの共通ラベルがあったか否かのフラグを記録し、すべての集計基準位置について他のツリーデータとの共通ラベルがあったとのフラグが記録された場合に冗長性があると判定し、そうでない場合には冗長性がないと判定することで行うこととしてよい。そして、冗長性判定部２４は、第１乃至第３冗長性判定部３２のいずれかにより冗長性があると判定された場合に冗長性ありと判定することとする。
【００４６】
パターン候補探索部１４は、処理対象とするパターンの伸張箇所について冗長性判定部２４により冗長性があると判定された場合にはその伸張箇所を伸張したパターンについての探索処理は行わないこととし、冗長性がないと判定されたパターンについてのみ探索処理を行うこととする。パターン候補探索部１４により伸張されたパターンに基づいて探索された新たな木構造パターンはパターン情報保持部１６に格納される。そして情報抽出装置１０は、パターンの探索、探索されたパターンの伸張箇所の選択、選択された伸張箇所の冗長性判定、冗長性がない伸張パターンに基づくパターンの探索という処理を再帰的に繰り返すことで、より要素数の多い木構造パターンを抽出する。
【００４７】
図１１には、図２に示したツリーデータから探索されるパターンの例を示した。拡張パターンの探索される順序により、図１１に示されるパターンＰ１とパターンＰ１を拡張したパターンが既に探索された後に、他のパターンＰ２〜Ｐ４を伸張しようとする際には、以下の冗長性判定が行われる。
【００４８】
まず、パターンＰ２のラベルＡのノードを伸張箇所、ラベルＢのノードを検査対象ノードとすると、第１冗長性判定部２８により検査対象ノードの子ノードであるラベルＤのノードが検査範囲から共通して見つかるため、このパターンＰ２の上記伸張箇所にノードを追加した伸張パターンは冗長な探索となると判定される。
【００４９】
次に、パターンＰ３のラベルＣのノードを伸張箇所、ラベルＡのノードを検査対象ノードとすると、第２冗長性判定部３０により検査対象ノードとその子ノードＫとの間に設けられる１エッジ上ノードにラベルＪのノードが共通して見つかるため、このパターンＰ３の上記伸張箇所にノードを追加した伸張パターンは冗長な探索となると判定される。
【００５０】
さらに、パターンＰ４のラベルＣのノードを伸張箇所、ラベルＡのノードを検査対象ノードとすると、第３冗長性判定部３２により検査対象ノードとその子ノードＤ，Ｅとの間に設けられる分岐点ノードにラベルＢのノードが共通して見つかるため、このパターンＰ４の上記伸張箇所にノードを追加した伸張パターンは冗長な探索となると判定される。
【００５１】
次に、図１２，図１３，図１４に示したフローチャートを参照しながら、情報抽出装置１０により行われる処理の流れの例を説明する。
【００５２】
図１２は、情報抽出装置１０により行われる情報抽出処理の例を示すフローチャートを示している。図１２に示されるように、情報抽出装置１０はツリーデータ保持部１２に保持されるツリーデータについて頻出するノード（頻出ノード）を探索し（Ｓ１０１）、未処理の頻出ノードが残っている場合には（Ｓ１０２：Ｙ）、未処理の頻出ノードを選択して（Ｓ１０３）、パターンデータを作成して（Ｓ１０４）、パターンの伸張探索処理を行う（Ｓ１０５）。パターンの伸張探索処理の詳細については後述する。パターンの伸張探索処理が終了するとＳ１０２に戻り、未処理の頻出ノードが残っていない場合には（Ｓ１０２：Ｎ）、処理を終了する。
【００５３】
図１３は、パターンの伸張探索処理の例を示すフローチャートを示している。図１３に示されるように、情報抽出装置１０は、パターンからＲＭＰを選定し（Ｓ２０１）、選定したＲＭＰ上に未処理の伸張箇所があるか否かを判断する（Ｓ２０２）。ここで、情報抽出装置１０は、未処理の伸張箇所があると判断する場合には（Ｓ２０２：Ｙ）、未処理の伸張箇所の１つを選択し（Ｓ２０３）、伸張箇所にノードを追加した伸張パターンの冗長性判定処理を行う（Ｓ２０４）。冗長性判定処理の詳細については後述する。
【００５４】
情報抽出装置１０は、冗長性判定処理により冗長性があると判定された場合には（Ｓ２０５：Ｙ）、その判定結果を記録し、処理Ｓ２０２に戻ってそれ以降の処理を繰り返す。一方で、情報抽出装置１０は、冗長性判定処理により冗長性がないと判定された場合には（Ｓ２０５：Ｎ）、伸張箇所にノードを追加した伸張パターンの候補をツリーデータから探索する（Ｓ２０６）。
【００５５】
情報抽出装置１０は、探索されたパターンの候補について未処理のものがある場合には（Ｓ２０７：Ｙ）、未処理のパターン候補を１つ選択し（Ｓ２０８）、パターンの伸張探索処理を再帰的に実行する（Ｓ２０９）。そして、情報抽出装置１０は、未処理のパターン候補がなくなると（Ｓ２０７：Ｎ）、Ｓ２０２に戻りそれ以降の処理を繰り返す。なお、Ｓ２０２において未処理の伸張箇所がないと判断された場合には（Ｓ２０２：Ｎ）、親プロセスにリターンする。
【００５６】
図１４には、冗長性判定処理の例を示すフローチャートを示した。図１４に示されるように、情報抽出装置１０は、伸張箇所が選定されたパターンの中から未処理の検査対象ノードがある場合には（Ｓ３０１：Ｙ）、未処理の検査対象ノードを１つ選択する（Ｓ３０２）。
【００５７】
情報抽出装置１０は、検査対象ノードに対する新たなリーフノードを追加したパターンが冗長な探索となるか否かを判定（第１冗長性判定）し（Ｓ３０３）、冗長な探索となると判定した場合には（Ｓ３０３：Ｙ）、冗長性ありと記録して（Ｓ３０６）、リターンする。また、情報抽出装置１０は、第１冗長性判定により冗長性が判定されない場合には（Ｓ３０３：Ｎ）、検査対象ノードとその子ノードとの間に設けられる１エッジ上ノードを追加したパターンが冗長な探索となるか否かを判定（第２冗長性判定）し（Ｓ３０４）、冗長な探索となると判定した場合には（Ｓ３０４：Ｙ）、冗長性ありと記録して（Ｓ３０６）、リターンする。さらに、情報抽出装置１０は、第２冗長性判定により冗長性が判定されない場合には（Ｓ３０４：Ｎ）、検査対象ノードとその複数の子ノードとの間に設けられる分岐点ノードを追加したパターンが冗長な探索となるか否かを判定（第３冗長性判定）し（Ｓ３０５）、冗長な探索となると判定した場合には（Ｓ３０４：Ｙ）、冗長性ありと記録して（Ｓ３０６）、リターンする。情報抽出装置１０は、未処理の検査対象ノードがなくなった場合には（Ｓ３０１：Ｎ）、冗長性なしと記録して（Ｓ３０７）、リターンする。
【００５８】
なお、上記の冗長性判定処理では、第１冗長性判定から第３冗長性判定の順に実行することとしたが、冗長性判定の順序はこれに限定されない。また、上記の冗長性判定処理において、検査対象ノードの子ノードの有無及び子ノードの数に応じて第１冗長性判定から第３冗長性判定の中から不要な冗長性判定処理を省略することとしてよい。
【００５９】
上記の実施形態に係る情報抽出装置１０では、Ｅｍｂｅｄｄｅｄ Ｓｕｂｔｒｅｅ Ｍｉｎｉｎｇにおいて、探索されたパターンを伸張した伸張パターンについての探索を開始する前に、パターンの内部にノードを埋め込んだ場合に他のパターンとの関係で冗長な探索となるか否かを判別し、冗長と判別された伸張パターンについての探索を行わないようにしたことで、こうした構成を有さない場合に比べて、ツリーデータに頻出する木構造パターンを抽出するのに要する処理ステップの数が低減される。
【００６０】
本発明は上記の実施形態に限定されるものではなく、例えば上記の実施形態では伸張箇所をＲＭＰから選択しているが、パターン探索のアルゴリズムを適切に設定すれば左端のパス（ＬＭＰ）や他の条件に基づいて選択されたパスから選択することとしても構わない。
【符号の説明】
【００６１】
１０ 情報抽出装置、１２ ツリーデータ保持部、１４ パターン候補探索部、１６ パターン情報保持部、１８ パターン出現情報保持部、２０ パターン伸張箇所選択部、２２ 伸張パターン存在範囲管理部、２４ 冗長性判定部、２６ 検査対象ノード選択部、２８ 第１冗長性判定部、３０ 第２冗長性判定部、３２ 第３冗長性判定部、３４ 集計基準位置設定部。
【技術分野】
【０００１】
本発明は、プログラム及び情報抽出装置に関する。
【背景技術】
【０００２】
多量のデータを分析して有意な情報を引き出すデータマイニングという技術がある。こうしたデータマイニングでは扱うデータ量が増加すると計算コストが指数関数的に増加するため、冗長な処理を省略することが行われている。例えば下記の特許文献１には、冗長となるパターンを省略して処理する枝刈処理が記載されている。
【０００３】
また、ＸＭＬ等の木構造情報（ツリーデータ）群に頻出する木構造のパターンを抽出するサブツリーマイニングに関し、要素の親子関係が厳密に一致する木構造のパターンを得るＩｎｄｕｃｅｄ Ｓｕｂｔｒｅｅ Ｍｉｎｉｎｇでは、木構造のパターンを伸張する際に既に探索した範囲から木構造のパターンの末端に共通する要素を追加できる場合（すなわち、新たなリーフノードを追加できる場合）には、上記木構造のパターンの伸張探索処理を省略しているものがある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１０−３０１９４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
要素間の親子関係が厳密に保たれていなくとも先祖子孫関係が保たれていれば同じ木構造のパターンとして抽出するＥｍｂｅｄｄｅｄ Ｓｕｂｔｒｅｅ Ｍｉｎｉｎｇでは、木構造のパターンの末端だけではなく内部にも要素が追加された場合を考慮して冗長な探索を招くか否かを判定する必要がある。
【０００６】
本発明の目的は、複数の木構造情報に頻出する木構造パターンを伸張しながら探索する過程でその木構造パターンの内部に要素を追加した場合に冗長な探索を招く木構造パターンを判定するプログラム及び情報抽出装置を提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、請求項１に記載の発明は、コンピュータを、複数の木構造情報の中から予め定められた数の木構造情報に共通して含まれる木構造のパターンを保持する保持手段、前記保持手段に保持された木構造のパターンから予め定められた条件に基づいてパスを選択するとともに、当該選択されたパスに要素を追加して前記木構造のパターンを伸張する伸張箇所を選択する選択手段、及び、前記木構造のパターンに含まれるいずれかの要素を検査対象要素とし、前記木構造のパターンにおける前記検査対象要素と前記伸張箇所とに基づいて前記複数の木構造情報のそれぞれについて定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその子要素との間に要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する判定手段として機能させるためのプログラムである。
【０００８】
また、請求項２に記載の発明は、請求項１に記載のプログラムにおいて、前記判定手段は、前記定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその１つの子要素との間に要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定することを特徴とする。
【０００９】
また、請求項３に記載の発明は、請求項１又は２に記載のプログラムにおいて、前記判定手段は、前記定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその複数の子要素とのそれぞれに接続する要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定することを特徴とする。
【００１０】
また、請求項４に記載の発明は、請求項１から３のいずれかに記載のプログラムにおいて、前記判定手段はさらに、前記定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素に新たな子要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定することを特徴とする。
【００１１】
また、請求項５に記載の発明は、請求項１から４のいずれかに記載のプログラムにおいて、前記コンピュータをさらに、前記木構造のパターンにおける前記検査対象要素と前記伸張箇所とに基づいて、前記複数の木構造情報のそれぞれについて前記検査対象要素とその子要素との間に追加された要素の候補を検出する基準位置を設定する設定手段として機能させるためのプログラムである。
【００１２】
また、請求項６に記載の発明は、請求項１から５のいずれかに記載のプログラムにおいて、前記コンピュータをさらに、前記判定手段により前記木構造のパターンの前記伸張箇所に新たな要素を追加した伸張パターンの探索を行うと判定した場合に、当該伸張パターンの候補を前記複数の木構造情報の中から探索する探索手段、前記探索手段により探索された前記伸張パターンの候補に基づいて生成した木構造のパターンを前記保持手段に保持させる手段、前記保持手段に保持された木構造のパターンを前記選択手段、前記判定手段、前記探索手段により伸張する処理を再帰的に実行する手段として機能させるためのプログラムである。
【００１３】
また、請求項７に記載の発明は、複数の木構造情報の中から予め定められた数の木構造情報に共通して含まれる木構造のパターンを保持する保持手段と、前記保持手段に保持された木構造のパターンから予め定められた条件に基づいてパスを選択するとともに、当該選択されたパスに要素を追加して前記木構造のパターンを伸張する伸張箇所を選択する選択手段と、前記木構造のパターンに含まれるいずれかの要素を検査対象要素とし、前記木構造のパターンにおける前記検査対象要素と前記伸張箇所とに基づいて前記複数の木構造情報のそれぞれについて定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその子要素との間に要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する判定手段と、を含むことを特徴とする情報抽出装置である。
【発明の効果】
【００１４】
請求項１及び７に記載の発明によれば、複数の木構造情報に頻出する木構造パターンを伸張しながら探索する過程でその木構造パターンの内部に要素を追加した場合に冗長な探索を招く木構造パターンを判定できる。
【００１５】
請求項２に記載の発明によれば、木構造パターンにおける検査対象要素とその１つの子要素との間に要素を追加したパターンと探索されるパターンが重複する場合に伸張探索を省略できる。
【００１６】
請求項３に記載の発明によれば、木構造パターンにおける検査対象要素とその複数の子要素との間に設けられる分岐要素を追加したパターンと探索されるパターンが重複する場合に伸張探索を省略できる。
【００１７】
請求項４に記載の発明によれば、木構造パターンにおける検査対象要素に新たな子要素を追加したパターンと探索されるパターンが重複する場合に伸張探索を省略できる。
【００１８】
請求項５に記載の発明によれば、本構成を有しない場合と比較して、冗長な探索となるか否かの判定を効率化できる。
【００１９】
請求項６に記載の発明によれば、複数の木構造情報に頻出する木構造パターンがより多くの要素を有するように伸張する際に冗長な伸張探索処理のステップ数を低減できる。
【図面の簡単な説明】
【００２０】
【図１】本実施形態に係る情報抽出装置の機能ブロック図である。
【図２】ツリーデータの一例を示した図である。
【図３】探索される木構造パターンの一例を示した図である。
【図４】ＲＭＰ上に設定された伸張箇所の一例を示した図である。
【図５】第１冗長性判定部における、検査対象ノードに関する検査範囲を示した図である。
【図６】第２冗長性判定部における、検査対象ノードに関する検査範囲を示した図である。
【図７】１エッジ上ノードと分岐点ノードとが共に含まれるツリーデータの一例を示す図である。
【図８】伸張箇所の上位に検査対象ノードがある場合に設定される集計基準位置の一例を示した図である。
【図９】伸張箇所、検査対象ノードが一致する場合に設定される集計基準位置の一例を示した図である。
【図１０】伸張箇所の下位に検査対象ノードが位置する場合に設定される集計基準位置の一例を示した図である。
【図１１】ツリーデータから探索されるパターンの例を示した図である。
【図１２】情報抽出処理のフローチャートである。
【図１３】伸張探索処理のフローチャートである。
【図１４】冗長性判定処理のフローチャートである。
【発明を実施するための形態】
【００２１】
以下、本発明を実施するための実施の形態（以下、実施形態という）を、図面に従って説明する。
【００２２】
図１には、本実施形態に係る情報抽出装置１０の機能ブロック図を示した。図１に示されるように、情報抽出装置１０は、ツリーデータ保持部１２、パターン候補探索部１４、パターン情報保持部１６、パターン出現情報保持部１８、パターン伸張箇所選択部２０、伸張パターン存在範囲管理部２２、及び冗長性判定部２４を含む。上記の各部の機能は、ＣＰＵ等の制御手段、メモリ等の記憶手段、外部デバイスとデータを送受信する入出力手段等を備えたコンピュータが、コンピュータ読み取り可能な情報記憶媒体に格納されたプログラムを読み込み実行することで実現されるものとしてよい。なお、プログラムは情報記憶媒体によってコンピュータたる情報抽出装置１０に供給されることとしてもよいし、インターネット等のデータ通信手段を介して供給されることとしてもよい。以下、情報抽出装置１０が有する各部の機能について詳細に説明する。
【００２３】
ツリーデータ保持部１２は、半導体メモリや磁気ディスク装置等の記憶装置を含み構成され、複数の木構造情報（以下、ツリーデータ）を保持するものである。ツリーデータは、複数の要素（以下、ノード）をその親子関係に基づいて接続したデータである。なお、ツリーデータにおいて頂点に位置するノードをルートノード、末端に位置するノードをリーフノード、ノード間を接続する線をエッジ、ルートノードからリーフノードへと辿る経路をパス、各ノードに該当する具体的情報をラベルと呼称する。ツリーデータ保持部１２に保持されるツリーデータは、図示しない入力デバイスを介してユーザーから入力されてもよいし、他のデバイスからのデータ転送により取得することとしてもよい。
【００２４】
図２には、ツリーデータ保持部１２に保持されるツリーデータの一例を示した。図２に示されたツリーデータは、ツリーデータ保持部１２に保持される複数のツリーデータの一部である。本実施形態では、ツリーデータ保持部１２に保持される複数のツリーデータのうち予め定められた条件を満たす木構造のパターンを抽出する処理を行う。上記条件は、例えば複数のツリーデータの中から予め定められた数（又は割合）のツリーデータに共通した、先祖子孫関係が一致する木構造のパターンであること（すなわちＥｍｂｅｄｄｅｄ Ｓｕｂｔｒｅｅ Ｍｉｎｉｎｇを用いる）としてよい。木構造のパターンを抽出する対象とするツリーデータは、ツリーデータ保持部１２に保持されるツリーデータのすべてとしてもよいし、その一部を選択することとしてもよい。
【００２５】
パターン候補探索部１４は、ツリーデータ保持部１２に保持される複数のツリーデータの中から指定されたパターンに合致する候補を探索するものである。具体的には、パターン候補探索部１４は、処理時点で得られている木構造のパターンに要素を加えて伸張したパターンに該当する候補を各ツリーデータから探索し、探索された候補が予め定められた条件（例えば予め定められた数以上あること）を満たせば、当該候補を上記の木構造のパターンに加えていく探索処理を行うものである。なお、パターン候補探索部１４は、伸張パターンの探索を、伸張箇所の候補となるノードを各ツリーデータから探索することにより行うこととしてよい。また、パターン候補探索部１４は、各ツリーデータに頻出する木構造のパターンについて指定された初期パターンが存在する場合には当該初期パターンに基づいて探索処理を開始することとしてよく、指定された初期パターンが存在しない場合には１ノードを初期パターンとして探索処理を開始することとしてよい。
【００２６】
パターン情報保持部１６は、パターン候補探索部１４により探索された木構造パターンを保持するものである。パターン情報保持部１６は、パターン候補探索部１４により順次探索された木構造パターンをすべて保持することとしてもよいし、その一部を選択的に保持することとしてもよい。
【００２７】
パターン出現情報保持部１８は、パターン候補探索部１４により探索された木構造パターンがツリーデータ保持部１２に保持される各ツリーデータのどこに出現しているかを示すパターン出現情報を保持するものである。
【００２８】
パターン伸張箇所選択部２０は、パターン情報保持部１６に保持される木構造パターンにノードを追加して伸張する箇所を選択するものである。本実施形態では木構造パターンを深さ優先により探索する（深さ優先探索）こととし、パターン伸張箇所選択部２０は、伸張対象とする木構造パターンの右端のパス（以下、ＲＭＰ（Right Most Path））を選択し、当該選択したＲＭＰのノード又はエッジを新たなノードを追加する伸張箇所として選択することとしてよい。なお、深さ優先探索とは、探索を開始するノードから下方向にパスを辿っていき、複数のパスに分岐するノードでは左側のノードを選択してリーフノードに至るまで探索し、リーフノードに至ると、他のパスとの分岐点まで戻り、分岐点からは当該他のパスを辿り、ここでも分岐点では左側のノードを選択してリーフノードに至るまで探索する、という処理を繰り返す探索である。
【００２９】
図３には、探索される木構造パターンの一例を、図４にはＲＭＰ上に設定された伸張箇所の一例を示した。図３は、ツリーデータに共通して含まれる木構造パターンの一例であり、右端のパスがＲＭＰとなる。
【００３０】
図４に示されるように、ＲＭＰへのノードの追加は、図４（Ａ）のようにＲＭＰの各ノードの新たな子ノードとして追加することとしてもよいし、図４（Ｂ）のようにノードとノード間のエッジ上にノードを入れ込むものも含むこととしてもよい。
【００３１】
伸張パターン存在範囲管理部２２は、パターン伸張箇所選択部２０により選択された伸張箇所にノードを追加した部分木構造が存在するツリーデータ上の存在範囲を管理するものである。伸張パターン存在範囲管理部２２は、伸張ノードを追加する前の木構造パターンのツリーデータ上における出現箇所に基づいて、上記存在範囲を特定し管理することとしてよい。伸張パターン存在範囲管理部２２において管理される情報は、伸張箇所が選択された際に伸張パターンの存在範囲を絞り込む際に用いられるとともに、伸張パターンの候補を探索する際にも用いられることとしてよい。
【００３２】
冗長性判定部２４は、検査対象ノード選択部２６、第１冗長性判定部２８、第２冗長性判定部３０、第３冗長性判定部３２、集計基準位置設定部３４を含み、パターン伸張箇所選択部２０により選択された伸張箇所にノードを追加したパターンが冗長な探索となるか否かを判定するものである。冗長な探索となると判定された場合にはそのパターンについての探索処理は省略される。以下、冗長性判定部２４による判定処理の詳細について説明する。
【００３３】
検査対象ノード選択部２６は、伸張箇所が選択されたパターンに含まれるノードの１つを検査対象ノードとして順次選択するものである。検査対象ノード選択部２６による検査対象ノードの選択順序は特に限定されるものではなく、例えば左側のパスの上位ノードから順に選択することとしてもよいし、伸張箇所の兄弟ノード、親ノード、子ノード等の周囲にあるノードから順に選択することとしてもよい。後者の方法により、ＸＭＬデータのように構造が定義されているデータにおいて伸張箇所と同じラベルが出現し易い伸張箇所の周囲のノードから検査を行うことで、他の部分から検査を行う場合に比べて枝刈処理の効率が向上する。
【００３４】
第１冗長性判定部２８は、検査対象ノード選択部２６により選択された検査対象ノードに新たなリーフノードを追加したパターンが冗長な探索となるか否かを判定するものである。具体的には、第１冗長性判定部２８は、パターン伸張箇所と、検査対象ノードとに基づいて定められた、パターンの探索がすでに行われているか、パターンを包含する他のパターンの探索範囲となる範囲に、検査対象ノードについてラベルが共通する新たなリーフノードが存在する場合には、冗長性ありと判定する。
【００３５】
図５には、第１冗長性判定部２８における、検査対象ノードに関する検査範囲を示した。図５においては、パターンにおける検査対象ノードとその子ノードをツリーデータ上で対応させた例を示している。図５に示されるように、検査対象ノードに関する検査範囲は、まず、検査対象ノードに接続する各子ノードの左側の領域が選ばれ、そして検査対象ノードがＲＭＰにあるか否か、そして伸張箇所と検査対象ノードとの位置関係に応じて右端の子ノードの右側の領域も検査範囲に選ばれる。そして、各ツリーデータについて定めた検査範囲から同じラベルのノードが検出された場合には冗長性ありと判定される。また、第１冗長性判定部２８は、検査対象ノードがルートノードである場合に、当該ルートノードに新たなルートノードを追加したパターンが冗長な探索となるか否かについても判定することとしてよい。
【００３６】
第２冗長性判定部３０は、検査対象ノード選択部２６により選択された検査対象ノードとその１つの子ノードとの間に新たなノード（１エッジ上ノード）を追加したパターンが冗長な探索となるか否かを判定するものである。具体的には、第２冗長性判定部３０は、パターン伸張箇所と、検査対象ノードとに基づいて定められた、パターンの探索がすでに行われているか、パターンを包含する他のパターンの探索範囲となる範囲に、検査対象ノードについてラベルが共通する新たな１エッジ上ノードが存在する場合には、冗長性ありと判定する。なお、検査対象ノードに子ノードがない場合には１エッジ上ノードは存在しないため、第２冗長性判定部３０による冗長性判定を省略してよい。
【００３７】
図６には、第２冗長性判定部３０における、検査対象ノードに関する検査範囲を示した。図６においては、パターンにおける検査対象ノードとその子ノードをツリーデータ上で対応させた例を示している。図６に示されるように、検査対象ノードに関する検査範囲は、検査対象ノードとその子ノードとの間の領域となる。そして、各ツリーデータについて定めた検査範囲から同じラベルのノードが検出された場合には冗長性ありと判定される。ただし、図７に例示されるように、検査対象ノードに複数の子ノードがあり、検査対象ノードとその一部の子ノードの分岐点ノードとなるノードは１エッジ上ノードには該当しないため、こうしたノードはラベルの検出対象から除外する。
【００３８】
第３冗長性判定部３２は、検査対象ノード選択部２６により選択された検査対象ノードとその複数の子ノードとの間に各ノードに接続する新たなノード（分岐点ノード）を追加したパターンが冗長な探索となるか否かを判定するものである。具体的には、第３冗長性判定部３２は、パターン伸張箇所と、検査対象ノードに基づいて定められた、パターンの探索がすでに行われているか、パターンを包含する他のパターンの探索範囲となる範囲に、検査対象ノードについてラベルが共通する新たな分岐点ノードが存在する場合には、冗長性ありと判定する。分岐点ノードは、図７におけるノードＬａに相当し、当該ノードＬａが検査範囲となる。なお、検査対象ノードに複数の子ノードがない場合には分岐点ノードは存在しないため、第３冗長性判定部３２による冗長性判定を省略してよい。
【００３９】
なお、第３冗長性判定部３２は、検査対象ノードの子ノードに関して取り得る組み合わせの各々について検査範囲を定め、ラベルが共通する分岐点ノードの存在を検査することとする。
【００４０】
集計基準位置設定部３４は、検査対象ノードと伸張箇所とに基づいて、伸張箇所を伸張させたパターンが冗長な探索となるか否かを判定する際にラベルが共通する新リーフノード、１エッジ上ノード、又は分岐点ノードの存在を集計する基準となるツリーデータ上の位置（集計基準位置）を設定するものである。集計基準位置設定部３４は、ツリーデータ上において、パターンの伸張箇所に該当するノードが複数存在する場合に、検査対象ノード、伸張箇所に基づいて、集計基準位置を設定する。例えば集計基準位置は、検査対象ノードが存在するパス上から、検査対象ノードと伸張箇所と検査対象パターンの子ノードとの関係に応じて選択した位置としてよい。この集計基準位置の設定の具体例については以下に述べる。
【００４１】
図８には、伸張箇所の上位に検査対象ノードがある場合に設定される集計基準位置の一例を示した。図８（Ａ）に示されるように、ツリーデータ上において伸張箇所に該当するノードが複数あり、さらに検査対象ノードの出現箇所も複数ある場合に、集計基準位置となり得るノードのうち最上位にあるものを集計基準位置として設定することとしてよい。
【００４２】
また、図８（Ｂ）に示されるように、ツリーデータ上において伸張箇所に該当するノードが複数あり、伸張箇所とは異なるパス上に検査対象ノードの出現箇所が複数ある場合には、伸張箇所、検査対象ノードがそれぞれ存在するパスが上位側で交わる位置を集計基準位置として設定することとしてよい。
【００４３】
図９には、伸張箇所、検査対象ノードが一致する場合に設定される集計基準位置の一例を示した。図９に例示されるように、伸張箇所と検査対象ノードが一致する場合であって、ツリーデータ上において伸張箇所に該当するノードが複数ある場合に、集計基準位置は伸張箇所の最上位の位置として設定することとしてよい。
【００４４】
図１０には、伸張箇所の下位に検査対象ノードが位置する場合に設定される集計基準位置の一例を示した。図１０に示されるように、ツリーデータ上において伸張箇所の子ノードのうちより下位に位置するものの位置に応じて集計基準位置を設定することとしてよい。
【００４５】
冗長性の判定は、各ツリーデータについて設定した集計基準位置について他のツリーデータとの共通ラベルがあったか否かのフラグを記録し、すべての集計基準位置について他のツリーデータとの共通ラベルがあったとのフラグが記録された場合に冗長性があると判定し、そうでない場合には冗長性がないと判定することで行うこととしてよい。そして、冗長性判定部２４は、第１乃至第３冗長性判定部３２のいずれかにより冗長性があると判定された場合に冗長性ありと判定することとする。
【００４６】
パターン候補探索部１４は、処理対象とするパターンの伸張箇所について冗長性判定部２４により冗長性があると判定された場合にはその伸張箇所を伸張したパターンについての探索処理は行わないこととし、冗長性がないと判定されたパターンについてのみ探索処理を行うこととする。パターン候補探索部１４により伸張されたパターンに基づいて探索された新たな木構造パターンはパターン情報保持部１６に格納される。そして情報抽出装置１０は、パターンの探索、探索されたパターンの伸張箇所の選択、選択された伸張箇所の冗長性判定、冗長性がない伸張パターンに基づくパターンの探索という処理を再帰的に繰り返すことで、より要素数の多い木構造パターンを抽出する。
【００４７】
図１１には、図２に示したツリーデータから探索されるパターンの例を示した。拡張パターンの探索される順序により、図１１に示されるパターンＰ１とパターンＰ１を拡張したパターンが既に探索された後に、他のパターンＰ２〜Ｐ４を伸張しようとする際には、以下の冗長性判定が行われる。
【００４８】
まず、パターンＰ２のラベルＡのノードを伸張箇所、ラベルＢのノードを検査対象ノードとすると、第１冗長性判定部２８により検査対象ノードの子ノードであるラベルＤのノードが検査範囲から共通して見つかるため、このパターンＰ２の上記伸張箇所にノードを追加した伸張パターンは冗長な探索となると判定される。
【００４９】
次に、パターンＰ３のラベルＣのノードを伸張箇所、ラベルＡのノードを検査対象ノードとすると、第２冗長性判定部３０により検査対象ノードとその子ノードＫとの間に設けられる１エッジ上ノードにラベルＪのノードが共通して見つかるため、このパターンＰ３の上記伸張箇所にノードを追加した伸張パターンは冗長な探索となると判定される。
【００５０】
さらに、パターンＰ４のラベルＣのノードを伸張箇所、ラベルＡのノードを検査対象ノードとすると、第３冗長性判定部３２により検査対象ノードとその子ノードＤ，Ｅとの間に設けられる分岐点ノードにラベルＢのノードが共通して見つかるため、このパターンＰ４の上記伸張箇所にノードを追加した伸張パターンは冗長な探索となると判定される。
【００５１】
次に、図１２，図１３，図１４に示したフローチャートを参照しながら、情報抽出装置１０により行われる処理の流れの例を説明する。
【００５２】
図１２は、情報抽出装置１０により行われる情報抽出処理の例を示すフローチャートを示している。図１２に示されるように、情報抽出装置１０はツリーデータ保持部１２に保持されるツリーデータについて頻出するノード（頻出ノード）を探索し（Ｓ１０１）、未処理の頻出ノードが残っている場合には（Ｓ１０２：Ｙ）、未処理の頻出ノードを選択して（Ｓ１０３）、パターンデータを作成して（Ｓ１０４）、パターンの伸張探索処理を行う（Ｓ１０５）。パターンの伸張探索処理の詳細については後述する。パターンの伸張探索処理が終了するとＳ１０２に戻り、未処理の頻出ノードが残っていない場合には（Ｓ１０２：Ｎ）、処理を終了する。
【００５３】
図１３は、パターンの伸張探索処理の例を示すフローチャートを示している。図１３に示されるように、情報抽出装置１０は、パターンからＲＭＰを選定し（Ｓ２０１）、選定したＲＭＰ上に未処理の伸張箇所があるか否かを判断する（Ｓ２０２）。ここで、情報抽出装置１０は、未処理の伸張箇所があると判断する場合には（Ｓ２０２：Ｙ）、未処理の伸張箇所の１つを選択し（Ｓ２０３）、伸張箇所にノードを追加した伸張パターンの冗長性判定処理を行う（Ｓ２０４）。冗長性判定処理の詳細については後述する。
【００５４】
情報抽出装置１０は、冗長性判定処理により冗長性があると判定された場合には（Ｓ２０５：Ｙ）、その判定結果を記録し、処理Ｓ２０２に戻ってそれ以降の処理を繰り返す。一方で、情報抽出装置１０は、冗長性判定処理により冗長性がないと判定された場合には（Ｓ２０５：Ｎ）、伸張箇所にノードを追加した伸張パターンの候補をツリーデータから探索する（Ｓ２０６）。
【００５５】
情報抽出装置１０は、探索されたパターンの候補について未処理のものがある場合には（Ｓ２０７：Ｙ）、未処理のパターン候補を１つ選択し（Ｓ２０８）、パターンの伸張探索処理を再帰的に実行する（Ｓ２０９）。そして、情報抽出装置１０は、未処理のパターン候補がなくなると（Ｓ２０７：Ｎ）、Ｓ２０２に戻りそれ以降の処理を繰り返す。なお、Ｓ２０２において未処理の伸張箇所がないと判断された場合には（Ｓ２０２：Ｎ）、親プロセスにリターンする。
【００５６】
図１４には、冗長性判定処理の例を示すフローチャートを示した。図１４に示されるように、情報抽出装置１０は、伸張箇所が選定されたパターンの中から未処理の検査対象ノードがある場合には（Ｓ３０１：Ｙ）、未処理の検査対象ノードを１つ選択する（Ｓ３０２）。
【００５７】
情報抽出装置１０は、検査対象ノードに対する新たなリーフノードを追加したパターンが冗長な探索となるか否かを判定（第１冗長性判定）し（Ｓ３０３）、冗長な探索となると判定した場合には（Ｓ３０３：Ｙ）、冗長性ありと記録して（Ｓ３０６）、リターンする。また、情報抽出装置１０は、第１冗長性判定により冗長性が判定されない場合には（Ｓ３０３：Ｎ）、検査対象ノードとその子ノードとの間に設けられる１エッジ上ノードを追加したパターンが冗長な探索となるか否かを判定（第２冗長性判定）し（Ｓ３０４）、冗長な探索となると判定した場合には（Ｓ３０４：Ｙ）、冗長性ありと記録して（Ｓ３０６）、リターンする。さらに、情報抽出装置１０は、第２冗長性判定により冗長性が判定されない場合には（Ｓ３０４：Ｎ）、検査対象ノードとその複数の子ノードとの間に設けられる分岐点ノードを追加したパターンが冗長な探索となるか否かを判定（第３冗長性判定）し（Ｓ３０５）、冗長な探索となると判定した場合には（Ｓ３０４：Ｙ）、冗長性ありと記録して（Ｓ３０６）、リターンする。情報抽出装置１０は、未処理の検査対象ノードがなくなった場合には（Ｓ３０１：Ｎ）、冗長性なしと記録して（Ｓ３０７）、リターンする。
【００５８】
なお、上記の冗長性判定処理では、第１冗長性判定から第３冗長性判定の順に実行することとしたが、冗長性判定の順序はこれに限定されない。また、上記の冗長性判定処理において、検査対象ノードの子ノードの有無及び子ノードの数に応じて第１冗長性判定から第３冗長性判定の中から不要な冗長性判定処理を省略することとしてよい。
【００５９】
上記の実施形態に係る情報抽出装置１０では、Ｅｍｂｅｄｄｅｄ Ｓｕｂｔｒｅｅ Ｍｉｎｉｎｇにおいて、探索されたパターンを伸張した伸張パターンについての探索を開始する前に、パターンの内部にノードを埋め込んだ場合に他のパターンとの関係で冗長な探索となるか否かを判別し、冗長と判別された伸張パターンについての探索を行わないようにしたことで、こうした構成を有さない場合に比べて、ツリーデータに頻出する木構造パターンを抽出するのに要する処理ステップの数が低減される。
【００６０】
本発明は上記の実施形態に限定されるものではなく、例えば上記の実施形態では伸張箇所をＲＭＰから選択しているが、パターン探索のアルゴリズムを適切に設定すれば左端のパス（ＬＭＰ）や他の条件に基づいて選択されたパスから選択することとしても構わない。
【符号の説明】
【００６１】
１０ 情報抽出装置、１２ ツリーデータ保持部、１４ パターン候補探索部、１６ パターン情報保持部、１８ パターン出現情報保持部、２０ パターン伸張箇所選択部、２２ 伸張パターン存在範囲管理部、２４ 冗長性判定部、２６ 検査対象ノード選択部、２８ 第１冗長性判定部、３０ 第２冗長性判定部、３２ 第３冗長性判定部、３４ 集計基準位置設定部。
【特許請求の範囲】
【請求項１】
コンピュータを、
複数の木構造情報の中から予め定められた数の木構造情報に共通して含まれる木構造のパターンを保持する保持手段、
前記保持手段に保持された木構造のパターンから予め定められた条件に基づいてパスを選択するとともに、当該選択されたパスに要素を追加して前記木構造のパターンを伸張する伸張箇所を選択する選択手段、及び、
前記木構造のパターンに含まれるいずれかの要素を検査対象要素とし、前記木構造のパターンにおける前記検査対象要素と前記伸張箇所とに基づいて前記複数の木構造情報のそれぞれについて定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその子要素との間に要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する判定手段
として機能させるためのプログラム。
【請求項２】
前記判定手段は、前記定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその１つの子要素との間に要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する
ことを特徴とする請求項１に記載のプログラム。
【請求項３】
前記判定手段は、前記定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその複数の子要素とのそれぞれに接続する要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する
ことを特徴とする請求項１又は２に記載のプログラム。
【請求項４】
前記判定手段はさらに、前記定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素に新たな子要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する
ことを特徴とする請求項１から３のいずれかに記載のプログラム。
【請求項５】
前記コンピュータをさらに、
前記木構造のパターンにおける前記検査対象要素と前記伸張箇所とに基づいて、前記複数の木構造情報のそれぞれについて前記検査対象要素とその子要素との間に追加された要素の候補を検出する基準位置を設定する設定手段
として機能させるための請求項１から４のいずれかに記載のプログラム。
【請求項６】
前記コンピュータをさらに、
前記判定手段により前記木構造のパターンの前記伸張箇所に新たな要素を追加した伸張パターンの探索を行うと判定した場合に、当該伸張パターンの候補を前記複数の木構造情報の中から探索する探索手段、
前記探索手段により探索された前記伸張パターンの候補に基づいて生成した木構造のパターンを前記保持手段に保持させる手段、
前記保持手段に保持された木構造のパターンを前記選択手段、前記判定手段、前記探索手段により伸張する処理を再帰的に実行する手段
として機能させるための請求項１から５のいずれかに記載のプログラム。
【請求項７】
複数の木構造情報の中から予め定められた数の木構造情報に共通して含まれる木構造のパターンを保持する保持手段と、
前記保持手段に保持された木構造のパターンから予め定められた条件に基づいてパスを選択するとともに、当該選択されたパスに要素を追加して前記木構造のパターンを伸張する伸張箇所を選択する選択手段と、
前記木構造のパターンに含まれるいずれかの要素を検査対象要素とし、前記木構造のパターンにおける前記検査対象要素と前記伸張箇所とに基づいて前記複数の木構造情報のそれぞれについて定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその子要素との間に要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する判定手段と、
を含むことを特徴とする情報抽出装置。
【請求項１】
コンピュータを、
複数の木構造情報の中から予め定められた数の木構造情報に共通して含まれる木構造のパターンを保持する保持手段、
前記保持手段に保持された木構造のパターンから予め定められた条件に基づいてパスを選択するとともに、当該選択されたパスに要素を追加して前記木構造のパターンを伸張する伸張箇所を選択する選択手段、及び、
前記木構造のパターンに含まれるいずれかの要素を検査対象要素とし、前記木構造のパターンにおける前記検査対象要素と前記伸張箇所とに基づいて前記複数の木構造情報のそれぞれについて定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその子要素との間に要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する判定手段
として機能させるためのプログラム。
【請求項２】
前記判定手段は、前記定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその１つの子要素との間に要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する
ことを特徴とする請求項１に記載のプログラム。
【請求項３】
前記判定手段は、前記定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその複数の子要素とのそれぞれに接続する要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する
ことを特徴とする請求項１又は２に記載のプログラム。
【請求項４】
前記判定手段はさらに、前記定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素に新たな子要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する
ことを特徴とする請求項１から３のいずれかに記載のプログラム。
【請求項５】
前記コンピュータをさらに、
前記木構造のパターンにおける前記検査対象要素と前記伸張箇所とに基づいて、前記複数の木構造情報のそれぞれについて前記検査対象要素とその子要素との間に追加された要素の候補を検出する基準位置を設定する設定手段
として機能させるための請求項１から４のいずれかに記載のプログラム。
【請求項６】
前記コンピュータをさらに、
前記判定手段により前記木構造のパターンの前記伸張箇所に新たな要素を追加した伸張パターンの探索を行うと判定した場合に、当該伸張パターンの候補を前記複数の木構造情報の中から探索する探索手段、
前記探索手段により探索された前記伸張パターンの候補に基づいて生成した木構造のパターンを前記保持手段に保持させる手段、
前記保持手段に保持された木構造のパターンを前記選択手段、前記判定手段、前記探索手段により伸張する処理を再帰的に実行する手段
として機能させるための請求項１から５のいずれかに記載のプログラム。
【請求項７】
複数の木構造情報の中から予め定められた数の木構造情報に共通して含まれる木構造のパターンを保持する保持手段と、
前記保持手段に保持された木構造のパターンから予め定められた条件に基づいてパスを選択するとともに、当該選択されたパスに要素を追加して前記木構造のパターンを伸張する伸張箇所を選択する選択手段と、
前記木構造のパターンに含まれるいずれかの要素を検査対象要素とし、前記木構造のパターンにおける前記検査対象要素と前記伸張箇所とに基づいて前記複数の木構造情報のそれぞれについて定められる検査範囲から、前記木構造のパターンにおける前記検査対象要素とその子要素との間に要素を追加した共通のパターンが検出される場合に、前記木構造のパターンの前記伸張箇所に新たな要素を追加したパターンの探索を行わないと判定する判定手段と、
を含むことを特徴とする情報抽出装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１１−１２３６１９（Ｐ２０１１−１２３６１９Ａ）
【公開日】平成２３年６月２３日（２０１１．６．２３）
【国際特許分類】
【出願番号】特願２００９−２７９７８４（Ｐ２００９−２７９７８４）
【出願日】平成２１年１２月９日（２００９．１２．９）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
【公開日】平成２３年６月２３日（２０１１．６．２３）
【国際特許分類】
【出願日】平成２１年１２月９日（２００９．１２．９）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
[ Back to top ]