JP4957618B2 - 情報処理装置及び情報処理プログラム - Google Patents

Description

本発明は、情報処理装置及び情報処理プログラムに関する。

コンピュータの処理能力、記憶装置の容量の飛躍的な増大に加え、ＩＴ化やネットワーク化が進んだことで大量な情報が容易に集められるようになってきた。集めた情報から市場機会やリスクに関する情報を早期に発見したり、隠れた知識を発見したりすることへの期待が高まっている。
しかし、集めた情報の量はしばしば人間の処理能力をはるかに超えるものとなる。このため、せっかく大量に集めた情報からリスクを発見したり、知識を抽出したりして活用することは実際には労力を伴う難しいものであった。

一方、パターン・マイニング等の技術の進展により、そのような大量の情報の中から例えば同時に購入される商品のパターンなどの情報が抽出可能となってきた。同時に購入される品物のパターンや購入される順序のパターンを抽出する技術が顧客の購買行動の分析などの需要から注目を集めて研究開発されてきたが、最近ではさまざまな情報の構造化、半構造化が進んできたこともあり、木構造のような構造を持つパターンを抽出するパターン・マイニングの技術が注目されてきている。構造情報を抽出するパターン・マイニングの技術の中でも、特に木構造はＸＭＬ（ｅＸｔｅｎｓｉｂｌｅ Ｍａｒｋｕｐ Ｌａｎｇｕａｇｅ）をはじめとしてドキュメントの構造化や知識表現などさまざまな情報の構造化に用いられるためパターン抽出への期待も大きい。

木構造のデータ群から部分木のパターンを抽出する技術には大きく分けて、親子関係が厳密に一致する構造だけを抽出するｉｎｄｕｃｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇの技術と、親子関係が多少乱れても先祖―子孫の関係があれば構造を抽出するｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇの技術がある。
現実社会で発生するデータ、例えば電子文書であるドキュメントの操作履歴などのように人の操作を記録したものでは、たとえ同じ内容の作業を行っても、作業者の操作順などが厳密には一致しないため操作の履歴データの親子関係が厳密に一致することは期待できない。このため、そのようなデータからパターンを抽出するためには、親子関係に揺れが生じたとしてもパターンが抽出できるｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇの技術を適用することが望ましい。また、人の操作の記録だけではなく、情報を整理した木構造データのようなものからも埋め込まれている隠れた構造を抽出するためには同様にｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇを用いる必要がある。

しかし、ｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇは、ｉｎｄｕｃｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇに比べて計算量も処理に必要となるメモリ量も膨大なものになることが知られている。例えば、ｉｎｄｕｃｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇ ではパターンの親子関係がツリーデータの親子関係と一致するため、パターン上のあるノードに接続する子供ノードの候補はツリーデータ上で対応するノードに直接接続する子供ノードだけとなる。これに対して、ｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇでは、パターン上のあるノードに接続する子供ノードの候補はツリーデータ上で対応するノードの子孫ノード全部となる。子孫ノードの数は木構造が大きくなるにつれて鼠算的に増えるため、処理のための時間も必要となるメモリ量も膨大なものとなる。
ｅｍｂｅｄｄｅｄ ｓｕｂｔｒｅｅ ｍｉｎｉｎｇを実現する従来の技術としては、ＴｒｅｅＭｉｎｅｒ、Ｄｒｙａｄｅ、ＭＢ３−ｍｉｎｅｒ、ＴＲＩＰＳなどを挙げることができる。

これらに関連する技術として、例えば、特許文献１には、データの集合からその中に含まれる重要なパターンを検出する方法及びシステムを提供することを課題とし、木構造データで表されたデータ集合を含むデータベースから、集計対象となる候補パターンを用いて、頻出パターンを検出するシステムであって、（１）データベースから候補パターンにマッチするパターンを集計する手段と、（２）前記集計により出現頻度の高いパターンを検出する手段と、（３）前記検出したパターンから、次の集計対象となる候補パターンを生成する手段と、を有するように構成することが開示されている。

また、例えば、特許文献２には、順序木において頻出するパターンを抽出するのに好適な抽出装置等を提供することを課題とし、抽出装置の入力受付部は、１つ以上の順序木の入力を受け付け、変換部は、入力が受け付けられた順序木のそれぞれを系列表現へ変換し、抽出部は、変換された系列表現のそれぞれが含むパターンのうち、所定の頻度以上で出現するパターンを抽出し、系列表現は、順序木を深さ優先探索して、枝を進む際に通過する節はその名前を表すマークを、枝を戻る際はバックトラックマークを、それぞれ並べることによりでき、パターンは、系列表現であるマークの列中の名前を表すマークのいずれかを最初のマークとして、これから射影を０回以上繰り返したときに、最初のマークから最後のマークに至るまでに出会うマークの列をいい、射影が成立するか否かは、マークの列の列文脈と、射影文脈の値により判定することが開示されている。
特開２００１−１３４５７５号公報 特開２００４−３５５４５７号公報

本発明は、複数の木構造内で複数回現れる構造パターンの探索において、その探索範囲を所定範囲内に収めるようにした情報処理装置及び情報処理プログラムを提供することを目的としている。

かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
請求項１の発明は、木構造内のノード毎に子孫ノードの範囲を示す情報を付与してノードを記憶手段に格納する格納手段と、複数の木構造内で複数回現れる構造パターンの探索を、前記木構造の所定の範囲内にあるノードに対して行うことによって、該構造パターンを抽出する構造パターン抽出手段と、前記木構造内におけるノードの出現箇所に関する情報である出現情報ごとに、既に前記構造パターン抽出手段によって抽出された構造パターンで子供ノードがあったノードの出現情報にそれぞれの既出の子供ノードの出現情報の少なくとも一部を対応付けて記憶する記憶手段を具備し、前記構造パターン抽出手段は、ノード間の上下関係の有無を、前記格納手段によって格納されたノードの子孫ノードの範囲を示す情報の包含関係の有無によって判定し、前記記憶手段に記憶された出現情報に基づいて、前記構造パターン内で複数回出現したラベルの分岐毎に前記所定の範囲を定め、該所定の範囲内での該ラベルによって構成された構造パターンを抽出し、該抽出処理を再帰的に繰り返すことによって、複数の木構造内で複数回現れる構造パターンを探索することを特徴とする情報処理装置である。
請求項２の発明は、木構造内のノード毎にルートノードからリーフノードまでに至る経路情報を記憶手段に格納する格納手段と、複数の木構造内で複数回現れる構造パターンの探索を、前記木構造の所定の範囲内にあるノードに対して行うことによって、該構造パターンを抽出する構造パターン抽出手段と、前記木構造内におけるノードの出現箇所に関する情報である出現情報ごとに、既に前記構造パターン抽出手段によって抽出された構造パターンで子供ノードがあったノードの出現情報にそれぞれの既出の子供ノードの出現情報の少なくとも一部を対応付けて記憶する記憶手段を具備し、前記構造パターン抽出手段は、ノード間の上下関係の有無を、該ノード間において前記格納手段によって格納されたノードの経路情報が共通のものを含むか否かによって判定し、前記記憶手段に記憶された出現情報に基づいて、前記構造パターン内で複数回出現したラベルの分岐毎に前記所定の範囲を定め、該所定の範囲内での該ラベルによって構成された構造パターンを抽出し、該抽出処理を再帰的に繰り返すことによって、複数の木構造内で複数回現れる構造パターンを探索することを特徴とする情報処理装置である。

請求項３の発明は、前記構造パターン抽出手段は、ノードに対応するラベルの出現回数に応じて選択されたラベルを用いて、前記構造パターンを抽出することを特徴とする請求項１又は２に記載の情報処理装置である。

請求項４の発明は、前記構造パターン抽出手段は、前記木構造の所定の範囲内のノードを探索することによって、前記構造パターンを抽出することを特徴とする請求項１又は２に記載の情報処理装置である。

請求項５の発明は、前記木構造のデータ構造に基づいて、請求項３又は請求項４に記載の構造パターン抽出手段による構造パターンの抽出のいずれかを選択する選択手段をさらに具備することを特徴とする請求項１又は２に記載の情報処理装置である。

請求項６の発明は、前記構造パターン内の現在の処理対象である現処理対象となっているノードと一致する前記木構造内でのノードのうち上下関係のあるものについては最上位のノードに基づいて、子孫を探索する範囲を決定する第１の探索範囲決定手段をさらに具備し、前記構造パターン抽出手段は、前記第１の探索範囲決定手段によって決定された範囲に基づいて探索を行うことを特徴とする請求項１又は２に記載の情報処理装置である。

請求項７の発明は、前記構造パターン内での親ノードと一致する前記木構造内でのノードのうち上下関係のあるものについては最上位のノード及び前記構造パターン内での子供ノードと一致する前記木構造内でのノードに上下関係のあるものについては最下位のノードに基づいて、探索範囲を決定する第２の探索範囲決定手段をさらに具備し、前記構造パターン抽出手段は、前記第２の探索範囲決定手段によって決定された範囲に基づいて探索を行うことを特徴とする請求項１又は２に記載の情報処理装置である。

請求項８の発明は、前記構造パターン内の現在の処理対象となっているノードの先祖のノードの出現箇所の中から、該現在の処理対象となっているノードの出現箇所のノードを子孫に含むノードに対応する出現箇所を保持する保持手段をさらに具備することを特徴とする請求項７に記載の情報処理装置である。

請求項９の発明は、前記木構造内で分岐のない範囲の最上位及び最下位以外の出現箇所を前記保持手段から削除する削除手段をさらに具備することを特徴とする請求項８に記載の情報処理装置である。

請求項１０の発明は、前記保持手段に保持させる出現箇所を対象とし、前記木構造内で分岐のない範囲の最上位及び最下位以外の出現箇所以外を削除したものを選別する選別手段をさらに具備することを特徴とする請求項８に記載の情報処理装置である。

請求項１１の発明は、コンピュータを、木構造内のノード毎に子孫ノードの範囲を示す情報を付与してノードを記憶手段に格納する格納手段と、複数の木構造内で複数回現れる構造パターンの探索を、前記木構造の所定の範囲内にあるノードに対して行うことによって、該構造パターンを抽出する構造パターン抽出手段と、前記木構造内におけるノードの出現箇所に関する情報である出現情報ごとに、既に前記構造パターン抽出手段によって抽出された構造パターンで子供ノードがあったノードの出現情報にそれぞれの既出の子供ノードの出現情報の少なくとも一部を対応付けて記憶する記憶手段として機能させ、前記構造パターン抽出手段は、ノード間の上下関係の有無を、前記格納手段によって格納されたノードの子孫ノードの範囲を示す情報の包含関係の有無によって判定し、前記記憶手段に記憶された出現情報に基づいて、前記構造パターン内で複数回出現したラベルの分岐毎に前記所定の範囲を定め、該所定の範囲内での該ラベルによって構成された構造パターンを抽出し、該抽出処理を再帰的に繰り返すことによって、複数の木構造内で複数回現れる構造パターンを探索することを特徴とする情報処理プログラムである。
請求項１２の発明は、コンピュータを、木構造内のノード毎にルートノードからリーフノードまでに至る経路情報を記憶手段に格納する格納手段と、複数の木構造内で複数回現れる構造パターンの探索を、前記木構造の所定の範囲内にあるノードに対して行うことによって、該構造パターンを抽出する構造パターン抽出手段と、前記木構造内におけるノードの出現箇所に関する情報である出現情報ごとに、既に前記構造パターン抽出手段によって抽出された構造パターンで子供ノードがあったノードの出現情報にそれぞれの既出の子供ノードの出現情報の少なくとも一部を対応付けて記憶する記憶手段として機能させ、前記構造パターン抽出手段は、ノード間の上下関係の有無を、該ノード間において前記格納手段によって格納されたノードの経路情報が共通のものを含むか否かによって判定し、前記記憶手段に記憶された出現情報に基づいて、前記構造パターン内で複数回出現したラベルの分岐毎に前記所定の範囲を定め、該所定の範囲内での該ラベルによって構成された構造パターンを抽出し、該抽出処理を再帰的に繰り返すことによって、複数の木構造内で複数回現れる構造パターンを探索することを特徴とする情報処理プログラムである。

