情報処理装置及び情報処理プログラム
【課題】複数の木構造内で複数回現れる構造パターンの探索において、ノードを加えた場所毎に再帰的処理による探索を行うようにした情報処理装置を提供する。
【解決手段】情報処理装置の第１の探索手段は、複数の木構造内で複数回現れる構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより下位のノードに対して行い、第２の探索手段は、前記構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより上位のノードであって該上位のノードの下位にあり、かつ未探索のノード毎に探索し、前記第１の探索手段と前記第２の探索手段は、探索の対象とすべきノードがなくなった場合に、該探索を始めた元のノードに戻る。
【解決手段】情報処理装置の第１の探索手段は、複数の木構造内で複数回現れる構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより下位のノードに対して行い、第２の探索手段は、前記構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより上位のノードであって該上位のノードの下位にあり、かつ未探索のノード毎に探索し、前記第１の探索手段と前記第２の探索手段は、探索の対象とすべきノードがなくなった場合に、該探索を始めた元のノードに戻る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置及び情報処理プログラムに関する。
【背景技術】
【０００２】
コンピュータの処理能力、記憶装置の容量の飛躍的な増大に加え、ＩＴ化やネットワーク化が進んだことで大量な情報が容易に集められるようになってきた。集めた情報から市場機会やリスクに関する情報を早期に発見したり、隠れた知識を発見したりすることへの期待が高まっている。
しかし、集めた情報の量はしばしば人間の処理能力をはるかに超えるものとなる。このため、せっかく大量に集めた情報からリスクを発見したり、知識を抽出したりして活用することは実際には労力を伴う難しいものであった。
【０００３】
一方、パターン・マイニング等の技術の進展により、そのような大量の情報の中から例えば同時に購入される商品のパターンなどの情報が抽出可能となってきた。同時に購入される品物のパターンや購入される順序のパターンを抽出する技術が顧客の購買行動の分析などの需要から注目を集めて研究開発されてきたが、最近ではさまざまな情報の構造化、半構造化が進んできたこともあり、木構造のような構造を持つパターンを抽出するパターン・マイニングの技術が注目されてきている。構造情報を抽出するパターン・マイニングの技術の中でも、特に木構造はＸＭＬ（ｅＸｔｅｎｓｉｂｌｅ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）をはじめとしてドキュメントの構造化や知識表現などさまざまな情報の構造化に用いられるためパターン抽出への期待も大きい。
【０００４】
木構造のデータ群から部分木のパターンを抽出する技術には大きく分けて、親子関係が厳密に一致する構造だけを抽出するｉｎｄｕｃｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇの技術と、親子関係が多少乱れても先祖―子孫の関係があれば構造を抽出するｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇの技術がある。
現実社会で発生するデータ、例えばドキュメントの操作履歴などのように人の操作を記録したものでは、人がたとえ同じように作業を行ったつもりでも、操作履歴のデータ上では必ずしもデータの親子関係が一致しないことがしばしば起きる。そのような場合にはｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇの技術を適用することが望ましい。現実世界のデータではしばしば同様にゆれが生じるため、ｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇの技術への期待は高い。ｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇを実現する技術として、開示されているものには、ＴｒｅｅＭｉｎｅｒ、Ｄｒｙａｄｅ、ＭＢ３−Ｍｉｎｅｒなどの技術が挙げられる。
【０００５】
これらに関連する技術として、例えば、特許文献１には、データの集合からその中に含まれる重要なパターンを検出する方法及びシステムを提供することを課題とし、木構造データで表わされたデータ集合を含むデータベースから、集計対象となる候補パターンを用いて、頻出パターンを検出するシステムであって、（１）データベースから候補パターンにマッチするパターンを集計する手段と、（２）前記集計により出現頻度の高いパターンを検出する手段と、（３）前記検出したパターンから、次の集計対象となる候補パターンを生成する手段と、を有するように構成することが開示されている。
【０００６】
また、例えば、特許文献２には、順序木において頻出するパターンを抽出するのに好適な抽出装置等を提供することを課題とし、抽出装置の入力受付部は、１つ以上の順序木の入力を受け付け、変換部は、入力を受け付けられた順序木のそれぞれを系列表現へ変換し、抽出部は、変換された系列表現のそれぞれが含むパターンのうち、所定の頻度以上で出現するパターンを抽出し、系列表現は、順序木を深さ優先探索して、枝を進む際に通過する節はその名前を表わすマークを、枝を戻る際はバックトラックマークを、それぞれ並べることによりでき、パターンは、系列表現であるマークの列中の名前を表わすマークのいずれかを最初のマークとして、これから射影を０回以上繰り返したときに、最初のマークから最後のマークに至るまでに出会うマークの列をいい、射影が成立するか否かは、マークの列の列文脈と、射影文脈の値により判定することが開示されている。
【特許文献１】特開２００１−１３４５７５号公報
【特許文献２】特開２００４−３５５４５７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、複数の木構造内で複数回現れる構造パターンの探索において、ノードを加えた場所毎に再帰的処理による探索を行うようにした情報処理装置及び情報処理プログラムを提供することを目的としている。
【課題を解決するための手段】
【０００８】
かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
請求項１の情報処理装置は、複数の木構造内で複数回現れる構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより下位のノードに対して行う第１の探索手段と、前記構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより上位のノードであって該上位のノードの下位にあり、かつ未探索のノード毎に探索する第２の探索手段を具備し、前記第１の探索手段と前記第２の探索手段は、探索の対象とすべきノードがなくなった場合に、該探索を始めた元のノードに戻ることを特徴とする。
【０００９】
請求項２の情報処理装置は、請求項１に記載する情報処理装置であって、前記構造パターン内の現在の処理対象である現処理対象となっているノードと一致する前記木構造内でのノードのうち上下関係のあるものについては最上位のノードに基づいて、子孫を探索する範囲を決定する第１の探索範囲決定手段をさらに具備し、前記第１の探索手段は、前記第１の探索範囲決定手段によって決定された範囲に基づいて探索を行うことを特徴とする。
【００１０】
請求項３の情報処理装置は、請求項１に記載する情報処理装置であって、前記構造パターン内での親ノードと一致する前記木構造内でのノードのうち上下関係のあるものについては最上位のノード及び前記構造パターン内での子ノードと一致する前記木構造内でのノードに上下関係のあるものについては最下位のノードに基づいて、探索範囲を決定する第２の探索範囲決定手段をさらに具備し、前記第２の探索手段は、前記第２の探索範囲決定手段によって決定された範囲に基づいて探索を行うことを特徴とする。
【００１１】
請求項４の情報処理装置は、請求項３に記載する情報処理装置であって、前記構造パターン内の現在の処理対象となっているノードの先祖のノードの出現箇所の中から、該現在の処理対象となっているノードの出現箇所のノードを子孫に含むノードに対応する出現箇所を保持する保持手段をさらに具備することを特徴とする。
【００１２】
請求項５の情報処理装置は、請求項４に記載する情報処理装置であって、前記木構造内で分岐のない範囲の最上位及び最下位以外の出現箇所を前記保持手段から削除する削除手段をさらに具備することを特徴とする。
【００１３】
請求項６の情報処理装置は、請求項４に記載する情報処理装置であって、前記保持手段に保持させる出現箇所を対象とし、前記木構造内で分岐のない範囲の最上位及び最下位以外の出現箇所以外を削除したものを選別する選別手段をさらに具備することを特徴とする。
【００１４】
請求項７の情報処理プログラムは、コンピュータを、複数の木構造内で複数回現れる構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより下位のノードに対して行う第１の探索手段と、前記構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより上位のノードであって該上位のノードの下位にあり、かつ未探索のノード毎に探索する第２の探索手段として機能させ、前記第１の探索手段と前記第２の探索手段は、探索の対象とすべきノードがなくなった場合に、該探索を始めた元のノードに戻ることを特徴とする。
【発明の効果】
【００１５】
請求項１記載の情報処理装置によれば、複数の木構造内で複数回現れる構造パターンの探索においてノードを加えた場所毎に再帰的処理による探索を行うことができる。
【００１６】
請求項２記載の情報処理装置によれば、探索処理における記憶容量及び処理時間の増大を抑制することができる。
【００１７】
請求項３記載の情報処理装置によれば、探索処理における記憶容量及び処理時間の増大を抑制することができる。
【００１８】
請求項４記載の情報処理装置によれば、探索状態を保持して、その探索における再帰的処理が実行できる。
【００１９】
請求項５記載の情報処理装置によれば、探索処理における記憶容量をより削減することができる。
【００２０】
請求項６記載の情報処理装置によれば、探索処理における記憶容量をより削減することができる。
【００２１】
請求項７記載の情報処理プログラムによれば、複数の木構造内で複数回現れる構造パターンの探索においてノードを加えた場所毎に再帰的処理による探索を行うことができる。
【発明を実施するための最良の形態】
【００２２】
まず、前述のＴｒｅｅＭｉｎｅｒ、Ｄｒｙａｄｅ、ＭＢ３−Ｍｉｎｅｒの技術について、説明する。
Ｄｒｙａｄｅは、兄弟ノードに同じものを含めないという機能制限があり、そのような場面が頻出するドキュメントの操作履歴などのマイニングには適さない。
ＭＢ３−Ｍｉｎｅｒは、幅優先探索であり、処理の階層毎に用意するパターン候補の数が膨大なものになるため、大規模なデータに適用するには限界がある。
また、ＴｒｅｅＭｉｎｅｒは、深さ優先探索であると主張されてはいるが、実際にはツリー（木）構造のルートから葉ノードをつないだパス方向に発生する枝の候補を全て再帰処理の深さ方向に送り込むことを行う。このため幅優先探索と同様の問題が生じてしまい、大規模なデータに適用すると候補生成でパターン候補の数が膨大なものになり処理できなくなるという問題があった。
【００２３】
また、ＭＢ３−ＭｉｎｅｒやＴｒｅｅＭｉｎｅｒにおいては、ツリーの出現位置（パターン木の中の各ノードと、データの木の中のノードとの対応関係）を管理するが、ｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇの場合には、その数が深さ方向に広がる子孫ノード候補の組み合わせにより指数関数的に膨れ上がるという問題があった。ＴｒｅｅＭｉｎｅｒでは、ＴｒｅｅＭｉｎｅｒＤにおいて、このことに対する対策がとられているが、実際には十分に機能していない。
同様の状況はドキュメントの操作履歴だけで生じるものではなく、例えば、たんぱく質の構造データなどにおいても同じラベルを持つノードが一連の系列の中に何度も現れることは少なくない。出現位置の組み合わせの管理については、このような場合に大量の情報を管理しなければならなくなり、処理に必要な記憶容量の増大と処理対象のデータの増大による処理コストの増大という問題が発生し、大規模なデータの処理を現実的な時間とリソースで実現することを難しくしてしまう。
つまり、従来は、木構造をストリング形式に変換して又はそれと等価なものに変換して探索を行っていた。本実施の形態は、木構造自体の探索を行うようにしているものである。
【００２４】
本実施の形態は、要素間に設定した関係を木構造として扱えるデータ群の中から、複数回にわたって現れる関係構造（部分木のパターン、以下、構造パターン、構造パターン木、パターンともいう）を抽出する技術に関するものである。
本実施の形態は、ルートノード（根）からリーフノード（葉）にいたるパス（以降、Ｅｐａｔｈともいう）、各ノードの属するＥｐａｔｈの範囲（以降、ＥｐＲａｎｇｅともいう）、のデータを用い、探索ステップに合わせて管理するノード出現情報管理機構を用いた、深さ優先探索で探索処理を行う情報抽出装置である。
さらに、パターン抽出の効率を上げるために、前記ＥｐＲａｎｇｅを用いたツリーデータ管理機構を備えている。
【００２５】
以下、図面に基づき本発明を実現するにあたっての好適な一実施の形態の例を説明する。
図１は、本実施の形態を適用するに好適なシステムの概念構成図である。このシステムは、構造情報ＤＢ１１０、情報収集装置１２０、情報抽出装置１３０、抽出情報管理装置１４０を有している。これらは、通信回線を介して接続されている。なお、これらの全ての装置群が一つの装置内に構築されていてもよいし、これらのうちの一部の装置が一つの装置内に構築されていてもよい。
【００２６】
構造情報ＤＢ１１０は、情報収集装置１２０、情報抽出装置１３０と接続されており、情報収集装置１２０から受け取ったデータであり、情報を抽出すべき対象である木構造データを蓄積して管理し、情報抽出装置１３０からアクセスされる。
情報収集装置１２０は、構造情報ＤＢ１１０と接続されており、図示しない他の装置から情報を集めて、あるいは図示しない他の装置から送信された情報を受け取って、必要なら情報の整形（情報抽出装置１３０が扱えるような木構造データへの変換）を行って、構造情報ＤＢ１１０に格納する。
情報抽出装置１３０は、構造情報ＤＢ１１０、抽出情報管理装置１４０と接続されており、構造情報ＤＢ１１０にアクセスして、木構造データから頻出情報を抽出して抽出情報管理装置１４０に送信する。
抽出情報管理装置１４０は、情報抽出装置１３０と接続されており、情報抽出装置１３０から送信された頻出情報を受け取って蓄積したり表示装置や印刷装置などの図示しない他の装置に送信したりする。
【００２７】
図２は、本実施の形態の情報抽出装置１３０内の構成例についての概念的なモジュール構成図である。
なお、モジュールとは、一般的に論理的に分離可能なソフトウェア（コンピュータ・プログラム）、ハードウェア等の部品を指す。したがって、本実施の形態におけるモジュールはコンピュータ・プログラムにおけるモジュールのことだけでなく、ハードウェア構成におけるモジュールも指す。それゆえ、本実施の形態は、コンピュータ・プログラム、システム及び方法の説明をも兼ねている。ただし、説明の都合上、「記憶する」、「記憶させる」、これらと同等の文言を用いるが、これらの文言は、実施の形態がコンピュータ・プログラムの場合は、記憶装置に記憶させる、又は記憶装置に記憶させるように制御するの意である。また、モジュールは機能にほぼ一対一に対応しているが、実装においては、１モジュールを１プログラムで構成してもよいし、複数モジュールを１プログラムで構成してもよく、逆に１モジュールを複数プログラムで構成してもよい。また、複数モジュールは１コンピュータによって実行されてもよいし、分散又は並列環境におけるコンピュータによって１モジュールが複数コンピュータで実行されてもよい。なお、１つのモジュールに他のモジュールが含まれていてもよい。また、以下、「接続」とは物理的な接続の他、論理的な接続（データの授受、指示、データ間の参照関係等）を含む。
また、システム又は装置とは、複数のコンピュータ、ハードウェア、装置等がネットワーク（一対一対応の通信接続を含む）等の通信手段で接続されて構成されるほか、１つのコンピュータ、ハードウェア、装置等によって実現される場合も含まれる。「装置」と「システム」とは、互いに同義の用語として用いる。
【００２８】
図１に示した情報抽出装置１３０は、図２に示すように構造情報管理モジュール２１０、出現情報選択モジュール２２０、出現情報管理モジュール２３０、調査範囲処理モジュール２４０、探索処理モジュール２５０、探索状態管理モジュール２６０、抽出情報処理モジュール２７０を有している。
【００２９】
構造情報管理モジュール２１０は、出現情報選択モジュール２２０、出現情報管理モジュール２３０、調査範囲処理モジュール２４０と接続されており、構造情報ＤＢ１１０中の構造情報を調査範囲処理モジュール２４０の指定にしたがって調査し、木構造データ中のノードの出現をラベル毎に集計する。また、構成によってはラベル毎に出現位置情報を収集するようにしてもよい。この集計結果である出現情報は、出現情報管理モジュール２３０に送信される。なお、出現情報には、出現箇所の情報と幾つの木に出現したかを示す集計値の両方を含んでいる。また、構造情報管理モジュール２１０は、必要であれば図示しない記憶手段を有し、構造情報ＤＢ１１０中の構造情報を処理に適したデータ構造に変換して蓄積することを行ってもよい。
【００３０】
出現情報選択モジュール２２０は、構造情報管理モジュール２１０、出現情報管理モジュール２３０と接続されており、構造情報管理モジュール２１０によって生成された出現情報に基づいて、対象とするラベルを選択する。つまり、構造情報管理モジュール２１０によって出現が確認されたノードのラベル毎の出現情報を受け取り、予め定めた基準を満たす要素（予め設定された回数以上出現するものなど）と満たさない要素を選別する。又は、図示しない入力装置によりユーザから指定された条件に見合わない出現情報を破棄したりして出現情報を整理する。
【００３１】
出現情報管理モジュール２３０は、出現情報選択モジュール２２０、探索処理モジュール２５０、構造情報管理モジュール２１０と接続されており、出現情報選択モジュール２２０により選択されたノードのラベルと出現情報を受け取り管理する。この情報を探索処理モジュール２５０の要求により順に探索処理モジュール２５０に送信する。
【００３２】
調査範囲処理モジュール２４０は、構造情報管理モジュール２１０、探索処理モジュール２５０、探索状態管理モジュール２６０と接続されており、探索状態管理モジュール２６０に記憶されている探索状態及び構造情報管理モジュール２１０によって生成され、探索処理モジュール２５０の指示にしたがって出現情報管理モジュール２３０から複製、あるいは移動して探索状態管理モジュール２６０内に格納されている出現情報に基づいて、木構造データ内の構造パターンの探索範囲を決定する。
【００３３】
探索処理モジュール２５０は、出現情報管理モジュール２３０、調査範囲処理モジュール２４０、探索状態管理モジュール２６０、抽出情報処理モジュール２７０と接続されており、出現情報管理モジュール２３０、調査範囲処理モジュール２４０、探索状態管理モジュール２６０、抽出情報処理モジュール２７０による処理を制御して、調査範囲処理モジュール２４０によって決定された探索範囲に基づいて、構造情報管理モジュール２１０が取り出し、出現情報選択モジュール２２０により選択されたラベルと出現情報を出現情報管理モジュール２３０から得て木構造データ内に複数回出現する構造パターンの探索を行い、その探索結果を抽出情報処理モジュール２７０へ渡す。この探索処理は適時探索状態管理モジュール２６０の探索状態を更新し再帰的に実行する。
【００３４】
探索状態管理モジュール２６０は、調査範囲処理モジュール２４０、探索処理モジュール２５０と接続されており、探索処理の途中状態を格納、管理する。記憶されるこの途中の状態は、探索処理モジュール２５０による再帰的な探索処理に利用される。探索処理モジュール２５０による探索処理中のパターン候補情報、構造パターン中のノードの各構造情報中での出現情報の保持と処理の過程における出現情報の更新・回復などを受け持つ。
抽出情報処理モジュール２７０は、探索処理モジュール２５０と接続されており、探索処理モジュール２５０より抽出したパターンを受け取り、図示しない記憶装置に格納したり、図示しない出力装置への出力処理を受け持つ。
【００３５】
図３は、本実施の形態による処理例を示したフローチャートである。
ステップＳ３０２（走査用情報の準備）では、構造情報管理モジュール２１０は、後の処理を効率的に実行するための準備を行うために、構造情報ＤＢ１１０に格納された構造情報を変換し、図示しない記憶手段に格納する。
【００３６】
図８は、説明のために用いる木構造データの例である。
例示した３つの木構造データＴｒ１（図８（ａ）），Ｔｒ２（図８（ｂ）），Ｔｒ３（図８（ｃ））には、それぞれ１６個、１６個、１１個のノードがある。説明の簡易化のために、兄弟間には順序関係があるとし、深さ優先探索でノードを辿った場合の順番をもとに、ノードにｖ０、ｖ１、・・・と識別子を設定した。以降、木構造を示す必要がない場合には、単にｖ０やｖ２等の表記でノードを指し、どの木データであるかを示す必要がある場合にはｖ０Ｔｒ１、ｖ２Ｔｒ２のようにそれぞれのノードが属する木データの識別子を添えて表記する。
図８に示した例では、ノードのラベルをＡ，Ｂ，Ｃ，・・・とした。例に現れるノードのラベルは、Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｉ，Ｊ，Ｋである。図８の丸内のアルファベットはそのノードのラベルである。
【００３７】
また、パターン抽出の条件を２つ以上の木構造データで出現するパターンとして説明する。
図９に示す例は、それぞれの木構造データについて、それぞれのルートノードからリーフノードまでのパスを示した図である。図中でそれぞれのパスにＥｐ１〜Ｅｐ６までの識別子をつけている。これも同様に木を示す必要がある場合には、Ｅｐ１Ｔｒ１のように木データの識別子を添えて表記する。例えばＥｐ４Ｔｒ１（Ｔｒ１のＥｐ４）は、ｖ０，ｖ１０，ｖ１１，ｖ１２，ｖ１３を通るパスであり、Ｅｐ２Ｔｒ３（Ｔｒ３のＥｐ２）は、ｖ０，ｖ１，ｖ２，ｖ３，ｖ４，ｖ６を通るパスである。
Ｅｐａｔｈをこのように設定することで、各ノードは少なくとも１つのＥｐａｔｈ上にあり、ノードによっては複数のＥｐａｔｈ上にある。例えば、ｖ１２Ｔｒ１は、Ｅｐ４Ｔｒ１とＥｐ５Ｔｒ１の上にあり、ｖ７Ｔｒ２は、Ｅｐ３Ｔｒ２とＥｐ４Ｔｒ２とＥｐ５Ｔｒ２の上にある。
【００３８】
各ノードが、どのＥＰａｔｈ上にあるかを示す情報ＥｐＲａｎｇｅを各ノードの関数として定義する。例えば、ＥｐＲａｎｇｅ（ｖ１２Ｔｒ１）＝｛Ｅｐ４Ｔｒ１，Ｅｐ５Ｔｒ１｝であり、ＥｐＲａｎｇｅ（ｖ７Ｔｒ２）＝｛Ｅｐ３Ｔｒ２，Ｅｐ４Ｔｒ２，Ｅｐ５Ｔｒ２｝である。
ここで、対象としている木構造は順序木を仮定しているため、ＥｐＲａｎｇｅに現れるＥＰａｔｈの番号は、連続する。そこで、説明の簡易化のためＥｐＲａｎｇｅを単純にＥＰａｔｈの番号の一番小さいものと一番大きいもので示すこととする。すなわち、次のように表記する。例えば、ＥｐＲａｎｇｅ（ｖ１２Ｔｒ１）＝［４，５］、ＥｐＲａｎｇｅ（ｖ７Ｔｒ２）＝［３，５］である。
このとき、ＥｐＲａｎｇｅの小さい側の番号をＥｐＲａｎｇｅＬ、大きい側の番号をＥｐＲａｎｇｅＲとして同様に関数で表わす。例えば、ＥｐＲａｎｇｅＬ（ｖ１２Ｔｒ１）＝４、ＥｐＲａｎｇｅＬ（ｖ７Ｔｒ２）＝３であり、ＥｐＲａｎｇｅＲ（ｖ１２Ｔｒ１）＝５、ＥｐＲａｎｇｅＲ（ｖ７Ｔｒ２）＝５である。
【００３９】
また、ＥｐＲａｎｇｅをノードの関数としてではなく、単にＥＰａｔｈの範囲として参照することも行う。例えば、｛Ｅｐ２Ｔｒ３，Ｅｐ３Ｔｒ３，Ｅｐ４Ｔｒ３｝を参照したい際に、単にＴｒ３のＥｐＲａｎｇｅＴｒ３［２，４］ と示すことも行う。また同様に、ＥｐＲａｎｇｅＬをＥｐＲａｎｇｅの小さい番号、ＥｐＲａｎｇｅＲをＥｐＲａｎｇｅの大きい番号としても用いる。
【００４０】
図１０に、図８に示した例のＴｒ１，Ｔｒ２，Ｔｒ３中の各ノードについて、（ノード識別子、ラベル、ＥｐＲａｎｇｅＬ，ＥｐＲａｎｇｅＲ）の組を示した。図１０（ａ）では、それぞれノードの識別子１００１ａ、ノードのラベル１００２ａ、ＥｐＲａｎｇｅＬ１００３ａ、ＥｐＲａｎｇｅＲ１００４ａが該当する。例えば、図１０（ａ）に示すＴｒ１のノード識別子：Ｖ０は、Ａというノードのラベルであり、ＥｐＲａｎｇｅＬは１、ＥｐＲａｎｇｅＲは６である。
【００４１】
構造情報管理モジュール２１０は、各木構造データに対してノードの存在範囲やＥｐＲａｎｇｅ範囲を指定してノードを走査する機能を有するために、図示しない内部の記憶手段に各ツリー情報中の必要な情報を別のデータ構造で保持することもできる。
【００４２】
図１１、図１２、図１３には、ツリー情報を内部に格納する一例を示した。図１１、図１２、図１３は、それぞれＴｒ１，Ｔｒ２，Ｔｒ３について、各ノードをＥｐＲａｎｇｅＬの値から辿りやすく格納した例であり、ツリーを深さ優先に辿りながらそれぞれのノードのＥｐＲａｎｇｅＬの場所にデータを追加することで構成できる。つまり、例えば図１１に示すＴｒ１のＥｐ情報１１００は、Ｅｐ１ １１０１、Ｅｐ２ １１０２、Ｅｐ３ １１０３、Ｅｐ４ １１０４、Ｅｐ５ １１０５、Ｅｐ６ １１０６へのリンク情報を含むものである。また、図示する都合上１１０１，１１０２、１１０３，１１０４，１１０５，１１０６が個別に示してあるが、これらが図１０に示したような順で連続領域に配置されてもよい。
【００４３】
図１１、図１２、図１３に示すツリー情報例の各ノードに対応するデータは、図１０に示した（ノード識別子、ラベル、ＥｐＲａｎｇｅＬ，ＥｐＲａｎｇｅＲ）の組に加えて、一番右に番号を加えている。この番号は、各データの同じＥｐＲａｎｇｅＬの中での位置を示す番号である。この番号は、同じＥｐＲａｎｇｅＬで、次に下位のデータを探すといった場合に用いるためのものである。
例えばＴｒ２について、ＥＰａｔｈ３，ＥＰａｔｈ４の上にあるノードを列挙したいとすると、ＥｐＲａｎｇｅＬが３あるいは４であるノードを辿って、ＥｐＲａｎｇｅＲが５より大きくならないものを探して列挙するという方法で簡単に実現できる。ただし、Ｅｐ３，Ｅｐ４の上にあるノードは、これだけが全てではなく、ＥｐＲａｎｇｅＬがＥｐ１であるｖ０，ｖ１が残される。しかし、後述する追加処理によって、このｖ０，ｖ１のようなノードも簡単に列挙することができる。
本実施の形態では、ＥｐＲａｎｇｅを指定して効率的にノードを列挙できる方法の一例として図１１、図１２、図１３に示すデータ構造を使って説明を行うが、他のデータ管理方法、例えばバケット分割を用いる方法や探索のための探索木による方法を適用してもよい。
【００４４】
ステップＳ３０４（要素の出現を集計）では、構造情報管理モジュール２１０によって、各ラベルがいくつのツリーで出現したかを集計する。この処理は前述のステップＳ３０２の際に同時に実行することもできる。処理の結果、各ラベルがいくつの木構造データで出現したかを判定できる情報を得て、パターン抽出の条件に見合うものだけを残した頻出要素（本実施の形態ではノードのラベル）のリストを作成する。構成により、各頻出要素の出現位置情報（以降簡単に出現情報とも呼ぶ）も合わせて処理結果となる。
ここでの例では、Ａ，Ｂ，Ｃ，Ｄ，Ｆが頻出要素のリストに残る。この頻出要素のリストにしたがい、リスト中の頻出要素それぞれをルートノードとした構造パターンを抽出する処理を以降の繰り返し処理で行う。
【００４５】
ステップＳ３０６（頻出要素処理終了？）では、頻出要素のリスト内のノードのラベル（例に示したＡ，Ｂ，Ｃ，Ｄ，Ｆ）それぞれについて処理が繰り返されたことを、検査し、処理の流れを制御する。頻出要素のリスト中の全てのラベルについて処理が終わったところで、処理を終了する（ステップＳ３１４）。
【００４６】
ステップＳ３０８（処理対象要素選択）では、出現情報選択モジュール２２０が、頻出要素のリスト内の未処理のものから一つ選ぶ。例ではノードのラベル、Ａ，Ｂ，Ｃ，Ｄ，Ｆの中から未処理のものを一つ選ぶことになる。どのラベルを選択した場合も処理の流れは共通であるため、以降ではラベルＡを選択した場合について説明を行う。
【００４７】
ステップＳ３１０（探索状態作成）では、探索状態管理モジュール２６０が、選択したラベルが各構造データにおいてどこで出現したかを示す情報を用意する。
このステップＳ３１０は、ステップＳ３０４において各ラベルの出現位置情報も合わせて出現情報管理モジュール２３０に格納される構成の場合には、その情報を取り出してくるだけの処理となる。構成によっては、記憶容量などの関係から出現位置の情報が出現情報管理モジュール２３０に記憶されていない場合もあり、そのような場合には、この段階で構造情報を走査して出現位置の情報を抽出するようにしてもよい。
例えば、ラベルＡの出現情報は、図１４に示すように、Ｔｒ１の出現情報１４１０内のｖ０Ｔｒ１、ｖ２Ｔｒ１、ｖ４Ｔｒ１、ｖ１２Ｔｒ１、Ｔｒ２の出現情報１４２０内のｖ１Ｔｒ２、ｖ３Ｔｒ２、ｖ９Ｔｒ２、ｖ１１Ｔｒ２、Ｔｒ３の出現情報１４３０内のｖ０Ｔｒ３、ｖ８Ｔｒ３、となる。ここで、図１４に示した出現情報は、図１１、図１２、図１３に格納されている情報と同じものを用いた。つまり、（１）「ノードの識別子」、（２）「ラベル」、（３）「ＥｐＲａｎｇｅＬ」、（４）「ＥｐＲａｎｇｅＲ」、（５）「ＥｐＲａｎｇｅＬ」を同じとして格納されている情報内での番号の組として示してある。
【００４８】
この出現情報に加えて、選択したラベルをルートとした構造パターン木を作成し、その構造パターン木中の現在処理位置を設定して、図１５の例に示す探索状態ノードを作成する。つまり、探索状態ノードは、構造パターン木１５１０、出現情報１５２０、変更情報スタック１５３０を有している。構造パターン木１５１０は、ステップＳ３０８で選択されたラベルのノードをルートとした構造パターン木とその構造パターン木中の現在処理位置を記憶している。出現情報１５２０内のＴｒ１ １５２１、Ｔｒ２ １５２２、Ｔｒ３ １５２３は、図１４で示した出現情報１４１０、出現情報１４２０、出現情報１４３０と同じものである。変更情報スタック１５３０は、後述の処理で使用するものである。
【００４９】
この探索状態ノードをルートノードとして、探索状態を図１６の例に示すように作成して、探索状態管理モジュール２６０に格納する。図１６は、探索状態ノードに格納されている構造パターン木に対応するパターンの構造を文字列で示したものを探索状態ノード（Ａ）１６１０に示したものである。
なお、構造パターン木の文字列の表記は、ここでは、｛親｝［｛子供１｝，｛子供２｝，・・・］という書き方を再帰的に適用することにより示す。ただし、子供がないノードについては［］を省略する。
【００５０】
ステップＳ３１２では、探索処理モジュール２５０が、頻出構造パターン探索を行う。ステップＳ３１２については、図４に示すフローチャートを用いて説明する。
なお、ステップＳ３１０（探索状態作成）は、ここではステップＳ３１２（頻出構造パターン探索）の前で行ったが、構成によってステップＳ３１０はステップＳ３１２の処理の中に組み込むこともできる。
【００５１】
図４は、本実施の形態による頻出構造パターン探索の処理例を示したフローチャートである。ここで２種類の探索を行っている。つまり、第１の探索である下位探索（ステップＳ４０４）と第２の探索である横枝探索（ステップＳ４１０）である。
また、下位探索処理（ステップＳ４０４）は、複数の木構造データ内で複数回現れる構造パターンの探索を、前記木構造データ内の現在の処理対象となっているノードより下位のノードに対して行う。
そして、横枝探索処理（ステップＳ４１０）では、前記構造パターンの探索を、前記木構造データ内の現在の処理対象となっているノードより上位のノードであって、その上位のノードの下位にあり、かつ未探索のノード毎に行う。
下位探索処理と横枝探索処理では、探索の対象とすべきノードがなくなった場合に、その探索を始めた元のノードに戻るようにしている。
【００５２】
ステップＳ４０２（構造パターン情報出力）では、その時点での探索状態ノードの構造パターン木のデータを出力する。この出力の手前で予め定められた基準にしたがって、出力するか否かの判定を行ってもよい。
【００５３】
ステップＳ４０４（下位探索）では、子孫方向に頻出する部分構造を探索する。この下位探索を行うときに、構造パターン内の現在の処理対象である現処理対象となっているノードと一致する前記木構造データ内のノード（ノードの間で上下関係があるものについては最上位のノード）に基づいて、子孫を探索する範囲を決定するようにしており、下位探索処理は、その決定された範囲に基づいて探索を行う。なお、ステップＳ４０４については、図５に示すフローチャートを用いて説明する。
そして、下位探索とは別に親ノードや先祖ノードから横方向に部分構造を探索する、横枝探索（ステップＳ４１０）の繰り返し処理が行われる。この横枝探索を行うときに、構造パターン内での親ノードと一致する前記木構造データ内のノード（ノード間で上下関係のあるものについては最上位のノード）及び前記構造パターン内での子ノードと一致する前記木構造データ内のノード（ノード間に上下関係があるときには最下位のノード）に基づいて、探索範囲を決定するようにしており、横枝探索処理は、その決定された範囲に基づいて探索を行う。
なお、この繰り返し処理中のステップＳ４０６（横枝探索箇所残りあり？）や、ステップＳ４０８（横枝探索箇所選択）は、パターン木中にノードが複数ある方が説明しやすいため、これらのステップの説明は後で行う。ステップＳ４１０（横枝探索）も別途後述する。
【００５４】
図５は、本実施の形態による下位探索の処理例を示したフローチャートである。
ステップＳ５０２（下位探索範囲情報準備）では、子孫ノードの探索範囲の準備を行う。このステップでは、具体的には各構造データに対して子孫ノードを探索する範囲を指定する。ここではその指定をＥｐＲａｎｇｅにより行う例を示す。
パターン中のノードをラベルＡで選び、そのときの探索状態ノードは図１５に示すようになる。このとき、例えば、Ｔｒ１においてラベルＡの子孫の候補は、Ｔｒ１ １５２１に基づいて、ｖ０Ｔｒ１の子孫、あるいはｖ２Ｔｒ１の子孫、あるいはｖ４Ｔｒ１の子孫、あるいはｖ１２Ｔｒ１の子孫である。
【００５５】
ｖ０Ｔｒ１の子孫はＥｐＲａｎｇｅ（ｖ０Ｔｒ１）＝［１，６］の範囲にあり、ｖ２Ｔｒ１の子孫はＥｐＲａｎｇｅ（ｖ２Ｔｒ１）＝［１，３］の範囲にあり、ｖ４Ｔｒ１の子孫はＥｐＲａｎｇｅ（ｖ４Ｔｒ１）＝［１，２］の範囲にあり、ｖ１２Ｔｒ１の子孫はＥｐＲａｎｇｅ（ｖ１２Ｔｒ１）＝［４，５］の範囲に存在する。
【００５６】
下の条件全て（（１）と（２））を満たすノードは先祖にラベルＡを持つノードが存在する。
（１）ＥｐＲａｎｇｅ（ｖ０Ｔｒ１）＝［１，６］，ＥｐＲａｎｇｅ（ｖ２Ｔｒ１）＝［１，３］，ＥｐＲａｎｇｅ（ｖ４Ｔｒ１）＝［１，２］，ＥｐＲａｎｇｅ（ｖ１２Ｔｒ１）＝［４，５］のいずれかのＥｐＲａｎｇｅの範囲にある。
（２）ｖ０Ｔｒ１，ｖ２Ｔｒ１，ｖ４Ｔｒ１，ｖ１２Ｔｒ１のいずれのＥｐＲａｎｇｅも、そのノードのＥｐＲａｎｇｅよりも広いものが存在しないなら、同じＥｐＲａｎｇｅを持つものでより上位のものが存在する。
ただし、前述の２つの条件は、本実施の形態で用いた構造情報の管理方法において、重複なく子孫ノードを列挙する際の一方法のための条件である。パターンに対応する出現情報から、全ての子孫ノード候補を列挙できるのであれば他の方法を用いても構わない。
【００５７】
前述の条件にしたがって、子孫ノードを列挙する一方法を示す。
まず各構造データ（例では、Ｔｒ１，Ｔｒ２，Ｔｒ３）毎に出現データのＥｐＲａｎｇｅの包含関係を調べ、他のＥｐＲａｎｇｅに含まれないものだけを残す。なお、ＥｐＲａｎｇｅが同じであれば、同じＥｐＲａｎｇｅＬを持つものの間でつけた番号がより小さいものを残す。この処理により、Ｔｒ１ではｖ０Ｔｒ１、Ｔｒ２ではｖ１Ｔｒ２、Ｔｒ３ではｖ０Ｔｒ３がそれぞれ残る。
【００５８】
これらの出現情報をもとに子孫ノードの探索を行う。
ノードＡからの子孫ノードの探索例は、Ｔｒ１ではｖ１Ｔｒ１以下全てのノード、Ｔｒ２ではｖ２Ｔｒ２以下全てのノード、Ｔｒ３ではｖ３Ｔｒ３以下全てのノードとなる。
この走査の過程で、ステップＳ５０４（要素の出現を集計）において、各ラベル毎に出現情報が集計され集められる。
この段階でも頻出と判定されるラベルはＡ，Ｂ，Ｃ，Ｄ，Ｆとなる。
【００５９】
次にこれらの頻出ラベルのそれぞれを処理対象要素と選んだ処理が、それぞれステップＳ５０６（頻出要素処理終了？）によって繰り返される。
例えば、ステップＳ５０８（処理対象要素選択）で、Ｂを選んだとして説明を行う。このときのＢの出現情報は、図１７に示すように、Ｔｒ１の出現情報１７１０内のｖ１Ｔｒ１、ｖ３Ｔｒ１、ｖ６Ｔｒ１、ｖ１１Ｔｒ１、ｖ１３Ｔｒ１、Ｔｒ２の出現情報１７２０内のｖ２Ｔｒ２、ｖ４Ｔｒ２、ｖ７Ｔｒ２、ｖ１２Ｔｒ２、Ｔｒ３の出現情報１７３０内のｖ２Ｔｒ３、ｖ１０Ｔｒ３となる。
【００６０】
そして、次にステップＳ５１０（探索状態作成・更新）の処理を行う。つまり、ここでは、構造パターン内の現在の処理対象となっているノードの先祖のノードの出現箇所から、その現在の処理対象となっているノードの出現箇所のノードを子孫に含むノードに対応する出現箇所を保持するようにしている。
構造パターン木のルートノードＡの下にＢが子供のノードとしてついたパターンを登録し、構造パターン木の中の現在位置情報はＢの位置を指す。また、出現情報として図１７に示す出現情報１７１０、出現情報１７２０、出現情報１７３０を登録して、図１８の例に示すように探索状態ノードを作成して探索状態管理モジュール２６０に登録する。つまり、図１８の例に示す探索状態ノードは、構造パターン木１８１０にラベルＡのノードの下にラベルＢのノードを有している構造パターン木とその構造パターン木の中の現在の位置情報（ラベルＢのノード）を記憶しており、出現情報１８２０に図１７に示したものと同様のＴｒ１ １８２１、Ｔｒ２ １８２２、Ｔｒ３ １８２３を記憶しており、さらに、変更情報スタック１８３０に変更情報１８３１を記憶している。
【００６１】
ここでの探索状態は、図１９の例に示すようになる。つまり、図１９の例に示す探索状態は、探索状態ノード（Ａ）１９１０下に探索状態ノード（Ａ[Ｂ]）１９２０が接続されている。
【００６２】
そして、探索状態の更新を行う。具体的には、登録した探索状態ノードから順に上位の探索状態ノードを辿り、下位の探索状態ノードに登録されている出現位置を一つも含まない出現情報をいったん削除して変更情報スタック１８３０に格納する。
この例の状態では、下位の探索状態ノードがＡ［Ｂ］、上位の探索状態ノードがＡであり、探索状態ノードＡ［Ｂ］の出現情報を一つも範囲に含まないものを探索状態ノードＡの出現情報から移動して、変更情報スタック１８３０に格納する。ここでは、この条件に該当する出現情報が、探索状態ノードＡにないため、なにもしない。もし、構造パターン木中の先祖方向の木の状態を更新した場合には、その更新した出現状態ノードの情報を上位方向の更新を開始する際の探索状態ノード（この場合探索状態ノードＡ［Ｂ］）の変更情報スタック１８３０に格納する。
【００６３】
そして、再帰的にステップＳ５１２（頻出構造パターン探索）の処理に入る。
頻出構造パターン探索処理では、構造パターン情報の出力処理において、予め定められた条件にしたがって、構造パターン木の情報Ａ［Ｂ］が出力される。次に、同様に下位探索に入る。
次の下位探索の処理では、Ｂの出現情報からの探索範囲は下のノードの子孫を探索することになる。すなわち、Ｔｒ１ではｖ１Ｔｒ１とｖ１１Ｔｒ１の子孫、Ｔｒ２ではｖ２Ｔｒ２とｖ７Ｔｒ２の子孫、Ｔｒ３ではｖ２Ｔｒ３の子孫の探索である。
この範囲で探索すると、例えばｖ１０Ｔｒ１，ｖ１５Ｔｒ１，ｖ６Ｔｒ２，ｖ１１Ｔｒ３などは探索の範囲にはいってこないなど、探索範囲が狭められてくるが、この段階ではまだ頻出ノードはＡ，Ｂ，Ｃ，Ｄ，Ｆのままである。
【００６４】
次に、ここでラベルＣのノードが選ばれたとする。すると、Ｃの出現情報はｖ８Ｔｒ１、ｖ１４Ｔｒ１、ｖ５Ｔｒ２、ｖ８Ｔｒ２、ｖ１３Ｔｒ２、ｖ３Ｔｒ３、ｖ９Ｔｒ３となる。この結果探索状態ノードは図２０に示すようになり、探索状態は図２１に示すようになる。つまり、図２０の例に示す探索状態ノードは、構造パターン木２０１０にラベルＡのノードの下にラベルＢのノード、そのラベルＢのノードの下にラベルＣのノードを有している構造パターン木とその構造パターン木の中の現在の位置情報（ラベルＣのノード）を記憶しており、出現情報２０２０にＴｒ１ ２０２１、Ｔｒ２ ２０２２、Ｔｒ３ ２０２３を記憶しており、さらに、変更情報スタック２０３０に変更情報２０３１を記憶している。図２１に示す探索状態は、探索状態ノード（Ａ）１９１０の下に探索状態ノード（Ａ[Ｂ]）１９２０が接続され、探索状態ノード（Ａ[Ｂ]）１９２０の下に探索状態ノード（Ａ[Ｂ[Ｃ]]）２１３０が接続されている。
【００６５】
そして、探索状態ノードの上位のものの更新が行われる。図２０に示すＣの出現情報２０２０を下位に持たない、すなわちＥｐＲａｎｇｅが図２０のＣのＴｒ１ ２０２１、Ｔｒ２ ２０２２、Ｔｒ３ ２０２３の出現情報のいずれよりも大きくない、あるいは同じであったとしても番号が大きいものは、変更情報２０３１に加えられて変更情報スタック２０３０に格納される。
この場合、ｖ６Ｔｒ１、ｖ１３Ｔｒ１、ｖ４Ｔｒ２、ｖ１２Ｔｒ２、ｖ１０Ｔｒ３を変更情報２０３１に登録して、変更情報スタック２０３０に格納する。その結果探索状態ノードＡ［Ｂ］は、図２２に示すように更新される。つまり、図２２の例に示す探索状態ノードは、構造パターン木２２１０にラベルＡのノードの下にラベルＢのノードを有している構造パターン木とその構造パターン木の中の現在の位置情報（ラベルＢのノード）を記憶しており、出現情報２２２０にＴｒ１ ２２２１、Ｔｒ２ ２２２２、Ｔｒ３ ２２２３を記憶しており、さらに、変更情報スタック２２３０に変更情報２２３１、変更情報２２３２を記憶している。そして、この更新した情報を、更新の原因となった探索状態ノードＡ［Ｂ［Ｃ］］の変更情報２２３１に格納する。
【００６６】
そして、下位の探索状態ノードＡ［Ｂ］が更新されたので、その上位の探索状態ノードＡの更新検査を行う。この場合、出現情報のうちｖ４Ｔｒ１、ｖ１２Ｔｒ１、ｖ３Ｔｒ２、ｖ９Ｔｒ２、ｖ１１Ｔｒ２、ｖ８Ｔｒ３が下位に該当するＢを持たなくなるため、出現情報からはずされて変更情報スタックに移動される。そして、この更新した情報を、更新の原因となった探索状態ノードＡ［Ｂ［Ｃ］］の変更情報に格納する。この探索状態ノードＡの更新結果を図２３に示す。つまり、図２３の例に示す探索状態ノードは、構造パターン木２３１０にラベルＡのノードを有している構造パターン木とその構造パターン木の中の現在の位置情報（ラベルＡのノード）を記憶しており、出現情報２３２０にＴｒ１ ２３２１、Ｔｒ２ ２３２２、Ｔｒ３ ２３２３を記憶しており、さらに、変更情報スタック２３３０に変更情報２３３１、変更情報２３３２を記憶している。そして、この更新した情報を、更新の原因となった探索状態ノードＡ［Ｂ［Ｃ］］の変更情報２２３１に格納する。
【００６７】
次に、続けて頻出構造パターン探索（ステップＳ５１２）に入る。この段階でもラベルＣを持つノードの下に頻出ラベルは見つけることができるが、同じ処理の流れの繰り返しとなるので、下位探索の処理は再帰的な実行が終了して次の処理に進んだところを説明する。
【００６８】
図４に示すフローチャートでのステップＳ４０６（横枝探索箇所残りあり？）以降の処理（ステップＳ４０６〜ステップＳ４１０）は、探索状態を上位方向に探索状態ノードを辿る処理となる。登録した一番新しい探索状態ノードから親探索状態ノードの方向に辿り、親子関係のペア毎に横枝探索の処理（ステップＳ４１０）が実行されることになる。
この例では、探索状態は図２１に示すように、３つの探索状態ノードからなっており、探索状態ノード（Ａ）１９１０の下に探索状態ノード（Ａ[Ｂ]）１９２０が接続されており、探索状態ノード（Ａ[Ｂ]）１９２０の下に探索状態ノード（Ａ[Ｂ[Ｃ]]）２１３０が接続されており、２段階の親子関係が構成されている。このため、このループは探索状態ノードＡ［Ｂ］と探索状態ノードＡ［Ｂ［Ｃ］］の間の親子関係と、探索状態ノードＡと探索状態ノードＡ［Ｂ］の間の親子関係について実行される。
この処理は、望ましくは探索状態ノードの下位から上位への順で行う。ここでは、まず探索状態ノードＡ［Ｂ］と探索状態ノードＡ［Ｂ［Ｃ］］の間の親子関係に対する処理を説明する。すなわち横枝探索箇所としてこの探索状態ノードの親子関係が選ばれたものとする（ステップＳ４０８）。
【００６９】
そして、ステップＳ４１０（横枝探索）の処理に入る。
図７に、横枝探索の処理例のフローチャートを示す。
横枝探索処理では、まずステップＳ７０２（横枝探索範囲情報準備）の処理を実行する。この処理は具体的には、選択された探索状態ノードの親子関係の間、ここでの例では、探索状態ノードＡ［Ｂ］と探索状態ノードＡ［Ｂ［Ｃ］］の間で横枝探索範囲情報を準備する。
【００７０】
この処理は、上位の探索状態ノードの出現情報から、ＥｐＲａｎｇｅが他の出現情報のＥｐＲａｎｇｅに包含されないものを選び、それぞれのＥｐＲａｎｇｅについて、下位の探索状態ノードの出現情報の中から上位のＥｐＲａｎｇｅにＥｐＲａｎｇｅが含まれるものの中でＥｐＲａｎｇｅＲが最小のものを選び（以降、下位最左ＥｐＲａｎｇｅとよぶ）、この選ばれた下位のＥｐＲａｎｇｅのＥｐＲａｎｇｅＲ（下位最左ＥｐＲａｎｇｅのＥｐＲａｎｇｅ）と上位ＥｐＲａｎｇｅのＥｐＲａｎｇｅで横枝探索範囲を算出する。
【００７１】
例えば、Ｔｒ１では上位探索状態ノードの出現情報のうち、ｖ３Ｔｒ１のＥｐＲａｎｇｅはｖ１Ｔｒ１のＥｐＲａｎｇｅに包含される（同じＥｐＲａｎｇｅの場合には一番右の番号が小さいものが番号の大きいものを包含するとして説明する。ただしＥｐＲａｎｇｅは同じなので逆としても結果に影響はない）。このため、上位探索状態ノードのＥｐＲａｎｇｅはｖ１Ｔｒ１とｖ１１Ｔｒ１のＥｐＲａｎｇｅとなる。ｖ１Ｔｒ１に対応する下位探索状態ノードの出現情報は、ｖ８Ｔｒ１のＥｐＲａｎｇｅとなる。したがって、この場合の上位ＥｐＲａｎｇｅは、ＥｐＲａｎｇｅ（ｖ１Ｔｒ１）＝［１，３］で下位最左ＥｐＲａｎｇｅはＥｐＲａｎｇｅ（ｖ８Ｔｒ１）＝［２，２］となる。その結果、ｖ１Ｔｒ１についての探索範囲は［２＋１，３］、すなわちＥｐＲａｎｇｅ［３，３］となる。
【００７２】
また、もう一方のｖ１１Ｔｒ１のＥｐＲａｎｇｅについては下位探索状態ノードの出現情報はｖ１４Ｔｒ１のＥｐＲａｎｇｅとなる。上位ＥｐＲａｎｇｅはＥｐＲａｎｇｅ（ｖ１１Ｔｒ１）＝［４，５］で下位最左ＥｐＲａｎｇｅはＥｐＲａｎｇｅ（ｖ１４Ｔｒ１）＝［５，５］となる。その結果、ｖ１１Ｔｒ１についての探索範囲は［５＋１，５］となり、矛盾した範囲となるため対応する探索範囲はないということになる。この結果、Ｔｒ１についての探索範囲はＥｐＲａｎｇｅ［３，３］だけとなる。同様にＴｒ２については上位、ｖ７Ｔｒ２のＥｐＲａｎｇｅと、これに対応する下位最左ＥｐＲａｎｇｅ、ｖ１３Ｔｒ２のＥｐＲａｎｇｅとの間でＥｐＲａｎｇｅ［５：５］が横枝の探索範囲となる。Ｔｒ３については上位、ｖ２Ｔｒ３のＥｐＲａｎｇｅと、これに対応する下位最左ＥｐＲａｎｇｅ、ｖ９Ｔｒ３のＥｐＲａｎｇｅとの間でＥｐＲａｎｇｅ［４：４］が横枝の探索範囲となる。
【００７３】
これらの探索範囲にしたがって、それぞれの木構造データを探索する（ステップＳ７０４〜ステップＳ７１４）。本実施の形態では、この探索処理を効率よく行う一方法として図１１、図１２、図１３のデータ構造を用いる方法を示している。他のデータ構造と処理方法を用いて、この探索処理を行ってもよいが、少なくともこの方法を用いることで、各木構造データからＥＰａｔｈの範囲を指定したノードの探索を容易に実現することができる。
【００７４】
Ｔｒ１からはＥｐＲａｎｇｅ［３，３］で探索すると、ｖ９Ｔｒ１だけが探索範囲となる。出現するラベルはＦである。Ｔｒ２からはＥｐＲａｎｇｅ［５，５］で探索すると、ｖ１４Ｔｒ２とｖ１５Ｔｒ２だけが探索範囲となる。出現するラベルはＧとＦである。Ｔｒ３からはＥｐＲａｎｇｅ［４，４］で探索すると、ｖ１０Ｔｒ２だけが探索範囲となる。出現するラベルはＢである。このときの頻出となるラベルはＦだけとなる（ステップＳ７０４）。
【００７５】
このラベルＦを選択して（ステップＳ７０８）、探索状態作成・更新の処理（ステップＳ７１０）を行う。また、ステップＳ７１０では、構造パターン内の現在の処理対象となっているノードの先祖のノードの出現箇所から、その現在の処理対象となっているノードの出現箇所のノードを子孫に含むノードに対応する出現箇所を保持するようにしている。
図２４に示す前述のＦの出現情報を用いて探索状態ノードを作成して、探索状態に登録する。このときの探索状態を図２５に示す。つまり、図２４の例に示す探索状態ノードは、構造パターン木２４１０にラベルＡのノードの下にラベルＢのノード、そのラベルＢのノードの下にラベルＣのノードとラベルＦのノードを有している構造パターン木とその構造パターン木の中の現在の位置情報（ラベルＦのノード）を記憶しており、出現情報２４２０にＴｒ１ ２４２１、Ｔｒ２ ２４２２を記憶しており、さらに、変更情報スタック２４３０に変更情報２４３１を記憶している。また、図２５に示す探索状態は、４つの探索状態ノードからなっており、探索状態ノード（Ａ）１９１０の下に探索状態ノード（Ａ[Ｂ]）１９２０が接続されており、探索状態ノード（Ａ[Ｂ]）１９２０の下に探索状態ノード（Ａ[Ｂ[Ｃ]]）２１３０と探索状態ノード（Ａ[Ｂ[ＣＦ]]）２５４０が接続されている。このとき探索状態ノードＡ［Ｂ［ＣＦ］］は、横枝の探索時に親側の探索状態ノードとして選んだ探索状態ノードＡ［Ｂ］の子供ノードとして関係付けられる。
【００７６】
次に、この探索状態ノードＡ［Ｂ［ＣＦ］］を登録したことによる影響を調べて探索状態ノードの更新を行う。
このとき、更新が必要であるかどうかを調べる探索状態ノードは、探索状態ノードＡ［Ｂ［ＣＦ］］の先祖である探索状態ノードである。具体的には、探索状態ノードＡ［Ｂ］と探索状態ノードＡである。この場合、探索状態ノードＡ［Ｂ］を検査した段階で更新が必要ないことがわかるので、探索状態ノードの更新は行われない。
【００７７】
そして、さらに頻出構造パターン探索（ステップＳ７１２）に移行する。
頻出構造パターン探索では、パターン候補Ａ［Ｂ［ＣＦ］］について、必要であれば出力処理を行い、下位探索の処理を行う。
ここでの下位探索においては、頻出となるラベルが存在しないためすぐに下位探索処理から戻ってくる。
次に、横枝探索の繰り返し処理が行われる。このときの横枝探索の候補となる探索状態ノードの親子関係は、探索状態ノードＡ［Ｂ［ＣＦ］］と探索状態ノードＡ［Ｂ］の間の関係、探索状態ノードＡと探索状態ノードＡ［Ｂ］の間の関係の二通りとなる。
この処理の流れは既に説明した。
しかし、ここではいずれの探索状態ノードの親子関係においても頻出となるラベルが現れない。
【００７８】
そして、この探索状態ノードＡ［Ｂ［ＣＦ］］における処理が終わる。これにより探索状態ノードＡ［Ｂ［ＣＦ］］に対応する頻出構造パターン探索の処理が終わり、上位の処理の流れに戻る。この場合には、横枝探索の処理に戻る。そして次のステップの探索状態回復の処理（ステップＳ７１４）が行われる。
【００７９】
この探索状態回復の処理（ステップＳ７１４、ステップＳ５１４）について説明する。
探索状態ノードＡ［Ｂ［ＣＦ］］の変更情報スタックを参照する。ここに更新した探索状態ノードＡ［Ｂ］，Ａが記録されている。
この両方の探索状態ノードについて、それぞれ探索状態スタックのトップの変更情報をもとに探索状態ノードの回復処理を行う。具体的には、探索状態ノードＡ［Ｂ］の場合には、出現情報のｖ６Ｔｒ１，ｖ１３Ｔｒ１，ｖ４Ｔｒ２，ｖ１２Ｔｒ２，ｖ１０Ｔｒ３を出現情報として戻す。戻した結果は、図２２に示したものと同じになる。同様に処理して、探索状態ノードＡも図２３に示したものと同じになる。
以上に示したように、処理を再帰的に実行していくことで予め指定された出現数以上の全ての先祖−子孫関係の木構造を抽出することができる。
【００８０】
図６に示すフローチャートを用いて、子孫ノードの走査処理について説明する。
ステップＳ６０２では、上位の出現情報の処理が終了しているか否かについて判断する。かかる判断において、終了していると判断した場合は子孫ノードの走査処理を終了し（ステップＳ６１２）、終了していないと判断した場合はステップＳ６０４へ進む。
ステップＳ６０４では、出現情報を一つ選択する。
【００８１】
ステップＳ６０６では、ステップＳ６０４で選択した出現情報のＥｐＲａｎｇｅＬ，ＥｐＲａｎｇｅＲを、それぞれＥｐＲａｎｇｅＬＰ，ＥｐＲａｎｇｅＲＰとする。
ステップＳ６０８では、出現情報のＥｐＲａｎｇｅＬがＥｐＲａｎｇｅＬＰと同じものを出現情報の次の番号から走査する。
ステップＳ６１０では、ＥｐＲａｎｇｅＬＰ＋１からＥｐＲａｎｇｅＲＰまでの範囲で、ＥｐＲａｎｇｅＲの値がＥｐＲａｎｇｅＲＰ以下のものを走査する。
【００８２】
なお、本実施の形態で示した例では、ＥｐＲａｎｇｅが同じ出現情報も皆同等に扱ったが、ＥｐＲａｎｇｅ（つまり、分岐がない範囲）が同じ出現情報は一つ（つまり、最上位と最下位のノード）を代表として扱って処理しても全く同等の効果が得られ、記憶しておく出現情報の量が減る分必要な記憶容量が削減され、さらに、検査などの処理のコストも削減される。つまり、木構造内で分岐のない範囲の最上位及び最下位以外の出現箇所を探索状態管理モジュール２６０から削除するようにしてもよい。あるいは、探索状態管理モジュール２６０に格納する前に選別してもよい、さらには、構造情報ＤＢ１１０に格納する時点でこの選別を行ってもよい。
【００８３】
また、木構造のノードを深さ優先探索してノードに番号をつけ、そのノードの番号を持ってノードの子孫のノードの範囲を示す方法が知られている。このｓｃｏｐｅと呼ばれる情報は、例えば図７に示すＴｒ２のｖ７では、自分自身の番号７と子孫のノードのうち最も大きな番号を持ったノードの番号を用いて［７，１５］と表わされる。
木構造から範囲を指定してノードを探索するために本実施の形態ではＥｐＴｒｅｅを用いたが、代わりにこのｓｃｏｐｅ情報を用いて探索する構成にすることも当業者に容易な変更の範囲である。ｓｃｏｐｅ情報は各ノードの子孫ノードの範囲を示す情報であるため、あるノードからの子孫の範囲を決定できる。また、横枝の探索時にも上位の出現情報のｓｃｏｐｅ情報と下位の出現情報のｓｃｏｐｅ情報を演算することが可能であり、本実施の形態の該当箇所に当てはめれば、横枝の探索範囲もｓｃｏｐｅ情報を用いて決定することができる。
【００８４】
なお、本実施の形態としてのプログラムが実行されるコンピュータのハードウェア構成は、図２６に例示するように、一般的なコンピュータであり、具体的にはパーソナルコンピュータ、サーバーとなり得るコンピュータ等である。構造情報管理モジュール２１０、出現情報選択モジュール２２０、出現情報管理モジュール２３０、調査範囲処理モジュール２４０、探索処理モジュール２５０、探索状態管理モジュール２６０、抽出情報処理モジュール２７０等のプログラムを実行するＣＰＵ２６０１と、そのプログラムやデータを記憶するＲＡＭ２６０２と、本コンピュータを起動するためのプログラム等が格納されているＲＯＭ２６０３と、補助記憶装置であるＨＤ２６０４（例えばハードディスクを用いることができる）と、キーボード、マウス等のデータを入力する入力装置２６０６と、ＣＲＴや液晶ディスプレイ等の出力装置２６０５と、通信ネットワークと接続するための通信回線インタフェース２６０７（例えばネットワークインタフェースカードを用いることができる）、そして、それらをつないでデータのやりとりをするためのバス２６０８により構成されている。これらのコンピュータが複数台互いにネットワークによって接続されていてもよい。
【００８５】
前述の実施の形態のうち、コンピュータ・プログラムによるものについては、本ハードウェア構成のシステムにソフトウェアであるコンピュータ・プログラムを読み込ませ、ソフトウェアとハードウェア資源とが協働して、前述の実施の形態が実現される。
なお、図２６に示すハードウェア構成は、１つの構成例を示すものであり、本実施の形態は、図２６に示す構成に限らず、本実施の形態において説明したモジュールを実行可能な構成であればよい。例えば、一部のモジュールを専用のハードウェア（例えばＡＳＩＣ等）で構成してもよく、一部のモジュールは外部のシステム内にあり通信回線で接続しているような形態でもよく、さらに図２６に示すシステムが複数互いに通信回線によって接続されていて互いに協調動作するようにしてもよい。また、特に、パーソナルコンピュータの他、情報家電、複写機、ファックス、スキャナ、プリンタ、複合機（スキャナ、プリンタ、複写機、ファックス等のいずれか２つ以上の機能を有している画像処理装置）などに組み込まれていてもよい。
【００８６】
なお、説明したプログラムについては、記録媒体に格納して提供してもよく、また、そのプログラムを通信手段によって提供してもよい。その場合、例えば、前記説明したプログラムについて、「プログラムを記録したコンピュータ読み取り可能な記録媒体」の発明として捉えてもよい。
「プログラムを記録したコンピュータ読み取り可能な記録媒体」とは、プログラムのインストール、実行、プログラムの流通などのために用いられる、プログラムが記録されたコンピュータで読み取り可能な記録媒体をいう。
なお、記録媒体としては、例えば、デジタル・バーサタイル・ディスク（ＤＶＤ）であって、ＤＶＤフォーラムで策定された規格である「ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ−ＲＡＭ等」、ＤＶＤ＋ＲＷで策定された規格である「ＤＶＤ＋Ｒ、ＤＶＤ＋ＲＷ等」、コンパクトディスク（ＣＤ）であって、読出し専用メモリ（ＣＤ−ＲＯＭ）、ＣＤレコーダブル（ＣＤ−Ｒ）、ＣＤリライタブル（ＣＤ−ＲＷ）等、光磁気ディスク（ＭＯ）、フレキシブルディスク（ＦＤ）、磁気テープ、ハードディスク、読出し専用メモリ（ＲＯＭ）、電気的消去及び書換可能な読出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュ・メモリ、ランダム・アクセス・メモリ（ＲＡＭ）等が含まれる。
そして、前記のプログラム又はその一部は、前記記録媒体に記録して保存や流通等させてもよい。また、通信によって、例えば、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、イントラネット、エクストラネット等に用いられる有線ネットワーク、あるいは無線通信ネットワーク、さらにこれらの組み合わせ等の伝送媒体を用いて伝送させてもよく、また、搬送波に乗せて搬送させてもよい。
さらに、前記のプログラムは、他のプログラムの一部分であってもよく、あるいは別個のプログラムと共に記録媒体に記録されていてもよい。また、複数の記録媒体に分割して
記録されていてもよい。また、圧縮や暗号化など、復元可能であればどのような態様で記録されていてもよい。
【図面の簡単な説明】
【００８７】
【図１】本実施の形態を好適に適用するシステムの概念構成例を示す説明図である。
【図２】本実施の形態の構成例についての概念的なモジュール構成図である。
【図３】本実施の形態による処理例を示したフローチャートである。
【図４】本実施の形態による頻出構造パターン探索の処理例を示したフローチャートである。
【図５】本実施の形態による下位探索の処理例を示したフローチャートである。
【図６】本実施の形態による子孫ノードの走査処理例を示したフローチャートである。
【図７】本実施の形態による横枝探索の処理例を示したフローチャートである。
【図８】対象とする木構造データの例を示す説明図である。
【図９】Ｅｐａｔｈの例を示す説明図である。
【図１０】各ノードにおけるＥｐＲａｎｇｅの例を示す説明図である。
【図１１】木構造データＴｒ１のＥｐＴｒｅｅの例を示す説明図である。
【図１２】木構造データＴｒ２のＥｐＴｒｅｅの例を示す説明図である。
【図１３】木構造データＴｒ３のＥｐＴｒｅｅの例を示す説明図である。
【図１４】各木構造データにおけるラベルＡの出現の例を示す説明図である。
【図１５】探索状態ノードの例を示す説明図である。
【図１６】パターンのルートノードにラベルＡを選択した場合の探索状態の例を示す説明図である。
【図１７】各木構造データにおけるラベルＢの出現の例を示す説明図である。
【図１８】ラベルＡの子孫としてラベルＢを選択した場合の探索状態ノードＡ［Ｂ］の例を示す説明図である。
【図１９】ラベルＡの子孫としてラベルＢを選択した場合の探索状態の例を示す説明図である。
【図２０】ラベルＢの子孫としてラベルＣを選択した場合の探索状態ノードＡ［Ｂ［Ｃ］］の例を示す説明図である。
【図２１】ラベルＢの子孫としてラベルＣを選択した場合の探索状態の例を示す説明図である。
【図２２】探索状態ノードＡ［Ｂ］の例を示す説明図である。
【図２３】探索状態ノードＡの例を示す説明図である。
【図２４】探索状態ノードＡ［Ｂ［ＣＦ］］の例を示す説明図である。
【図２５】探索状態Ａ［Ｂ［ＣＦ］］の例を示す説明図である。
【図２６】本実施の形態を実現するコンピュータのハードウェア構成例を示すブロック図である。
【符号の説明】
【００８８】
１１０…構造情報ＤＢ
１２０…情報収集装置
１３０…情報抽出装置
１４０…抽出情報管理装置
２１０…構造情報管理モジュール
２２０…出現情報選択モジュール
２３０…出現情報管理モジュール
２４０…調査範囲処理モジュール
２５０…探索処理モジュール
２６０…探索状態管理モジュール
２７０…抽出情報処理モジュール
【技術分野】
【０００１】
本発明は、情報処理装置及び情報処理プログラムに関する。
【背景技術】
【０００２】
コンピュータの処理能力、記憶装置の容量の飛躍的な増大に加え、ＩＴ化やネットワーク化が進んだことで大量な情報が容易に集められるようになってきた。集めた情報から市場機会やリスクに関する情報を早期に発見したり、隠れた知識を発見したりすることへの期待が高まっている。
しかし、集めた情報の量はしばしば人間の処理能力をはるかに超えるものとなる。このため、せっかく大量に集めた情報からリスクを発見したり、知識を抽出したりして活用することは実際には労力を伴う難しいものであった。
【０００３】
一方、パターン・マイニング等の技術の進展により、そのような大量の情報の中から例えば同時に購入される商品のパターンなどの情報が抽出可能となってきた。同時に購入される品物のパターンや購入される順序のパターンを抽出する技術が顧客の購買行動の分析などの需要から注目を集めて研究開発されてきたが、最近ではさまざまな情報の構造化、半構造化が進んできたこともあり、木構造のような構造を持つパターンを抽出するパターン・マイニングの技術が注目されてきている。構造情報を抽出するパターン・マイニングの技術の中でも、特に木構造はＸＭＬ（ｅＸｔｅｎｓｉｂｌｅ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）をはじめとしてドキュメントの構造化や知識表現などさまざまな情報の構造化に用いられるためパターン抽出への期待も大きい。
【０００４】
木構造のデータ群から部分木のパターンを抽出する技術には大きく分けて、親子関係が厳密に一致する構造だけを抽出するｉｎｄｕｃｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇの技術と、親子関係が多少乱れても先祖―子孫の関係があれば構造を抽出するｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇの技術がある。
現実社会で発生するデータ、例えばドキュメントの操作履歴などのように人の操作を記録したものでは、人がたとえ同じように作業を行ったつもりでも、操作履歴のデータ上では必ずしもデータの親子関係が一致しないことがしばしば起きる。そのような場合にはｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇの技術を適用することが望ましい。現実世界のデータではしばしば同様にゆれが生じるため、ｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇの技術への期待は高い。ｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇを実現する技術として、開示されているものには、ＴｒｅｅＭｉｎｅｒ、Ｄｒｙａｄｅ、ＭＢ３−Ｍｉｎｅｒなどの技術が挙げられる。
【０００５】
これらに関連する技術として、例えば、特許文献１には、データの集合からその中に含まれる重要なパターンを検出する方法及びシステムを提供することを課題とし、木構造データで表わされたデータ集合を含むデータベースから、集計対象となる候補パターンを用いて、頻出パターンを検出するシステムであって、（１）データベースから候補パターンにマッチするパターンを集計する手段と、（２）前記集計により出現頻度の高いパターンを検出する手段と、（３）前記検出したパターンから、次の集計対象となる候補パターンを生成する手段と、を有するように構成することが開示されている。
【０００６】
また、例えば、特許文献２には、順序木において頻出するパターンを抽出するのに好適な抽出装置等を提供することを課題とし、抽出装置の入力受付部は、１つ以上の順序木の入力を受け付け、変換部は、入力を受け付けられた順序木のそれぞれを系列表現へ変換し、抽出部は、変換された系列表現のそれぞれが含むパターンのうち、所定の頻度以上で出現するパターンを抽出し、系列表現は、順序木を深さ優先探索して、枝を進む際に通過する節はその名前を表わすマークを、枝を戻る際はバックトラックマークを、それぞれ並べることによりでき、パターンは、系列表現であるマークの列中の名前を表わすマークのいずれかを最初のマークとして、これから射影を０回以上繰り返したときに、最初のマークから最後のマークに至るまでに出会うマークの列をいい、射影が成立するか否かは、マークの列の列文脈と、射影文脈の値により判定することが開示されている。
【特許文献１】特開２００１−１３４５７５号公報
【特許文献２】特開２００４−３５５４５７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、複数の木構造内で複数回現れる構造パターンの探索において、ノードを加えた場所毎に再帰的処理による探索を行うようにした情報処理装置及び情報処理プログラムを提供することを目的としている。
【課題を解決するための手段】
【０００８】
かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
請求項１の情報処理装置は、複数の木構造内で複数回現れる構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより下位のノードに対して行う第１の探索手段と、前記構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより上位のノードであって該上位のノードの下位にあり、かつ未探索のノード毎に探索する第２の探索手段を具備し、前記第１の探索手段と前記第２の探索手段は、探索の対象とすべきノードがなくなった場合に、該探索を始めた元のノードに戻ることを特徴とする。
【０００９】
請求項２の情報処理装置は、請求項１に記載する情報処理装置であって、前記構造パターン内の現在の処理対象である現処理対象となっているノードと一致する前記木構造内でのノードのうち上下関係のあるものについては最上位のノードに基づいて、子孫を探索する範囲を決定する第１の探索範囲決定手段をさらに具備し、前記第１の探索手段は、前記第１の探索範囲決定手段によって決定された範囲に基づいて探索を行うことを特徴とする。
【００１０】
請求項３の情報処理装置は、請求項１に記載する情報処理装置であって、前記構造パターン内での親ノードと一致する前記木構造内でのノードのうち上下関係のあるものについては最上位のノード及び前記構造パターン内での子ノードと一致する前記木構造内でのノードに上下関係のあるものについては最下位のノードに基づいて、探索範囲を決定する第２の探索範囲決定手段をさらに具備し、前記第２の探索手段は、前記第２の探索範囲決定手段によって決定された範囲に基づいて探索を行うことを特徴とする。
【００１１】
請求項４の情報処理装置は、請求項３に記載する情報処理装置であって、前記構造パターン内の現在の処理対象となっているノードの先祖のノードの出現箇所の中から、該現在の処理対象となっているノードの出現箇所のノードを子孫に含むノードに対応する出現箇所を保持する保持手段をさらに具備することを特徴とする。
【００１２】
請求項５の情報処理装置は、請求項４に記載する情報処理装置であって、前記木構造内で分岐のない範囲の最上位及び最下位以外の出現箇所を前記保持手段から削除する削除手段をさらに具備することを特徴とする。
【００１３】
請求項６の情報処理装置は、請求項４に記載する情報処理装置であって、前記保持手段に保持させる出現箇所を対象とし、前記木構造内で分岐のない範囲の最上位及び最下位以外の出現箇所以外を削除したものを選別する選別手段をさらに具備することを特徴とする。
【００１４】
請求項７の情報処理プログラムは、コンピュータを、複数の木構造内で複数回現れる構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより下位のノードに対して行う第１の探索手段と、前記構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより上位のノードであって該上位のノードの下位にあり、かつ未探索のノード毎に探索する第２の探索手段として機能させ、前記第１の探索手段と前記第２の探索手段は、探索の対象とすべきノードがなくなった場合に、該探索を始めた元のノードに戻ることを特徴とする。
【発明の効果】
【００１５】
請求項１記載の情報処理装置によれば、複数の木構造内で複数回現れる構造パターンの探索においてノードを加えた場所毎に再帰的処理による探索を行うことができる。
【００１６】
請求項２記載の情報処理装置によれば、探索処理における記憶容量及び処理時間の増大を抑制することができる。
【００１７】
請求項３記載の情報処理装置によれば、探索処理における記憶容量及び処理時間の増大を抑制することができる。
【００１８】
請求項４記載の情報処理装置によれば、探索状態を保持して、その探索における再帰的処理が実行できる。
【００１９】
請求項５記載の情報処理装置によれば、探索処理における記憶容量をより削減することができる。
【００２０】
請求項６記載の情報処理装置によれば、探索処理における記憶容量をより削減することができる。
【００２１】
請求項７記載の情報処理プログラムによれば、複数の木構造内で複数回現れる構造パターンの探索においてノードを加えた場所毎に再帰的処理による探索を行うことができる。
【発明を実施するための最良の形態】
【００２２】
まず、前述のＴｒｅｅＭｉｎｅｒ、Ｄｒｙａｄｅ、ＭＢ３−Ｍｉｎｅｒの技術について、説明する。
Ｄｒｙａｄｅは、兄弟ノードに同じものを含めないという機能制限があり、そのような場面が頻出するドキュメントの操作履歴などのマイニングには適さない。
ＭＢ３−Ｍｉｎｅｒは、幅優先探索であり、処理の階層毎に用意するパターン候補の数が膨大なものになるため、大規模なデータに適用するには限界がある。
また、ＴｒｅｅＭｉｎｅｒは、深さ優先探索であると主張されてはいるが、実際にはツリー（木）構造のルートから葉ノードをつないだパス方向に発生する枝の候補を全て再帰処理の深さ方向に送り込むことを行う。このため幅優先探索と同様の問題が生じてしまい、大規模なデータに適用すると候補生成でパターン候補の数が膨大なものになり処理できなくなるという問題があった。
【００２３】
また、ＭＢ３−ＭｉｎｅｒやＴｒｅｅＭｉｎｅｒにおいては、ツリーの出現位置（パターン木の中の各ノードと、データの木の中のノードとの対応関係）を管理するが、ｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇの場合には、その数が深さ方向に広がる子孫ノード候補の組み合わせにより指数関数的に膨れ上がるという問題があった。ＴｒｅｅＭｉｎｅｒでは、ＴｒｅｅＭｉｎｅｒＤにおいて、このことに対する対策がとられているが、実際には十分に機能していない。
同様の状況はドキュメントの操作履歴だけで生じるものではなく、例えば、たんぱく質の構造データなどにおいても同じラベルを持つノードが一連の系列の中に何度も現れることは少なくない。出現位置の組み合わせの管理については、このような場合に大量の情報を管理しなければならなくなり、処理に必要な記憶容量の増大と処理対象のデータの増大による処理コストの増大という問題が発生し、大規模なデータの処理を現実的な時間とリソースで実現することを難しくしてしまう。
つまり、従来は、木構造をストリング形式に変換して又はそれと等価なものに変換して探索を行っていた。本実施の形態は、木構造自体の探索を行うようにしているものである。
【００２４】
本実施の形態は、要素間に設定した関係を木構造として扱えるデータ群の中から、複数回にわたって現れる関係構造（部分木のパターン、以下、構造パターン、構造パターン木、パターンともいう）を抽出する技術に関するものである。
本実施の形態は、ルートノード（根）からリーフノード（葉）にいたるパス（以降、Ｅｐａｔｈともいう）、各ノードの属するＥｐａｔｈの範囲（以降、ＥｐＲａｎｇｅともいう）、のデータを用い、探索ステップに合わせて管理するノード出現情報管理機構を用いた、深さ優先探索で探索処理を行う情報抽出装置である。
さらに、パターン抽出の効率を上げるために、前記ＥｐＲａｎｇｅを用いたツリーデータ管理機構を備えている。
【００２５】
以下、図面に基づき本発明を実現するにあたっての好適な一実施の形態の例を説明する。
図１は、本実施の形態を適用するに好適なシステムの概念構成図である。このシステムは、構造情報ＤＢ１１０、情報収集装置１２０、情報抽出装置１３０、抽出情報管理装置１４０を有している。これらは、通信回線を介して接続されている。なお、これらの全ての装置群が一つの装置内に構築されていてもよいし、これらのうちの一部の装置が一つの装置内に構築されていてもよい。
【００２６】
構造情報ＤＢ１１０は、情報収集装置１２０、情報抽出装置１３０と接続されており、情報収集装置１２０から受け取ったデータであり、情報を抽出すべき対象である木構造データを蓄積して管理し、情報抽出装置１３０からアクセスされる。
情報収集装置１２０は、構造情報ＤＢ１１０と接続されており、図示しない他の装置から情報を集めて、あるいは図示しない他の装置から送信された情報を受け取って、必要なら情報の整形（情報抽出装置１３０が扱えるような木構造データへの変換）を行って、構造情報ＤＢ１１０に格納する。
情報抽出装置１３０は、構造情報ＤＢ１１０、抽出情報管理装置１４０と接続されており、構造情報ＤＢ１１０にアクセスして、木構造データから頻出情報を抽出して抽出情報管理装置１４０に送信する。
抽出情報管理装置１４０は、情報抽出装置１３０と接続されており、情報抽出装置１３０から送信された頻出情報を受け取って蓄積したり表示装置や印刷装置などの図示しない他の装置に送信したりする。
【００２７】
図２は、本実施の形態の情報抽出装置１３０内の構成例についての概念的なモジュール構成図である。
なお、モジュールとは、一般的に論理的に分離可能なソフトウェア（コンピュータ・プログラム）、ハードウェア等の部品を指す。したがって、本実施の形態におけるモジュールはコンピュータ・プログラムにおけるモジュールのことだけでなく、ハードウェア構成におけるモジュールも指す。それゆえ、本実施の形態は、コンピュータ・プログラム、システム及び方法の説明をも兼ねている。ただし、説明の都合上、「記憶する」、「記憶させる」、これらと同等の文言を用いるが、これらの文言は、実施の形態がコンピュータ・プログラムの場合は、記憶装置に記憶させる、又は記憶装置に記憶させるように制御するの意である。また、モジュールは機能にほぼ一対一に対応しているが、実装においては、１モジュールを１プログラムで構成してもよいし、複数モジュールを１プログラムで構成してもよく、逆に１モジュールを複数プログラムで構成してもよい。また、複数モジュールは１コンピュータによって実行されてもよいし、分散又は並列環境におけるコンピュータによって１モジュールが複数コンピュータで実行されてもよい。なお、１つのモジュールに他のモジュールが含まれていてもよい。また、以下、「接続」とは物理的な接続の他、論理的な接続（データの授受、指示、データ間の参照関係等）を含む。
また、システム又は装置とは、複数のコンピュータ、ハードウェア、装置等がネットワーク（一対一対応の通信接続を含む）等の通信手段で接続されて構成されるほか、１つのコンピュータ、ハードウェア、装置等によって実現される場合も含まれる。「装置」と「システム」とは、互いに同義の用語として用いる。
【００２８】
図１に示した情報抽出装置１３０は、図２に示すように構造情報管理モジュール２１０、出現情報選択モジュール２２０、出現情報管理モジュール２３０、調査範囲処理モジュール２４０、探索処理モジュール２５０、探索状態管理モジュール２６０、抽出情報処理モジュール２７０を有している。
【００２９】
構造情報管理モジュール２１０は、出現情報選択モジュール２２０、出現情報管理モジュール２３０、調査範囲処理モジュール２４０と接続されており、構造情報ＤＢ１１０中の構造情報を調査範囲処理モジュール２４０の指定にしたがって調査し、木構造データ中のノードの出現をラベル毎に集計する。また、構成によってはラベル毎に出現位置情報を収集するようにしてもよい。この集計結果である出現情報は、出現情報管理モジュール２３０に送信される。なお、出現情報には、出現箇所の情報と幾つの木に出現したかを示す集計値の両方を含んでいる。また、構造情報管理モジュール２１０は、必要であれば図示しない記憶手段を有し、構造情報ＤＢ１１０中の構造情報を処理に適したデータ構造に変換して蓄積することを行ってもよい。
【００３０】
出現情報選択モジュール２２０は、構造情報管理モジュール２１０、出現情報管理モジュール２３０と接続されており、構造情報管理モジュール２１０によって生成された出現情報に基づいて、対象とするラベルを選択する。つまり、構造情報管理モジュール２１０によって出現が確認されたノードのラベル毎の出現情報を受け取り、予め定めた基準を満たす要素（予め設定された回数以上出現するものなど）と満たさない要素を選別する。又は、図示しない入力装置によりユーザから指定された条件に見合わない出現情報を破棄したりして出現情報を整理する。
【００３１】
出現情報管理モジュール２３０は、出現情報選択モジュール２２０、探索処理モジュール２５０、構造情報管理モジュール２１０と接続されており、出現情報選択モジュール２２０により選択されたノードのラベルと出現情報を受け取り管理する。この情報を探索処理モジュール２５０の要求により順に探索処理モジュール２５０に送信する。
【００３２】
調査範囲処理モジュール２４０は、構造情報管理モジュール２１０、探索処理モジュール２５０、探索状態管理モジュール２６０と接続されており、探索状態管理モジュール２６０に記憶されている探索状態及び構造情報管理モジュール２１０によって生成され、探索処理モジュール２５０の指示にしたがって出現情報管理モジュール２３０から複製、あるいは移動して探索状態管理モジュール２６０内に格納されている出現情報に基づいて、木構造データ内の構造パターンの探索範囲を決定する。
【００３３】
探索処理モジュール２５０は、出現情報管理モジュール２３０、調査範囲処理モジュール２４０、探索状態管理モジュール２６０、抽出情報処理モジュール２７０と接続されており、出現情報管理モジュール２３０、調査範囲処理モジュール２４０、探索状態管理モジュール２６０、抽出情報処理モジュール２７０による処理を制御して、調査範囲処理モジュール２４０によって決定された探索範囲に基づいて、構造情報管理モジュール２１０が取り出し、出現情報選択モジュール２２０により選択されたラベルと出現情報を出現情報管理モジュール２３０から得て木構造データ内に複数回出現する構造パターンの探索を行い、その探索結果を抽出情報処理モジュール２７０へ渡す。この探索処理は適時探索状態管理モジュール２６０の探索状態を更新し再帰的に実行する。
【００３４】
探索状態管理モジュール２６０は、調査範囲処理モジュール２４０、探索処理モジュール２５０と接続されており、探索処理の途中状態を格納、管理する。記憶されるこの途中の状態は、探索処理モジュール２５０による再帰的な探索処理に利用される。探索処理モジュール２５０による探索処理中のパターン候補情報、構造パターン中のノードの各構造情報中での出現情報の保持と処理の過程における出現情報の更新・回復などを受け持つ。
抽出情報処理モジュール２７０は、探索処理モジュール２５０と接続されており、探索処理モジュール２５０より抽出したパターンを受け取り、図示しない記憶装置に格納したり、図示しない出力装置への出力処理を受け持つ。
【００３５】
図３は、本実施の形態による処理例を示したフローチャートである。
ステップＳ３０２（走査用情報の準備）では、構造情報管理モジュール２１０は、後の処理を効率的に実行するための準備を行うために、構造情報ＤＢ１１０に格納された構造情報を変換し、図示しない記憶手段に格納する。
【００３６】
図８は、説明のために用いる木構造データの例である。
例示した３つの木構造データＴｒ１（図８（ａ）），Ｔｒ２（図８（ｂ）），Ｔｒ３（図８（ｃ））には、それぞれ１６個、１６個、１１個のノードがある。説明の簡易化のために、兄弟間には順序関係があるとし、深さ優先探索でノードを辿った場合の順番をもとに、ノードにｖ０、ｖ１、・・・と識別子を設定した。以降、木構造を示す必要がない場合には、単にｖ０やｖ２等の表記でノードを指し、どの木データであるかを示す必要がある場合にはｖ０Ｔｒ１、ｖ２Ｔｒ２のようにそれぞれのノードが属する木データの識別子を添えて表記する。
図８に示した例では、ノードのラベルをＡ，Ｂ，Ｃ，・・・とした。例に現れるノードのラベルは、Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｉ，Ｊ，Ｋである。図８の丸内のアルファベットはそのノードのラベルである。
【００３７】
また、パターン抽出の条件を２つ以上の木構造データで出現するパターンとして説明する。
図９に示す例は、それぞれの木構造データについて、それぞれのルートノードからリーフノードまでのパスを示した図である。図中でそれぞれのパスにＥｐ１〜Ｅｐ６までの識別子をつけている。これも同様に木を示す必要がある場合には、Ｅｐ１Ｔｒ１のように木データの識別子を添えて表記する。例えばＥｐ４Ｔｒ１（Ｔｒ１のＥｐ４）は、ｖ０，ｖ１０，ｖ１１，ｖ１２，ｖ１３を通るパスであり、Ｅｐ２Ｔｒ３（Ｔｒ３のＥｐ２）は、ｖ０，ｖ１，ｖ２，ｖ３，ｖ４，ｖ６を通るパスである。
Ｅｐａｔｈをこのように設定することで、各ノードは少なくとも１つのＥｐａｔｈ上にあり、ノードによっては複数のＥｐａｔｈ上にある。例えば、ｖ１２Ｔｒ１は、Ｅｐ４Ｔｒ１とＥｐ５Ｔｒ１の上にあり、ｖ７Ｔｒ２は、Ｅｐ３Ｔｒ２とＥｐ４Ｔｒ２とＥｐ５Ｔｒ２の上にある。
【００３８】
各ノードが、どのＥＰａｔｈ上にあるかを示す情報ＥｐＲａｎｇｅを各ノードの関数として定義する。例えば、ＥｐＲａｎｇｅ（ｖ１２Ｔｒ１）＝｛Ｅｐ４Ｔｒ１，Ｅｐ５Ｔｒ１｝であり、ＥｐＲａｎｇｅ（ｖ７Ｔｒ２）＝｛Ｅｐ３Ｔｒ２，Ｅｐ４Ｔｒ２，Ｅｐ５Ｔｒ２｝である。
ここで、対象としている木構造は順序木を仮定しているため、ＥｐＲａｎｇｅに現れるＥＰａｔｈの番号は、連続する。そこで、説明の簡易化のためＥｐＲａｎｇｅを単純にＥＰａｔｈの番号の一番小さいものと一番大きいもので示すこととする。すなわち、次のように表記する。例えば、ＥｐＲａｎｇｅ（ｖ１２Ｔｒ１）＝［４，５］、ＥｐＲａｎｇｅ（ｖ７Ｔｒ２）＝［３，５］である。
このとき、ＥｐＲａｎｇｅの小さい側の番号をＥｐＲａｎｇｅＬ、大きい側の番号をＥｐＲａｎｇｅＲとして同様に関数で表わす。例えば、ＥｐＲａｎｇｅＬ（ｖ１２Ｔｒ１）＝４、ＥｐＲａｎｇｅＬ（ｖ７Ｔｒ２）＝３であり、ＥｐＲａｎｇｅＲ（ｖ１２Ｔｒ１）＝５、ＥｐＲａｎｇｅＲ（ｖ７Ｔｒ２）＝５である。
【００３９】
また、ＥｐＲａｎｇｅをノードの関数としてではなく、単にＥＰａｔｈの範囲として参照することも行う。例えば、｛Ｅｐ２Ｔｒ３，Ｅｐ３Ｔｒ３，Ｅｐ４Ｔｒ３｝を参照したい際に、単にＴｒ３のＥｐＲａｎｇｅＴｒ３［２，４］ と示すことも行う。また同様に、ＥｐＲａｎｇｅＬをＥｐＲａｎｇｅの小さい番号、ＥｐＲａｎｇｅＲをＥｐＲａｎｇｅの大きい番号としても用いる。
【００４０】
図１０に、図８に示した例のＴｒ１，Ｔｒ２，Ｔｒ３中の各ノードについて、（ノード識別子、ラベル、ＥｐＲａｎｇｅＬ，ＥｐＲａｎｇｅＲ）の組を示した。図１０（ａ）では、それぞれノードの識別子１００１ａ、ノードのラベル１００２ａ、ＥｐＲａｎｇｅＬ１００３ａ、ＥｐＲａｎｇｅＲ１００４ａが該当する。例えば、図１０（ａ）に示すＴｒ１のノード識別子：Ｖ０は、Ａというノードのラベルであり、ＥｐＲａｎｇｅＬは１、ＥｐＲａｎｇｅＲは６である。
【００４１】
構造情報管理モジュール２１０は、各木構造データに対してノードの存在範囲やＥｐＲａｎｇｅ範囲を指定してノードを走査する機能を有するために、図示しない内部の記憶手段に各ツリー情報中の必要な情報を別のデータ構造で保持することもできる。
【００４２】
図１１、図１２、図１３には、ツリー情報を内部に格納する一例を示した。図１１、図１２、図１３は、それぞれＴｒ１，Ｔｒ２，Ｔｒ３について、各ノードをＥｐＲａｎｇｅＬの値から辿りやすく格納した例であり、ツリーを深さ優先に辿りながらそれぞれのノードのＥｐＲａｎｇｅＬの場所にデータを追加することで構成できる。つまり、例えば図１１に示すＴｒ１のＥｐ情報１１００は、Ｅｐ１ １１０１、Ｅｐ２ １１０２、Ｅｐ３ １１０３、Ｅｐ４ １１０４、Ｅｐ５ １１０５、Ｅｐ６ １１０６へのリンク情報を含むものである。また、図示する都合上１１０１，１１０２、１１０３，１１０４，１１０５，１１０６が個別に示してあるが、これらが図１０に示したような順で連続領域に配置されてもよい。
【００４３】
図１１、図１２、図１３に示すツリー情報例の各ノードに対応するデータは、図１０に示した（ノード識別子、ラベル、ＥｐＲａｎｇｅＬ，ＥｐＲａｎｇｅＲ）の組に加えて、一番右に番号を加えている。この番号は、各データの同じＥｐＲａｎｇｅＬの中での位置を示す番号である。この番号は、同じＥｐＲａｎｇｅＬで、次に下位のデータを探すといった場合に用いるためのものである。
例えばＴｒ２について、ＥＰａｔｈ３，ＥＰａｔｈ４の上にあるノードを列挙したいとすると、ＥｐＲａｎｇｅＬが３あるいは４であるノードを辿って、ＥｐＲａｎｇｅＲが５より大きくならないものを探して列挙するという方法で簡単に実現できる。ただし、Ｅｐ３，Ｅｐ４の上にあるノードは、これだけが全てではなく、ＥｐＲａｎｇｅＬがＥｐ１であるｖ０，ｖ１が残される。しかし、後述する追加処理によって、このｖ０，ｖ１のようなノードも簡単に列挙することができる。
本実施の形態では、ＥｐＲａｎｇｅを指定して効率的にノードを列挙できる方法の一例として図１１、図１２、図１３に示すデータ構造を使って説明を行うが、他のデータ管理方法、例えばバケット分割を用いる方法や探索のための探索木による方法を適用してもよい。
【００４４】
ステップＳ３０４（要素の出現を集計）では、構造情報管理モジュール２１０によって、各ラベルがいくつのツリーで出現したかを集計する。この処理は前述のステップＳ３０２の際に同時に実行することもできる。処理の結果、各ラベルがいくつの木構造データで出現したかを判定できる情報を得て、パターン抽出の条件に見合うものだけを残した頻出要素（本実施の形態ではノードのラベル）のリストを作成する。構成により、各頻出要素の出現位置情報（以降簡単に出現情報とも呼ぶ）も合わせて処理結果となる。
ここでの例では、Ａ，Ｂ，Ｃ，Ｄ，Ｆが頻出要素のリストに残る。この頻出要素のリストにしたがい、リスト中の頻出要素それぞれをルートノードとした構造パターンを抽出する処理を以降の繰り返し処理で行う。
【００４５】
ステップＳ３０６（頻出要素処理終了？）では、頻出要素のリスト内のノードのラベル（例に示したＡ，Ｂ，Ｃ，Ｄ，Ｆ）それぞれについて処理が繰り返されたことを、検査し、処理の流れを制御する。頻出要素のリスト中の全てのラベルについて処理が終わったところで、処理を終了する（ステップＳ３１４）。
【００４６】
ステップＳ３０８（処理対象要素選択）では、出現情報選択モジュール２２０が、頻出要素のリスト内の未処理のものから一つ選ぶ。例ではノードのラベル、Ａ，Ｂ，Ｃ，Ｄ，Ｆの中から未処理のものを一つ選ぶことになる。どのラベルを選択した場合も処理の流れは共通であるため、以降ではラベルＡを選択した場合について説明を行う。
【００４７】
ステップＳ３１０（探索状態作成）では、探索状態管理モジュール２６０が、選択したラベルが各構造データにおいてどこで出現したかを示す情報を用意する。
このステップＳ３１０は、ステップＳ３０４において各ラベルの出現位置情報も合わせて出現情報管理モジュール２３０に格納される構成の場合には、その情報を取り出してくるだけの処理となる。構成によっては、記憶容量などの関係から出現位置の情報が出現情報管理モジュール２３０に記憶されていない場合もあり、そのような場合には、この段階で構造情報を走査して出現位置の情報を抽出するようにしてもよい。
例えば、ラベルＡの出現情報は、図１４に示すように、Ｔｒ１の出現情報１４１０内のｖ０Ｔｒ１、ｖ２Ｔｒ１、ｖ４Ｔｒ１、ｖ１２Ｔｒ１、Ｔｒ２の出現情報１４２０内のｖ１Ｔｒ２、ｖ３Ｔｒ２、ｖ９Ｔｒ２、ｖ１１Ｔｒ２、Ｔｒ３の出現情報１４３０内のｖ０Ｔｒ３、ｖ８Ｔｒ３、となる。ここで、図１４に示した出現情報は、図１１、図１２、図１３に格納されている情報と同じものを用いた。つまり、（１）「ノードの識別子」、（２）「ラベル」、（３）「ＥｐＲａｎｇｅＬ」、（４）「ＥｐＲａｎｇｅＲ」、（５）「ＥｐＲａｎｇｅＬ」を同じとして格納されている情報内での番号の組として示してある。
【００４８】
この出現情報に加えて、選択したラベルをルートとした構造パターン木を作成し、その構造パターン木中の現在処理位置を設定して、図１５の例に示す探索状態ノードを作成する。つまり、探索状態ノードは、構造パターン木１５１０、出現情報１５２０、変更情報スタック１５３０を有している。構造パターン木１５１０は、ステップＳ３０８で選択されたラベルのノードをルートとした構造パターン木とその構造パターン木中の現在処理位置を記憶している。出現情報１５２０内のＴｒ１ １５２１、Ｔｒ２ １５２２、Ｔｒ３ １５２３は、図１４で示した出現情報１４１０、出現情報１４２０、出現情報１４３０と同じものである。変更情報スタック１５３０は、後述の処理で使用するものである。
【００４９】
この探索状態ノードをルートノードとして、探索状態を図１６の例に示すように作成して、探索状態管理モジュール２６０に格納する。図１６は、探索状態ノードに格納されている構造パターン木に対応するパターンの構造を文字列で示したものを探索状態ノード（Ａ）１６１０に示したものである。
なお、構造パターン木の文字列の表記は、ここでは、｛親｝［｛子供１｝，｛子供２｝，・・・］という書き方を再帰的に適用することにより示す。ただし、子供がないノードについては［］を省略する。
【００５０】
ステップＳ３１２では、探索処理モジュール２５０が、頻出構造パターン探索を行う。ステップＳ３１２については、図４に示すフローチャートを用いて説明する。
なお、ステップＳ３１０（探索状態作成）は、ここではステップＳ３１２（頻出構造パターン探索）の前で行ったが、構成によってステップＳ３１０はステップＳ３１２の処理の中に組み込むこともできる。
【００５１】
図４は、本実施の形態による頻出構造パターン探索の処理例を示したフローチャートである。ここで２種類の探索を行っている。つまり、第１の探索である下位探索（ステップＳ４０４）と第２の探索である横枝探索（ステップＳ４１０）である。
また、下位探索処理（ステップＳ４０４）は、複数の木構造データ内で複数回現れる構造パターンの探索を、前記木構造データ内の現在の処理対象となっているノードより下位のノードに対して行う。
そして、横枝探索処理（ステップＳ４１０）では、前記構造パターンの探索を、前記木構造データ内の現在の処理対象となっているノードより上位のノードであって、その上位のノードの下位にあり、かつ未探索のノード毎に行う。
下位探索処理と横枝探索処理では、探索の対象とすべきノードがなくなった場合に、その探索を始めた元のノードに戻るようにしている。
【００５２】
ステップＳ４０２（構造パターン情報出力）では、その時点での探索状態ノードの構造パターン木のデータを出力する。この出力の手前で予め定められた基準にしたがって、出力するか否かの判定を行ってもよい。
【００５３】
ステップＳ４０４（下位探索）では、子孫方向に頻出する部分構造を探索する。この下位探索を行うときに、構造パターン内の現在の処理対象である現処理対象となっているノードと一致する前記木構造データ内のノード（ノードの間で上下関係があるものについては最上位のノード）に基づいて、子孫を探索する範囲を決定するようにしており、下位探索処理は、その決定された範囲に基づいて探索を行う。なお、ステップＳ４０４については、図５に示すフローチャートを用いて説明する。
そして、下位探索とは別に親ノードや先祖ノードから横方向に部分構造を探索する、横枝探索（ステップＳ４１０）の繰り返し処理が行われる。この横枝探索を行うときに、構造パターン内での親ノードと一致する前記木構造データ内のノード（ノード間で上下関係のあるものについては最上位のノード）及び前記構造パターン内での子ノードと一致する前記木構造データ内のノード（ノード間に上下関係があるときには最下位のノード）に基づいて、探索範囲を決定するようにしており、横枝探索処理は、その決定された範囲に基づいて探索を行う。
なお、この繰り返し処理中のステップＳ４０６（横枝探索箇所残りあり？）や、ステップＳ４０８（横枝探索箇所選択）は、パターン木中にノードが複数ある方が説明しやすいため、これらのステップの説明は後で行う。ステップＳ４１０（横枝探索）も別途後述する。
【００５４】
図５は、本実施の形態による下位探索の処理例を示したフローチャートである。
ステップＳ５０２（下位探索範囲情報準備）では、子孫ノードの探索範囲の準備を行う。このステップでは、具体的には各構造データに対して子孫ノードを探索する範囲を指定する。ここではその指定をＥｐＲａｎｇｅにより行う例を示す。
パターン中のノードをラベルＡで選び、そのときの探索状態ノードは図１５に示すようになる。このとき、例えば、Ｔｒ１においてラベルＡの子孫の候補は、Ｔｒ１ １５２１に基づいて、ｖ０Ｔｒ１の子孫、あるいはｖ２Ｔｒ１の子孫、あるいはｖ４Ｔｒ１の子孫、あるいはｖ１２Ｔｒ１の子孫である。
【００５５】
ｖ０Ｔｒ１の子孫はＥｐＲａｎｇｅ（ｖ０Ｔｒ１）＝［１，６］の範囲にあり、ｖ２Ｔｒ１の子孫はＥｐＲａｎｇｅ（ｖ２Ｔｒ１）＝［１，３］の範囲にあり、ｖ４Ｔｒ１の子孫はＥｐＲａｎｇｅ（ｖ４Ｔｒ１）＝［１，２］の範囲にあり、ｖ１２Ｔｒ１の子孫はＥｐＲａｎｇｅ（ｖ１２Ｔｒ１）＝［４，５］の範囲に存在する。
【００５６】
下の条件全て（（１）と（２））を満たすノードは先祖にラベルＡを持つノードが存在する。
（１）ＥｐＲａｎｇｅ（ｖ０Ｔｒ１）＝［１，６］，ＥｐＲａｎｇｅ（ｖ２Ｔｒ１）＝［１，３］，ＥｐＲａｎｇｅ（ｖ４Ｔｒ１）＝［１，２］，ＥｐＲａｎｇｅ（ｖ１２Ｔｒ１）＝［４，５］のいずれかのＥｐＲａｎｇｅの範囲にある。
（２）ｖ０Ｔｒ１，ｖ２Ｔｒ１，ｖ４Ｔｒ１，ｖ１２Ｔｒ１のいずれのＥｐＲａｎｇｅも、そのノードのＥｐＲａｎｇｅよりも広いものが存在しないなら、同じＥｐＲａｎｇｅを持つものでより上位のものが存在する。
ただし、前述の２つの条件は、本実施の形態で用いた構造情報の管理方法において、重複なく子孫ノードを列挙する際の一方法のための条件である。パターンに対応する出現情報から、全ての子孫ノード候補を列挙できるのであれば他の方法を用いても構わない。
【００５７】
前述の条件にしたがって、子孫ノードを列挙する一方法を示す。
まず各構造データ（例では、Ｔｒ１，Ｔｒ２，Ｔｒ３）毎に出現データのＥｐＲａｎｇｅの包含関係を調べ、他のＥｐＲａｎｇｅに含まれないものだけを残す。なお、ＥｐＲａｎｇｅが同じであれば、同じＥｐＲａｎｇｅＬを持つものの間でつけた番号がより小さいものを残す。この処理により、Ｔｒ１ではｖ０Ｔｒ１、Ｔｒ２ではｖ１Ｔｒ２、Ｔｒ３ではｖ０Ｔｒ３がそれぞれ残る。
【００５８】
これらの出現情報をもとに子孫ノードの探索を行う。
ノードＡからの子孫ノードの探索例は、Ｔｒ１ではｖ１Ｔｒ１以下全てのノード、Ｔｒ２ではｖ２Ｔｒ２以下全てのノード、Ｔｒ３ではｖ３Ｔｒ３以下全てのノードとなる。
この走査の過程で、ステップＳ５０４（要素の出現を集計）において、各ラベル毎に出現情報が集計され集められる。
この段階でも頻出と判定されるラベルはＡ，Ｂ，Ｃ，Ｄ，Ｆとなる。
【００５９】
次にこれらの頻出ラベルのそれぞれを処理対象要素と選んだ処理が、それぞれステップＳ５０６（頻出要素処理終了？）によって繰り返される。
例えば、ステップＳ５０８（処理対象要素選択）で、Ｂを選んだとして説明を行う。このときのＢの出現情報は、図１７に示すように、Ｔｒ１の出現情報１７１０内のｖ１Ｔｒ１、ｖ３Ｔｒ１、ｖ６Ｔｒ１、ｖ１１Ｔｒ１、ｖ１３Ｔｒ１、Ｔｒ２の出現情報１７２０内のｖ２Ｔｒ２、ｖ４Ｔｒ２、ｖ７Ｔｒ２、ｖ１２Ｔｒ２、Ｔｒ３の出現情報１７３０内のｖ２Ｔｒ３、ｖ１０Ｔｒ３となる。
【００６０】
そして、次にステップＳ５１０（探索状態作成・更新）の処理を行う。つまり、ここでは、構造パターン内の現在の処理対象となっているノードの先祖のノードの出現箇所から、その現在の処理対象となっているノードの出現箇所のノードを子孫に含むノードに対応する出現箇所を保持するようにしている。
構造パターン木のルートノードＡの下にＢが子供のノードとしてついたパターンを登録し、構造パターン木の中の現在位置情報はＢの位置を指す。また、出現情報として図１７に示す出現情報１７１０、出現情報１７２０、出現情報１７３０を登録して、図１８の例に示すように探索状態ノードを作成して探索状態管理モジュール２６０に登録する。つまり、図１８の例に示す探索状態ノードは、構造パターン木１８１０にラベルＡのノードの下にラベルＢのノードを有している構造パターン木とその構造パターン木の中の現在の位置情報（ラベルＢのノード）を記憶しており、出現情報１８２０に図１７に示したものと同様のＴｒ１ １８２１、Ｔｒ２ １８２２、Ｔｒ３ １８２３を記憶しており、さらに、変更情報スタック１８３０に変更情報１８３１を記憶している。
【００６１】
ここでの探索状態は、図１９の例に示すようになる。つまり、図１９の例に示す探索状態は、探索状態ノード（Ａ）１９１０下に探索状態ノード（Ａ[Ｂ]）１９２０が接続されている。
【００６２】
そして、探索状態の更新を行う。具体的には、登録した探索状態ノードから順に上位の探索状態ノードを辿り、下位の探索状態ノードに登録されている出現位置を一つも含まない出現情報をいったん削除して変更情報スタック１８３０に格納する。
この例の状態では、下位の探索状態ノードがＡ［Ｂ］、上位の探索状態ノードがＡであり、探索状態ノードＡ［Ｂ］の出現情報を一つも範囲に含まないものを探索状態ノードＡの出現情報から移動して、変更情報スタック１８３０に格納する。ここでは、この条件に該当する出現情報が、探索状態ノードＡにないため、なにもしない。もし、構造パターン木中の先祖方向の木の状態を更新した場合には、その更新した出現状態ノードの情報を上位方向の更新を開始する際の探索状態ノード（この場合探索状態ノードＡ［Ｂ］）の変更情報スタック１８３０に格納する。
【００６３】
そして、再帰的にステップＳ５１２（頻出構造パターン探索）の処理に入る。
頻出構造パターン探索処理では、構造パターン情報の出力処理において、予め定められた条件にしたがって、構造パターン木の情報Ａ［Ｂ］が出力される。次に、同様に下位探索に入る。
次の下位探索の処理では、Ｂの出現情報からの探索範囲は下のノードの子孫を探索することになる。すなわち、Ｔｒ１ではｖ１Ｔｒ１とｖ１１Ｔｒ１の子孫、Ｔｒ２ではｖ２Ｔｒ２とｖ７Ｔｒ２の子孫、Ｔｒ３ではｖ２Ｔｒ３の子孫の探索である。
この範囲で探索すると、例えばｖ１０Ｔｒ１，ｖ１５Ｔｒ１，ｖ６Ｔｒ２，ｖ１１Ｔｒ３などは探索の範囲にはいってこないなど、探索範囲が狭められてくるが、この段階ではまだ頻出ノードはＡ，Ｂ，Ｃ，Ｄ，Ｆのままである。
【００６４】
次に、ここでラベルＣのノードが選ばれたとする。すると、Ｃの出現情報はｖ８Ｔｒ１、ｖ１４Ｔｒ１、ｖ５Ｔｒ２、ｖ８Ｔｒ２、ｖ１３Ｔｒ２、ｖ３Ｔｒ３、ｖ９Ｔｒ３となる。この結果探索状態ノードは図２０に示すようになり、探索状態は図２１に示すようになる。つまり、図２０の例に示す探索状態ノードは、構造パターン木２０１０にラベルＡのノードの下にラベルＢのノード、そのラベルＢのノードの下にラベルＣのノードを有している構造パターン木とその構造パターン木の中の現在の位置情報（ラベルＣのノード）を記憶しており、出現情報２０２０にＴｒ１ ２０２１、Ｔｒ２ ２０２２、Ｔｒ３ ２０２３を記憶しており、さらに、変更情報スタック２０３０に変更情報２０３１を記憶している。図２１に示す探索状態は、探索状態ノード（Ａ）１９１０の下に探索状態ノード（Ａ[Ｂ]）１９２０が接続され、探索状態ノード（Ａ[Ｂ]）１９２０の下に探索状態ノード（Ａ[Ｂ[Ｃ]]）２１３０が接続されている。
【００６５】
そして、探索状態ノードの上位のものの更新が行われる。図２０に示すＣの出現情報２０２０を下位に持たない、すなわちＥｐＲａｎｇｅが図２０のＣのＴｒ１ ２０２１、Ｔｒ２ ２０２２、Ｔｒ３ ２０２３の出現情報のいずれよりも大きくない、あるいは同じであったとしても番号が大きいものは、変更情報２０３１に加えられて変更情報スタック２０３０に格納される。
この場合、ｖ６Ｔｒ１、ｖ１３Ｔｒ１、ｖ４Ｔｒ２、ｖ１２Ｔｒ２、ｖ１０Ｔｒ３を変更情報２０３１に登録して、変更情報スタック２０３０に格納する。その結果探索状態ノードＡ［Ｂ］は、図２２に示すように更新される。つまり、図２２の例に示す探索状態ノードは、構造パターン木２２１０にラベルＡのノードの下にラベルＢのノードを有している構造パターン木とその構造パターン木の中の現在の位置情報（ラベルＢのノード）を記憶しており、出現情報２２２０にＴｒ１ ２２２１、Ｔｒ２ ２２２２、Ｔｒ３ ２２２３を記憶しており、さらに、変更情報スタック２２３０に変更情報２２３１、変更情報２２３２を記憶している。そして、この更新した情報を、更新の原因となった探索状態ノードＡ［Ｂ［Ｃ］］の変更情報２２３１に格納する。
【００６６】
そして、下位の探索状態ノードＡ［Ｂ］が更新されたので、その上位の探索状態ノードＡの更新検査を行う。この場合、出現情報のうちｖ４Ｔｒ１、ｖ１２Ｔｒ１、ｖ３Ｔｒ２、ｖ９Ｔｒ２、ｖ１１Ｔｒ２、ｖ８Ｔｒ３が下位に該当するＢを持たなくなるため、出現情報からはずされて変更情報スタックに移動される。そして、この更新した情報を、更新の原因となった探索状態ノードＡ［Ｂ［Ｃ］］の変更情報に格納する。この探索状態ノードＡの更新結果を図２３に示す。つまり、図２３の例に示す探索状態ノードは、構造パターン木２３１０にラベルＡのノードを有している構造パターン木とその構造パターン木の中の現在の位置情報（ラベルＡのノード）を記憶しており、出現情報２３２０にＴｒ１ ２３２１、Ｔｒ２ ２３２２、Ｔｒ３ ２３２３を記憶しており、さらに、変更情報スタック２３３０に変更情報２３３１、変更情報２３３２を記憶している。そして、この更新した情報を、更新の原因となった探索状態ノードＡ［Ｂ［Ｃ］］の変更情報２２３１に格納する。
【００６７】
次に、続けて頻出構造パターン探索（ステップＳ５１２）に入る。この段階でもラベルＣを持つノードの下に頻出ラベルは見つけることができるが、同じ処理の流れの繰り返しとなるので、下位探索の処理は再帰的な実行が終了して次の処理に進んだところを説明する。
【００６８】
図４に示すフローチャートでのステップＳ４０６（横枝探索箇所残りあり？）以降の処理（ステップＳ４０６〜ステップＳ４１０）は、探索状態を上位方向に探索状態ノードを辿る処理となる。登録した一番新しい探索状態ノードから親探索状態ノードの方向に辿り、親子関係のペア毎に横枝探索の処理（ステップＳ４１０）が実行されることになる。
この例では、探索状態は図２１に示すように、３つの探索状態ノードからなっており、探索状態ノード（Ａ）１９１０の下に探索状態ノード（Ａ[Ｂ]）１９２０が接続されており、探索状態ノード（Ａ[Ｂ]）１９２０の下に探索状態ノード（Ａ[Ｂ[Ｃ]]）２１３０が接続されており、２段階の親子関係が構成されている。このため、このループは探索状態ノードＡ［Ｂ］と探索状態ノードＡ［Ｂ［Ｃ］］の間の親子関係と、探索状態ノードＡと探索状態ノードＡ［Ｂ］の間の親子関係について実行される。
この処理は、望ましくは探索状態ノードの下位から上位への順で行う。ここでは、まず探索状態ノードＡ［Ｂ］と探索状態ノードＡ［Ｂ［Ｃ］］の間の親子関係に対する処理を説明する。すなわち横枝探索箇所としてこの探索状態ノードの親子関係が選ばれたものとする（ステップＳ４０８）。
【００６９】
そして、ステップＳ４１０（横枝探索）の処理に入る。
図７に、横枝探索の処理例のフローチャートを示す。
横枝探索処理では、まずステップＳ７０２（横枝探索範囲情報準備）の処理を実行する。この処理は具体的には、選択された探索状態ノードの親子関係の間、ここでの例では、探索状態ノードＡ［Ｂ］と探索状態ノードＡ［Ｂ［Ｃ］］の間で横枝探索範囲情報を準備する。
【００７０】
この処理は、上位の探索状態ノードの出現情報から、ＥｐＲａｎｇｅが他の出現情報のＥｐＲａｎｇｅに包含されないものを選び、それぞれのＥｐＲａｎｇｅについて、下位の探索状態ノードの出現情報の中から上位のＥｐＲａｎｇｅにＥｐＲａｎｇｅが含まれるものの中でＥｐＲａｎｇｅＲが最小のものを選び（以降、下位最左ＥｐＲａｎｇｅとよぶ）、この選ばれた下位のＥｐＲａｎｇｅのＥｐＲａｎｇｅＲ（下位最左ＥｐＲａｎｇｅのＥｐＲａｎｇｅ）と上位ＥｐＲａｎｇｅのＥｐＲａｎｇｅで横枝探索範囲を算出する。
【００７１】
例えば、Ｔｒ１では上位探索状態ノードの出現情報のうち、ｖ３Ｔｒ１のＥｐＲａｎｇｅはｖ１Ｔｒ１のＥｐＲａｎｇｅに包含される（同じＥｐＲａｎｇｅの場合には一番右の番号が小さいものが番号の大きいものを包含するとして説明する。ただしＥｐＲａｎｇｅは同じなので逆としても結果に影響はない）。このため、上位探索状態ノードのＥｐＲａｎｇｅはｖ１Ｔｒ１とｖ１１Ｔｒ１のＥｐＲａｎｇｅとなる。ｖ１Ｔｒ１に対応する下位探索状態ノードの出現情報は、ｖ８Ｔｒ１のＥｐＲａｎｇｅとなる。したがって、この場合の上位ＥｐＲａｎｇｅは、ＥｐＲａｎｇｅ（ｖ１Ｔｒ１）＝［１，３］で下位最左ＥｐＲａｎｇｅはＥｐＲａｎｇｅ（ｖ８Ｔｒ１）＝［２，２］となる。その結果、ｖ１Ｔｒ１についての探索範囲は［２＋１，３］、すなわちＥｐＲａｎｇｅ［３，３］となる。
【００７２】
また、もう一方のｖ１１Ｔｒ１のＥｐＲａｎｇｅについては下位探索状態ノードの出現情報はｖ１４Ｔｒ１のＥｐＲａｎｇｅとなる。上位ＥｐＲａｎｇｅはＥｐＲａｎｇｅ（ｖ１１Ｔｒ１）＝［４，５］で下位最左ＥｐＲａｎｇｅはＥｐＲａｎｇｅ（ｖ１４Ｔｒ１）＝［５，５］となる。その結果、ｖ１１Ｔｒ１についての探索範囲は［５＋１，５］となり、矛盾した範囲となるため対応する探索範囲はないということになる。この結果、Ｔｒ１についての探索範囲はＥｐＲａｎｇｅ［３，３］だけとなる。同様にＴｒ２については上位、ｖ７Ｔｒ２のＥｐＲａｎｇｅと、これに対応する下位最左ＥｐＲａｎｇｅ、ｖ１３Ｔｒ２のＥｐＲａｎｇｅとの間でＥｐＲａｎｇｅ［５：５］が横枝の探索範囲となる。Ｔｒ３については上位、ｖ２Ｔｒ３のＥｐＲａｎｇｅと、これに対応する下位最左ＥｐＲａｎｇｅ、ｖ９Ｔｒ３のＥｐＲａｎｇｅとの間でＥｐＲａｎｇｅ［４：４］が横枝の探索範囲となる。
【００７３】
これらの探索範囲にしたがって、それぞれの木構造データを探索する（ステップＳ７０４〜ステップＳ７１４）。本実施の形態では、この探索処理を効率よく行う一方法として図１１、図１２、図１３のデータ構造を用いる方法を示している。他のデータ構造と処理方法を用いて、この探索処理を行ってもよいが、少なくともこの方法を用いることで、各木構造データからＥＰａｔｈの範囲を指定したノードの探索を容易に実現することができる。
【００７４】
Ｔｒ１からはＥｐＲａｎｇｅ［３，３］で探索すると、ｖ９Ｔｒ１だけが探索範囲となる。出現するラベルはＦである。Ｔｒ２からはＥｐＲａｎｇｅ［５，５］で探索すると、ｖ１４Ｔｒ２とｖ１５Ｔｒ２だけが探索範囲となる。出現するラベルはＧとＦである。Ｔｒ３からはＥｐＲａｎｇｅ［４，４］で探索すると、ｖ１０Ｔｒ２だけが探索範囲となる。出現するラベルはＢである。このときの頻出となるラベルはＦだけとなる（ステップＳ７０４）。
【００７５】
このラベルＦを選択して（ステップＳ７０８）、探索状態作成・更新の処理（ステップＳ７１０）を行う。また、ステップＳ７１０では、構造パターン内の現在の処理対象となっているノードの先祖のノードの出現箇所から、その現在の処理対象となっているノードの出現箇所のノードを子孫に含むノードに対応する出現箇所を保持するようにしている。
図２４に示す前述のＦの出現情報を用いて探索状態ノードを作成して、探索状態に登録する。このときの探索状態を図２５に示す。つまり、図２４の例に示す探索状態ノードは、構造パターン木２４１０にラベルＡのノードの下にラベルＢのノード、そのラベルＢのノードの下にラベルＣのノードとラベルＦのノードを有している構造パターン木とその構造パターン木の中の現在の位置情報（ラベルＦのノード）を記憶しており、出現情報２４２０にＴｒ１ ２４２１、Ｔｒ２ ２４２２を記憶しており、さらに、変更情報スタック２４３０に変更情報２４３１を記憶している。また、図２５に示す探索状態は、４つの探索状態ノードからなっており、探索状態ノード（Ａ）１９１０の下に探索状態ノード（Ａ[Ｂ]）１９２０が接続されており、探索状態ノード（Ａ[Ｂ]）１９２０の下に探索状態ノード（Ａ[Ｂ[Ｃ]]）２１３０と探索状態ノード（Ａ[Ｂ[ＣＦ]]）２５４０が接続されている。このとき探索状態ノードＡ［Ｂ［ＣＦ］］は、横枝の探索時に親側の探索状態ノードとして選んだ探索状態ノードＡ［Ｂ］の子供ノードとして関係付けられる。
【００７６】
次に、この探索状態ノードＡ［Ｂ［ＣＦ］］を登録したことによる影響を調べて探索状態ノードの更新を行う。
このとき、更新が必要であるかどうかを調べる探索状態ノードは、探索状態ノードＡ［Ｂ［ＣＦ］］の先祖である探索状態ノードである。具体的には、探索状態ノードＡ［Ｂ］と探索状態ノードＡである。この場合、探索状態ノードＡ［Ｂ］を検査した段階で更新が必要ないことがわかるので、探索状態ノードの更新は行われない。
【００７７】
そして、さらに頻出構造パターン探索（ステップＳ７１２）に移行する。
頻出構造パターン探索では、パターン候補Ａ［Ｂ［ＣＦ］］について、必要であれば出力処理を行い、下位探索の処理を行う。
ここでの下位探索においては、頻出となるラベルが存在しないためすぐに下位探索処理から戻ってくる。
次に、横枝探索の繰り返し処理が行われる。このときの横枝探索の候補となる探索状態ノードの親子関係は、探索状態ノードＡ［Ｂ［ＣＦ］］と探索状態ノードＡ［Ｂ］の間の関係、探索状態ノードＡと探索状態ノードＡ［Ｂ］の間の関係の二通りとなる。
この処理の流れは既に説明した。
しかし、ここではいずれの探索状態ノードの親子関係においても頻出となるラベルが現れない。
【００７８】
そして、この探索状態ノードＡ［Ｂ［ＣＦ］］における処理が終わる。これにより探索状態ノードＡ［Ｂ［ＣＦ］］に対応する頻出構造パターン探索の処理が終わり、上位の処理の流れに戻る。この場合には、横枝探索の処理に戻る。そして次のステップの探索状態回復の処理（ステップＳ７１４）が行われる。
【００７９】
この探索状態回復の処理（ステップＳ７１４、ステップＳ５１４）について説明する。
探索状態ノードＡ［Ｂ［ＣＦ］］の変更情報スタックを参照する。ここに更新した探索状態ノードＡ［Ｂ］，Ａが記録されている。
この両方の探索状態ノードについて、それぞれ探索状態スタックのトップの変更情報をもとに探索状態ノードの回復処理を行う。具体的には、探索状態ノードＡ［Ｂ］の場合には、出現情報のｖ６Ｔｒ１，ｖ１３Ｔｒ１，ｖ４Ｔｒ２，ｖ１２Ｔｒ２，ｖ１０Ｔｒ３を出現情報として戻す。戻した結果は、図２２に示したものと同じになる。同様に処理して、探索状態ノードＡも図２３に示したものと同じになる。
以上に示したように、処理を再帰的に実行していくことで予め指定された出現数以上の全ての先祖−子孫関係の木構造を抽出することができる。
【００８０】
図６に示すフローチャートを用いて、子孫ノードの走査処理について説明する。
ステップＳ６０２では、上位の出現情報の処理が終了しているか否かについて判断する。かかる判断において、終了していると判断した場合は子孫ノードの走査処理を終了し（ステップＳ６１２）、終了していないと判断した場合はステップＳ６０４へ進む。
ステップＳ６０４では、出現情報を一つ選択する。
【００８１】
ステップＳ６０６では、ステップＳ６０４で選択した出現情報のＥｐＲａｎｇｅＬ，ＥｐＲａｎｇｅＲを、それぞれＥｐＲａｎｇｅＬＰ，ＥｐＲａｎｇｅＲＰとする。
ステップＳ６０８では、出現情報のＥｐＲａｎｇｅＬがＥｐＲａｎｇｅＬＰと同じものを出現情報の次の番号から走査する。
ステップＳ６１０では、ＥｐＲａｎｇｅＬＰ＋１からＥｐＲａｎｇｅＲＰまでの範囲で、ＥｐＲａｎｇｅＲの値がＥｐＲａｎｇｅＲＰ以下のものを走査する。
【００８２】
なお、本実施の形態で示した例では、ＥｐＲａｎｇｅが同じ出現情報も皆同等に扱ったが、ＥｐＲａｎｇｅ（つまり、分岐がない範囲）が同じ出現情報は一つ（つまり、最上位と最下位のノード）を代表として扱って処理しても全く同等の効果が得られ、記憶しておく出現情報の量が減る分必要な記憶容量が削減され、さらに、検査などの処理のコストも削減される。つまり、木構造内で分岐のない範囲の最上位及び最下位以外の出現箇所を探索状態管理モジュール２６０から削除するようにしてもよい。あるいは、探索状態管理モジュール２６０に格納する前に選別してもよい、さらには、構造情報ＤＢ１１０に格納する時点でこの選別を行ってもよい。
【００８３】
また、木構造のノードを深さ優先探索してノードに番号をつけ、そのノードの番号を持ってノードの子孫のノードの範囲を示す方法が知られている。このｓｃｏｐｅと呼ばれる情報は、例えば図７に示すＴｒ２のｖ７では、自分自身の番号７と子孫のノードのうち最も大きな番号を持ったノードの番号を用いて［７，１５］と表わされる。
木構造から範囲を指定してノードを探索するために本実施の形態ではＥｐＴｒｅｅを用いたが、代わりにこのｓｃｏｐｅ情報を用いて探索する構成にすることも当業者に容易な変更の範囲である。ｓｃｏｐｅ情報は各ノードの子孫ノードの範囲を示す情報であるため、あるノードからの子孫の範囲を決定できる。また、横枝の探索時にも上位の出現情報のｓｃｏｐｅ情報と下位の出現情報のｓｃｏｐｅ情報を演算することが可能であり、本実施の形態の該当箇所に当てはめれば、横枝の探索範囲もｓｃｏｐｅ情報を用いて決定することができる。
【００８４】
なお、本実施の形態としてのプログラムが実行されるコンピュータのハードウェア構成は、図２６に例示するように、一般的なコンピュータであり、具体的にはパーソナルコンピュータ、サーバーとなり得るコンピュータ等である。構造情報管理モジュール２１０、出現情報選択モジュール２２０、出現情報管理モジュール２３０、調査範囲処理モジュール２４０、探索処理モジュール２５０、探索状態管理モジュール２６０、抽出情報処理モジュール２７０等のプログラムを実行するＣＰＵ２６０１と、そのプログラムやデータを記憶するＲＡＭ２６０２と、本コンピュータを起動するためのプログラム等が格納されているＲＯＭ２６０３と、補助記憶装置であるＨＤ２６０４（例えばハードディスクを用いることができる）と、キーボード、マウス等のデータを入力する入力装置２６０６と、ＣＲＴや液晶ディスプレイ等の出力装置２６０５と、通信ネットワークと接続するための通信回線インタフェース２６０７（例えばネットワークインタフェースカードを用いることができる）、そして、それらをつないでデータのやりとりをするためのバス２６０８により構成されている。これらのコンピュータが複数台互いにネットワークによって接続されていてもよい。
【００８５】
前述の実施の形態のうち、コンピュータ・プログラムによるものについては、本ハードウェア構成のシステムにソフトウェアであるコンピュータ・プログラムを読み込ませ、ソフトウェアとハードウェア資源とが協働して、前述の実施の形態が実現される。
なお、図２６に示すハードウェア構成は、１つの構成例を示すものであり、本実施の形態は、図２６に示す構成に限らず、本実施の形態において説明したモジュールを実行可能な構成であればよい。例えば、一部のモジュールを専用のハードウェア（例えばＡＳＩＣ等）で構成してもよく、一部のモジュールは外部のシステム内にあり通信回線で接続しているような形態でもよく、さらに図２６に示すシステムが複数互いに通信回線によって接続されていて互いに協調動作するようにしてもよい。また、特に、パーソナルコンピュータの他、情報家電、複写機、ファックス、スキャナ、プリンタ、複合機（スキャナ、プリンタ、複写機、ファックス等のいずれか２つ以上の機能を有している画像処理装置）などに組み込まれていてもよい。
【００８６】
なお、説明したプログラムについては、記録媒体に格納して提供してもよく、また、そのプログラムを通信手段によって提供してもよい。その場合、例えば、前記説明したプログラムについて、「プログラムを記録したコンピュータ読み取り可能な記録媒体」の発明として捉えてもよい。
「プログラムを記録したコンピュータ読み取り可能な記録媒体」とは、プログラムのインストール、実行、プログラムの流通などのために用いられる、プログラムが記録されたコンピュータで読み取り可能な記録媒体をいう。
なお、記録媒体としては、例えば、デジタル・バーサタイル・ディスク（ＤＶＤ）であって、ＤＶＤフォーラムで策定された規格である「ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ−ＲＡＭ等」、ＤＶＤ＋ＲＷで策定された規格である「ＤＶＤ＋Ｒ、ＤＶＤ＋ＲＷ等」、コンパクトディスク（ＣＤ）であって、読出し専用メモリ（ＣＤ−ＲＯＭ）、ＣＤレコーダブル（ＣＤ−Ｒ）、ＣＤリライタブル（ＣＤ−ＲＷ）等、光磁気ディスク（ＭＯ）、フレキシブルディスク（ＦＤ）、磁気テープ、ハードディスク、読出し専用メモリ（ＲＯＭ）、電気的消去及び書換可能な読出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュ・メモリ、ランダム・アクセス・メモリ（ＲＡＭ）等が含まれる。
そして、前記のプログラム又はその一部は、前記記録媒体に記録して保存や流通等させてもよい。また、通信によって、例えば、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、イントラネット、エクストラネット等に用いられる有線ネットワーク、あるいは無線通信ネットワーク、さらにこれらの組み合わせ等の伝送媒体を用いて伝送させてもよく、また、搬送波に乗せて搬送させてもよい。
さらに、前記のプログラムは、他のプログラムの一部分であってもよく、あるいは別個のプログラムと共に記録媒体に記録されていてもよい。また、複数の記録媒体に分割して
記録されていてもよい。また、圧縮や暗号化など、復元可能であればどのような態様で記録されていてもよい。
【図面の簡単な説明】
【００８７】
【図１】本実施の形態を好適に適用するシステムの概念構成例を示す説明図である。
【図２】本実施の形態の構成例についての概念的なモジュール構成図である。
【図３】本実施の形態による処理例を示したフローチャートである。
【図４】本実施の形態による頻出構造パターン探索の処理例を示したフローチャートである。
【図５】本実施の形態による下位探索の処理例を示したフローチャートである。
【図６】本実施の形態による子孫ノードの走査処理例を示したフローチャートである。
【図７】本実施の形態による横枝探索の処理例を示したフローチャートである。
【図８】対象とする木構造データの例を示す説明図である。
【図９】Ｅｐａｔｈの例を示す説明図である。
【図１０】各ノードにおけるＥｐＲａｎｇｅの例を示す説明図である。
【図１１】木構造データＴｒ１のＥｐＴｒｅｅの例を示す説明図である。
【図１２】木構造データＴｒ２のＥｐＴｒｅｅの例を示す説明図である。
【図１３】木構造データＴｒ３のＥｐＴｒｅｅの例を示す説明図である。
【図１４】各木構造データにおけるラベルＡの出現の例を示す説明図である。
【図１５】探索状態ノードの例を示す説明図である。
【図１６】パターンのルートノードにラベルＡを選択した場合の探索状態の例を示す説明図である。
【図１７】各木構造データにおけるラベルＢの出現の例を示す説明図である。
【図１８】ラベルＡの子孫としてラベルＢを選択した場合の探索状態ノードＡ［Ｂ］の例を示す説明図である。
【図１９】ラベルＡの子孫としてラベルＢを選択した場合の探索状態の例を示す説明図である。
【図２０】ラベルＢの子孫としてラベルＣを選択した場合の探索状態ノードＡ［Ｂ［Ｃ］］の例を示す説明図である。
【図２１】ラベルＢの子孫としてラベルＣを選択した場合の探索状態の例を示す説明図である。
【図２２】探索状態ノードＡ［Ｂ］の例を示す説明図である。
【図２３】探索状態ノードＡの例を示す説明図である。
【図２４】探索状態ノードＡ［Ｂ［ＣＦ］］の例を示す説明図である。
【図２５】探索状態Ａ［Ｂ［ＣＦ］］の例を示す説明図である。
【図２６】本実施の形態を実現するコンピュータのハードウェア構成例を示すブロック図である。
【符号の説明】
【００８８】
１１０…構造情報ＤＢ
１２０…情報収集装置
１３０…情報抽出装置
１４０…抽出情報管理装置
２１０…構造情報管理モジュール
２２０…出現情報選択モジュール
２３０…出現情報管理モジュール
２４０…調査範囲処理モジュール
２５０…探索処理モジュール
２６０…探索状態管理モジュール
２７０…抽出情報処理モジュール
【特許請求の範囲】
【請求項１】
複数の木構造内で複数回現れる構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより下位のノードに対して行う第１の探索手段と、
前記構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより上位のノードであって該上位のノードの下位にあり、かつ未探索のノード毎に探索する第２の探索手段
を具備し、
前記第１の探索手段と前記第２の探索手段は、探索の対象とすべきノードがなくなった場合に、該探索を始めた元のノードに戻る
ことを特徴とする情報処理装置。
【請求項２】
前記構造パターン内の現在の処理対象である現処理対象となっているノードと一致する前記木構造内でのノードのうち上下関係のあるものについては最上位のノードに基づいて、子孫を探索する範囲を決定する第１の探索範囲決定手段
をさらに具備し、
前記第１の探索手段は、前記第１の探索範囲決定手段によって決定された範囲に基づいて探索を行う
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記構造パターン内での親ノードと一致する前記木構造内でのノードのうち上下関係のあるものについては最上位のノード及び前記構造パターン内での子ノードと一致する前記木構造内でのノードに上下関係のあるものについては最下位のノードに基づいて、探索範囲を決定する第２の探索範囲決定手段
をさらに具備し、
前記第２の探索手段は、前記第２の探索範囲決定手段によって決定された範囲に基づいて探索を行う
ことを特徴とする請求項１に記載の情報処理装置。
【請求項４】
前記構造パターン内の現在の処理対象となっているノードの先祖のノードの出現箇所の中から、該現在の処理対象となっているノードの出現箇所のノードを子孫に含むノードに対応する出現箇所を保持する保持手段
をさらに具備することを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記木構造内で分岐のない範囲の最上位及び最下位以外の出現箇所を前記保持手段から削除する削除手段
をさらに具備することを特徴とする請求項４に記載の情報処理装置。
【請求項６】
前記保持手段に保持させる出現箇所を対象とし、前記木構造内で分岐のない範囲の最上位及び最下位以外の出現箇所以外を削除したものを選別する選別手段
をさらに具備することを特徴とする請求項４に記載の情報処理装置。
【請求項７】
コンピュータを、
複数の木構造内で複数回現れる構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより下位のノードに対して行う第１の探索手段と、
前記構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより上位のノードであって該上位のノードの下位にあり、かつ未探索のノード毎に探索する第２の探索手段
として機能させ、
前記第１の探索手段と前記第２の探索手段は、探索の対象とすべきノードがなくなった場合に、該探索を始めた元のノードに戻る
ことを特徴とする情報処理プログラム。
【請求項１】
複数の木構造内で複数回現れる構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより下位のノードに対して行う第１の探索手段と、
前記構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより上位のノードであって該上位のノードの下位にあり、かつ未探索のノード毎に探索する第２の探索手段
を具備し、
前記第１の探索手段と前記第２の探索手段は、探索の対象とすべきノードがなくなった場合に、該探索を始めた元のノードに戻る
ことを特徴とする情報処理装置。
【請求項２】
前記構造パターン内の現在の処理対象である現処理対象となっているノードと一致する前記木構造内でのノードのうち上下関係のあるものについては最上位のノードに基づいて、子孫を探索する範囲を決定する第１の探索範囲決定手段
をさらに具備し、
前記第１の探索手段は、前記第１の探索範囲決定手段によって決定された範囲に基づいて探索を行う
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記構造パターン内での親ノードと一致する前記木構造内でのノードのうち上下関係のあるものについては最上位のノード及び前記構造パターン内での子ノードと一致する前記木構造内でのノードに上下関係のあるものについては最下位のノードに基づいて、探索範囲を決定する第２の探索範囲決定手段
をさらに具備し、
前記第２の探索手段は、前記第２の探索範囲決定手段によって決定された範囲に基づいて探索を行う
ことを特徴とする請求項１に記載の情報処理装置。
【請求項４】
前記構造パターン内の現在の処理対象となっているノードの先祖のノードの出現箇所の中から、該現在の処理対象となっているノードの出現箇所のノードを子孫に含むノードに対応する出現箇所を保持する保持手段
をさらに具備することを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記木構造内で分岐のない範囲の最上位及び最下位以外の出現箇所を前記保持手段から削除する削除手段
をさらに具備することを特徴とする請求項４に記載の情報処理装置。
【請求項６】
前記保持手段に保持させる出現箇所を対象とし、前記木構造内で分岐のない範囲の最上位及び最下位以外の出現箇所以外を削除したものを選別する選別手段
をさらに具備することを特徴とする請求項４に記載の情報処理装置。
【請求項７】
コンピュータを、
複数の木構造内で複数回現れる構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより下位のノードに対して行う第１の探索手段と、
前記構造パターンの探索を、前記木構造内の現在の処理対象となっているノードより上位のノードであって該上位のノードの下位にあり、かつ未探索のノード毎に探索する第２の探索手段
として機能させ、
前記第１の探索手段と前記第２の探索手段は、探索の対象とすべきノードがなくなった場合に、該探索を始めた元のノードに戻る
ことを特徴とする情報処理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【公開番号】特開２００９−１８７２２４（Ｐ２００９−１８７２２４Ａ）
【公開日】平成２１年８月２０日（２００９．８．２０）
【国際特許分類】
【出願番号】特願２００８−２５６３５（Ｐ２００８−２５６３５）
【出願日】平成２０年２月５日（２００８．２．５）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
【公開日】平成２１年８月２０日（２００９．８．２０）
【国際特許分類】
【出願日】平成２０年２月５日（２００８．２．５）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
[ Back to top ]