(57)【特許請求の範囲】
【請求項１】
複数の木構造内で複数回現れる一次パターンを抽出する一次パターン抽出手段と、
前記一次パターン抽出手段によって抽出された一次パターンに該一次パターンの出現数を表す符号を付加する符号付加手段と、
前記符号付加手段によって符号が付加された一次パターンから二次パターンを抽出する二次パターン抽出手段と、
前記一次パターンと前記二次パターンを比較して、前記複数の木構造内で複数回現れるパターンのうち、二次パターンに現れない一次パターンを選択する選択手段
を具備することを特徴とする情報処理装置。
【請求項２】
複数の木構造内で複数回現れる一次パターンを抽出する一次パターン抽出手段と、
前記一次パターン抽出手段によって抽出された一次パターンを該一次パターンの出現数毎に分類する分類手段と、
前記分類手段によって分類された一次パターンから二次パターンを抽出する二次パターン抽出手段と、
前記二次パターン抽出手段による二次パターンの抽出処理過程で、前記複数の木構造内で複数回現れるパターンのうち、二次パターンに現れない一次パターンを選択する選択手段
を具備することを特徴とする情報処理装置。
【請求項３】
前記一次パターン抽出手段は、対象としているノードよりも下位にあるパターンの出現数を用いてパターンを抽出する
ことを特徴とする請求項１又は２に記載の情報処理装置。
【請求項４】
前記一次パターン抽出手段は、対象としているノードよりも下位であるパターンの出現数に基づいて、該パターンの抽出を継続する
ことを特徴とする請求項１から３のいずれか一項に記載の情報処理装置。
【請求項５】
前記選択手段は、前記二次パターン抽出手段によって抽出されなかった前記一次パターンを選択する
ことを特徴とする請求項１、３、４のいずれか一項に記載の情報処理装置。
【請求項６】
前記選択手段は、前記二次パターン抽出手段による抽出のときに抽出されなかった前記一次パターンを選択する
ことを特徴とする請求項２から４のいずれか一項に記載の情報処理装置。
【請求項７】
前記符号付加手段は、前記一次パターンの順序を前記二次パターン抽出手段によって抽出される順序に揃える
ことを特徴とする請求項１から６のいずれか一項に記載の情報処理装置。
【請求項８】
前記一次パターン抽出手段と前記二次パターン抽出手段の抽出の順序を揃える
ことを特徴とする請求項１から６のいずれか一項に記載の情報処理装置。
【請求項９】
コンピュータを、
複数の木構造内で複数回現れる一次パターンを抽出する一次パターン抽出手段と、
前記一次パターン抽出手段によって抽出された一次パターンに該一次パターンの出現数を表す符号を付加する符号付加手段と、
前記符号付加手段によって符号が付加された一次パターンから二次パターンを抽出する二次パターン抽出手段と、
前記一次パターンと前記二次パターンを比較して、前記複数の木構造内で複数回現れるパターンのうち、二次パターンに現れない一次パターンを選択する選択手段
として機能させることを特徴とする情報処理プログラム。
【請求項１０】
コンピュータを、
複数の木構造内で複数回現れる一次パターンを抽出する一次パターン抽出手段と、
前記一次パターン抽出手段によって抽出された一次パターンを該一次パターンの出現数毎に分類する分類手段と、
前記分類手段によって分類された一次パターンから二次パターンを抽出する二次パターン抽出手段と、
前記二次パターン抽出手段による二次パターンの抽出処理過程で、前記複数の木構造内で複数回現れるパターンのうち、二次パターンに現れない一次パターンを選択する選択手段
として機能させることを特徴とする情報処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置及び情報処理プログラムに関する。
【背景技術】
【０００２】
コンピュータの処理能力、記憶装置の容量の飛躍的な増大に加え、ＩＴ化やネットワーク化が進んだことで大量な情報が容易に集められるようになってきた。集めた情報から市場機会やリスクに関する情報を早期に発見したり、隠れた知識を発見したりすることへの期待が高まっている。
しかし、集めた情報の量はしばしば人間の処理能力をはるかに超えるものとなる。このため、せっかく大量に集めた情報からリスクを発見したり、知識を抽出したりして活用することは実際には労力を伴う難しいものであった。
【０００３】
一方、パターン・マイニング等の技術の進展により、そのような大量の情報の中から例えば同時に購入される商品のパターンなどの情報が抽出可能となってきた。同時に購入される品物のパターンや購入される順序のパターンを抽出する技術が顧客の購買行動の分析などの需要から注目を集めて研究開発されてきたが、最近ではさまざまな情報の構造化、半構造化が進んできたこともあり、木構造のような構造を持つパターンを抽出するパターン・マイニングの技術が注目されてきている。構造情報を抽出するパターン・マイニングの技術の中でも、特に木構造はＸＭＬ（ｅＸｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）をはじめとしてドキュメントの構造化や知識表現などさまざまな情報の構造化に用いられるためパターン抽出への期待も大きい。
【０００４】
木構造のデータ群から部分木のパターンを抽出する技術には大きく分けて、親子関係が厳密に一致する構造だけを抽出するｉｎｄｕｃｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇの技術と、親子関係が多少乱れても先祖―子孫の関係があれば構造を抽出するｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇの技術がある。
現実社会で発生するデータ、例えば電子文書であるドキュメントの操作履歴などのように人の操作を記録したものでは、たとえ同じ内容の作業を行っても、作業者の操作順などが厳密には一致しないため操作の履歴データの親子関係が厳密に一致することは期待できない。このため、そのようなデータからパターンを抽出するためには、親子関係に揺れが生じたとしてもパターンが抽出できるｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇの技術を適用することが望ましい。また、人の操作の記録だけではなく、情報を整理した木構造データのようなものからも埋め込まれている隠れた構造を抽出するためには同様にｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇを用いる必要がある。
ｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇを実現する従来の技術としては、ＴｒｅｅＭｉｎｅｒ、Ｄｒｙａｄｅ、ＭＢ３−ｍｉｎｅｒ、ＴＲＩＰＳなどを挙げることができる。
【０００５】
これらに関連する技術として、例えば、特許文献１には、データの集合からその中に含まれる重要なパターンを検出する方法及びシステムを提供することを課題とし、木構造データで表されたデータ集合を含むデータベースから、集計対象となる候補パターンを用いて、頻出パターンを検出するシステムであって、（１）データベースから候補パターンにマッチするパターンを集計する手段と、（２）前記集計により出現頻度の高いパターンを検出する手段と、（３）前記検出したパターンから、次の集計対象となる候補パターンを生成する手段と、を有するように構成することが開示されている。
【０００６】
また、例えば、特許文献２には、順序木において頻出するパターンを抽出するのに好適な抽出装置等を提供することを課題とし、抽出装置の入力受付部は、１つ以上の順序木の入力を受け付け、変換部は、入力が受け付けられた順序木のそれぞれを系列表現へ変換し、抽出部は、変換された系列表現のそれぞれが含むパターンのうち、所定の頻度以上で出現するパターンを抽出し、系列表現は、順序木を深さ優先探索して、枝を進む際に通過する節はその名前を表すマークを、枝を戻る際はバックトラックマークを、それぞれ並べることによりでき、パターンは、系列表現であるマークの列中の名前を表すマークのいずれかを最初のマークとして、これから射影を０回以上繰り返したときに、最初のマークから最後のマークに至るまでに出会うマークの列をいい、射影が成立するか否かは、マークの列の列文脈と、射影文脈の値により判定することが開示されている。
【特許文献１】特開２００１−１３４５７５号公報
【特許文献２】特開２００４−３５５４５７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、ｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇは、ｉｎｄｕｃｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇよりもパターンの抽出能力が高い反面、抽出結果のパターンが大量になるという問題があった。これら従来技術のうち、Ｄｒｙａｄｅは、出現数の同じ場合にはより大きなパターンを出力するというｃｌｏｓｅｄ  ｐａｔｔｅｒｎ（クローズドパターン）の抽出を実現するが、兄弟ノードに同じものを含めないという機能制限がある。また、そのような場面が頻出するドキュメントの操作履歴などの多くの現実のデータのマイニングには適さなかった。なお、ｃｌｏｓｅｄ  ｐａｔｔｅｒｎ  ｍｉｎｉｎｇでは、同じ出現数のパターンの中で小さくないものを抽出するが、この抽出されるパターンがｃｌｏｓｅｄ  ｐａｔｔｅｒｎである。また、極端な例として、ノード一つだけからなるパターンであっても、同じラベルのノードを持つパターンがなければ、ｃｌｏｓｅｄ  ｐａｔｔｅｒｎとなり得る。
【０００８】
ｃｌｏｓｅｄ  ｐａｔｔｅｒｎ又はＭａｘｉｍａｌ  ｐａｔｔｅｒｎ（マクシマルパターン）の抽出は、所定の情報量を落とさずに出力パターン数を削減することができるため、抽出したパターンを利用するうえで重要である。本発明は、ｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇにおいて、ｃｌｏｓｅｄ  ｐａｔｔｅｒｎ又はＭａｘｉｍａｌ  ｐａｔｔｅｒｎを出力するようにした情報処理装置及び情報処理プログラムを提供することを目的としている。
【課題を解決するための手段】
【０００９】
かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
請求項１の発明は、複数の木構造内で複数回現れる一次パターンを抽出する一次パターン抽出手段と、前記一次パターン抽出手段によって抽出された一次パターンに該一次パターンの出現数を表す符号を付加する符号付加手段と、前記符号付加手段によって符号が付加された一次パターンから二次パターンを抽出する二次パターン抽出手段と、前記一次パターンと前記二次パターンを比較して、前記複数の木構造内で複数回現れるパターンのうち、二次パターンに現れない一次パターンを選択する選択手段を具備することを特徴とする情報処理装置である。
【００１０】
請求項２の発明は、複数の木構造内で複数回現れる一次パターンを抽出する一次パターン抽出手段と、前記一次パターン抽出手段によって抽出された一次パターンを該一次パターンの出現数毎に分類する分類手段と、前記分類手段によって分類された一次パターンから二次パターンを抽出する二次パターン抽出手段と、前記二次パターン抽出手段による二次パターンの抽出処理過程で、前記複数の木構造内で複数回現れるパターンのうち、二次パターンに現れない一次パターンを選択する選択手段を具備することを特徴とする情報処理装置である。
【００１１】
請求項３の発明は、前記一次パターン抽出手段は、対象としているノードよりも下位にあるパターンの出現数を用いてパターンを抽出することを特徴とする請求項１又は２に記載の情報処理装置である。
【００１２】
請求項４の発明は、前記一次パターン抽出手段は、対象としているノードよりも下位であるパターンの出現数に基づいて、該パターンの抽出を継続することを特徴とする請求項１から３のいずれか一項に記載の情報処理装置である。
【００１３】
請求項５の発明は、前記選択手段は、前記二次パターン抽出手段によって抽出されなかった前記一次パターンを選択することを特徴とする請求項１、３、４のいずれか一項に記載の情報処理装置である。
【００１４】
請求項６の発明は、前記選択手段は、前記二次パターン抽出手段による抽出のときに抽出されなかった前記一次パターンを選択することを特徴とする請求項２から４のいずれか一項に記載の情報処理装置である。
【００１５】
請求項７の発明は、前記符号付加手段は、前記一次パターンの順序を前記二次パターン抽出手段によって抽出される順序に揃えることを特徴とする請求項１から６のいずれか一項に記載の情報処理装置である。
【００１６】
請求項８の発明は、前記一次パターン抽出手段と前記二次パターン抽出手段の抽出の順序を揃えることを特徴とする請求項１から６のいずれか一項に記載の情報処理装置である。
【００１７】
請求項９の発明は、コンピュータを、複数の木構造内で複数回現れる一次パターンを抽出する一次パターン抽出手段と、前記一次パターン抽出手段によって抽出された一次パターンに該一次パターンの出現数を表す符号を付加する符号付加手段と、前記符号付加手段によって符号が付加された一次パターンから二次パターンを抽出する二次パターン抽出手段と、前記一次パターンと前記二次パターンを比較して、前記複数の木構造内で複数回現れるパターンのうち、二次パターンに現れない一次パターンを選択する選択手段として機能させることを特徴とする情報処理プログラムである。
【００１８】
請求項１０の発明は、コンピュータを、複数の木構造内で複数回現れる一次パターンを抽出する一次パターン抽出手段と、前記一次パターン抽出手段によって抽出された一次パターンを該一次パターンの出現数毎に分類する分類手段と、前記分類手段によって分類された一次パターンから二次パターンを抽出する二次パターン抽出手段と、前記二次パターン抽出手段による二次パターンの抽出処理過程で、前記複数の木構造内で複数回現れるパターンのうち、二次パターンに現れない一次パターンを選択する選択手段として機能させることを特徴とする情報処理プログラムである。
【発明の効果】
【００１９】
請求項１記載の情報処理装置によれば、ｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇにおいて、ｃｌｏｓｅｄ  ｐａｔｔｅｒｎ又はＭａｘｉｍａｌ  ｐａｔｔｅｒｎを出力することができる。
【００２０】
請求項２記載の情報処理装置によれば、ｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇにおいて、ｃｌｏｓｅｄ  ｐａｔｔｅｒｎ又はＭａｘｉｍａｌ  ｐａｔｔｅｒｎを出力することができる。
【００２１】
請求項３記載の情報処理装置によれば、本構成を有していない場合に比較して、第１のパターンの抽出処理の負荷を軽減させることができる。
【００２２】
請求項４記載の情報処理装置によれば、本構成を有していない場合に比較して、第１のパターンの抽出処理の負荷を軽減させることができる。
【００２３】
請求項５記載の情報処理装置によれば、本構成を有していない場合に比較して、ｃｌｏｓｅｄ  ｐａｔｔｅｒｎを確実に抽出することができる。
【００２４】
請求項６記載の情報処理装置によれば、本構成を有していない場合に比較して、ｃｌｏｓｅｄ  ｐａｔｔｅｒｎを確実に抽出することができる。
【００２５】
請求項７記載の情報処理装置によれば、本構成を有していない場合に比較して、選択処理の負荷を軽減させることができる。
【００２６】
請求項８記載の情報処理装置によれば、本構成を有していない場合に比較して、選択処理の負荷を軽減させることができる。
【００２７】
請求項９記載の情報処理プログラムによれば、ｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇにおいて、ｃｌｏｓｅｄ  ｐａｔｔｅｒｎ又はＭａｘｉｍａｌ  ｐａｔｔｅｒｎを出力することができる。
【００２８】
請求項１０記載の情報処理プログラムによれば、ｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇにおいて、ｃｌｏｓｅｄ  ｐａｔｔｅｒｎ又はＭａｘｉｍａｌ  ｐａｔｔｅｒｎを出力することができる。
【発明を実施するための最良の形態】
【００２９】
以下、図面に基づき本発明を実現するにあたっての好適な各種の実施の形態の例を説明する。以下説明する実施の形態は、要素間に設定した関係を木構造として扱えるデータ群（以下、単にツリーともいう）の中から、複数回現れる関係構造（以下、単にパターンともいう）を抽出する技術に関するものである。
図１は、第１の実施の形態の構成例についての概念的なモジュール構成図を示している。
なお、モジュールとは、一般的に論理的に分離可能なソフトウェア（コンピュータ・プログラム）、ハードウェア等の部品を指す。したがって、本実施の形態におけるモジュールはコンピュータ・プログラムにおけるモジュールのことだけでなく、ハードウェア構成におけるモジュールも指す。それゆえ、本実施の形態は、コンピュータ・プログラム、システム及び方法の説明をも兼ねている。ただし、説明の都合上、「記憶する」、「記憶させる」、これらと同等の文言を用いるが、これらの文言は、実施の形態がコンピュータ・プログラムの場合は、記憶装置に記憶させる、又は記憶装置に記憶させるように制御するの意である。また、モジュールは機能にほぼ一対一に対応しているが、実装においては、１モジュールを１プログラムで構成してもよいし、複数モジュールを１プログラムで構成してもよく、逆に１モジュールを複数プログラムで構成してもよい。また、複数モジュールは１コンピュータによって実行されてもよいし、分散又は並列環境におけるコンピュータによって１モジュールが複数コンピュータで実行されてもよい。なお、１つのモジュールに他のモジュールが含まれていてもよい。また、以下、「接続」とは物理的な接続の他、論理的な接続（データの授受、指示、データ間の参照関係等）の場合にも用いる。
また、システム又は装置とは、複数のコンピュータ、ハードウェア、装置等がネットワーク（一対一対応の通信接続を含む）等の通信手段で接続されて構成されるほか、１つのコンピュータ、ハードウェア、装置等によって実現される場合も含まれる。「装置」と「システム」とは、互いに同義の用語として用いる。「所定」という用語は、予め定められたの意の他に、そのときの状況・状態に応じて、又はそれまでの状況・状態に応じての意を含めて用いる。
【００３０】
第１の実施の形態は、図１に示すように、ツリーデータ入力モジュール１０２、ツリーデータ記憶モジュール１０４、第一整形モジュール１０６、第二整形モジュール１０８、パターン抽出モジュール１１０、パターン記憶モジュール１１２、出力モジュール１１４、パターン選択モジュール１１６、制御モジュール１１８を有している。
【００３１】
ツリーデータ入力モジュール１０２は、ツリーデータ記憶モジュール１０４と接続されており、図示しない入力インタフェースを介してツリーデータを受け取り、そのツリーデータを必要なら処理にあわせて加工するなどして、ツリーデータ記憶モジュール１０４に渡す。
【００３２】
ツリーデータ記憶モジュール１０４は、ツリーデータ入力モジュール１０２、第一整形モジュール１０６、パターン抽出モジュール１１０と接続されている。ツリーデータ入力モジュール１０２から受け取ったツリーデータを格納し、パターン抽出モジュール１１０からの要求にこたえてツリーデータの一部あるいは全部に関する情報を渡す。また、第一整形モジュール１０６により整形されたツリーデータも受け付けて格納し、その第一整形モジュール１０６から得たツリーデータに対してもパターン抽出モジュール１１０が二次パターン抽出処理ができるようにする。
【００３３】
第一整形モジュール１０６は、ツリーデータ記憶モジュール１０４、パターン記憶モジュール１１２、制御モジュール１１８と接続されている。パターン記憶モジュール１１２に記憶されている一次パターンに、その一次パターンの出現数を表す符号を付加して、ツリーデータ記憶モジュール１０４に記憶させる。また、一次パターンの順序をパターン抽出モジュール１１０による二次パターン抽出処理によって抽出される順序に揃えるようにしてもよい。
つまり、第一整形モジュール１０６は、パターン抽出モジュール１１０によって抽出され、パターン記憶モジュール１１２に格納された一次パターンについて加工する。そして、パターン抽出モジュール１１０を再利用すること（つまり、二次パターン抽出処理）により、ｃｌｏｓｅｄ  ｐａｔｔｅｒｎを選択できるようにするための前処理を行い、処理結果をツリーデータ記憶モジュール１０４に渡す。
【００３４】
第二整形モジュール１０８は、パターン抽出モジュール１１０、パターン選択モジュール１１６、制御モジュール１１８と接続されており、パターン抽出モジュール１１０による二次パターン抽出処理の結果を加工する。つまり、二次パターンに対して、パターン選択モジュール１１６のパターン選択処理に適合させる変換を行う。
【００３５】
パターン抽出モジュール１１０は、ツリーデータ記憶モジュール１０４、第二整形モジュール１０８、パターン記憶モジュール１１２、制御モジュール１１８と接続されている。パターン抽出モジュール１１０は、２つの処理を行う。
１つ目の処理（以下、一次パターン抽出処理ともいう）は、ツリーデータ記憶モジュール１０４に記憶されている複数のツリーデータ内で、複数回現れる一次パターンを抽出し、パターン記憶モジュール１１２に渡す。その場合、対象としているノードよりも下位にあるパターンの出現数を用いてパターンを抽出するようにしてもよい。また、対象としているノードよりも下位であるパターンの出現数に基づいて、そのパターンの抽出を継続するようにしてもよい。
２つ目の処理（以下、二次パターン抽出処理ともいう）は、ツリーデータ記憶モジュール１０４に記憶されている第一整形モジュール１０６によって符号が付加された一次パターンから、二次パターンを抽出し、第二整形モジュール１０８に渡す。
つまり、図示しない入力装置を介してユーザから、あるいはシステムの設定により指定された条件にしたがってツリーデータ記憶モジュール１０４に格納されたツリーデータの中から共通のパターンを抽出してパターン記憶モジュール１１２又は第二整形モジュール１０８に渡す。
【００３６】
パターン記憶モジュール１１２は、第一整形モジュール１０６、パターン抽出モジュール１１０、パターン選択モジュール１１６と接続されている。パターン抽出モジュール１１０による一次パターン抽出処理により抽出された一次パターンを記憶し、第一整形モジュール１０６とパターン選択モジュール１１６に供給する。
【００３７】
パターン選択モジュール１１６は、第二整形モジュール１０８、パターン記憶モジュール１１２、出力モジュール１１４、制御モジュール１１８と接続されている。一次パターンと二次パターンを比較して、ツリーデータ内で複数回現れるパターンのうち、ｃｌｏｓｅｄ  ｐａｔｔｅｒｎを選択する。パターン抽出モジュール１１０による二次パターン抽出によって抽出されなかった一次パターンを選択するようにしてもよい。つまり、パターン選択モジュール１１６は、第二整形モジュール１０８から得た情報にしたがって、パターン記憶モジュール１１２に格納されているパターンの取捨選択を行って、出力モジュール１１４に渡す。
【００３８】
出力モジュール１１４は、パターン選択モジュール１１６と接続されており、パターン選択モジュール１１６からパターンを受け取り、そのパターンを出力する。パターンを出力するとは、そのパターンの構造をディスプレイに表示すること、プリンタで印刷すること、データベース等へ書き込むこと、通信回線を介して他のシステムへ送信すること等が含まれる。
【００３９】
制御モジュール１１８は、第一整形モジュール１０６、第二整形モジュール１０８、パターン抽出モジュール１１０、パターン選択モジュール１１６と接続されており、これらのモジュールに対して、各々の処理を行うように制御する。
【００４０】
図２は、第１の実施の形態における処理の流れを示すフローチャートである。
ステップＳ２０２では、パターン抽出モジュール１１０が一次パターン抽出処理を行う。
一次パターン抽出処理は、従来技術であるｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｍｉｎｉｎｇの技術を用いるようにしてもよい。また、一次パターン抽出として、複数のツリーデータ内で複数回現れるパターンの探索を、そのツリーデータ内の現在の処理対象となっているノードより下位のノードに対して行い、パターンの探索を、ツリーデータ内の現在の処理対象となっているノードより上位のノードであってその上位のノードの下位にあり、かつ未探索のノード毎に探索するようにしてもよい。また、それらの処理の一部を変更して採用してもよい。第１の実施の形態では、図３〜５に示す処理を用いる。
図３の例に示すフローチャートは、ｃｌｏｓｅｄ  ｐａｔｔｅｒｎの抽出を前提として出力パターンの削減と無駄になる処理を除いた、パターン抽出の処理の流れである。また図４の例に示すフローチャートは、その場合の一次パターン抽出処理における再帰部分の処理の流れを示したものである。図５の例に示すフローチャートは、その場合の二次パターン抽出処理における再帰部分の処理の流れを示したものである。これらの処理の詳細については後述する。
【００４１】
理解を容易にするために、例えば図１０に示したような、ドキュメントの操作ログの２つのツリーデータがあった場合に最低出現数が２のパターンを抽出する場合を想定する。図１０（ａ）のツリー例は、ドキュメントの作成として、閲覧と承認が２人の操作者によって並行して行われ、承認の後に、さらに２人の操作者によって、一方では印刷され閲覧が行われ、他方では修正され閲覧が行われたことを示している。また、図１０（ｂ）のツリー例は、ドキュメントの作成として、閲覧と修正が２人の操作者によって並行して行われ、修正の後に承認が行われ、さらに２人の操作者によって、一方では印刷され閲覧が行われ、他方では修正され閲覧が行われたことを示している。つまり、図１０（ｂ）のツリー例は、図１０（ａ）のツリー例に承認の前に修正のノードが付加されたものである。
まず、説明と図の簡単のために図１０に示すツリーのラベルの「作成」をＡ、「閲覧」をＢ、「修正」をＣ、「印刷」をＤ、「承認」をＥと変換して説明する。つまり、図１０の例に示すノードのラベルをこのように変換したツリーを図１１に示す。
【００４２】
そして、次に説明の簡単のために、ツリーデータの文字列表記を導入する。図１１のツリー例において、兄弟ノード間では左側のノードが先と順番を決めて、それぞれルートノードから深さ優先探索を行い、各ノードに到着したときにラベルを読み上げ、上位のノードに戻るときに記号（−１）を読み上げて文字列にしたものをツリーの文字列表記とする。例えば、図１１（ａ）、図１１（ｂ）については、それぞれ図１２（ａ）に示す「ＡＢ−１ＥＤＢ−１−１ＣＢ」、図１２（ｂ）に示す「ＡＢ−１ＣＥＤＢ−１−１ＣＢ」のようになる。また、簡単のために各文字列の最後に続く−１は省略して表記する。以降の説明では、パターンの出現数をサポートとも呼ぶ。
【００４３】
図１１に示す２つのツリー例を入力として最低出現数を２としたときのｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｐａｔｔｅｒｎは、図２１の例に挙げるように多くのパターン（「ＡＢ−１Ｄ：２」、「ＡＢ−１ＤＢ：２」等）が出力される。なお、「：２」は、サポートが２であることを示している。
これに対して、後述する図３に示すフローチャートによる処理を施すことで、一次パターン抽出の処理時に抽出されるパターンは大きく削減され図２２の例に示すようになる。
【００４４】
ステップＳ２０４では、第一整形モジュール１０６が、ステップＳ２０２の処理結果に対して、一次パターンの出現数を表す符号を付加する整形処理を行う。
つまり、第一整形モジュール１０６は、一次パターン抽出処理の結果を整形する。ｃｌｏｓｅｄ  ｐａｔｔｅｒｎは、サポート数が同じであるパターン間での包含関係を判定し、より大きなパターンに包含されるパターンを出力しない。このため、サポート数に対応し、かつ他のラベルと共通にならない符号をラベルとして設定したノードを各パターンツリーのルートの上位につけて新たなツリーとする。例えば、サポート数２に対して符号Ｙを与えることにより、ＥＢ−１Ｂ（図２２の４行目のパターン）は、ＹＥＢ−１Ｂ（図２３の４行目のパターン）のツリーに変換される。同様にして図２２のパターンは図２３のように変換される。
【００４５】
ステップＳ２０６では、パターン抽出モジュール１１０が、ステップＳ２０４の処理結果に対して、二次パターン抽出処理を行う。
つまり、パターン抽出モジュール１１０は、整形された一次パターンに再度パターン抽出をかける。この際の最低出現するサポート数の指定は２とするが、必要に応じてこの指定を変えるようにしてもよい。
複数のパターンの中に現れ、さらに追加したルートノード（サポート数を表している）が等しい場合には、そのパターンは同じサポートを持つ他のパターンの中に含まれるということを意味する。すなわち、二次パターン抽出処理による抽出結果のパターンを、一次パターン抽出処理の結果から除いたものがｃｌｏｓｅｄ  ｐａｔｔｅｒｎになる。
二次パターン抽出処理は、サポート数を表すラベルがルートノードにあるものだけを探せばよいので、二次パターン抽出の処理自体をそのように動作を制限することもできる。この制御以外は一次パターン抽出と同じ機構を用いて処理することもできる。なお、一次パターン抽出と二次パターン抽出は処理が異なっており、必ずしも全く同じ機構でなければならないわけではない。
【００４６】
ステップＳ２０８では、第二整形モジュール１０８が、ステップＳ２０６の処理結果に対して、整形処理を行う。
つまり、第二整形モジュール１０８は、二次パターン抽出処理の結果をパターン記憶モジュール１１２に含まれている一次パターンと比較しやすくする処理を行う。パターン選択モジュール１１６が直接それぞれのデータの形式に対応することで、第二整形モジュール１０８による二次結果整形の処理を省略することも可能である。
【００４７】
ステップＳ２１０では、パターン選択モジュール１１６が、一次パターン及び二次パターンを用いて、ｃｌｏｓｅｄ  ｐａｔｔｅｒｎを選択し、出力モジュール１１４がｃｌｏｓｅｄ  ｐａｔｔｅｒｎを出力する。
つまり、パターン選択モジュール１１６は、パターン記憶モジュール１１２に記憶されたパターンデータの中から、二次パターン抽出処理で抽出されなかったものを選択する。ここでの例では、図２１に示したパターンの中から図２４にないもの（先頭のＹの違いを除いて比べる）を選んで出力することになる。あるいは、図２３に示したパターンの中から図２４に無いものを選択して、形式を図２１の形に戻すなどの処理を行って出力する。
この選択処理の結果は、ここでの例ではＡＢ−１ＥＤＢ−１−１ＣＢ（図２１）という一つのパターンだけとなり、一つだけのパターンがｃｌｏｓｅｄ  ｐａｔｔｅｒｎ  ｍｉｎｉｎｇの出力結果となる。
【００４８】
次に図３〜図５の説明を行う。これらのフローチャート例は、パターン抽出処理をｃｌｏｓｅｄ  ｐａｔｔｅｒｎの抽出にあわせて効率化したものである。
【００４９】
図３に示すフローチャート例では、頻出ラベルを抽出し（ステップＳ３０２）、未処理の頻出ラベルがあった場合（ステップＳ３０４でｙ）には、未処理の頻出ラベルを一つ選んで（ステップＳ３０６）、そのラベルをルートノードとしたツリーパターンを作成し（ステップＳ３０８）、図４又は図５で説明するパターン抽出再帰処理（ステップＳ３１０）に入る。なお、一次パターン抽出処理では図４に示すフローチャート例のパターン抽出再帰処理、二次パターン抽出処理では図５に示すフローチャート例のパターン抽出再帰処理である。未処理の頻出ラベルがなくなった場合（ステップＳ３０４でｎ）には、図３に示すパターン抽出処理を終了する（ステップＳ３９９）。
【００５０】
図４に示すフローチャート例では、まず、作業中のパターンツリーのあるパスを選択し、そのパス上のノードを列挙する。そして、下位サポートと呼ぶ変数を用意して初期化する（ステップＳ４０２）。
未処理ノードがあり、かつ、下位サポートに同じものがない場合（ステップＳ４０４でｙ）は、ステップＳ４０６へ進み、それ以外の場合はステップＳ４２０へ進む。
ステップＳ４０６では、未処理ノードを選択する。例えば、パスとして最も右側のパス（ｒｉｇｈｔｍｏｓｔ  ｐａｔｈ  ：  ＲＭＰ）を選ぶことができる。より具体的には、図４の処理に入ったときに、作業中のパターンが図１３に示すツリー例であった場合、列挙されるノードはＡとＥとなる（以降もラベルを利用してノードの指定を行う）。
【００５１】
ステップＳ４０８では、伸張候補である頻出するラベルを探索する。ステップＳ４０６で最初にＥが選ばれたとすると、ステップＳ４０８では、Ｅの子供ノードとして頻出するラベルを列挙する。
ステップＳ４１０では、未処理の頻出ラベルがあるか否かを判断する。かかる判断においてある場合（ステップＳ４１０でｙ）にはステップＳ４１２へ進み、それ以外の場合（ステップＳ４１０でｎ）にはステップＳ４０４に戻る。この例では、ＢとＤとＥが挙げられるので、ステップＳ４１２へ進む。
【００５２】
そして、ステップＳ４１２では、伸張候補である頻出するラベルを選択する。そして、ステップＳ４１４で、その選択されたラベルついてのパターンを生成する。さきの例では、Ｄを選んで子ノードとした場合には図１４、Ｃを選んで子ノードとした場合には図１５、Ｂを選んで子ノードとした場合には図１６のパターンとなる。ここで、Ｄが選ばれたとすると、図１４に示すパターン例が生成される。
そして、ステップＳ４１６では、再帰的に本処理であるパターン抽出処理を呼び出す。再帰的に呼び出された先では例えば図１７、１８、１９に示すようなパターンが調べられて出力される。
そして、ステップＳ４１８では、ステップＳ４１６の再帰的処理から戻ってくると、下位サポートを更新する。さきの例では、下位サポートは２に設定される。この下位サポートの更新は、未処理の頻出ラベルを選択した際にすぐ行ってもよい。更新の際には下位サポートの値は最大の値を保つように更新する。そして、ステップＳ４１０へ戻る。
【００５３】
さきの例は、Ｅの子ノードになるラベルの処理が全て終わると（ステップＳ４１０でｎ）、次の伸張箇所のノードの選択（ステップＳ４０６）に移る。しかし、このとき既に下位サポートの数値が図１３のサポートの値と同じになっている（ステップＳ４０４でｎ）ので、新たな伸張箇所についての探索は行わない。これは、仮にＡから何らかのノードを伸張したパターンが頻出になったとしても、そのパターンは必ずＥの子供があるパターンにおいてＡに同じノードを伸張したパターンに含まれてしまうためである。
【００５４】
ステップＳ４２０では、下位サポートに同じものがあるか否かを判断する。かかる判断において同じものがある場合（ステップＳ４２０でｙ）には終了し（ステップＳ４９９）、それ以外の場合（ステップＳ４２０でｎ）はステップＳ４２２へ進む。つまり、下位サポートがそのパターンのサポートと同じでない場合には、そのパターンと同じサポートであり、かつそのパターンを含むパターンが存在しない可能性があるのでパターンを出力する（ステップＳ４２２）。
この処理により、ｃｌｏｓｅｄ  ｐａｔｔｅｒｎになりえないパターンの出力が抑えられて処理効率を上げることができる。
【００５５】
次に、図５に示すフローチャート例を用いて、二次パターン抽出処理におけるパターン抽出再帰処理を説明する。二次パターン抽出処理におけるパターン抽出再帰処理は、図４に示したフローチャート例と同様の処理を行う。つまり、ステップＳ５０２、ステップＳ５０６〜ステップＳ５１６は、それぞれステップＳ４０２、ステップＳ４０６〜ステップＳ４１６と同様である。二次パターン抽出処理では、下位サポートの判断処理が不要となる。したがって、ステップＳ４０４とは異なりステップＳ５０４で「未処理ノードあり」の判断だけを行い、ステップＳ４１８とステップＳ４２０の処理が不要となる。
【００５６】
次に、第２の実施の形態を説明する。図６は、第２の実施の形態の構成例についての概念的なモジュール構成図を示している。
第１の実施の形態では、抽出したパターンから再度パターンを抽出した後で、パターン同士を比較していたが、第２の実施の形態では、二次抽出パターンを出力しない。二次抽出パターンは、例に示したように一次抽出パターンよりも数が多くなる場合があり、このことが処理効率を下げる場合がある。第２の実施の形態は、二次抽出処理と選択処理においてパターンの抽出を行うのではなく、一次パターンが二次抽出処理において出現するか否かの判断を行うものである。
【００５７】
第２の実施の形態は、図６に示すように、ツリーデータ入力モジュール６０２、ツリーデータ記憶モジュール６０４、第一整形モジュール６０６、パターン抽出モジュール６１０、パターン記憶モジュール６１２、出力モジュール６１４、パターン選択モジュール６１６、制御モジュール６１８を有している。
第１の実施の形態と同様のモジュールは、同様の名称にしている。なお、第１の実施の形態と異なるのは、第二整形モジュール１０８がないことである。つまり、一次パターン抽出処理までは第１の実施の形態と同様である。第１の実施の形態と異なるモジュールの働きについて説明する。
【００５８】
パターン抽出モジュール６１０は、ツリーデータ記憶モジュール６０４、パターン記憶モジュール６１２、パターン選択モジュール６１６、制御モジュール６１８と接続されており、パターン抽出モジュール６１０による一次パターン抽出処理によって抽出された一次パターンを一次パターンの出現数毎に分類し、その分類された一次パターンから二次パターンを抽出する。
パターン選択モジュール６１６は、パターン抽出モジュール６１０、パターン記憶モジュール６１２、出力モジュール６１４、制御モジュール６１８と接続されており、パターン抽出モジュール６１０によって一次パターンを参照して行われる二次パターンの抽出処理過程で、ツリーデータ内で複数回現れるパターンのうち、ｃｌｏｓｅｄ  ｐａｔｔｅｒｎを選択する。つまり、参照パターンに沿ってラベルの選択が行えない場合、参照パターンを出力する。また、パターン抽出モジュール６１０の二次パターン抽出処理による抽出のときに抽出されなかった一次パターンを選択するようにしてもよい。
【００５９】
図７に示すフローチャート例は、第２の実施の形態による処理例である。一次パターンを抽出し（ステップＳ７０２）、一次パターンを整形し（ステップＳ７０４）、一次パターンのリストに沿って、二次パターンの抽出処理と同時に一次パターンの選択処理を行う（ステップＳ７０６）。
ステップＳ７０２での一次パターンの抽出処理は、例えば、図３、図４に示す処理例と同様のものであってもよい。
【００６０】
図８に示すフローチャート例は、二次パターン抽出・一次パターン選択出力処理（ステップＳ７０６）の処理例を示したものである。
図５に示すフローチャート例との違いは、頻出ラベルの選択（ステップＳ８０６）が参照パターン（一次パターン）に沿って行われることと、参照パターンに沿ってラベルの選択が行えない（参照パターンが頻出パターンとして出現しない）場合（ステップＳ８０４でｎ）、参照パターンを出力する（ステップＳ８１２）点である。
【００６１】
ステップＳ８０２では、一次パターンから頻出ラベルを抽出する。
ステップＳ８０４では、参照パターンに沿ったラベルを選択できるか否かを判断する。かかる判断において選択できる場合（ステップＳ８０４でｙ）にはステップＳ８０６へ進み、それ以外の場合（ステップＳ８０４でｎ）はステップＳ８１２へ進む。
ステップＳ８０６では、ステップＳ８０４で選択できると判断したラベルを選択する。
ステップＳ８０８では、そのラベルを用いたパターンを作成する。
ステップＳ８１０では、図９に示すフローチャート例を呼び出す。戻ってきたらステップＳ８０４に戻る。
ステップＳ８１２では、参照パターンを出力する。
ステップＳ８１４では、未処理の参照パターンがあるか否かを判断する。かかる判断において未処理の参照パターンがある場合（ステップＳ８１４でｙ）にはステップＳ８１６へ進み、それ以外の場合（ステップＳ８１４でｎ）には終了する（ステップＳ８９９）。
ステップＳ８１６では、参照パターンを更新して、ステップＳ８０４へ戻る。
【００６２】
図９に示すフローチャート例は、図８のステップＳ８１０から呼び出されて再帰的にパターンを探索する処理例である。
この処理例も図５に示すフローチャート例と類似した処理を行うが、伸張箇所が決まった際にラベルを参照パターンに沿って選べなかったとき（ステップＳ９１２、参照パターンが頻出パターンとして出現しえないとき）、参照パターンを出力する点（ステップＳ９２２）が異なっている。
【００６３】
図９に示すフローチャート例に制御が移ったとき、常に抽出中のパターンと参照パターンは一致している。
ステップＳ９０２では、未処理の参照パターンがあるか否かを判断する。かかる判断においてある場合にはステップＳ９０４に進み、それ以外の場合には終了する（ステップＳ９９９）。
ステップＳ９０４では、参照パターンを更新する。
つまり、ステップＳ９０２、ステップＳ９０４では、参照パターンを抽出処理中のパターンよりも先に進める（次のラベルを選択する指針とするためには参照パターンが先に進んでいなければならない）処理を行っている。
ステップＳ９０６以降では、参照パターンが先に進んでいるため、参照パターンに従って制御を進める（ラベルの選択を行う）ことができる。
ステップＳ９０６では、参照パターンにしたがって、ノードを選択できるか否かを判断する。かかる判断において選択できる場合（ステップＳ９０６でｙ）にはステップＳ９０８に進み、それ以外の場合（ステップＳ９０６でｎ）は終了する（ステップＳ９９９）。
ステップＳ９０８では、その参照パターンにしたがって、ノードを選択する。
ステップＳ９１０では、伸張候補である頻出ラベルを探索する。
【００６４】
ステップＳ９１２では、参照パターンにしたがって、ラベルを選択できるか否かを判断する。かかる判断において選択できる場合（ステップＳ９１２でｙ）にはステップＳ９１４に進み、それ以外の場合（ステップＳ９１２でｎ）はステップＳ９２２に進む。
ステップＳ９１４では、ステップＳ９１２で選択できると判断されたラベル、つまり伸張候補の頻出ラベルを選択する。
ステップＳ９１６では、パターンを作成する。
ステップＳ９１８では、パターン抽出再帰処理（図９に示すフローチャート例による処理）を再帰的に呼び出す。
ステップＳ９２０では、参照パターンは同じノードからの伸張であるか否かを判断する。かかる判断において同じノードからの伸張である場合（ステップＳ９２０でｙ）にはステップＳ９１２に戻り、それ以外の場合（ステップＳ９２０でｎ）はステップＳ９０６に戻る。
【００６５】
ステップＳ９２２では、その参照パターンを出力する。
ステップＳ９２４では、未処理の参照パターンがあるか否かを判断する。かかる判断においてある場合（ステップＳ９２４でｙ）にはステップＳ９２６に進み、それ以外の場合（ステップＳ９２４でｎ）には終了する（ステップＳ９９９）。
ステップＳ９２６では、参照パターンを更新し、ステップＳ９２０に進む。
【００６６】
図８と図９に示すフローチャート例の処理により、二次パターン探索・一次パターン選択出力の処理を効率的に実行することができる。処理の結果、図１１に示すツリー例を入力として、最低出現する回数として２を指定すると、一次パターン抽出の結果として図２２に示すパターンがパターン記憶モジュール６１２に保持された後、図２４に示すパターン例は出力されずに、直接結果として図２０に示すｃｌｏｓｅｄ  ｐａｔｔｅｒｎを表す出力が一つ提示される。
【００６７】
前述の第１の実施の形態又は第２の実施の形態において、パターン選択モジュール１１６又はパターン選択モジュール６１６による処理に先立って、参照パターンは辞書順などで整列させておくことでより効率的に処理を実現することができる。この整列は出力した一次パターンを第一整形モジュール１０６又は第一整形モジュール６０６にて整列処理をかけることでも実現できる。また、一次パターン抽出処理、二次パターン抽出処理における処理の順序を制御することによっても実現できる。つまり、参照パターンの整列と二次パターン抽出処理の処理順が揃っていることが処理効率を高めることになる。
【００６８】
また、前述の例ではサポート数として２だけであったが、通常はデータのツリーの数も多く、サポート数は２以上であってもよい。
制御モジュール１１８、制御モジュール６１８は、第１の実施の形態、第２の実施の形態の両方において、例えばサポートの数毎に一次結果の整形以降の処理を行うように制御するようにしてもよい。
また、サポートの数の違いを無視した処理に変形すると、Ｍａｘｉｍａｌ  ｐａｔｔｅｒｎの抽出処理を実現することもできる。
また、一次パターン抽出処理の結果を直接、二次パターン抽出（探索）処理で入力できるように一次パターン抽出処理の出力部分あるいは二次パターン抽出（探索）処理の入力部分を改変することで、一次結果の整形を省略する構成とすることも容易な変更である。
十分に大きな主記憶装置を用意して、一次パターン抽出処理の結果を主記憶上に保持することでパターン記憶モジュール１１２又はパターン記憶モジュール６１２を主記憶上に用意することもできる。
また、前述の例では、サポート数を表す符号をパターンの先頭に付加したが、パターンの最後尾やルートノードの最初の子ノードとして付加するようにしてもよい。
【００６９】
また、一次パターン抽出処理の結果をサポート数毎に処理するように制御することで、大量のパターンを分割処理することもできる。その場合には、第一整形モジュール１０６では、サポート数を表すノードをルートノードにつける必要が必ずしもなくなるため、第一整形モジュール１０６の処理をそのように適用させる改変も可能である。
【００７０】
なお、前述の実施の形態としてのプログラムが実行されるコンピュータのハードウェア構成は、図２５に例示するように、一般的なコンピュータであり、具体的にはパーソナルコンピュータ、サーバーとなりえるコンピュータ等である。パターン抽出モジュール１１０、第一整形モジュール１０６、第二整形モジュール１０８、パターン抽出モジュール６１０、第一整形モジュール６０６等のプログラムを実行するＣＰＵ２５０１（この例では演算部としてＣＰＵを用いた）と、そのプログラムやデータを記憶するＲＡＭ２５０２と、本コンピュータを起動するためのプログラム等が格納されているＲＯＭ２５０３と、補助記憶装置であるＨＤ２５０４（例えばハードディスクを用いることができる）と、キーボード、マウス等のデータを入力する入力装置２５０６と、ＣＲＴや液晶ディスプレイ等の出力装置２５０５と、通信ネットワークと接続するための通信回線インタフェース２５０７（例えばネットワークインタフェースカードを用いることができる）、そして、それらをつないでデータのやりとりをするためのバス２５０８により構成されている。これらのコンピュータが複数台互いにネットワークによって接続されていてもよい。
【００７１】
前述の実施の形態のうち、コンピュータ・プログラムによるものについては、本ハードウェア構成のシステムにソフトウェアであるコンピュータ・プログラムを読み込ませ、ソフトウェアとハードウェア資源とが協働して、前述の実施の形態が実現される。
なお、図２５に示すハードウェア構成は、１つの構成例を示すものであり、前述の実施の形態は、図２５に示す構成に限らず、前述の実施の形態において説明したモジュールを実行可能な構成であればよい。例えば、一部のモジュールを専用のハードウェア（例えばＡＳＩＣ等）で構成してもよく、一部のモジュールは外部のシステム内にあり通信回線で接続しているような形態でもよく、さらに図２５に示すシステムが複数互いに通信回線によって接続されていて互いに協調動作するようにしてもよい。また、特に、パーソナルコンピュータの他、情報家電、複写機、ファックス、スキャナ、プリンタ、複合機（スキャナ、プリンタ、複写機、ファックス等のいずれか２つ以上の機能を有している画像処理装置）などに組み込まれていてもよい。
【００７２】
なお、説明したプログラムについては、記録媒体に格納して提供してもよく、また、そのプログラムを通信手段によって提供してもよい。その場合、例えば、前記説明したプログラムについて、「プログラムを記録したコンピュータ読み取り可能な記録媒体」の発明として捉えてもよい。
「プログラムを記録したコンピュータ読み取り可能な記録媒体」とは、プログラムのインストール、実行、プログラムの流通などのために用いられる、プログラムが記録されたコンピュータで読み取り可能な記録媒体をいう。
なお、記録媒体としては、例えば、デジタル・バーサタイル・ディスク（ＤＶＤ）であって、ＤＶＤフォーラムで策定された規格である「ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ−ＲＡＭ等」、ＤＶＤ＋ＲＷで策定された規格である「ＤＶＤ＋Ｒ、ＤＶＤ＋ＲＷ等」、コンパクトディスク（ＣＤ）であって、読出し専用メモリ（ＣＤ−ＲＯＭ）、ＣＤレコーダブル（ＣＤ−Ｒ）、ＣＤリライタブル（ＣＤ−ＲＷ）等、ブルーレイ・ディスク（Ｂｌｕｅ−ｒａｙ  Ｄｉｓｋ）、光磁気ディスク（ＭＯ）、フレキシブルディスク（ＦＤ）、磁気テープ、ハードディスク、読出し専用メモリ（ＲＯＭ）、電気的消去及び書換可能な読出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュ・メモリ、ランダム・アクセス・メモリ（ＲＡＭ）等が含まれる。
そして、前記のプログラム又はその一部は、前記記録媒体に記録して保存や流通等させてもよい。また、通信によって、例えば、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、イントラネット、エクストラネット等に用いられる有線ネットワーク、あるいは無線通信ネットワーク、さらにこれらの組み合わせ等の伝送媒体を用いて伝送させてもよく、また、搬送波に乗せて搬送させてもよい。
さらに、前記のプログラムは、他のプログラムの一部分であってもよく、あるいは別個のプログラムと共に記録媒体に記録されていてもよい。また、複数の記録媒体に分割して
記録されていてもよい。また、圧縮や暗号化など、復元可能であればどのような態様で記録されていてもよい。
【図面の簡単な説明】
【００７３】
【図１】第１の実施の形態の構成例についての概念的なモジュール構成図である。
【図２】第１の実施の形態による処理例を示すフローチャートである。
【図３】第１の実施の形態によるパターン抽出の処理例を示すフローチャートである。
【図４】第１の実施の形態による一次パターン抽出における再帰処理例を示すフローチャートである。
【図５】第１の実施の形態による二次パターン抽出における再帰処理例を示すフローチャートである。
【図６】第２の実施の形態の構成例についての概念的なモジュール構成図である。
【図７】第２の実施の形態による処理例を示すフローチャートである。
【図８】第２の実施の形態による二次パターン抽出・一次パターン選択出力の処理例を示すフローチャートである。
【図９】第２の実施の形態によるパターン抽出における再帰処理例を示すフローチャートである。
【図１０】ドキュメントの操作ログのツリーデータの例を示す説明図である。
【図１１】ドキュメントの操作ログのツリーデータのラベルを変換した例を示す説明図である。
【図１２】ツリーデータを文字列表記した場合の例を示す説明図である。
【図１３】作業中のパターンの例を示す説明図である。
【図１４】ラベルＤを選択した場合のパターンの例を示す説明図である。
【図１５】ラベルＣを選択した場合のパターンの例を示す説明図である。
【図１６】ラベルＢを選択した場合のパターンの例を示す説明図である。
【図１７】出力されるパターンの例を示す説明図である。
【図１８】出力されるパターンの例を示す説明図である。
【図１９】出力されるパターンの例を示す説明図である。
【図２０】出力されるｃｌｏｓｅｄ  ｐａｔｔｅｒｎの例を示す説明図である。
【図２１】対象とする２つのツリーの最低出現数を２としたときの抽出されるｅｍｂｅｄｄｅｄ  ｓｕｂｔｒｅｅ  ｐａｔｔｅｒｎの例を示す説明図である。
【図２２】一次パターン抽出処理によって抽出されるパターンの例を示す説明図である。
【図２３】抽出された一次パターンに符号を付加した例を示す説明図である。
【図２４】二次パターン抽出によって抽出されたパターンの例を示す説明図である。
【図２５】第１及び第２の実施の形態を実現するコンピュータのハードウェア構成例を示すブロック図である。
【符号の説明】
【００７４】
１０２、６０２…ツリーデータ入力モジュール
１０４、６０４…ツリーデータ記憶モジュール
１０６、６０６…第一整形モジュール
１０８…第二整形モジュール
１１０、６１０…パターン抽出モジュール
１１２、６１２…パターン記憶モジュール
１１４、６１４…出力モジュール
１１６、６１６…パターン選択モジュール
１１８、６１８…制御モジュール
【図１】
0004957656.tif 000002
【図２】
0004957656.tif 000003
【図３】
0004957656.tif 000004
【図４】
0004957656.tif 000005
【図５】
0004957656.tif 000006
【図６】
0004957656.tif 000007
【図７】
0004957656.tif 000008
【図８】
0004957656.tif 000009
【図９】
0004957656.tif 000010
【図１０】
0004957656.tif 000011
【図１１】
0004957656.tif 000012
【図１２】
0004957656.tif 000013
【図１３】
0004957656.tif 000014
【図１４】
0004957656.tif 000015
【図１５】
0004957656.tif 000016
【図１６】
0004957656.tif 000017
【図１７】
0004957656.tif 000018
【図１８】
0004957656.tif 000019
【図１９】
0004957656.tif 000020
【図２０】
0004957656.tif 000021
【図２１】
0004957656.tif 000022
【図２２】
0004957656.tif 000023
【図２３】
0004957656.tif 000024
【図２４】
0004957656.tif 000025
【図２５】
0004957656.tif 000026