請求項１記載の情報処理装置によれば、複数の木構造内で複数回現れる構造パターンの探索において、その探索範囲を所定範囲内に収めることができる。
請求項２記載の情報処理装置によれば、複数の木構造内で複数回現れる構造パターンの探索において、その探索範囲を所定範囲内に収めることができる。

請求項３記載の情報処理装置によれば、探索処理における記憶容量及び処理時間の増大を抑制するのに適した構造パターンの抽出を行うことができる。

請求項４記載の情報処理装置によれば、探索処理における記憶容量及び処理時間の増大を抑制するのに適した構造パターンの抽出を行うことができる。

請求項５記載の情報処理装置によれば、木構造のデータ構造に応じて、探索処理における記憶容量及び処理時間の増大を抑制するのに適した構造パターンの抽出方法を使い分けることができる。

請求項６記載の情報処理装置によれば、探索処理における記憶容量及び処理時間の増大を抑制することができる。

請求項７記載の情報処理装置によれば、探索処理における記憶容量及び処理時間の増大を抑制することができる。

請求項８記載の情報処理装置によれば、探索状態を保持して、その探索における再帰的処理が実行できる。

請求項９記載の情報処理装置によれば、探索処理における記憶容量をより削減することができる。

請求項１０記載の情報処理装置によれば、探索処理における記憶容量をより削減することができる。

請求項１１記載の情報処理プログラムによれば、複数の木構造内で複数回現れる構造パターンの探索において、その探索範囲を所定範囲内に収めることができる。
請求項１２記載の情報処理プログラムによれば、複数の木構造内で複数回現れる構造パターンの探索において、その探索範囲を所定範囲内に収めることができる。

まず、前述のＴｒｅｅＭｉｎｅｒ、Ｄｒｙａｄｅ、ＭＢ３−Ｍｉｎｅｒ、ＴＲＩＰＳの技術について、説明する。
Ｄｒｙａｄｅは、兄弟ノードに同じものを含めないという機能制限があり、ドキュメントの操作履歴など多くの現実のデータを処理するには十分なものではなかった。
ＴｒｅｅＭｉｎｅｒ、ＭＢ３−ｍｉｎｅｒ、ＴＲＩＰＳはいずれも、小さなパターンツリーを用意し、そのパターンツリーに一つノードを加えたパターンツリーを見つけるという再帰処理を行うことで全ての頻出パターンツリーを見つけていく。
これらのうち、ＭＢ３−Ｍｉｎｅｒは、１つのノードからなるパターンツリーを見つけ、次に２つのノードからなるパターンツリーを全て見つけ、その次に３つのノードからなるパターンツリーを全て見つけるというように、ノード数の同じパターンツリーを全て見つけた後で、次のステップでノード数が一つ大きいパターンツリー全てを探すことを繰り返す。ノードを一つ加えたパターンツリーの数は指数関数的に増えるため、ＭＢ３−ｍｉｎｅｒでは、現実的な計算機環境で抽出できるパターンツリーの大きさが制限されてしまう。

ＴｒｅｅＭｉｎｅｒとＴＲＩＰＳは、一つの頻出ノードからなるあるパターンツリーに対して、一つノードを加えたパターンツリーを探し、それらのパターンツリーのそれぞれついてさらに一つノードを加えたパターンツリーを探していき深さ優先探索を行う。これらの方法ではＭＢ３−Ｍｉｎｅｒのようにあるノード数のパターン全てをメモリ上に用意する必要はないため、多くのパターンツリーが見つかるデータも処理できる場合がある。
しかし、一つノードの多いパターンツリーの候補を見つける処理の制御を、ツリーデータ上のノードを一筆書きにした系列データにそった制御を行っており、ツリーデータの構造を制御に生かしていないため、パターンツリーのノード数が増えてくると各ステップでの処理と必要となるメモリ量が増大してしまう。その結果、大きなパターンツリーを探索することが困難になってしまう。
ＴＲＩＰＳは、ＴｒｅｅＭｉｎｅｒよりもメモリ中に保持するデータを削減しているためこの問題が少しではあるが緩和される。一方で、次パターンノードの探索時に各データノードの先祖ノードを順にたどってパターンノードに対応するものを探す処理を行うため、大きなパターンツリーとなるほどオーバーヘッドが生じてしまう。
これらの従来技術では、ツリーデータの構造情報をパターンの探索に用いず、より単純な系列データなどに変換した情報を用いてパターンの探索を行っていることから、探索処理における記憶容量及び処理時間の増大が発生してしまう。

本実施の形態のパターン抽出装置では、木構造の構造情報を用いた構造パターン（以下、単にパターンともいう）の探索を行う。つまり、具体的には、パターンツリーの枝の分岐ごとにパターンノードの候補を列挙する。これを実現するために、パターンツリーに既出のノードの出現位置の情報をもとに候補の選択範囲の算出装置を有し、さらに、前のステップで見つけたパターンノード候補の情報を選別して使用することで、パターンノード候補の探索と出現回数の計数を効率化する。これによって、木構造の分岐ごとにパターンツリーを探索していくことで効率的にパターンツリーを列挙するパターン抽出装置を提供する。なお、「出現位置」という用語は、パターン内のノードの出現箇所の位置を指し示す用語として用いる。

以下、図面に基づき本発明を実現するにあたっての好適な一実施の形態の例を説明する。
図１は、本実施の形態の構成例についての概念的なモジュール構成図を示している。
なお、モジュールとは、一般的に論理的に分離可能なソフトウェア（コンピュータ・プログラム）、ハードウェア等の部品を指す。したがって、本実施の形態におけるモジュールはコンピュータ・プログラムにおけるモジュールのことだけでなく、ハードウェア構成におけるモジュールも指す。それゆえ、本実施の形態は、コンピュータ・プログラム、システム及び方法の説明をも兼ねている。ただし、説明の都合上、「記憶する」、「記憶させる」、「保持する」、これらと同等の文言を用いるが、これらの文言は、実施の形態がコンピュータ・プログラムの場合は、記憶装置に記憶させる、又は記憶装置に記憶させるように制御するの意である。また、モジュールは機能にほぼ一対一に対応しているが、実装においては、１モジュールを１プログラムで構成してもよいし、複数モジュールを１プログラムで構成してもよく、逆に１モジュールを複数プログラムで構成してもよい。また、複数モジュールは１コンピュータによって実行されてもよいし、分散又は並列環境におけるコンピュータによって１モジュールが複数コンピュータで実行されてもよい。なお、１つのモジュールに他のモジュールが含まれていてもよい。また、以下、「接続」とは物理的な接続の他、論理的な接続（データの授受、指示、データ間の参照関係等）の場合にも用いる。
また、システム又は装置とは、複数のコンピュータ、ハードウェア、装置等がネットワーク（一対一対応の通信接続を含む）等の通信手段で接続されて構成されるほか、１つのコンピュータ、ハードウェア、装置等によって実現される場合も含まれる。「装置」と「システム」とは、互いに同義の用語として用いる。

本実施の形態は、図１に示すように、ツリーデータ入力モジュール１１０、ツリーデータ保持モジュール１２０、制御モジュール１３０、パターン抽出モジュール１４０、パターン情報出力モジュール１５０を有している。

ツリーデータ入力モジュール１１０は、ツリーデータ保持モジュール１２０と接続されている。ツリー構造を有する又はツリー構造を構成できるデータを図示しない入力機構やデータ送信機構から受け取る。受け取ったデータを必要であればツリー構造に構成、ツリー構造の変換又はノードに付けられたラベルの変換などを行って、ツリーデータ保持モジュール１２０に送信する。このときに、ツリーデータだけでなく、ツリーデータを構成したり、変換したり、ラベルの変換を行ったりしたときに使用されたり生成されたりした情報もツリーデータ保持モジュール１２０に送信してもよい。また、このツリーデータの生成や変換を行うときには制御モジュール１３０からの命令にしたがって処理を変化させてもよい。なお、ツリーデータ入力モジュール１１０が受け取るツリー構造を有する又はツリー構造を構成できるデータは複数であってもよい。

ツリーデータ保持モジュール１２０は、ツリーデータ入力モジュール１１０、パターン抽出モジュール１４０と接続されている。ツリーデータ保持モジュール１２０は、ツリーデータ入力モジュール１１０から送信されたデータを保持し、パターン抽出モジュール１４０からの要求に応じてデータの取り出しや、送信を行う。ツリーデータ保持モジュール１２０は、パターン抽出モジュール１４０が発行する命令にしたがって、ノードやラベルの検索や集計を行ってもよい。また、パターン抽出モジュール１４０の要求に応じて、ツリーデータ入力モジュール１１０から送信されたツリーデータ以外の情報をパターン抽出モジュール１４０に送信してもよい。

制御モジュール１３０は、パターン抽出モジュール１４０と接続されている。制御モジュール１３０は、図示しない入力モジュール（例えば、キーボード、マウス等）を通じてユーザからの指示を受け取り、パターン抽出モジュール１４０の動作の制御を行う。ユーザからの指示の一部が図示しない記憶装置にいったん格納されており、その記憶装置から情報を読み出してパターン抽出モジュール１４０の制御に利用してもよい。

パターン抽出モジュール１４０は、ツリーデータ保持モジュール１２０、制御モジュール１３０、パターン情報出力モジュール１５０と接続されている。パターン抽出モジュール１４０は、制御モジュール１３０からの指示を受けて、ツリーデータ保持モジュール１２０に保持されているツリー構造データからパターンを抽出してパターン情報出力モジュール１５０に送信する。つまり、複数のツリーデータ内に現れるパターンの探索を、そのツリーデータの所定の範囲内にあるノードに対して行うことによって、パターンを抽出する。そして、後述する出現位置情報保持モジュール２６０に記憶された出現情報（出現情報とは、ツリーデータにおけるノードの出現箇所に関する情報である）に基づいて、その所定の範囲を定める。また、抽出したパターンをツリーデータ保持モジュール１２０を参照してラベルの値などを変換してからパターン情報出力モジュール１５０に送信してもよい。変換したパターン情報は、抽出したパターンのツリー構造を表す情報であってもよいし、抽出したパターンのツリー構造が出現したツリーデータやその数の情報でもよいし、それらの組み合わせにより構成された情報であってもよい。

