(57)【要約】【課題】複数のツリーデータのうち、予め定められる数以上のツリーデータに含まれる種パターンを抽出する処理量が、複数のツリーデータを対象として処理を行う場合より小さいプログラム及び情報抽出装置を提供する。【解決手段】複数のツリーデータを示すツリーデータ情報を蓄積するツリーデータ情報蓄積部１０８と、予め定められる数以上のツリーデータに含まれるパターンである種パターンを示す種パターン情報を取得する入力受付部１０２と、種パターンを含むツリーデータを示す種パターン含有ツリーデータ情報を取得する種パターン含有ツリーデータ情報保持部１１０と、ツリーデータ情報と、種パターン情報と、種パターン含有ツリーデータ情報と、に基づき、種パターンを含むツリーデータのうち、所与の閾値以上の数のツリーデータに含まれる拡張パターンを生成する拡張パターン生成部１１８、としてコンピュータを機能させるプログラムである。【選択図】図１
2011123626.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータを、
それぞれが複数の枝と複数のノードとを有する複数のツリーデータを示すツリーデータ情報を蓄積するツリーデータ情報蓄積手段と、
前記複数のツリーデータのうちの予め定められる数以上のツリーデータに含まれるパターンである種パターンを示す種パターン情報を取得する種パターン情報取得手段と、
前記種パターンを含むツリーデータを示す種パターン含有ツリーデータ情報を保持する種パターン含有ツリーデータ情報保持手段と、
前記ツリーデータ情報と、前記種パターン情報と、前記種パターン含有ツリーデータ情報と、に基づき、前記種パターンを含むツリーデータのうち、所与の閾値以上の数のツリーデータに含まれる拡張パターンを生成する拡張パターン生成手段、
として機能させるためのプログラム。
【請求項２】
請求項１に記載のプログラムにおいて、
前記拡張パターン生成手段は、前記予め定められる数のツリーデータのそれぞれに含まれるノードが、前記所与の閾値以上の数のツリーデータに含まれるか否か判定する判定処理を行い、前記判定処理において、前記所与の閾値以上の数のツリーデータに含まれると判定されるノードを前記種パターンに追加することで、前記拡張パターンを生成することを特徴とするプログラム。
【請求項３】
請求項１または２に記載のプログラムにおいて、
前記コンピュータを、
前記種パターンに含まれる枝をガイドと定義する探索ガイド制御手段としてさらに機能させ、
前記拡張パターン生成手段は、前記予め定められる数のツリーデータにおいて、前記ガイドに対応するノードにより規定される追加ノード探索範囲に含まれるノードのそれぞれについて、前記判定処理を行うことを特徴とするプログラム。
【請求項４】
請求項３に記載のプログラムにおいて、
前記追加ノード探索範囲は、前記ガイドに対し左右いずれかの一方向に存在するノード及び前記ガイドの子ノードを含み、
前記探索ガイド制御手段は、前記追加ノード探索範囲に含まれるノードに対する前記判定処理が終了すると、前記ガイドを他方向に変更することを特徴とするプログラム。
【請求項５】
請求項１から４のいずれかに記載のプログラムにおいて、
前記拡張パターン生成手段は、
前記種パターンに含まれるノードのそれぞれについて該ノードの全ての子ノードを抽出し、
前記予め定められる数のツリーパターンのそれぞれにおいて、該ノードに対応する対応親ノード及び前記子ノードに対応する対応子ノードを抽出し、
前記対応親ノードの子ノードであって、前記対応子ノードから任意に選択されるノードの親ノードであるノードについて、前記判定処理を行うことを特徴とするプログラム。
【請求項６】
請求項５に記載のプログラムにおいて、
前記拡張パターン生成手段は、前記任意に選択されるノードとして、前記対応子ノードの全て、前記対応子ノードの長兄ノードのみ、及び前記対応子ノードの全てから任意の数の末弟ノードが除かれたノード、の全ての組み合わせを選択することを特徴とするプログラム。
【請求項７】
請求項１から６のいずれかに記載のプログラムにおいて
前記コンピュータを、
前記種パターンのノードのそれぞれと、該ノードに対応する前記予め定められる数のツリーデータのそれぞれのノードと、を関連づけて記憶する手段としてさらに機能させ、
前記ツリーデータ情報蓄積手段に蓄積される情報は、前記複数のツリーデータのそれぞれに含まれる複数のノードの全てが配列されるデータ構造を有し、
前記拡張パターン生成手段は、前記ツリーデータ情報蓄積手段に蓄積される情報が配列されたデータ構造内の、前記種パターン情報取得手段により取得される前記種パターン情報に基づいて決定される領域に含まれるノードについて、前記判定処理を行うことを特徴とするプログラム。
【請求項８】
請求項１から７のいずれかに記載のプログラムにおいて、
前記拡張パターン生成手段は、前記種パターンの上端のノードに１又は複数のノードを追加することで生成される前記拡張パターンを出力し、生成される前記拡張パターンのうち、前記種パターンの全てのノードを含むものを出力することを特徴とするプログラム。
【請求項９】
それぞれが複数の枝と複数のノードとを有する複数のツリーデータを示すツリーデータ情報を蓄積するツリーデータ情報蓄積手段と、
前記複数のツリーデータのうちの予め定められる数以上のツリーデータに含まれるパターンである種パターンを示す種パターン情報を取得する種パターン情報取得手段と、
前記種パターンを含むツリーデータを示す種パターン含有ツリーデータ情報を保持する種パターン含有ツリーデータ情報保持手段と、
前記ツリーデータ情報と、前記種パターン情報と、前記種パターン含有ツリーデータ情報と、に基づき、前記種パターンを含むツリーデータのうち、所与の閾値以上の数のツリーデータに含まれる拡張パターンを生成する拡張パターン生成手段と、
を有することを特徴とする情報抽出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、プログラム及び情報抽出装置に関する。
【背景技術】
【０００２】
複数のツリーデータのうち、予め定められる数以上のツリーデータに含まれるパターンを抽出する情報抽出装置がある。
【０００３】
特許文献１には、グラフ構造によりそれぞれ表現された複数のオブジェクトに共通して含まれる多頻度部分グラフを抽出する多頻度パターン抽出装置が開示されている。特許文献２には、複数の木構造内で複数回現れる構造パターンを探索する情報処理装置が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−０６３２７７号公報
【特許文献２】特開２００６−０３１５２３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、抽出するパターンに共通して含まれる木構造（以降、種パターン）を指定し、種パターンにノードや部分木を一つあるいは複数追加した形のより大きな種パターンであり、指定した複数のツリーデータのうち、予め定められる数以上のツリーデータに含まれる該種パターンを抽出する処理における処理量が、単に複数のツリーデータを対象として予め定められる数以上のツリーデータに含まれるパターンを抽出する処理を行う場合より小さいプログラム及び情報抽出装置を提供することにある。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、請求項１に記載の発明は、コンピュータを、それぞれが複数の枝と複数のノードとを有する複数のツリーデータを示すツリーデータ情報を蓄積するツリーデータ情報蓄積手段と、前記複数のツリーデータのうちの予め定められる数以上のツリーデータに含まれるパターンである種パターンを示す種パターン情報を取得する種パターン情報取得手段と、前記種パターンを含むツリーデータを示す種パターン含有ツリーデータ情報を保持する種パターン含有ツリーデータ情報保持手段と、前記ツリーデータ情報と、前記種パターン情報と、前記種パターン含有ツリーデータ情報と、に基づき、前記種パターンを含むツリーデータのうち、所与の閾値以上の数のツリーデータに含まれる拡張パターンを生成する拡張パターン生成手段、として機能させるためのプログラムである。
【０００７】
また、請求項２に記載の発明は、請求項１に記載のプログラムにおいて、前記拡張パターン生成手段は、前記予め定められる数のツリーデータのそれぞれに含まれるノードが、前記所与の閾値以上の数のツリーデータに含まれるか否か判定する判定処理を行い、前記判定処理において、前記所与の閾値以上の数のツリーデータに含まれると判定されるノードを前記種パターンに追加することで、前記拡張パターンを生成することを特徴とする。
【０００８】
また、請求項３に記載の発明は、請求項１または２に記載のプログラムにおいて、前記コンピュータを、前記種パターンに含まれる枝をガイドと定義する探索ガイド制御手段としてさらに機能させ、前記拡張パターン生成手段は、前記予め定められる数のツリーデータにおいて、前記ガイドに対応するノードにより規定される追加ノード探索範囲に含まれるノードのそれぞれについて、前記判定処理を行うことを特徴とする。
【０００９】
また、請求項４に記載の発明は、請求項３に記載のプログラムにおいて、前記追加ノード探索範囲は、前記ガイドに対し左右いずれかの一方向に存在するノード及び前記ガイドの子ノードを含み、前記探索ガイド制御手段は、前記追加ノード探索範囲に含まれるノードに対する前記判定処理が終了すると、前記ガイドを他方向に変更することを特徴とする。
【００１０】
また、請求項５に記載の発明は、請求項１から４のいずれかに記載のプログラムにおいて、前記拡張パターン生成手段は、前記種パターンに含まれるノードのそれぞれについて該ノードの全ての子ノードを抽出し、前記予め定められる数のツリーパターンのそれぞれにおいて、該ノードに対応する対応親ノード及び前記子ノードに対応する対応子ノードを抽出し、前記対応親ノードの子ノードであって、前記対応子ノードから任意に選択されるノードの親ノードであるノードについて、前記判定処理を行うことを特徴とする。
【００１１】
また、請求項６に記載の発明は、請求項５に記載のプログラムにおいて、前記拡張パターン生成手段は、前記任意に選択されるノードとして、前記対応子ノードの全て、前記対応子ノードの長兄ノードのみ、及び前記対応子ノードの全てから任意の数の末弟ノードが除かれたノード、の全ての組み合わせを選択することを特徴とする。
【００１２】
また、請求項７に記載の発明は、請求項１から６のいずれかに記載のプログラムにおいて、前記コンピュータを、前記種パターンのノードのそれぞれと、該ノードに対応する前記予め定められる数のツリーデータのそれぞれのノードと、を関連づけて記憶する手段としてさらに機能させ、前記ツリーデータ情報蓄積手段に蓄積される情報は、前記複数のツリーデータのそれぞれに含まれる複数のノードの全てが配列されるデータ構造を有し、前記拡張パターン生成手段は、前記ツリーデータ情報蓄積手段に蓄積される情報が配列されたデータ構造内の、前記種パターン情報取得手段により取得される前記種パターン情報に基づいて決定される領域に含まれるノードについて、前記判定処理を行うことを特徴とする。
【００１３】
また、請求項８に記載の発明は、請求項１から７のいずれかに記載のプログラムにおいて、前記拡張パターン生成手段は、前記種パターンの上端のノードに１又は複数のノードを追加することで生成される前記拡張パターンを出力し、生成される前記拡張パターンのうち、前記種パターンの全てのノードを含むものを出力することを特徴とする。
【００１４】
また、請求項９に記載の情報抽出装置の発明は、それぞれが複数の枝と複数のノードとを有する複数のツリーデータを示すツリーデータ情報を蓄積するツリーデータ情報蓄積手段と、前記複数のツリーデータのうちの予め定められる数以上のツリーデータに含まれるパターンである種パターンを示す種パターン情報を取得する種パターン情報取得手段と、前記種パターンを含むツリーデータを示す種パターン含有ツリーデータ情報を保持する種パターン含有ツリーデータ情報保持手段と、前記ツリーデータ情報と、前記種パターン情報と、前記種パターン含有ツリーデータ情報と、に基づき、前記種パターンを含むツリーデータのうち、所与の閾値以上の数のツリーデータに含まれる拡張パターンを生成する拡張パターン生成手段と、を有することを特徴とする。
【発明の効果】
【００１５】
請求項１，９に記載の発明によれば、複数のツリーデータのうち、予め定められる数以上のツリーデータに含まれる拡張パターンを抽出する処理における処理が、複数のツリーデータのうち、種パターンを含むツリーデータに対して行われ、さらに種パターンを含んだ拡張パターンの探索に制限してパターンの抽出が行われる。
【００１６】
請求項２に記載の発明によれば、種パターンに、所与の閾値以上の数のツリーデータに含まれるノードを追加することで拡張パターンが生成される。
【００１７】
請求項３に記載の発明によれば、種パターンに追加されるノードの判定処理は、ガイドにより規定される追加ノード探索範囲に含まれるノードに対して行われる。
【００１８】
請求項４に記載の発明によれば、追加ノード探索範囲を規定するガイドは、追加ノード探索範囲におけるノードに対する判定処理が終了すると変更され、種パターンに対してノードの追加が適切に制御される。
【００１９】
請求項５に記載の発明によれば、前記種パターンに含まれるノードのそれぞれについて該ノードの全ての子ノードが抽出され、前記予め定められる数のツリーパターンのそれぞれにおいて、該ノードに対応する対応親ノード及び前記子ノードに対応する対応子ノードが抽出され、対応親ノードの子ノードであって、対応子ノードから任意に選択されるノードの親ノードであるノードについて、判定処理が行われ、種パターン上の親子関係の間に、ノードや部分木構造を追加した拡張パターンが正しく抽出される。
【００２０】
請求項６に記載の発明によれば、任意に選択されるノードとして、前記対応子ノードの全て、前記対応子ノードの全てから任意の数の末弟ノードが除かれたノード、及び前記対応子ノードの長兄ノードのみが順に選択されて、種パターン上の親子関係の間に、ノードや部分木構造を追加した拡張パターンが見落としなく抽出される。
【００２１】
請求項７に記載の発明によれば、拡張パターン生成手段は、ツリーデータ情報蓄積手段に蓄積される情報が配列されたデータ構造内の、種パターン情報取得手段により取得される種パターン情報に基づいて決定される領域に含まれるノードについて、判定処理を行う。
【００２２】
請求項８に記載の発明によれば、拡張パターン生成手段は、種パターンの全てのノードを含む拡張パターンを出力する。
【図面の簡単な説明】
【００２３】
【図１】本実施形態に係る情報抽出装置の構成を示す図である。
【図２】グラフ構造の一例を示す図である。
【図３】ラベル付き根付き木の一例を示す図である。
【図４】ツリーの一例を示す図である。
【図５】ツリーの一例を示す図である。
【図６】ツリーの一例を示す図である。
【図７】ツリーの一例を示す図である。
【図８】ツリーの一例を示す図である。
【図９】ツリーの一例を示す図である。
【図１０】ツリーの一例を示す図である。
【図１１】抽出されるパターンの一例を示す図である。
【図１２】ツリーの一例を示す図である。
【図１３】ツリーデータ情報蓄積部に記憶されるツリーデータのデータ構造の一例を示す図である。
【図１４】種パターンの一例を示す図である。
【図１５】種パターン情報保持部に記憶されるデータの、データ構造の一例を示す図である。
【図１６】種パターン出現箇所情報保持部に保持されるデータの、データ構造の一例を示す図である。
【図１７】種パターン含有ツリーデータ情報保持部に保持されるデータの、データ構造の一例を示す図である。
【図１８】グループ分けされたデータ構造の一例を示す図である。
【図１９】拡張ノード探索処理の一例を示すフローチャートである。
【図２０】拡張ノード探索処理の一例を示すフローチャートである。
【図２１】種パターンの一例を示す図である。
【発明を実施するための形態】
【００２４】
最初に、用語と背景技術の説明を行う。図２はグラフ構造の一例を示す図である。図２は４つのノードと３本のエッジ（枝）からなるグラフ構造を有するグラフ２００を示している。このようにループのないグラフ構造をツリーという。ツリーのノードの一つをルート（根）ノードに選択し、各ノードにラベルを与えたツリーをラベル付き根付き木（ｌａｂｅｌｅｄ  ｒｏｏｔｅｄ  ｔｒｅｅ）と呼ぶ。図３はラベル付き根付き木の一例を示す図である。以降、説明を簡単にするため、ラベル付き根付き木をツリーまたは木構造と呼ぶ。また、ツリー３００の構造を持つデータをツリーデータと呼ぶ。また、ツリーの図を描く際に、一番上側のノードをルートノードとし、エッジで接続された２つのノードの上側のノードを親ノード、下側のノードを子ノードと呼ぶ。
【００２５】
図４、図５、図６はツリーの一例を示す図である。図４に示されるツリー４００は図５のツリー５００の破線で示される範囲に存在する。図４に示されるツリー４００のノードのそれぞれに対応するノードが図５に示されるツリー５００に存在し、対応するノード間でそれぞれノードのラベルも対応がとれている。そして、図４の各ノード間の親子関係が、図５のツリー中の対応するノード間においても保持されている。このとき図４に示されるツリー４００は図５に示されるツリー５００で出現するといい、さらに、図４に示されるツリー４００は、図５に示されるツリー５００のｉｎｄｕｃｅｄ  ｓｕｂｔｒｅｅであるという。図４に示されるツリー４００は図６に示されるツリー６００の破線で示される範囲にも出現しており、図４に示されるツリー４００は、図６に示されるツリー６００のｉｎｄｕｃｅｄ  ｓｕｂｔｒｅｅでもある。
【００２６】
ここで、図５及び図６に示されるツリー５００，６００を示すツリーデータからなるデータベースを考え、このデータベースに対して閾値を指定して閾値以上の数のツリーデータにおいてｉｎｄｕｃｅｄ  ｓｕｂｔｒｅｅとなるツリーを列挙する処理をｉｎｄｕｃｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇといい、抽出されるツリーを（ｉｎｄｕｃｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇによる）パターンと呼ぶ。例えば、データベースに図５及び図６に示されるツリー５００，６００のツリーデータが登録されており、閾値として２が指定されたときには、図４に示されるツリー４００が抽出されて列挙されるパターンの一例となる。
【００２７】
親子関係を子ノード側から親ノード側に順にエッジを辿って辿り着けるノードを先祖ノードと呼ぶ。逆に、親子関係を子ノード側に向かってエッジを辿って辿り着けるノードを子孫ノードと呼ぶ。先祖ノードと子孫ノードの間の関係を先祖子孫関係と呼ぶ。前述のｉｎｄｕｃｅｄ  ｓｕｂｔｒｅｅの抽出においては、ｉｎｄｕｃｅｄ  ｓｕｂｔｒｅｅの親子関係が、該ｉｎｄｕｃｅｄ  ｓｕｂｔｒｅｅが出現するツリーにおける対応するノード間の親子関係に対応するという条件が規定されるが、これを先祖子孫関係まで拡張したものがｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅである。
【００２８】
図７、図８、図９、及び図１０は、ツリーの一例を示す図である。図７に示されるツリー７００は、図８に示されるツリー８００、図９に示されるツリー９００、及び図１０に示されるツリー１０００においてｉｎｄｕｃｅｄ  ｓｕｂｔｒｅｅとしては出現しないが、図７に示されるツリーの各ノードを図８、図９、及び図１０においてそれぞれ実線の矢印で示されるノードに対応付けることで、図７の各ノード間の親子関係が、図８、図９、及び図１０において矢印で示されるノード間の先祖子孫関係として対応付けられる。この対応付けがなされることにより、図７に示されるツリー７００は、図８、図９、及び図１０に示されるツリー８００，９００，１０００のｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅであるといい、図７に示されるツリー７００は図８、図９、及び図１０に示されるツリー８００，９００，１０００に（ｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅとして）出現するという。
【００２９】
ここで、図８、図９、及び図１０に示されるツリー８００，９００，１０００を示すツリーデータからなるデータベースを考え、このデータベースに対して、閾値を指定して閾値以上の数のツリーデータにおいてｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅとなるツリーを列挙する処理をｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇといい、抽出されるツリーを（ｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｇによる）パターンと呼ぶ。例えば、データベースに図８、図９、及び図１０に示されるツリー８００，９００，１０００を示すツリーデータが登録されており、閾値として３が指定されたときには、図７に示されるツリー７００が抽出されて列挙されるパターンの一例となる。
【００３０】
なお、ｉｎｄｕｃｅｄ  ｓｕｂｔｒｅｅとｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅとを区別しないときは、単にｓｕｂｔｒｅｅ、又は部分木といい、ｉｎｄｕｃｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇとｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇとを区別しないときは、単にｓｕｂｔｒｅｅ  ｍｉｎｉｎｇという。ここではよりパターンの抽出能力が高いｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇを中心に説明を行う。
【００３１】
親を共通とする兄弟ノード間に順序関係があるツリーは順序木（ｏｒｄｅｒｅｄ  ｔｒｅｅ）、順序関係がないツリーは非順序木（ｕｎｏｒｄｅｒｅｄ  ｔｒｅｅ）という。そして順序木から兄弟間の順序関係を守ってパターンを抽出する処理をｏｒｄｅｒｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇ、兄弟間の順序関係に制限されずにパターンを抽出する処理をｕｎｏｒｄｅｒｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇという。通常はパターンを重複無く列挙するためにパターンのツリーについては兄弟間にラベルの辞書順やデータベースに登録されるツリーデータ中で出現した兄弟関係の順など、なんらかの順序を付けたうえで処理が行われるため、ここでは説明を簡単にするためにｏｒｄｅｒｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇを例として用いる。
【００３２】
抽出されるパターンの数はデータベース中のツリーデータと閾値に依存するが、閾値を下げると非常に多くのパターンが抽出される。抽出処理の処理時間も抽出されるパターンの数が増えるにつれて長くなり、処理に必要なメモリー容量も増えることが多い。
【００３３】
しかし、例えば抽出したパターンの中に注目したいパターンを見出し、そのパターンのツリーを含んだ、もう少し大きなツリーからなるパターンを知りたいといった場合には、閾値を小さくして抽出処理を実行する必要が生じる。例えば図７に示されるツリー７００は、図８、図９、及び図１０に示されるツリー８００，９００，１０００が登録されたデータベースから閾値３で抽出されるパターンの例である。このとき、図７に示されるツリー７００に注目して、ツリーを含む、より大きいパターンを抽出したいと考えて閾値を２に下げて抽出処理を行うと、より大きいパターンが抽出される。図１１は、抽出されるパターンの一例を示す図である。図１１に示されるツリー１１００の各ノードは、図８に示されるツリー８００と図９に示されるツリー９００において、実線及び破線の矢印で示したノードに対応するノードを含む（ノードの出現箇所と呼ぶ）。
【００３４】
ところが、このようにより大きいパターンを抽出する場合には、しばしば閾値を下げる必要が生じるため、非常に長い処理時間や非常に大きなメモリー容量が要求されることになり、場合によっては現実的な時間では処理が終了しないという事態も生じてしまう。さらに、その処理時間の大半は注目したいパターンを含まないパターン探索のために費やされていることがしばしばである。以降の実施例では、探索処理を注目したいパターンを含むパターンの探索のみに制限することで、この、より大きいパターンの抽出処理の効率を向上する。
【００３５】
以降、上記の説明における図７に示されるツリー７００のように、パターンに含まれることを指定するツリーを種パターンと呼ぶ。そして、図１１に示されるツリー１１００のように種パターンを含み、ノードの数が増えているパターンを拡張パターンと呼ぶ。拡張パターンは種パターンに対して、少しずつノードを追加することを繰り返して算出されることになる。このとき、ノードを追加する前のツリーを拡張元ツリー、または拡張元パターンと呼ぶ。拡張元パターンにノードが追加されて拡張パターンが得られた後、拡張パターンを拡張元パターンとして設定してノードを追加して新たな拡張パターンを順次得ていく処理を以降の実施例にて図面を用いて説明を行う。
【００３６】
以下、本発明を実施するための好適な実施の形態（以下、実施形態という）を、図面に従って説明する。
【００３７】
図１は、本実施形態に係る情報抽出装置１００の構成を示す図である。情報抽出装置１００は、種パターン情報取得手段として機能する入力受付部１０２、種パターン情報保持部１０４、種パターン出現箇所情報保持部１０６、ツリーデータ情報蓄積手段として機能するツリーデータ情報蓄積部１０８、種パターン含有ツリーデータ情報保持手段として機能する種パターン含有ツリーデータ情報保持部１１０、探索ガイド制御手段として機能する探索ガイド制御部１１２、拡張ノード探索部１１４、拡張ノード集計部１１６、拡張パターン生成手段として機能する拡張パターン生成部１１８、拡張パターン記憶部１２０、及び出力部１２２を有する。
【００３８】
本実施形態では、入力受付部１０２は例えばキーボードで構成される。種パターン情報保持部１０４、種パターン含有ツリーデータ情報保持部１１０、ツリーデータ情報蓄積部１０８、及び拡張パターン記憶部１２０は、本実施形態では例えばメモリーにより構成され、種パターン出現箇所情報保持部１０６、探索ガイド制御部１１２、拡張ノード探索部１１４、拡張ノード集計部１１６、及び拡張パターン生成部１１８は例えばＣＰＵの１機能として実現される。出力部１２２は、例えばディスプレイで構成される。
【００３９】
ツリーデータ情報蓄積部１０８は、それぞれが複数の枝と複数のノードとを有する複数のツリーを示すツリーデータ情報を蓄積する。ツリーとは、前述のように複数のノード及びノードの間を繋ぐエッジにより構成される構造である。図１２は、ツリーの一例を示す図である。図１２に示されるツリー１２００は、ｖ０〜ｖ１０の１１個のノード及び１０本のエッジを有する。ここでは、ノードのそれぞれに固有の識別子（ｖ０〜ｖ１０）を付す。また、ノードのそれぞれに示されるＡ〜Ｅは、ノードのそれぞれに付されるラベルである。
【００４０】
ツリー１２００において、最も上に位置するノードｖ０はルートノードであり、ルートノードから下方向に、エッジ及びノードを、エッジがなくなるまで辿る経路をここでは説明を簡単にするため、単にパスという。ツリー１２００では、ｖ０からｖ４までのパス、ｖ０からｖ５までのパス、ｖ０からｖ６までのパス、ｖ０からｖ８までのパス、ｖ０からｖ１０までのパスの、５本のパスが存在し、ここではそれぞれに番号を付したうえでＥｐ１〜Ｅｐ５の識別子で識別する。そしてパスの最後のノード（下に位置するノードがないノード）をリーフノードという。
【００４１】
ノードｖ０〜ｖ１０の全ては、少なくとも１つのパスの上に位置する。そして、ノードのそれぞれについて、該ノードが位置するパスのうち、番号が最も小さい（ツリー１２００上で最も左）のパスの番号をＥｐｒａｎｇｅＬ、番号が最も大きい（ツリー１２００上で最も右）のパスの番号をＥｐｒａｎｇｅＲとする。例えばｖ０ではＥｐｒａｎｇｅＬ＝１、ＥｐｒａｎｇｅＲ＝５であり、ｖ７ではＥｐｒａｎｇｅＬ＝４、ＥｐｒａｎｇｅＲ＝５である。
【００４２】
さらに、ノードｖ０〜ｖ１０のそれぞれには、ルートノードｖ０から該ノードまで経路上に存在する枝の数であるパラメータｄが規定される。ノードｖ０ではｄ＝０、ノードｖ５ではｄ＝３である。
【００４３】
ツリーデータ情報蓄積部１０８は、ツリー１２００を示すツリーデータとして、以上のパラメータを記憶する。図１３は、ツリーデータ情報蓄積部１０８に記憶されるツリーデータのデータ構造の一例を示す図である。図１３では、図１２に示されるツリー１２００を示すデータの例を示す。図１３に示されるデータ構造では、ツリー１２００に含まれるノードｖ０〜ｖ１０は、後述する深さ優先探索で探索される順序で配列されている。
【００４４】
種パターン情報保持部１０４は、入力受付部１０２により取得される、種パターン１４００を示す情報を保持する。種パターン１４００とは、前述のとおり、抽出されるパターンに含まれることが期待されるツリー構造のことである。図１４は、種パターン１４００の一例を示す図である。種パターン情報保持部１０４は、種パターン１４００を示す情報を、ツリーデータ情報蓄積部１０８に蓄積されるデータと同じ形式で記憶する。図１５は、種パターン情報保持部１０４に記憶されるデータの、データ構造の一例を示す図である。図１５には、図１４に示される種パターン１４００を示すデータの例を示す。
【００４５】
種パターン出現箇所情報保持部１０６は、ツリーデータ情報蓄積部１０８に蓄積されるツリーデータにより示されるツリーのうち、種パターンを含むツリー（種パターン含有ツリーデータ）のそれぞれにおける種パターンの出現箇所を示す情報を取得し、保持する。種パターン出現箇所情報保持部１０６は、種パターン情報保持部１０４に保持される種パターン１４００を示す情報と、ツリーデータ情報蓄積部１０８に蓄積されるツリーデータを示す情報と、に基づいて、種パターン１４００を含むツリーを示す情報及びそれらのツリーデータにおける種パターンの出現箇所を示す情報を取得して保持する。種パターン出現箇所情報保持部１０６は、種パターン出現箇所情報として、種パターンのノードを示す情報と、そのそれぞれに対応する、各ツリーのノードを示す情報と、を関連づけて記憶する。図１６は、種パターン出現箇所情報保持部１０６に保持されるデータの、データ構造の一例を示す図である。ツリーデータＩＤはツリーデータを特定する識別子であり、ここでツリーデータＩＤ（０２００）は、図１２に示されるツリー１２００を特定するものとする。
【００４６】
なお、ここでは説明を簡単にするために種パターンのノードとツリーデータのノードとが一対一で対応する例が示されているが、種パターンのノードが、同一のツリーデータの複数箇所に出現する場合もあり、対応は一対一に限定されない。図１６に示されるデータ構造においても、対応するノードの情報を加えることで一対一に限定されない場合における情報を保持することができる。
【００４７】
種パターン含有ツリーデータ情報保持部１１０は、ツリーデータ情報蓄積部１０８に蓄積されるツリーデータのうち、種パターン１４００を含むツリーデータを示す種パターン含有ツリーデータ情報を保持する。種パターン含有ツリーデータ情報は、種パターン出現箇所情報保持部１０６により生成される。種パターン含有ツリーデータ情報保持部１１０は、例えば種パターン１４００を含むツリーデータを示すツリーデータ識別子を記憶する。図１７は、種パターン含有ツリーデータ情報保持部１１０に保持されるデータの、データ構造の一例を示す図である。
【００４８】
探索ガイド制御部１１２は、種パターンの一部からなる拡張ノード探索のガイドを制御する。すなわち、探索ガイド制御部１１２は、種パターン含有ツリーデータ情報保持部１１０に保持されるツリーデータ（含有ツリーデータ）の識別子情報と、種パターンのノードのうち、後述するガイドとして選択されたエッジの、含有ツリーデータに示されるツリーにおける出現箇所を示す情報と、を拡張ノード探索部１１４に出力する。
【００４９】
拡張ノード探索部１１４は、種パターン含有ツリーデータを探索し、拡張パターンの生成の際に種パターンに追加されるノード（拡張ノード）の候補を決定する。拡張ノード探索部１１４は、探索対象を、ツリーデータ情報蓄積部１０８にツリーデータが蓄積されるツリーのうち、探索ガイド制御部１１２から入力される、種パターン含有ツリーデータ情報保持部１１０に保持される情報により示されるツリーに制限した探索を行い、拡張ノードの候補を決定する。ここで行われる探索については後述する。
【００５０】
拡張ノード集計部１１６は、拡張ノード探索部１１４により探索された拡張ノードの候補それぞれが、ツリーデータ情報蓄積部１０８に蓄積される種パターン含有ツリーデータのうちいくつのツリーデータに含まれるか集計し、得られる個数（拡張ノード含有ツリーデータ数）を記憶する。
【００５１】
拡張パターン生成部１１８は、種パターンのルートノード（上端のノード）に、種パターンの他のノード及び拡張ノードを追加することで拡張パターンを生成する。拡張パターン生成部１１８は、拡張ノード集計部１１６に記憶される拡張ノードの候補のそれぞれの拡張ノード含有ツリーデータ数を参照し、拡張ノード含有ツリーデータ数が所与の閾値以上である拡張ノードを種パターンに追加して拡張パターンを生成し、得られる拡張パターンを示す情報を拡張パターン記憶部１２０に出力する。ここで所与の閾値とは、入力受付部１０２を介してユーザーによって入力されるパラメータであり、拡張パターン生成部１１８において記憶される。
【００５２】
拡張パターン記憶部１２０は、拡張パターン生成部１１８により生成される拡張パターンを示す情報を記憶する。拡張パターン記憶部１２０は、拡張パターンを示す情報を、ツリーデータ情報蓄積部１０８と同様の形式で記憶しても、種パターン情報と同様の形式で記憶してもよい。ここでは種パターンがツリーデータ情報蓄積部１０８と同形式で記憶される場合について説明する。拡張パターンを示す情報は、更に拡張パターンにノードが追加されるため、拡張元パターンの情報として拡張ノード探索部１１４に出力される。記憶された拡張パターンを示す情報は、例えばユーザーの操作に応じて出力部１２２であるディスプレイに表示され、ユーザーに提供される。記憶された拡張パターンを示す情報はデータ形式のまま保存されており、例えば表示に関する処理が行われることなく、他の処理の入力として使用されてもよい。
【００５３】
出力部１２２は、ユーザーによる操作に応じて拡張パターン記憶部１２０に記憶される拡張パターンを示す情報を例えばツリー構造に変換して表示する。その際、出力部１２２は、ユーザーにより拡張パターンの出力を指示する操作が行われると、拡張パターン生成部１１８から、拡張パターンの生成状況（拡張パターンが出力可能な状態か否か）を示す情報を受け取り、出力可能であることが確認された場合にのみ出力を行う。出力可能であることが確認されなかった場合には、例えば「作成中です」等のメッセージを表示する。
【００５４】
拡張ノード探索部１１４における拡張パターン探索処理を以下に説明する。
【００５５】
拡張パターン探索処理は、図１３に示されるデータ構造で表されるツリーデータを用いて行われる。図１３に示されるデータ構造を用いた拡張パターン探索処理において実行される処理の例として、拡張元パターン中のノードの子ノードの候補の探索、拡張元パターン中のノードの弟ノード候補の探索、及び深さ優先探索を説明する。
【００５６】
これらの探索では、図１３に示されるデータ構造を、ＥｐｒａｎｇｅＬが等しいものでグループ分けしたデータ構造が使用される。図１８は、グループ分けされたデータ構造の一例を示す図である。
【００５７】
拡張元パターン中のノード（対象ノード）の子ノード候補の探索は、拡張元パターン中で指定された対象ノードに対応するツリーデータ中のノードの、子孫ノードの探索となる。ツリーデータ中の子孫ノードの探索は、図１８に示されるグループ分けされたデータ構造に対して行われる。すなわち、対象ノードの子孫ノードは、図１８に示されるデータ構造では、対象ノードに対応するデータよりも下に位置するノード（下位ノード）及び、下位ノードのＥｐｒａｎｇｅＲで示されるパスに含まれる全てのノードとなる。すなわち、図１８の例では、ｖ２の子孫ノードは、ｖ３、ｖ４、ｖ５である。
【００５８】
次に、弟ノードの探索を説明する。拡張元パターン中の対象ノードの弟ノードの探索は、拡張元パターン中で指定される対象ノードの親ノードに対応するツリーデータ中のノードを通るパスにあるノードのうち、拡張元パターン中で指定される対象ノードに対応するツリーデータ中のノードを通るパスにあるノードを除いた範囲を探索する処理となる。ここでは、拡張元パターン中で指定される対象ノードに対応するツリーデータ中のノードを図１２のツリー１２００においてノードｖ１とし、拡張元パターン中で指定される対象ノードの親ノードに対応するツリーデータ中のノードをｖ０とすると、弟ノードの候補はｖ７、ｖ８、ｖ９、ｖ１０である。
【００５９】
そして図１８に示されるデータ構造では、拡張元パターン中で指定された対象ノードに対応するツリーデータ中のノードがＥｐＲａｎｇｅＬ＝ｘ、ＥｐＲａｎｇｅＲ＝ｙであり、拡張元パターン中で指定された対象ノードの親ノードに対応するツリーデータ中のノードがＥｐＲａｎｇｅＬ＝ｗ、ＥｐＲａｎｇｅＲ＝ｚである場合、拡張元パターン中で指定されたノードの弟ノードの候補は、グループ（ｙ＋１）、グループ（ｙ＋２）、…、グループ（ｚ）の全てのノードとなる。例えば拡張元パターン中で指定された対象ノードに対応するノードがｖ０（ＥｐＲａｎｇｅＬ＝１、ＥｐＲａｎｇｅＲ＝５）であるときの弟ノード候補は、グループ４、グループ５の全てのノードである。
【００６０】
次に、深さ優先探索を説明する。深さ優先探索とは、探索を開始するノードから下方向にパスを辿っていき、複数のパスに分岐するノードでは左側のノードを選択してリーフノードに至るまで探索し、リーフノードに至ると、他パスとの分岐点まで戻り、分岐点からは該他パスを辿り、ここでも分岐点では左側のノードを選択してリーフノードに至るまで探索する、という処理を繰り返す探索である。図１２のツリー１２００においてノードｖ０から深さ優先探索を開始した場合、ｖ０、ｖ１、ｖ２、ｖ３、ｖ４、ｖ５、ｖ６、ｖ７、ｖ８、ｖ９、ｖ１０の順にノードが探索される。
【００６１】
この深さ優先探索は、図１３に示されるデータ構造において、探索を開始するノードのデータから下方向に探索することで実行される。そして、あるノード（該枝に接続されるノード）に到達する１つ手前のノードまでこの深さ優先探索で探索することで、該ノードより左方向にあるノードは、全て探索される。また、深さ優先探索において最後に探索されたノードとルートノードとを結ぶパスは、探索されたパスのうち最も右側に位置するＲＭＰ（Ｒｉｇｈｔ  Ｍｏｓｔ  Ｐａｔｈ）になる。
【００６２】
以上の処理を使用した、拡張ノード探索部１１４における拡張ノード探索処理を説明する。
【００６３】
図１９、図２０は拡張ノード探索処理の一例を示すフローチャートである。図２１は、種パターン２１００の一例を示す図である。ここでは、図２１に示される種パターン２１００における拡張ノード探索処理の例を説明する。
【００６４】
探索ガイド制御部１１２は、種パターン２１００に含まれるノードから選択される基準ノード及び選択ノードにより特定される枝をガイドと定義し、この情報を拡張ノード探索部１１４に出力する。拡張ノード探索部１１４は、ガイドに対応するノードにより規定される追加ノード探索範囲（ガイドの一方（左側）の領域）に含まれるノードを探索する。
【００６５】
まず、探索ガイド制御部１１２は、種パターン２１００のルートノードｗ０を基準ノードと規定し（Ｓ１９００）、基準ノードに子ノードがあるか確認する（Ｓ１９０１）。
【００６６】
基準ノードに子ノードが存在しなければ（Ｓ１９０１：Ｎ）、パターン拡張処理は終了し、子ノードが存在すれば（Ｓ１９０１：Ｙ）子ノードの集合を集合Ｖ１と定義する（Ｓ１９０２）。種パターン２１００ではＶ１＝{ｗ１、ｗ４、ｗ５}である。
【００６７】
そして集合Ｖ１に含まれる子ノードのそれぞれを随時選択ノードと定義して、図２０で示されるサブルーチン処理を実行する（Ｓ１９０３）。選択ノードの定義を行う際、Ｖ１に含まれる子ノードは、ツリー上で左側に位置する子ノードから順（種パターン２１００ではｗ１、ｗ４、ｗ５の順）に選択されてサブルーチン処理Ｓ１９０３が実行される。
【００６８】
サブルーチン処理Ｓ１９０３が終了すると、探索ガイド制御部１１２は、拡張ノード探索部１１４に、最後の選択ノードの右側について、ガイドの制限を外したうえで弟ノード領域において弟ノード候補の探索を実行させて（Ｓ１９０４）、拡張ノード探索処理は終了する。例では種パターン２１００において選択ノードがノードｗ５である場合が相当し、この場合、範囲Ｆについて探索及び集計処理が行われ、拡張パターン生成部１１８にてパターンの拡張が可能であれば、拡張パターンが生成される。拡張ノード探索処理が終了すると、拡張ノード集計部１１６での集計、拡張パターン生成部１１８での拡張パターン生成が行われ、生成された拡張パターンが出力される。
【００６９】
なお、以降の説明を含めて、拡張元パターンにノードを追加する処理では、追加されるノードが見つからなかった場合を含めて、何も新しいノードが追加されないまま次のステップに進む場合があることも許容される。
【００７０】
次に、サブルーチン処理を説明する。図２０に示されるサブルーチン処理では、次のような処理を行う。図２１において、ノードｗ０が基準ノード、ノードｗ１が選択ノードと定義されて、枝ｂ０がガイドと定義されているとする。探索ガイド制御部１１２は、枝ｂ０がガイドであるとの情報を拡張ノード探索部１１４に出力する。拡張ノード探索部１１４は、枝ｂ０をガイドとして拡張候補ノードの探索処理を行う。ここでは、拡張ノード探索部１１４は、まず、含有ツリーデータのそれぞれの、枝ｂ０（ガイド）に対応する枝より左の範囲Ａにおいて、拡張パターンの探索処理を行う（Ｓ２００１）。拡張パターンの探索は、拡張元パターンに追加するノードを探索及び追加して拡張パターンを得る処理を繰り返す。追加されるノードの探索においては、従来技術において採用されているノードの探索方法が利用され、探索範囲にはガイドによる制限がかけられたうえで、拡張ノード探索部１１４によって実行される。拡張ノード探索部１１４は、探索されたノードのラベル情報を拡張ノード集計部１１６に出力し、拡張ノード集計部１１６は、ラベル情報ごとに該当するノードが出現したツリーデータの数を取得する。この、ラベルに該当するノードを含むツリーデータの数を取得し、取得されたツリーデータの数が拡張ノード集計部１１６において記憶される処理を、集計処理と呼ぶ。Ｓ２００１での拡張ノード探索処理の全てにおいて、探索範囲はガイドであるｂ０より左に制限されて実行される。図１３に示されるデータ構造であれば、例えばルートノードの子孫ノードを探索する際には、ルートノードから、ガイドに対応する枝に接続されるノードのＥｐｒａｎｇｅＬよりもＥｐｒａｎｇｅＲが小さいノードの範囲に制限した探索が実行される。すなわち、種パターン情報に基づいて決定されるガイドに基づく領域に対して探索は行われる。拡張元パターンの最も右のパス（Ｒｉｇｈｔ  Ｍｏｓｔ  Ｐａｔｈ；ＲＭＰ）がガイドに近くなって拡張元パターンのＲＭＰの右側に新たに追加するノードを見つけられなくなった時点で、拡張ノード探索部１１４は拡張パターンの探索処理を停止する。
【００７１】
領域Ａにおいて拡張パターンの探索処理が終了すると、探索ガイド制御部１１２は、拡張ノード探索部１１４に選択ノードの親ノードを追加された形の拡張パターンの探索処理（枝ｂ０（ガイド）上のノードを探索して拡張パターンを探索する探索処理）を行うよう指示して実行させる（Ｓ２００２）。ここで、種パターン２１００において、選択ノードであるノードｗ１の弟ノード（右側に位置するノード）が存在する場合、拡張ノード探索部１１４は、拡張元パターンを含む（が出現する）ツリーデータのそれぞれの、ノードｗ１に対応するノードの親ノードであり、かつノードｗ１の全ての弟ノードに対応するノードの親でもあるノード（範囲Ｂに相当）について探索及び集計処理を行い拡張パターン生成部１１８にて拡張元パターンにノードを追加して拡張パターンを生成する処理を行う。
【００７２】
次に、拡張ノード探索部１１４は、含有ツリーデータのそれぞれの、ノードｗ１に対応するノードの親ノードであり、かつ、ノードｗ１の複数の弟ノードのうち、最も右のノードを除く全ての弟ノードの親であるようなノードの探索（範囲Ｃに相当）及び集計処理を行い、拡張パターン生成部１１８は拡張元パターンにノードを追加して拡張パターンを生成する処理を行う。以下、ノードｗ１の親であり、かつ複数の弟ノードを右から１つずつに削除して得られる子ノードの組の全ての親であるようなノードの探索及び拡張パターンの生成を、ノードｗ１のみの親が対象となるまで行う（探索範囲が範囲Ｄになるまで実行）。以上で選択ノードの親ノードの探索処理（Ｓ２００２）が終了する。
【００７３】
このＳ２００２でノードを追加した拡張パターンが得られた場合、拡張ノード探索部１１４は探索ガイド制御部１１２にその旨を通知し、探索ガイド制御部１１２は処理中のガイドの情報を保存した上で、ガイドの選択ノードは変更することなく基準ノードを新たに追加されたノードに変更し、拡張ノード探索部１１４は、再帰的に図２０に示されるサブルーチンを呼び出す処置を内部で行って変更されたガイドに対する処理を実行する。以上で選択ノードの親ノードの探索処理（Ｓ２００２）が終了する。
【００７４】
ガイド上の探索処理が終了すると、拡張ノード探索部１１４は選択ノードを拡張パターンに加えることを拡張パターン生成部１１８に指示し（Ｓ２００３）、生成された拡張パターンを拡張元パターンに設定する。拡張ノード探索部１１４は、選択ノードに子ノードがあるか判定を行う（Ｓ２００４）。子ノードが存在しなければ（Ｓ２００４：Ｎ）、探索ガイド制御部１１２は拡張ノード探索部１１４に、新たに追加される子ノードの候補として、選択ノードに対応するツリーデータのノードの子孫ノードが存在する領域についてノードを探索して集計処理を行い、拡張パターン生成部１１８が拡張パターンの生成処理を行う（Ｓ２００７）。この領域での拡張パターンの探索処理が終わると、サブルーチン処理は終了する。選択ノードに子ノードが存在すれば（Ｓ２００４：Ｙ）、子ノードの集合が集合Ｖ２と定義され（Ｓ２００５）、ガイドの状態が保存された後、選択ノードであるノードが基準ノードと定義される（Ｓ２００６）。図２１の例では、ｗ１が新たに基準ノードと定義され、Ｖ２＝{ｗ２}である。そして、Ｖ２に含まれるノードを左から順に選択ノードと定義したうえで、サブルーチンの処理（Ｓ２００８）を再帰的に呼び出して実行する処理が繰り返される。
【００７５】
この処理が、最後の子ノードが選択ノードとして規定された状態でサブルーチンが再帰的に呼び出されてその実行が終了するまで実行されると、サブルーチンを再帰的に呼び出す繰り返し処理であるサブルーチンＳ２００８は終了する。そして、最後の子ノードの右側の領域（弟ノード領域）について図１９のＳ１９０４と同様にガイドによる探索範囲の制限を外したうえで、追加可能なノードを探索する拡張パターン探索処理を実行する（Ｓ２００９）。この処理が終了すると、サブルーチン処理は終了する。
【００７６】
拡張パターンの探索処理では、拡張ノード探索処理が終了した後、拡張パターン生成部１１８は拡張ノード集計部１１６に記憶されている、拡張ノードのそれぞれを含むツリーの数を参照し、ツリーの数が所与の閾値より大きい拡張ノードを拡張元パターンに追加して、拡張パターンを生成する。拡張パターンを示すデータは拡張パターン記憶部１２０に記憶され、出力部１２２において出力され、また、さらにノードが追加された拡張パターンを探索する際には、拡張パターンの探索処理を繰り返す処理における拡張元パターンとして、拡張ノード探索部１１４に出力される。
【００７７】
拡張パターン生成部１１８は、種パターンの最後のノードを拡張パターンに追加すると拡張パターン記憶部１２０に生成された拡張パターンを示すデータを出力し、拡張パターンに種パターンの最後のノードを追加する前であれば拡張パターン記憶部１２０に拡張パターンを示すデータを出力しない。すなわち、拡張パターン生成部１１８は、生成される拡張パターンのうち、種パターンの全てのノードを含む拡張パターンを出力し、拡張パターンが種パターンの一部のノードを含まない場合には、該拡張パターンの出力を制限する。この際、拡張パターン生成部１１８は、探索ガイド制御部１１２に対し、ガイドの種パターン内での位置情報を問い合わせてもよい。拡張パターン生成部１１８は、拡張パターンの生成状況（生成中、生成終了（拡張パターン出力可能））を示す情報を、出力部１２２に出力する。
【００７８】
なお、種パターンに拡張パターンがいくつか追加された時点で、種パターン含有ツリーのいくつかが種パターン含有ツリーに該当しなくなることがある。すなわち、追加された拡張パターンを含まないツリーについては、含有ツリーから除外する必要がある。そのため、実際には、拡張パターンを含むツリー数について閾値判定は拡張パターンの探索及び集計処理が終わるたびに、種パターン出現箇所情報保持部１０６に記憶される対応関係及び種パターン含有ツリーデータ情報保持部１１０に記憶される識別子は更新される。拡張パターンの探索処理もノードを一つずる追加する処理を再帰的に呼び出すことで実現されるので、種パターン含有ツリーからいくつかのツリーデータを除外したものも、再帰処理から戻った際に種パターン含有ツリーとして復帰させるよう構成することは容易である。
【００７９】
以上の処理により、予め定められる数以上のツリーデータに含まれるパターンを抽出する処理において、探索及び集計処理は全てのツリーデータ（複数のツリーデータ）に対して行われず、種パターン含有ツリーデータ情報保持部１１０に記憶される情報で示されるツリーデータに対してのみ実行されるため、拡張パターン生成処理の処理量が、ツリーデータ情報蓄積部１０８に蓄積される複数のツリーデータの全てを対象として行う場合より小さくなる。
【００８０】
また、拡張ノード探索部１１４は、探索ガイド制御部１１２により定義されるガイドにより規定される範囲で拡張ノードを探索するため、全範囲に対して一度に探索処理を行う場合に比べて処理の効率が高く、かつ漏れなく探索が実行される。
【００８１】
また、拡張パターン生成部１１８は、拡張パターンが種パターンの一部を含む場合には、拡張パターンの出力を制限することにより、求められる拡張パターンのみが拡張パターン記憶部１２０に記憶され、拡張パターンを記憶するために使用される拡張パターン記憶部１２０の記憶容量が、生成される全ての拡張パターンが記憶されている場合に比べ削減される。
【００８２】
そして、従来技術における拡張パターンの探索処理が全てのツリーデータに対して行われていた場合に対して、探索に要する処理量は（１／２）の（種パターンのノード数）乗程度まで削減される。
【００８３】
なお、情報抽出装置１００はパソコン等の情報処理装置であり、情報処理装置のメモリーに記憶されるプログラムを動作させることで実現される。このプログラムは、通信によって提供されてもよいし、コンピュータによる読み取りが可能な、ＣＤ−ＲＯＭ等の記憶媒体に格納されて提供されてもよい。
【００８４】
また、本実施形態では入力受付部１０２としてキーボード、出力部１２２としてディスプレイが設けられる構成が示されたが、これに限定されず、例えば入力受付部１０２としてタッチパネル、受信装置等が設けられてもよいし、出力部１２２として、プリンタや、記憶媒体への書き込み装置が設けられてもよい。また、情報抽出装置１００は１つの装置として構成されていなくてもよく、例えば各構成が互いに離れた情報処理装置によって実現されてもよい。
【００８５】
本実施形態に係る構成は、例えば医療機関における患者の処置データの管理に適用可能である。この場合、患者ごとに１つのツリーデータが構成され、ツリーの階層（深さｄ）ごとに「手術前、手術後」、「何日前（後）」、「処置内容」、「処方した薬」がラベルに相当する内容としてデータベースに記憶される。そしてこのデータベースに対して、例えば「手術の２日前にこの薬を投与したケースにおいて、他に投与された薬（所定人数以上の患者に投与された薬）を知りたい」といったケースに、本実施形態に係る構成は適用可能である。
【符号の説明】
【００８６】
１００  情報抽出装置、１０２  入力受付部、１０４  種パターン情報保持部、１０６  種パターン出現箇所情報保持部、１０８  ツリーデータ情報蓄積部、１１０  種パターン含有ツリーデータ情報保持部、１１２  探索ガイド制御部、１１４  拡張ノード探索部、１１６  拡張ノード集計部、１１８  拡張パターン生成部、１２０  拡張パターン記憶部、１２２  出力部、２００  グラフ、３００，４００，５００，６００，７００，８００，９００，１０００，１１００，１２００  ツリー、１４００，２１００  種パターン。
【図１】
2011123626.tif 000003
【図２】
2011123626.tif 000004
【図３】
2011123626.tif 000005
【図４】
2011123626.tif 000006
【図５】
2011123626.tif 000007
【図６】
2011123626.tif 000008
【図７】
2011123626.tif 000009
【図８】
2011123626.tif 000010
【図９】
2011123626.tif 000011
【図１０】
2011123626.tif 000012
【図１１】
2011123626.tif 000013
【図１２】
2011123626.tif 000014
【図１３】
2011123626.tif 000015
【図１４】
2011123626.tif 000016
【図１５】
2011123626.tif 000017
【図１６】
2011123626.tif 000018
【図１７】
2011123626.tif 000019
【図１８】
2011123626.tif 000020
【図１９】
2011123626.tif 000021
【図２０】
2011123626.tif 000022
【図２１】
2011123626.tif 000023