また、パターン抽出モジュール１４０は、パターン内の現在の処理対象である現処理対象となっているノードと一致するツリーデータ内でのノードのうち上下関係のあるものについては最上位のノードに基づいて、子孫を探索する範囲を決定し、その決定された範囲に基づいて探索を行うようにしてもよい。
また、パターン抽出モジュール１４０は、パターン内での親ノードと一致するツリーデータ内でのノードのうち上下関係のあるものについては最上位のノード及びパターン内での子供ノードと一致するツリーデータ内でのノードに上下関係のあるものについては最下位のノードに基づいて、探索範囲を決定し、その決定された範囲に基づいて探索を行うようにしてもよい。
また、パターン内の現在の処理対象となっているノードの先祖のノードの出現箇所の中から、その現在の処理対象となっているノードの出現箇所のノードを子孫に含むノードに対応する出現箇所を保持するようにしてもよい。なお、「出現箇所」という用語は、パターン内のノードのツリーデータ内での出現箇所を指す用語として用いる。
また、パターン抽出モジュール１４０は、ツリーデータ内で分岐のない範囲の最上位及び最下位以外の出現箇所を後述する出現位置情報保持モジュール２６０から削除するようにしてもよい。
また、パターン抽出モジュール１４０は、出現位置情報保持モジュール２６０に保持させる出現箇所を対象とし、ツリーデータ内で分岐のない範囲の最上位及び最下位以外の出現箇所以外を削除したものを選別するようにしてもよい。
なお、パターン抽出モジュール１４０の内部構成については、後に詳述する。

パターン情報出力モジュール１５０は、パターン抽出モジュール１４０と接続されている。パターン情報出力モジュール１５０は、パターン抽出モジュール１４０から受け取った情報を図示しない出力装置に出力するものである。この出力は、ディスプレイや電子ペーパーや紙又は３次元の投影装置などを介した人への情報の提示であってもよいし、ファイル出力などの電子情報の出力であってもよい。パターン情報出力モジュール１５０は、データの加工を行って出力してもよいし、そのときにパターン抽出モジュール１４０やツリーデータ保持モジュール１２０と通信して加工に必要な情報を得てもよい。

図２は、本実施の形態のパターン抽出モジュール１４０内の構成例についての概念的なモジュール構成図である。パターン抽出モジュール１４０は、図２に示した構成の装置を複数持っていてもよく、また図２に示した構成の装置を処理の過程で繰り返し使用してもよい。
パターン抽出モジュール１４０は、図２に示すように、伸張元パターン情報受付モジュール２１０、パターン出力モジュール２２０、パターン伸張点選択モジュール２３０、伸張候補選定基準算出モジュール２４０、伸張候補選定モジュール２５０、出現位置情報保持モジュール２６０、出現位置情報選別モジュール２７０、出現位置情報回復モジュール２８０、パターン伸張モジュール２９０、パターン伸張起動モジュール２９５を有している。

伸張元パターン情報受付モジュール２１０は、パターン出力モジュール２２０、パターン伸張点選択モジュール２３０、伸張候補選定モジュール２５０、出現位置情報保持モジュール２６０と接続されている。伸張元パターン情報受付モジュール２１０は、パターン抽出の命令を受けたときの入力情報の受け付けを行う。入力データは、しばしば探索するパターン又はパターンの一部のノードの情報とそれらのノードの出現箇所の情報からなる。構成によっては、途中の制御を変更する拘束条件や、パターンとして抽出するために最低いくつのデータで出現するものであるかを示す数値であるｍｉｎｉｍｕｍ ｓｕｐｐｏｒｔ（以降、ｍｉｎｓｕｐという）が入力される。

伸張元パターン情報受付モジュール２１０は、パターン情報と場合によっては出現箇所の情報をパターン出力モジュール２２０に送信する。また、伸張元パターン情報受付モジュール２１０は、受け付けたパターン情報をパターン伸張点選択モジュール２３０に送信する。また、伸張元パターン情報受付モジュール２１０は、受け付けた出現位置に関する情報を出現位置情報保持モジュール２６０に送信する。また、伸張元パターン情報受付モジュール２１０は、受け付けたｍｉｎｓｕｐと、もしあれば拘束条件などの制御情報を伸張候補選定モジュール２５０に送信する。

パターン出力モジュール２２０は、伸張元パターン情報受付モジュール２１０と接続されている。パターン出力モジュール２２０は、パターンの出力を担当する。この構成例では、伸張元パターン情報受付モジュール２１０で受け付けたパターン情報を出力する構成としたが、パターン伸張モジュール２９０で新たに伸張したパターンを出力する構成に変更することは容易な変更である。

パターン伸張点選択モジュール２３０は、伸張元パターン情報受付モジュール２１０、伸張候補選定基準算出モジュール２４０、パターン伸張モジュール２９０と接続されている。パターン伸張点選択モジュール２３０は、伸張元パターン情報受付モジュール２１０から送信された、伸張元パターンの情報又はその一部のノードの情報からパターンを伸張する箇所のパターン上のノードを選択し、その選択したパターン上のノードに関する情報を順に伸張候補選定基準算出モジュール２４０に送信する。また、その選択したパターン上のノードに関する情報をパターン伸張モジュール２９０にも送信する。

通常はパターン伸張点の候補は、パターンのルートノードと一つのリーフノードを結ぶパス上にのるノードとなる。このような処理が行われる際には、パターン上のノードの兄弟ノード間に順序を設定して、ルートノードから順に子供をたどる際に最後の兄弟ノードを選んだパスが選定されることが多く、こうして選ばれるパスはｒｉｇｈｔｍｏｓｔ ｐａｔｈと呼ばれ、そのパス上のリーフノードはｒｉｇｈｔｍｏｓｔ ｌｅａｆと呼ばれる。以降、説明の簡単のために、ここで選ばれるパスをＲＭＰと呼び説明を行う。ｒｉｇｈｔｍｏｓｔ ｐａｔｈ以外のパス、例えば兄弟間順序の最初のものを選び続けたパスなどを排除するものではない。

ＲＭＰ上のノードの情報が順に選ばれて、伸張候補選定基準算出モジュール２４０に送信される。このとき、ＲＭＰのリーフノード以外のノードについては、ＲＭＰ上での子供ノードの情報が同時に送信されてもよい。また、別のリーフノードか否かを識別するための情報が同時に送信されてもよい。ＲＭＰ上のノードの選択順は、リーフノードから順に行ってもよい。下位のノードとその出現箇所の情報は、次の繰り返しでもう一度使用されるため、処理効率上有利となる。

伸張候補選定基準算出モジュール２４０は、パターン伸張点選択モジュール２３０、伸張候補選定モジュール２５０、出現位置情報保持モジュール２６０と接続されている。伸張候補選定基準算出モジュール２４０は、パターン伸張点選択モジュール２３０で選択された伸張点のノードの情報を得て、パターンをその伸張点で伸張するラベルの候補を選択するための基準となる情報を算出して伸張候補選定モジュール２５０に送信する。また、伸張候補選定基準算出モジュール２４０は、伸張点で伸張するラベルの候補を選択するための基準の出現位置に関する情報を出現位置情報保持モジュール２６０に送信する。

伸張候補選定モジュール２５０は、伸張元パターン情報受付モジュール２１０、伸張候補選定基準算出モジュール２４０、出現位置情報保持モジュール２６０、出現位置情報選別モジュール２７０、パターン伸張モジュール２９０と接続されている。伸張候補選定モジュール２５０は、伸張元パターン情報受付モジュール２１０、伸張候補選定基準算出モジュール２４０から受け取った情報に基づいて、ツリーデータを走査する、又はパターン伸張元データが小さいときに選択されていた伸張候補の中から該情報に基づいて選択する。そして、このことにより、パターンを伸張するラベル（パターンツリー上ではノード）の候補を選定する。選定した伸張候補をパターン伸張モジュール２９０へ送信する。また、伸張候補選定モジュール２５０は、選定した伸張候補の出現位置に関する情報を出現位置情報保持モジュール２６０、出現位置情報選別モジュール２７０に送信する。

出現位置情報保持モジュール２６０は、伸張元パターン情報受付モジュール２１０、伸張候補選定基準算出モジュール２４０、伸張候補選定モジュール２５０、出現位置情報選別モジュール２７０、出現位置情報回復モジュール２８０、パターン伸張起動モジュール２９５と接続されている。出現位置情報保持モジュール２６０は、伸張候補選定モジュール２５０によって選定された候補のツリーデータ上での出現箇所（ノードの位置情報）を保持する。全ての出現箇所を保持してもよいが、分岐のない範囲ではルートに一番近い出現箇所と一番ルートから離れた出現箇所を保持し、それ以外の出現箇所の情報を保持しなくても構わない。この判定は出現位置情報保持モジュール２６０で行ってもよいし、伸張候補選定モジュール２５０において行ってもよいし、さらに、ツリーデータ保持モジュール１２０に保持されているツリーデータがこの条件を満たすように、例えばツリーデータ入力モジュール１１０により加工されていてもよい。また、出現位置情報保持モジュール２６０は、伸張元パターン情報受付モジュール２１０が受け付けた出現位置に関する情報を保持する。また、出現位置情報保持モジュール２６０は、伸張候補選定基準算出モジュール２４０が算出した伸張点で伸張するラベルの候補を選択するための基準の出現位置に関する情報を保持する。また、保持している情報を、出現位置情報選別モジュール２７０、出現位置情報回復モジュール２８０、パターン伸張起動モジュール２９５からの要求に応じて送信する。

また、出現位置情報保持モジュール２６０は、探索済み範囲の情報を保持するようにしてもよい。つまり、出現位置情報保持モジュール２６０は、それぞれの出現情報ごとに、既にパターンに加えたそれぞれの子孫ノードの出現情報の少なくとも一部を対応付けて保持する。これにより、精密な出現情報の管理を実現できる。

出現位置情報選別モジュール２７０は、伸張候補選定モジュール２５０、出現位置情報保持モジュール２６０、出現位置情報回復モジュール２８０と接続されている。出現位置情報選別モジュール２７０は、伸張候補選定モジュール２５０が選定した伸張候補の出現位置を基に、出現位置情報保持モジュール２６０が保持している出現位置に関する情報の中から、伸張点のノードを含めたＲＭＰ上のノードの出現位置情報の選別を行う。ＲＭＰ上のノードはパターンツリー上ではそれぞれ親子関係でつながれているため、それぞれのノードの出現位置は先祖−子孫関係が存在する。ＲＭＰ上のノードの出現位置がこの条件を満たすように選別を行う。なお、この処理は、ＲＭＰ上のノードの下位（ルートから遠い方）から上位（ルートノードに近い方）に向いて行うと効率がよい。

出現位置情報回復モジュール２８０は、出現位置情報保持モジュール２６０、出現位置情報選別モジュール２７０、パターン伸張起動モジュール２９５と接続されている。出現位置情報回復モジュール２８０は、パターンの伸張候補を選定して、出現位置情報選別モジュール２７０が出現位置情報を選別してから選定したパターン伸張候補を加えたパターンを探索した後の処理を行う。この処理の内容は、パターンの伸張候補を選定したときに、出現位置情報選別モジュール２７０が選別したＲＭＰ上のノードであって、出現位置情報保持モジュール２６０が保持している出現位置情報の回復である。この処理を行うために、出現位置情報選別モジュール２７０は、選別により削除した出現情報に関する情報を出現位置情報回復モジュール２８０に送信してもよい。
また、出現位置情報選別モジュール２７０が、出現情報の複製を行うなどして後続の処理に副作用を及ぼさない形で処理を行った場合には、この出現位置情報回復モジュール２８０を省略した構成とすることもできる。

パターン伸張モジュール２９０は、パターン伸張点選択モジュール２３０、伸張候補選定モジュール２５０、パターン伸張起動モジュール２９５と接続されている。パターン伸張モジュール２９０は、伸張候補選定モジュール２５０が選定した伸張候補を、伸張元パターンのパターン伸張点選択モジュール２３０が選択した伸張位置に加えた新しいパターンを用意する。

パターン伸張起動モジュール２９５は、出現位置情報保持モジュール２６０、出現位置情報回復モジュール２８０、パターン伸張モジュール２９０と接続されている。パターン伸張起動モジュール２９５は、パターン伸張モジュール２９０で用意した新しいパターン情報に基づいて、パターン伸張モジュール２９０の処理を再帰的に起動する。そのために、出現位置情報保持モジュール２６０が保持している出現位置に関する情報を用いる。また、再帰的な起動に合わせて、出現位置情報回復モジュール２８０による処理を制御する。

図３は、本実施の形態による処理例を示すフローチャートである。
この図３に示す処理例は、図４に示す処理例の特殊な場合、すなわち伸張元パターンが空で、伸張元パターンのＲＭＰのノードがない場合である。この場合を特別に取り出しているが、後述の図４に示す処理例の中で統一的に対応してもよい。同様に、図２に示すパターン抽出モジュール１４０の構成例においても、図３に示す処理例が担当する処理の最初の特殊な場合用に調整された構成をとった処理モジュール（つまり図３に示す処理例を行うモジュール）を別途用意してもよい。

ステップＳ３０２では、頻出ラベルを列挙する。つまり、指定されたｍｉｎｓｕｐなどの条件にしたがって、ノードの数が１となるパターンを抽出する。
ノードの数が１となるパターンは、端的に言えば頻出するラベルとなる。伸張候補選定モジュール２５０は、ツリーデータ保持モジュール１２０に問い合わせて、又はツリーデータ保持モジュール１２０に保持されたツリーデータのノードを走査して頻出ラベルを集計して列挙する。頻出ラベルが予めツリーデータ保持モジュール１２０にて集計して列挙されている構成の場合には、その情報を取得すればよい。

次に伸張候補選定モジュール２５０が選定した情報に基づいた制御のもと頻出ラベルについて繰り返し処理を行う（ステップＳ３０４の判断によって、未処理頻出ラベルがなくなるまで、ステップＳ３０６からステップＳ３１０までの繰り返し処理）。ただし、この処理は必ずしも繰り返す必要はなく、並列処理として実現することも容易である。そのために、伸張候補選定モジュール２５０は、未処理頻出ラベルの有無判定と未処理頻出ラベルの選択を行う。
ステップＳ３０６では、選択された未処理頻出ラベルが伸張候補となる。

ステップＳ３０８では、パターン、出現箇所情報の準備を行う。つまり、伸張候補が伸張候補選定モジュール２５０からパターン伸張モジュール２９０に送信されて、新しく伸張したパターンが準備される。また、伸張候補の出現箇所情報が出現位置情報保持モジュール２６０に送信されて保持される。
なお、この図３に示す処理例では、新しく伸張したパターンツリーのノードの数が１であり、伸張候補以外のＲＭＰ上のノードが存在しないため、出現位置情報選別モジュール２７０は動作する必要がない。

ステップＳ３１０では、伸張パターンを探索する。つまり、伸張したパターンと出現箇所の情報を入力としてパターン抽出の処理を起動する。この起動は再帰的な起動でもよいし、別途用意された別のパターン抽出モジュール１４０の起動でもよい。なお、パターン抽出（伸張パターンの探索）の処理については、図４を用いて詳述する。
起動した処理が終了すると、図示していないが、必要であれば生成したパターンや出現情報の開放を行い、次の未処理頻出ラベルの処理を行う。

図４は、本実施の形態による伸張パターンの探索処理例を示すフローチャートである。
ステップＳ４０２では、最初に入力されたパターンをパターン出力モジュール２２０が出力する。この出力処理は必ずこのステップＳ４０２のステップになければならないわけではない。パターンが伸張されて新しいパターンが作成された直後でもよいし、そのパターンに関する処理が全て終わった後でもよいし、処理の過程のどこかで行われてもよい。

次に、パターン伸張点選択モジュール２３０は、伸張元パターン情報受付モジュール２１０が受け取った情報からパターンのＲＭＰ上のノードを選出し、それぞれのノードに対する処理を繰り返し行う（ステップＳ４０４の判断によって、伸張パス上の未処理ノードがなくなるまで、ステップＳ４０６からステップＳ４２０までの繰り返し処理）。この繰り返し処理も必ずしも繰り返す必要はなく、並列化による実現は容易であり除外するものではない。
未処理ノードがあった場合には、ステップＳ４０６でパターン伸張点選択モジュール２３０が未処理ノードを選択する。

ステップＳ４０８では、範囲を算出する。つまり、伸張候補選定基準算出モジュール２４０がそのノードと必要ならばそのノードの上（ルートに近い方）あるいは下（ルートから遠い方）のノードの出現位置の情報を用いて次の伸張候補を選定する基準を算出する。

ステップＳ４１０では、算出した範囲の頻出ラベルを列挙する。つまり、伸張候補選定モジュール２５０が、ノードに対応するラベルの出現回数（出現するツリーの数）に応じて選択されたラベルを用いて、パターンを抽出する。つまり、ステップＳ４０８で伸張候補選定基準算出モジュール２４０により算出された範囲情報を指定して、ツリーデータ保持モジュール１２０に保持されているツリーデータに出現するラベルとその出現位置の情報を得て、さらに出現頻度の集計を行って、頻出ラベルの選定を行う。
また、伸張候補選定モジュール２５０が、ツリーデータの所定の範囲内のノードを探索することによって、パターンを抽出するようにしてもよい。つまり、伸張候補選定基準算出モジュール２４０により算出された範囲情報に基づいて、ツリーデータ保持モジュール１２０に保持されているツリーデータのノードに対応するラベルを走査して、指定された範囲に出現するラベルやその出現位置の情報を得てもよい。また、ＲＭＰ上のノード候補を選定したときの集計情報を、伸張元パターン情報の伸張候補を選定した伸張候補選定モジュール２５０に問い合わせて頻出ラベル情報を得て、その中から範囲情報に合うものを選択してもよい。

前述の処理の頻出ラベルの情報を使用する方法を採用すると、頻出でないラベルに関する処理が全く必要なくなる。
また、前述の頻出ラベルの集計情報を利用する方法とツリーデータを走査する方法を、ツリーデータのデータ構造に応じて選択する選択モジュールを設けて、使い分けを行ってもよい。
なお、ステップＳ４０８とステップＳ４１０の処理の途中までは、出現位置の情報を使用する。このため、この部分をツリーデータごとにまとめて行うようにしてもよく、このことも容易な変更である。

ステップＳ４１２では、未処理の頻出ラベルがあるか否かを判断する。つまり、ステップＳ４１０で列挙された頻出ラベルの中で、未処理の頻出ラベルが残っているか否かを判定して繰り返し処理（ステップＳ４１４からステップＳ４２０までの処理）に入る。ここでの繰り返し処理も必ずしも繰り返して行う必要はなく、並列化して処理することを排除しない。並列化は簡単な変更で実現することができる。

未処理頻出ラベルがあった場合には、ステップＳ４１４で、伸張候補選定モジュール２５０がその未処理頻出ラベルを選択する。
ステップＳ４１６では、パターン、出現箇所の情報を準備する。つまり、ステップＳ４１４で選択された未処理頻出ラベルの情報にしたがって、パターン伸張モジュール２９０が伸張したパターンを準備し、出現位置情報保持モジュール２６０が出現位置を保持するとともに、出現位置情報選別モジュール２７０がＲＭＰ上の他のノードの出現位置の選別を行う。

ステップＳ４１８では、伸張パターン探索の処理を行う。つまり、この図４に示す処理例を再帰的に起動する。別の処理リソースがあった場合にはそれを起動してもよいし、同じ処理リソースを用いる場合には、処理に使用した情報をスタックなどに退避して新たに処理を実行させることもできる。
このステップＳ４１８の処理が終わると、選択した未処理頻出ラベルだけをＲＭＰの指定の箇所に接続したパターンが生成されて、その生成されたパターンを予め定めた伸張方法で伸張し、その伸張した全てのパターンに対する処理が終っていることになる。

ステップＳ４２０では、パターン、出現箇所情報の復帰を行う。つまり、出現位置情報回復モジュール２８０によって、ＲＭＰ上のノードの出現位置情報の回復を行う。出現位置情報選別モジュール２７０で削除された情報を出現位置情報回復モジュール２８０や図示しない他の記憶装置に保持しておけば、保持しておいた出現情報を戻すことで、簡単にこのステップの処理を実現することができる。
そして、未処理の頻出ラベルがなくなったら（ステップＳ４１２でＮ）、ステップＳ４０４で伸張パス上の次の未処理ノードを調べる。全ての未処理ノードの処理が終わっていれば、伸張パターン探索の処理は終了する（ステップＳ４９９）。

以降、処理対象であるツリーデータの例を用いながら範囲情報の算出方法や出現位置情報の選別などについても説明を行う。
図５は、本実施の形態の説明に用いるツリーデータの例である。つまり、この３つのツリーデータの例から複数回現れている構造パターンを抽出する。このツリーデータは、具体的には、ドキュメントの操作履歴のデータであり、
（１）ドキュメントが作成された（「作成Ａ」）、
（２）そのドキュメントが閲覧された（「閲覧Ｂ」）、
（３）そのドキュメントが修正された（「修正Ｃ」）、
（４）そのドキュメントがあるユーザによって確認処理が行われた（「確認Ｄ」）、
（５）そのドキュメントが承認権限を持つユーザによって承認された（「承認Ｅ」）、
（６）そのドキュメントが電子的にコピーされた（「電子複写Ｆ」）、
（７）そのドキュメントが印刷された（「印刷Ｇ」）、
（８）そのドキュメントが紙の状態からスキャンされた（「スキャンＨ」）
という８種類の操作からなる操作の履歴例である。図５等に示すツリーデータの各ノードは、これらの操作を表すラベルが、それぞれのラベルに対応させた記号「Ａ」〜「Ｈ」とともに表示されている。各ノードのラベルは処理の過程では記号に変換して処理することもできるし、数字からなるラベルに変換して処理することもできるし、これらの組み合わせであってもよい。

例えばツリーデータ（ａ）の履歴を説明すると、あるドキュメントが作成された（「作成Ａ」）のち、修正を行った（「修正Ｃ」）。そして、その修正前のドキュメントを誰かが閲覧している（「閲覧Ｂ」）。また、修正したドキュメントをあるユーザが閲覧して（「閲覧Ｂ」）修正している（「修正Ｃ」）が、その閲覧する前のバージョンを誰かが電子的に複写している（「電子複写Ｆ」）。閲覧して修正されたドキュメントはその後確認されて（「確認Ｄ」）、承認された（「承認Ｅ」）後に２名に閲覧されている（「閲覧Ｂ」、「閲覧Ｂ」）。一方、電子複写されたドキュメントは、修正されて（「修正Ｃ」）印刷され（「印刷Ｇ」）、２名がその紙を閲覧している（「閲覧Ｂ」、「閲覧Ｂ」）。図５に示すツリーデータ（ｂ）、（ｃ）も同様にドキュメントが作成されてからの操作の履歴を表したものである。

図６は、図５のツリーデータの各ノードに以降の説明のために番号情報をつけた例を示すものである。ツリーデータには、同じラベルが複数出現することはめずらしくないので、ラベルの出現位置を特定するために、各ノードに識別子を与えることを行う。図６に示した番号は、ツリーデータの各ノードを深さ優先で探索して、全てのノードを訪れたときの順番を各ノードの番号にする方法で付けられたものである。以降の説明で、ノードの番号を指定したときにはこの図６で示した番号の位置のノードを示している。例えば（ａ）ｖ６と書いたときにはツリーデータ（ａ）の左下のリーフノード（「閲覧Ｂ」）を指すことになる。

図７は、図５のツリーデータについて、ルートノードからリーフノードまでに至るパス（以降ＥＰａｔｈ，ＥＰとも示す）を求め、そのＥＰａｔｈに番号をつけた例である。全てのノードは、１つ以上のＥＰａｔｈにのる。したがって、ルートノードはそのツリーの全てのＥＰａｔｈにのるし、各リーフノードは一つだけのＥＰａｔｈにのることになる。以降、ＥＰａｔｈ又はＥＰで番号を示したときには、この図７に示したＥＰａｔｈを指しているものとする。例えば、（ａ）ＥＰ５と書いたときには、ツリーデータ（ａ）の右上のＥＰａｔｈ、「作成Ａ」のラベルを持つルートノード（ｖ０）から「閲覧Ｂ」のラベルを持つ右上のノード（ｖ１３）へのＥＰａｔｈを指す。

図５の３つのツリーデータを入力の木構造データとして、ｍｉｎｓｕｐを２と設定して本実施の形態の動作を説明する。
これらのツリーデータ（ａ）、（ｂ）、（ｃ）は、ツリーデータ入力モジュール１１０を通じてツリーデータ保持モジュール１２０に格納される。
このとき、ツリーデータは、処理に適したものとするためにツリーデータ入力モジュール１１０によって加工される。加工の例を２つ（ＳＣＯＰＥ情報の付加、ＥＰａｔｈ情報の付加）示す。
その一つの例として、各ノードにＳＣＯＰＥ（スコープ）と呼ばれる子孫ノードの範囲を示す情報を付与してノードを格納する。例えば、（ａ）ｖ９には［９，１２］というデータがＳＣＯＰＥとして付与されて、ツリーデータ保持モジュール１２０に保持される。つまり、このＳＣＯＰＥ情報によって、（ａ）ｖ９は自分自身を除くと、（ａ）ｖ１０から（ａ）ｖ１２の子孫ノードを有していることがわかる。同様に（ｂ）ｖ０には［０，１３］という情報がＳＣＯＰＥとして付与されて、ツリーデータ保持モジュール１２０に保持される。
また、もう一つのＥＰａｔｈを用いて処理する実現方法では、各ノードにそのノードがのるＥＰａｔｈの情報と、ＥＰａｔｈ上でのそのノードの位置を示す情報を付与してノードを格納する。例えば、（ａ）ｖ０は、ＥＰ１，ＥＰ２，ＥＰ３，ＥＰ４，ＥＰ５にのっているので、＜１，５，０＞という情報が付与される。ここでの標記の例では＜＞内の最初の「１」と次の「５」は、ＥＰの番号の範囲（ＥＰ１からＥＰ５）を示しており、＜＞内の最後の「０」は、同じＥＰａｔｈの組にのるものの中での順番を示す。同様に（ｂ）ｖ３には＜１，４，２＞、（ｃ）ｖ６には＜３，５，０＞という情報が付与される。＜＞内の最後の数値は他にも、単純にＥＰａｔｈ上でのルートからの距離を用いてもよいし、ＥＰａｔｈの一つを共通とするものの中での順番を用いてもよく、同じＥＰａｔｈの組の間での順序関係が識別できればどの方法を用いてもよい。

パターン抽出モジュール１４０による処理が開始されると、まず頻出ラベルの列挙処理を行う（ステップＳ３０２）。この例では、ほとんどのラベルが頻出ラベルとなるが、３つのツリーデータ内で１回しか出現していない（ｃ）ｖ９の「スキャンＨ」のみが頻出ラベルとならない。各頻出ラベルにはその出現箇所の情報も保持される。例えば「承認Ｅ：（ａ）ｖ５，（ｂ）ｖ５，（ｃ）ｖ３」といった形の情報となる。

ここでは説明のために、頻出ラベルの選択を説明シナリオにそって恣意的に選択していく。実際には、頻出ラベルの選択は、本説明にしたがう必要はなく、他の順番で選択されるものであってもよい。
最初に頻出ラベルとして「作成」が選ばれたものとする（ステップＳ３０６）。したがって、最初の構造パターンは「作成Ａ」をラベルに持つノードのみからなるツリーとなる（図２１（ａ）に示すＰａｔ１参照）。このときの出現情報は、「（ａ）ｖ０，（ｂ）ｖ０，（ｃ）ｖ０」となる。以降、説明のためこれらの出現情報にｏｃｃｌｉｓｔＮの形で識別子をつける。ここでの出現情報「（ａ）ｖ０，（ｂ）ｖ０，（ｃ）ｖ０」はｏｃｃｌｉｓｔ０とする。つまり、ｏｃｃｌｉｓｔＮは、パターンにＮ＋１番目に追加したノードがツリーデータ上で出現する箇所となるノードの識別子の組を指し示す識別子である。

次に、このパターン情報と出現情報を保持して（ステップＳ３０８）、伸張パターンの探索処理（ステップＳ３１０）に移る。
このとき、出現情報を全て受け渡すのでなく、出現情報を保持しているデータ構造にアクセスできるだけの情報（例えば、そのデータ構造を指し示すポインタ）を渡すようにしてもよい。

最初に、パターンの出力を行う（ステップＳ４０２）。この場合、例えば「作成Ａ、サポート数３」といった情報を出力する。以降の説明では、伸張パターン探索を行うたびのパターン出力は省略して説明する。なお、パターンの出力は必ず最初に行わなければならない理由はなく、他のステップの後で行うことも可能である。
このときの伸張パスは、「作成Ａ」だけから構成されるので、未処理ノードとして「作成Ａ」を選択する（ステップＳ４０６）。
次に、パターンの伸張を行うノードの選定範囲を算出する（ステップＳ４０８）。「作成Ａ」のノードがパターンツリー上でリーフノードか否かを判定し、「作成Ａ」はリーフノードであるので、次のノードの選定範囲は「作成Ａ」の子孫ノード全てとなる。

ノードに付与されている情報をＳＣＯＰＥとしている実現例では、そのＳＣＯＰＥ情報から直接候補のノードを決定する。例えば（ａ）の場合には、「作成Ａ」の出現位置（ａ）ｖ０のＳＣＯＰＥ情報は［０，１３］であるので、ｖ０の位置を除いたｖ１，ｖ２，・・・，ｖ１３を選び、それらのノードのラベルである「修正Ｃ」、「閲覧Ｂ」などの集計を行う。この集計は、ツリーデータ１つでの出現を１として数えることができる。ＥＰａｔｈを用いた実現例では、（ａ）ｖ０の乗るＥＰ１，ＥＰ２，ＥＰ３，ＥＰ４,ＥＰ５から、（ａ）ｖ０よりも下位となるノードの範囲を算出することで同様にｖ１,ｖ２,・・・,ｖ１３を選び出すことができる。

図８は、このようにして選定範囲に入ったノードの範囲を点線で示した（ツリーデータ（ａ）の選定範囲８００ａ、ツリーデータ（ｂ）の選定範囲８００ｂ、ツリーデータ（ｃ）の選定範囲８００ｃ）図である。ここでの例ではこれらのノードのラベルのほとんどは、頻出ラベルとなる（「スキャンＨ」は集計後頻出ラベルとならない）。

次に、頻出ラベルの中から「修正Ｃ」を選んだ場合（ステップＳ４１６）を想定する。パターンは「作成Ａ」のラベルを持つノードと「修正Ｃ」のラベルを持つノードの２つのノードからなるツリーデータとなる（図２１（ｂ）に示すＰａｔ２参照）。この「修正Ｃ」の出現箇所は「（ａ）ｖ１，（ａ）ｖ３，（ａ）ｖ９，（ｂ）ｖ２，（ｂ）ｖ１２，（ｃ）ｖ１」（ｏｃｃｌｉｓｔ１）となる。このパターンと出現箇所の情報を設定等する準備を行い（ステップＳ４１６）、伸張パターン探索の処理（ステップＳ４１８）を起動する。

このときの伸張パスは、「作成Ａ」のラベルを持つノードと「修正Ｃ」のラベルを持つノードの２箇所である。
ここでは、「修正Ｃ」のラベルを持つノードからの伸張を説明する。
次に、パターンを伸張するためのノードの選定範囲を計算する。「修正Ｃ」のノードは、パターンツリー上ではリーフノードなので、「修正Ｃ」が出現したｏｃｃｌｉｓｔ１のノードの子孫ノードの存在範囲が算出すべき範囲である。ツリーデータ（ａ）、（ｂ）には複数の出現箇所があり、しかも、それらの間には上下の関係がある。このように上下関係がある出現箇所の情報は、より上位のものだけを選択するようにし、範囲を定める。つまり、子孫を探すときには、より上位の出現箇所だけを選んで範囲を決定する。この理由は、下位の出現箇所の子孫ノードは必ず上位の出現箇所の子孫ノードに含まれるため、下位の出現箇所に対する処理は冗長となるためである。このとき、上下の関係の有無の判定処理と、どちらが上位の情報であるかを判定する処理が必要となる。

上下関係の有無の判定処理は、ＳＣＯＰＥ情報を用いた処理では、子孫ノードの範囲の包含関係の有無で行える。ＥＰａｔｈを用いた処理では、共通のＥＰａｔｈを含むか否かで判定できる。
どちらが上位の情報であるかを判定する処理は、ＳＣＯＰＥ情報を付与していた場合には、子孫ノードの範囲の包含関係で判定できる。ＥＰａｔｈを用いた場合には、ＥＰａｔｈの包含関係で判定できる場合と、同じＥＰａｔｈの組にのっている場合に位置情報を用いて判定する場合がある。

このようにして、例えばツリーデータ（ａ）では（ａ）ｖ１の子孫全部の範囲を算出する。算出結果は、ＳＣＯＰＥ情報を用いた処理では、（ａ）ｖ２から（ａ）ｖ１２までのノードの範囲と示され、ＥＰａｔｈを用いた場合には、ＥＰ１，ＥＰ２，ＥＰ３，ＥＰ４にのりｖ１の位置より下位のノードとして示される。ツリーデータ（ｂ）ではｖ２の子孫とｖ１２の子孫が範囲となる。
このように示されたノードの範囲を図９に示す。これらの範囲（ツリーデータ（ａ）の選定範囲９００ａ、ツリーデータ（ｂ）の選定範囲９００ｂ、ツリーデータ（ｃ）の選定範囲９００ｃ）のノードのラベルについて集計を行い、頻出ラベルを選出する。この段階でも、ほとんどのラベルが頻出ラベルとなる。「スキャンＨ」は、また集計後に頻出でないと判定される。さらに、ここでは「スキャンＨ」に加えて「電子複写Ｆ」も頻出ラベルではなくなる。

ノードのラベルの集計を行う方法には、算出した範囲のノードのラベルをツリーデータを参照して集計する方法の他に、上位のノードの伸張候補を探す際に集計した頻出ノードの情報を用いるようにしてもよい。この方法を用いれば、「スキャンＨ」のように集計しても結局頻出にならないラベルの情報を何度も処理する必要がなくなる。この方法を実現するには、伸張パターン探索処理に起動をかけた側の伸張パターン探索処理における伸張候補選定モジュール２５０と通信ができるか、その集計結果にアクセスすることができるだけでよい。
また、予め定めた条件にしたがってツリーデータのノードを走査して集計する方法と上位のノードを処理した際のラベルの集計結果情報を利用する方法を切り替える制御を行うようにしてもよい。

未処理の頻出ラベルを選択する処理に移る。次に、頻出ラベルとして「確認Ｄ」を選択する。確認Ｄの出現情報は「（ａ）ｖ４，（ｂ）ｖ４，（ｃ）ｖ２」（ｏｃｃｌｉｓｔ２）である。そして、パターンは「作成Ａ」に子供ノードとして「修正Ｃ」をラベルに持つノードがつき、そのノードに「確認Ｄ」が子供についた３つのノードからなるツリーとなる（図２１（ｃ）に示すＰａｔ３参照）。

そして、ここで出現箇所情報準備の一工程として出現位置情報選別モジュール２７０により行われる出現情報の整理について、ｏｃｃｌｉｓｔ１の出現情報が整理される例を用いて示す。つまり、出現箇所のリストの整理に関するものである。
ｏｃｃｌｉｓｔ１の出現情報のうち、ｏｃｃｌｉｓｔ２の出現情報を子孫に持たない出現情報を除く。例えば、（ａ）ｖ３の子孫に（ａ）ｖ４が存在するが、（ａ）ｖ９の子孫には該当するものがない。このため、ｏｃｃｌｉｓｔ１から（ａ）ｖ９を除く。同様にして、（ｂ）ｖ１２も除かれるので、ｏｃｃｌｉｓｔ１は「（ａ）ｖ１，（ａ）ｖ３，（ｂ）ｖ２，（ｃ）ｖ１」となる。
このときの判定処理は、先祖−子孫の関係を判定する処理となるので、前述の上下関係の有無の判定とどちらが上位の情報であるかを判定する処理において、ＳＣＯＰＥ情報を用いた場合にもＥＰａｔｈを用いた場合にも実現することができる。

そして、再度伸張パターンの探索処理を起動する。
ここで起動した探索処理が終わると、ｏｃｃｌｉｓｔ１は出現位置情報回復モジュール２８０によりもとの状態に戻される。
起動された探索処理においては、このときも「確認Ｄ」の子孫ノードを候補とする処理となるので、前述の処理と同様になる。このときの次の候補の選定範囲を図１０に示す。つまり、ツリーデータ（ａ）は選定範囲１０００ａ、ツリーデータ（ｂ）は選定範囲１０００ｂ、ツリーデータ（ｃ）は選定範囲１０００ｃとなる。
そして、次の頻出ラベルに「承認Ｅ」を選んだ場合には、次の候補の選定範囲は図１１のようになる。つまり、ツリーデータ（ａ）は選定範囲１１００ａ、ツリーデータ（ｂ）は選定範囲１１００ｂ、ツリーデータ（ｃ）は選定範囲１１００ｃとなる。そして、パターンは図２１（ｄ）に示すＰａｔ４のようになる。

次に、「閲覧Ｂ」を選ぶ。このとき、「閲覧Ｂ」の出現位置は次のようになる。「（ａ）ｖ６，（ａ）ｖ７，（ｂ）ｖ６，（ｂ）ｖ７，（ｃ）ｖ４，（ｃ）ｖ５，（ｃ）ｖ７，（ｃ）ｖ８，（ｃ）ｖ１０」（ｏｃｃｌｉｓｔ４）となる。
このとき、パターンは「作成Ａ」、「修正Ｃ」、「確認Ｄ」、「承認Ｅ」、「閲覧Ｂ」をそれぞれラベルに持つノードが一列につながったツリーととる（図２１（ｅ）に示すＰａｔ５参照）。

次の伸張パターン探索処理では、この一列に連なったパスがＲＭＰとなる。ここで、「承認Ｅ」を伸張箇所として選択した場合の処理を説明する。
パターン上で「承認Ｅ」の子供ノード、「閲覧Ｂ」の兄弟ノードとなるラベルで頻出するものを探すことになる。
ここまでの範囲算出は、出現箇所の子孫ノードを表す範囲を算出していたが、ここでは「承認Ｅ」の出現箇所の子孫ノードで「閲覧Ｂ」の出現箇所と先祖子孫関係にならないものの存在する範囲を算出することになる。

まず、ＳＣＯＰＥ情報を用いた処理について説明する。上位の「承認Ｅ」の出現箇所について、もし包含関係（上下関係を以降でも包含関係とも呼ぶ）があれば最上位のものを選択する。ここでの例では「承認Ｅ」は各ツリーデータ上で一箇所ずつしか出現していないので、この選択は簡単である。
そして、下位の「閲覧Ｂ」については「承認Ｅ」の出現情報の子孫のうちで、最下位かつ兄弟間に順序がある場合には、その最も前のものを選択する。つまり、兄弟ノードを探すときに下側の出現箇所はより下位のものを選ぶようにする。例えば、最もノード番号の若いものを選び、そのノードのＳＣＯＰＥの範囲にある最も下位にあるノードを選ぶことを繰り返せば得られる。ツリーデータ（ｃ）の例では、「承認Ｅ」に対して（ｃ）ｖ３を、「閲覧Ｂ」に対しては（ｃ）ｖ４を選ぶことになる。（ｃ）ｖ３のスコープが［３，１０］であり、（ｃ）ｖ４のスコープが［４，４］であることから、下位のスコープの最大の値（４）＋１から、上位のスコープの最大の値（１０）までの範囲が算出される。すなわち、ｖ５、ｖ６、・・・ｖ１０が求めるノードの範囲となる。

ＥＰａｔｈ情報を用いた処理の場合には、上位と下位のノードを選ぶ条件までは同じであり、上位のノードについては、包含関係がある場合にはより上位のノードを選択し、下位のノードについてはよりＥＰａｔｈの小さいものを選択する。そして、上位のノードのＥＰａｔｈの範囲から下位のノードのＥＰａｔｈを差し引いた範囲が算出される。（ｃ）ｖ３のＥＰａｔｈの範囲は{ＥＰ１，ＥＰ２，ＥＰ３，ＥＰ４，ＥＰ５}であり、「閲覧Ｂ」の出現位置のＥＰａｔｈの範囲の最も小さいものは｛ＥＰ１｝であるので、この場合にはノードを調べるＥＰａｔｈの範囲は、ＥＰ２，ＥＰ３，ＥＰ４，ＥＰ５となり、これらのＥＰａｔｈのみにのるノードが求めるノードの範囲となる。こうして算出された範囲を図１２に示す。つまり、ツリーデータ（ａ）は選定範囲１２００ａ、ツリーデータ（ｂ）は選定範囲１２００ｂ、ツリーデータ（ｃ）は選定範囲１２００ｃとなる。

次に、「閲覧Ｂ」を頻出ラベルとして選択する（ここでは一つしかない）。
このとき、パターンは「作成Ａ」、「修正Ｃ」、「確認Ｄ」、「承認Ｅ」をそれぞれラベルに持つノードが一列につながり、「承認Ｅ」のラベルを持つノードに「閲覧Ｂ」をラベルに持つノードが２つつながったツリーとなる（図２１（ｆ）に示すＰａｔ６参照）。
また、このとき、ＲＭＰは、「閲覧Ｂ」をラベルに持つ２つのリーフノードの片方（通常はパターンの伸張方向を定めて処理するのでどちらかが決まる）とパターンのルートノード「作成Ａ」をつないだパスとなる。このＲＭＰが次の伸張パスとなる。

次に、このＲＭＰ上で「修正Ｃ」から伸張する場合を説明する。「修正Ｃ」を上位ノード、「確認Ｄ」を下位ノードとして前述と同様に算出した次の候補の範囲を図１３に示す。つまり、ツリーデータ（ａ）は選定範囲１３００ａ、ツリーデータ（ｂ）は選定範囲１３００ｂとなる。なお、ツリーデータ（ｃ）には該当するものがない。
「修正Ｃ」の出現箇所は、ツリーデータ（ａ）において２つ（（ａ）ｖ１と（ａ）ｖ３）あるが、上位ノードの出現位置をより上位の（ａ）ｖ１を選んで範囲計算を行わないと、図１３に示した範囲を算出することができず、パターンの抽出に失敗することになる。

次に、「印刷Ｇ」を選ぶと、パターンは図２１（ｇ）に示すＰａｔ７のようになり、そのときのＲＭＰは「作成Ａ」，「修正Ｃ」，「印刷Ｇ」を結ぶパスとなる。このとき、ツリーデータ（ｃ）は、対応する出現箇所がなくなり、処理対象から外れる。
次の伸張箇所の候補名「作成Ａ」、「修正Ｃ」、「印刷Ｇ」の３箇所となるが、ここでは「印刷Ｇ」が選ばれた場合の説明を続ける。このときの次の候補選定範囲は図１４に示した範囲となる。この中で「閲覧Ｂ」は頻出ラベルとなる。

この「閲覧Ｂ」を「印刷Ｇ」に接続したパターンは図２１（ｈ）に示すｐａｔ８となる。次に、ＲＭＰの中から伸張箇所にもう一度「印刷Ｇ」を選択すると、次の候補の範囲は図１５のようになる。つまり、ツリーデータ（ａ）は選定範囲１５００ａ、ツリーデータ（ｂ）は選定範囲１５００ｂとなる。そして、このときの頻出ラベルは再度「閲覧Ｂ」となる。

次のパターンは、図２１（ｉ）に示すｐａｔ９になる。
このパターンは、例えば、作成されて修正され、確認されて承認されたドキュメントを閲覧している人たちがいて、一方で、確認前のドキュメントを印刷して閲覧している人が複数人いるという形の、確認前のドキュメントが印刷されて閲覧されている（配布されているのかもしれない）という点で、場面によっては問題が生じるかもしれないパターンと解釈できる。
このパターンが抽出された後は、ＲＭＰの伸張箇所として作成Ａを選んだ場合の伸張パターンが抽出できる。
このときの候補の範囲は図１６のようになる。つまり、ツリーデータ（ａ）は選定範囲１６００ａ、ツリーデータ（ｂ）は選定範囲１６００ｂとなる。ここでは、「閲覧Ｂ」が頻出ラベルとなり、この頻出ラベルを加えることで図２１（ｊ）に示すｐａｔ１０のパターンが抽出される。

この後は、ＲＭＰから頻出ラベルが見つからなくなるため、再帰的に起動された伸張パターン探索処理を次々と呼び出し元に制御を戻す。
そして、図２１（ｆ）に示すＰａｔ６のパターンのＲＭＰを処理していたところまで戻り、伸張箇所の選択で「作成Ａ」が選ばれた場合を続けて説明する。
この場合、上位ノード「作成Ａ」はなるべく上側のノードを選び（各ツリーデータ上でひとつずつしかない）、下位ノード「修正Ｃ」はなるべく左側の下側のものを選択する。ツリーデータ（ａ）では、このときの「修正Ｃ」の出現箇所は（ａ）ｖ１と（ａ）ｖ３であり、下側の（ａ）ｖ３を選んで範囲の算出を行う。その結果、図１７に示す範囲が算出される。つまり、ツリーデータ（ａ）は選定範囲１７００ａ、ツリーデータ（ｂ）は選定範囲１７００ｂとなる。このとき、ツリーデータ（ａ）には「修正Ｃ」の出現箇所はもう一つ（ａ）ｖ９があるが、これはパターンのＲＭＰ上の「修正Ｃ」の出現箇所に入っていないので範囲計算には影響を及ぼさない。このとき、仮にツリーデータ（ａ）において下位ノード「修正Ｃ」の出現箇所として（ａ）を用いて範囲の算出を行うと１７００ａの範囲のノードのラベルを調べることができず以降のパターンが抽出されなくなってしまう。このため範囲の算出時に下位ノードの出現位置の選択を正しく行うことは重要である。

以降、同様に頻出ラベルを候補から選んでパターンを作成し、パターンの伸張箇所を選択して範囲計算を行うことを繰り返した例を図１７、図１８、図１９、図２０に示す。つまり、図１７に示すツリーデータ（ａ）では選定範囲１７００ａ、ツリーデータ（ｂ）は選定範囲１７００ｂが対象となり「電子複写Ｆ」を頻出ラベルとして選びパターンを伸張する。そして、処理が１段進むと、図１８に示すツリーデータ（ａ）では選定範囲１８００ａ、ツリーデータ（ｂ）は選定範囲１８００ｂとなり頻出ラベルとして「修正Ｃ」を選びパターンを伸張する。さらに処理が１段進むと、図１９に示すツリーデータ（ａ）では選定範囲１９００ａ、ツリーデータ（ｂ）は選定範囲１９００ｂとなり頻出ラベルとして「閲覧Ｂ」を選びパターンを伸張する。そして、図２０に示すツリーデータ（ａ）では選定範囲２０００ａとなるが、頻出ラベルはみつからなくなる。
このときに抽出されるパターンの例は、図１７から図２０までに示すツリーデータの処理結果に合わせて、それぞれ図２２（ｂ）に示すｐａｔ７ｂ、（ｃ）に示すｐａｔ８ｂ、（ｄ）に示すｐａｔ９ｂ、（ｅ）に示すｐａｔ１０ｂとなる。なお、ｐａｔ１０ｂは、ドキュメントが作成されて修正、確認、承認、閲覧と進むパスの他に、修正後電子的に複写されて別途修正された後で誰かが閲覧している操作の流れが繰り返し起きていることを示している。

また、出現位置情報保持モジュール２６０が探索済み範囲の情報を保持する機構について説明する。例えば、図５に示したツリーデータ（ａ）を取り上げて説明する。
「修正Ｃ」のラベルを持つノードをルートノードとしたとき、出現情報はｖ１，ｖ３，ｖ９となる。
次に「修正Ｃ」のラベルを持つノードに、「閲覧Ｂ」のラベルを持つノードが一つ子供に加わったパターンを対象としたとする。このとき、子供側の「閲覧Ｂ」の出現情報は、ｖ２、ｖ６、ｖ７、ｖ１１、ｖ１２となる。
そして、「修正Ｃ」のラベルを持つノードにもう一つ「閲覧Ｂ」のラベルを持つノードを子供に加えたパターン（「修正Ｃ」の子供ノードとして「閲覧Ｂ」が２つ接続されたパターン）を探す場合を想定する。
この処理は、兄弟ノードの探索となるので、上位側の出現情報として一番上位のｖ１、下位側の出現情報には一番左側かつ一番下位の出現情報ｖ６が選択されて、次の候補を判定する範囲情報が決定される。
このときに２番目の閲覧Ｂの候補となるのはｖ７，ｖ１１，ｖ１２となる。

そして、２番目の閲覧Ｂの出現箇所と修正Ｃの出現箇所の対応が計算される。
それぞれの出現情報のもつ出現箇所や範囲だけでは、「修正Ｃ」の出現箇所と２つめの「閲覧Ｂ」の出現箇所の対応関係を更新するとき、ｖ１に対してはｖ７、ｖ１１、ｖ１２が、ｖ３に対してはｖ７が対応するものとして判定できるが、ｖ９の「修正Ｃ」に対してはｖ１１、ｖ１２の両方ともがｖ９の子孫であるため、パターン上で「修正Ｃ」の子供ノードの２番目の「閲覧Ｂ」の出現箇所としてｖ１１とｖ１２とも選択されてしまう。
これに対して、それぞれの出現情報に対して処理済の範囲情報、例えば「修正Ｃ」の子供ノードとして処理が済んだ範囲を探索済み範囲情報として保持することで、より精密な処理を実現することができる。
ここでの例では、「修正Ｃ」の処理済の子供ノード（一番目の「閲覧Ｂ」）の範囲情報として、ｖ１にはＥＰ１、ｖ３にはＥＰ１、ｖ９にはＥＰ３の情報を対応付けて保持しておき、２番目の「閲覧Ｂ」の出現情報を対応付けるときに、この情報を参照して判定することができる。
これにより、ｖ９の子孫の範囲にはｖ１１、ｖ１２も入るが、ｖ１１は処理済のＥＰ３に含まれるため、２番目の「閲覧Ｂ」の出現箇所はｖ９に対してｖ１２のみを選ぶというように精密に対応付けを行うことができる。

本実施の形態では、従来の技術が行っていた出現箇所の組み合わせの保存を行わないため、パターンの大きさ（ノード数）が大きくなっても、メモリ使用量が爆発的に増えることがおきない。また、従来の技術がＲＭＰからの伸張候補をまとめて扱っていたのに対して、本実施の形態では、それらを伸張箇所ごとに細かく制御してパターンの探索を行うので、伸張パターン探索の起動ごとのメモリ消費量が抑えられ、処理の効率もよい。

なお、本実施の形態としてのプログラムが実行されるコンピュータのハードウェア構成は、図２３に例示するように、一般的なコンピュータであり、具体的にはパーソナルコンピュータ、サーバーとなり得るコンピュータ等である。制御モジュール１３０、パターン抽出モジュール１４０等のプログラムを実行するＣＰＵ２３０１（この例では演算部としてＣＰＵを用いた）と、そのプログラムやデータを記憶するＲＡＭ２３０２と、本コンピュータを起動するためのプログラム等が格納されているＲＯＭ２３０３と、補助記憶装置であるＨＤ２３０４（例えばハードディスクを用いることができる）と、キーボード、マウス等のデータを入力する入力装置２３０６と、ＣＲＴや液晶ディスプレイ等の出力装置２３０５と、通信ネットワークと接続するための通信回線インタフェース２３０７（例えばネットワークインタフェースカードを用いることができる）、そして、それらをつないでデータのやりとりをするためのバス２３０８により構成されている。これらのコンピュータが複数台互いにネットワークによって接続されていてもよい。

前述の実施の形態のうち、コンピュータ・プログラムによるものについては、本ハードウェア構成のシステムにソフトウェアであるコンピュータ・プログラムを読み込ませ、ソフトウェアとハードウェア資源とが協働して、前述の実施の形態が実現される。
なお、図２３に示すハードウェア構成は、１つの構成例を示すものであり、本実施の形態は、図２３に示す構成に限らず、本実施の形態において説明したモジュールを実行可能な構成であればよい。例えば、一部のモジュールを専用のハードウェア（例えばＡＳＩＣ等）で構成してもよく、一部のモジュールは外部のシステム内にあり通信回線で接続しているような形態でもよく、さらに図２３に示すシステムが複数互いに通信回線によって接続されていて互いに協調動作するようにしてもよい。また、特に、パーソナルコンピュータの他、情報家電、複写機、ファックス、スキャナ、プリンタ、複合機（スキャナ、プリンタ、複写機、ファックス等のいずれか２つ以上の機能を有している画像処理装置）などに組み込まれていてもよい。

なお、本実施の形態で示した例では、ＥｐＲａｎｇｅが同じ出現情報も皆同等に扱ったが、ＥｐＲａｎｇｅ（つまり、分岐がない範囲）が同じ出現情報は一つ（つまり、最上位と最下位のノード）を代表として扱って処理しても全く同等の効果が得られ、記憶しておく出現情報の量が減る分必要な記憶容量が削減され、さらに、検査などの処理のコストも削減される。つまり、木構造内で分岐のない範囲の最上位及び最下位以外の出現箇所を出現位置情報保持モジュール２６０から削除するようにしてもよい。あるいは、出現位置情報保持モジュール２６０に格納する前に選別してもよい、さらには、ツリーデータ保持１２０に格納する時点でこの選別を行ってもよい。

前記実施の形態においては、対象とするツリーデータとして、ドキュメントの操作履歴のデータを示したが、他の木構造であるデータを対象としてもよい。例えば、順序関係のある商品購入、ドキュメントの構造、遺伝子の配列、遺伝子の二次構造、たんぱく質の構造、画像や映像の特徴情報の構造、人の行動履歴構造、テキストデータの解析結果の構造、オントロジーなどの知識体系、ＸＭＬ等のツリー形式で構造化された情報等であってもよい。

なお、説明したプログラムについては、記録媒体に格納して提供してもよく、また、そのプログラムを通信手段によって提供してもよい。その場合、例えば、前記説明したプログラムについて、「プログラムを記録したコンピュータ読み取り可能な記録媒体」の発明として捉えてもよい。
「プログラムを記録したコンピュータ読み取り可能な記録媒体」とは、プログラムのインストール、実行、プログラムの流通などのために用いられる、プログラムが記録されたコンピュータで読み取り可能な記録媒体をいう。
なお、記録媒体としては、例えば、デジタル・バーサタイル・ディスク（ＤＶＤ）であって、ＤＶＤフォーラムで策定された規格である「ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ−ＲＡＭ等」、ＤＶＤ＋ＲＷで策定された規格である「ＤＶＤ＋Ｒ、ＤＶＤ＋ＲＷ等」、コンパクトディスク（ＣＤ）であって、読出し専用メモリ（ＣＤ−ＲＯＭ）、ＣＤレコーダブル（ＣＤ−Ｒ）、ＣＤリライタブル（ＣＤ−ＲＷ）等、光磁気ディスク（ＭＯ）、フレキシブルディスク（ＦＤ）、磁気テープ、ハードディスク、読出し専用メモリ（ＲＯＭ）、電気的消去及び書換可能な読出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュ・メモリ、ランダム・アクセス・メモリ（ＲＡＭ）等が含まれる。
そして、前記のプログラム又はその一部は、前記記録媒体に記録して保存や流通等させてもよい。また、通信によって、例えば、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、イントラネット、エクストラネット等に用いられる有線ネットワーク、あるいは無線通信ネットワーク、さらにこれらの組み合わせ等の伝送媒体を用いて伝送させてもよく、また、搬送波に乗せて搬送させてもよい。
さらに、前記のプログラムは、他のプログラムの一部分であってもよく、あるいは別個のプログラムと共に記録媒体に記録されていてもよい。また、複数の記録媒体に分割して
記録されていてもよい。また、圧縮や暗号化など、復元可能であればどのような態様で記録されていてもよい。

本実施の形態の構成例についての概念的なモジュール構成図である。 本実施の形態のパターン抽出モジュール内の構成例についての概念的なモジュール構成図である。 本実施の形態による処理例を示すフローチャートである。 本実施の形態による伸張パターンの探索処理例を示すフローチャートである。 本実施の形態による処理対象であるツリーデータの例を示す説明図である。 ツリーデータに番号情報を付加した例を示す説明図である。 ツリーデータ内のＥＰａｔｈの例を示した説明図である。 ツリーデータに対する処理途中の選定範囲の例を示した説明図である。 ツリーデータに対する処理途中の選定範囲の例を示した説明図である。 ツリーデータに対する処理途中の選定範囲の例を示した説明図である。 ツリーデータに対する処理途中の選定範囲の例を示した説明図である。 ツリーデータに対する処理途中の選定範囲の例を示した説明図である。 ツリーデータに対する処理途中の選定範囲の例を示した説明図である。 ツリーデータに対する処理途中の選定範囲の例を示した説明図である。 ツリーデータに対する処理途中の選定範囲の例を示した説明図である。 ツリーデータに対する処理途中の選定範囲の例を示した説明図である。 ツリーデータに対する処理途中の選定範囲の例を示した説明図である。 ツリーデータに対する処理途中の選定範囲の例を示した説明図である。 ツリーデータに対する処理途中の選定範囲の例を示した説明図である。 ツリーデータに対する処理途中の選定範囲の例を示した説明図である。 本実施の形態によるパターンの生成過程の例を示す説明図である。 本実施の形態によるパターンの生成過程の例を示す説明図である。 本実施の形態を実現するコンピュータのハードウェア構成例を示すブロック図である。

符号の説明

１１０…ツリーデータ入力モジュール
１２０…ツリーデータ保持モジュール
１３０…制御モジュール
１４０…パターン抽出モジュール
１５０…パターン情報出力モジュール
２１０…伸張元パターン情報受付モジュール
２２０…パターン出力モジュール
２３０…パターン伸張点選択モジュール
２４０…伸張候補選定基準算出モジュール
２５０…伸張候補選定モジュール
２６０…出現位置情報保持モジュール
２７０…出現位置情報選別モジュール
２８０…出現位置情報回復モジュール
２９０…パターン伸張モジュール
２９５…パターン伸張起動モジュール

Claims (12)

1. 木構造内のノード毎に子孫ノードの範囲を示す情報を付与してノードを記憶手段に格納する格納手段と、
   複数の木構造内で複数回現れる構造パターンの探索を、前記木構造の所定の範囲内にあるノードに対して行うことによって、該構造パターンを抽出する構造パターン抽出手段と、
   前記木構造内におけるノードの出現箇所に関する情報である出現情報ごとに、既に前記構造パターン抽出手段によって抽出された構造パターンで子供ノードがあったノードの出現情報にそれぞれの既出の子供ノードの出現情報の少なくとも一部を対応付けて記憶する記憶手段
   を具備し、
   前記構造パターン抽出手段は、ノード間の上下関係の有無を、前記格納手段によって格納されたノードの子孫ノードの範囲を示す情報の包含関係の有無によって判定し、前記記憶手段に記憶された出現情報に基づいて、前記構造パターン内で複数回出現したラベルの分岐毎に前記所定の範囲を定め、該所定の範囲内での該ラベルによって構成された構造パターンを抽出し、該抽出処理を再帰的に繰り返すことによって、複数の木構造内で複数回現れる構造パターンを探索する
   ことを特徴とする情報処理装置。
2. 木構造内のノード毎にルートノードからリーフノードまでに至る経路情報を記憶手段に格納する格納手段と、
   複数の木構造内で複数回現れる構造パターンの探索を、前記木構造の所定の範囲内にあるノードに対して行うことによって、該構造パターンを抽出する構造パターン抽出手段と、
   前記木構造内におけるノードの出現箇所に関する情報である出現情報ごとに、既に前記構造パターン抽出手段によって抽出された構造パターンで子供ノードがあったノードの出現情報にそれぞれの既出の子供ノードの出現情報の少なくとも一部を対応付けて記憶する記憶手段
   を具備し、
   前記構造パターン抽出手段は、ノード間の上下関係の有無を、該ノード間において前記格納手段によって格納されたノードの経路情報が共通のものを含むか否かによって判定し、前記記憶手段に記憶された出現情報に基づいて、前記構造パターン内で複数回出現したラベルの分岐毎に前記所定の範囲を定め、該所定の範囲内での該ラベルによって構成された構造パターンを抽出し、該抽出処理を再帰的に繰り返すことによって、複数の木構造内で複数回現れる構造パターンを探索する
   ことを特徴とする情報処理装置。
3. 前記構造パターン抽出手段は、ノードに対応するラベルの出現回数に応じて選択されたラベルを用いて、前記構造パターンを抽出する
   ことを特徴とする請求項１又は２に記載の情報処理装置。
4. 前記構造パターン抽出手段は、前記木構造の所定の範囲内のノードを探索することによって、前記構造パターンを抽出する
   ことを特徴とする請求項１又は２に記載の情報処理装置。
5. 前記木構造のデータ構造に基づいて、請求項３又は請求項４に記載の構造パターン抽出手段による構造パターンの抽出のいずれかを選択する選択手段
   をさらに具備することを特徴とする請求項１又は２に記載の情報処理装置。
6. 前記構造パターン内の現在の処理対象である現処理対象となっているノードと一致する前記木構造内でのノードのうち上下関係のあるものについては最上位のノードに基づいて、子孫を探索する範囲を決定する第１の探索範囲決定手段
   をさらに具備し、
   前記構造パターン抽出手段は、前記第１の探索範囲決定手段によって決定された範囲に基づいて探索を行う
   ことを特徴とする請求項１又は２に記載の情報処理装置。
7. 前記構造パターン内での親ノードと一致する前記木構造内でのノードのうち上下関係のあるものについては最上位のノード及び前記構造パターン内での子供ノードと一致する前記木構造内でのノードに上下関係のあるものについては最下位のノードに基づいて、探索範囲を決定する第２の探索範囲決定手段
   をさらに具備し、
   前記構造パターン抽出手段は、前記第２の探索範囲決定手段によって決定された範囲に基づいて探索を行う
   ことを特徴とする請求項１又は２に記載の情報処理装置。
8. 前記構造パターン内の現在の処理対象となっているノードの先祖のノードの出現箇所の中から、該現在の処理対象となっているノードの出現箇所のノードを子孫に含むノードに対応する出現箇所を保持する保持手段
   をさらに具備することを特徴とする請求項７に記載の情報処理装置。
9. 前記木構造内で分岐のない範囲の最上位及び最下位以外の出現箇所を前記保持手段から削除する削除手段
   をさらに具備することを特徴とする請求項８に記載の情報処理装置。
10. 前記保持手段に保持させる出現箇所を対象とし、前記木構造内で分岐のない範囲の最上位及び最下位以外の出現箇所以外を削除したものを選別する選別手段
    をさらに具備することを特徴とする請求項８に記載の情報処理装置。
11. コンピュータを、
    木構造内のノード毎に子孫ノードの範囲を示す情報を付与してノードを記憶手段に格納する格納手段と、
    複数の木構造内で複数回現れる構造パターンの探索を、前記木構造の所定の範囲内にあるノードに対して行うことによって、該構造パターンを抽出する構造パターン抽出手段と、
    前記木構造内におけるノードの出現箇所に関する情報である出現情報ごとに、既に前記構造パターン抽出手段によって抽出された構造パターンで子供ノードがあったノードの出現情報にそれぞれの既出の子供ノードの出現情報の少なくとも一部を対応付けて記憶する記憶手段
    として機能させ、
    前記構造パターン抽出手段は、ノード間の上下関係の有無を、前記格納手段によって格納されたノードの子孫ノードの範囲を示す情報の包含関係の有無によって判定し、前記記憶手段に記憶された出現情報に基づいて、前記構造パターン内で複数回出現したラベルの分岐毎に前記所定の範囲を定め、該所定の範囲内での該ラベルによって構成された構造パターンを抽出し、該抽出処理を再帰的に繰り返すことによって、複数の木構造内で複数回現れる構造パターンを探索する
    ことを特徴とする情報処理プログラム。
12. コンピュータを、
    木構造内のノード毎にルートノードからリーフノードまでに至る経路情報を記憶手段に格納する格納手段と、
    複数の木構造内で複数回現れる構造パターンの探索を、前記木構造の所定の範囲内にあるノードに対して行うことによって、該構造パターンを抽出する構造パターン抽出手段と、
    前記木構造内におけるノードの出現箇所に関する情報である出現情報ごとに、既に前記構造パターン抽出手段によって抽出された構造パターンで子供ノードがあったノードの出現情報にそれぞれの既出の子供ノードの出現情報の少なくとも一部を対応付けて記憶する記憶手段
    として機能させ、
    前記構造パターン抽出手段は、ノード間の上下関係の有無を、該ノード間において前記格納手段によって格納されたノードの経路情報が共通のものを含むか否かによって判定し、前記記憶手段に記憶された出現情報に基づいて、前記構造パターン内で複数回出現したラベルの分岐毎に前記所定の範囲を定め、該所定の範囲内での該ラベルによって構成された構造パターンを抽出し、該抽出処理を再帰的に繰り返すことによって、複数の木構造内で複数回現れる構造パターンを探索する
    ことを特徴とする情報処理プログラム。

Images