(57)【要約】      （修正有）【課題】効率良く所定のパターンを抽出する。【解決手段】抽出プログラム３３０ａは、イベントを含む第１のパターンに対して順序に従ってイベントを追加して第２のパターンを生成する際に、第１の値が所定の閾値未満である場合に、イベントを追加して第２のパターンを生成する。そして、抽出プログラム３３０ａは、イベントが追加された場合に、第１の値に所定値を加算し、表の各列に対応付けられた第２の値のうち、追加されたイベントの端に対応する列の第２の値に所定値を加算する。そして、抽出プログラム３３０ａは、所定の条件を満たす第２のパターンを抽出する。そして、抽出プログラム３３０ａは、表において２列目以降のイベントを追加する際に、第１の値から、追加されるイベントの端の直前の列の第２の値を減算し、所定の閾値との比較対象である第１の値を更新する。【選択図】図３６
2014109879.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
記憶部に記憶された、排他的なイベントが同列に配置され、同種の隣り合うイベントが繋げられ、出現順にイベントに順序が付与された表を参照し、イベントを含む第１のパターンに対して前記順序に従ってイベントを追加して第２のパターンを生成する際に、第１の値が所定の閾値未満である場合に、当該イベントを追加して第２のパターンを生成し、
前記イベントが追加された場合に、前記第１の値に所定値を加算し、前記表の各列に対応付けられた第２の値のうち、追加されたイベントの端に対応する列の第２の値に前記所定値を加算し、
所定の条件を満たす前記第２のパターンを抽出し、
前記表において２列目以降のイベントを追加する際に、前記第１の値から、追加されるイベントの端の直前の列の前記第２の値を減算し、前記所定の閾値との比較対象である前記第１の値を更新する
各処理を実行させるための抽出プログラム。
【請求項２】
前記第２のパターンを生成する処理は、前記第１の値が、所定のウィンドウ幅に基づいて定まる閾値未満である場合に、前記第２のパターンを生成し、
前記第２のパターンを抽出する処理は、前記記憶部に記憶された複数のイベントと各イベントの出現時刻とを対応付けた複数のデータを含むイベントデータに基づいて、前記所定のウィンドウ幅内に含まれる前記出現時刻に対応付けられたイベントに基づいて、前記第２のパターンが前記イベントデータが示すイベントのパターンに登場する頻度を算出し、該頻度が条件を満たす前記第２のパターンを抽出する
ことを特徴とする請求項１に記載の抽出プログラム。
【請求項３】
前記コンピュータに、更に、
前記第２のパターンを生成する際に前記第１のパターンに追加されるイベントが該第１のパターンのイベントの先頭又は末尾に追加されるイベントである場合には、前記閾値から、前記第１のパターンに含まれる前記排他的なイベントが前記イベントデータが示すイベントのパターンに出現する回数に対応する値を減算した値を用いて前記閾値を更新する
処理を実行させ、
前記第２のパターンを生成する処理は、前記第１の値及び前記閾値が更新された場合には、更新された前記第１の値が、更新された前記閾値未満である場合に、前記順序が１番目のイベントを追加して前記第２のパターンを生成する
ことを特徴とする請求項１または２に記載の抽出プログラム。
【請求項４】
前記コンピュータに、更に、
前記所定の条件を満たさない前記第２のパターンから、該第２のパターンに最後に追加されたイベントを削除することで、前記第１のパターンを生成し、
前記第１のパターンが生成された際に、前記更新された第１の値に、前記回数に対応する値を加算した値を用いて前記第１の値を新たに更新し、
前記第１のパターンが生成された際に、削除された前記イベントが先頭又は末尾のイベントである場合には、前記更新された閾値に、前記回数に対応する値を加算した値を用いて前記閾値を新たに更新する
各処理を実行させ、
前記第２のパターンを生成する処理は、前記第１の値及び前記閾値が新たに更新された場合には、新たに更新された前記第１の値が、新たに更新された前記閾値未満である場合に、順序が１番目のイベントを追加して前記第２のパターンを生成する
ことを特徴とする請求項３に記載の抽出プログラム。
【請求項５】
前記コンピュータに、更に、
新たに生成された前記第２のパターンに、任意のイベントを追加する
処理を実行させる
ことを特徴とする請求項３に記載の抽出プログラム。
【請求項６】
排他的なイベントが同列に配置され、同種の隣り合うイベントが繋げられ、出現順にイベントに順序が付与された表が記憶された記憶部と、
前記記憶部に記憶された表に基づいて、イベントを含む第１のパターンに対して前記順序に従ってイベントを追加して第２のパターンを生成する際に、第１の値が所定の閾値未満である場合に、当該イベントを追加して第２のパターンを生成する生成部と、
前記イベントが追加された場合に、前記第１の値に所定値を加算し、前記表の各列に対応付けられた第２の値のうち、追加されたイベントの端に対応する列の第２の値に前記所定値を加算するとともに、前記表において２列目以降のイベントを追加する際に、前記第１の値から、追加されるイベントの端の直前の列の前記第２の値を減算し、前記所定の閾値との比較対象である前記第１の値を更新する更新部と、
所定の条件を満たす前記第２のパターンを抽出する抽出部と、
を有することを特徴とする抽出装置。
【請求項７】
コンピュータが、
記憶部に記憶された、排他的なイベントが同列に配置され、同種の隣り合うイベントが繋げられ、出現順にイベントに順序が付与された表を参照し、イベントを含む第１のパターンに対して前記順序に従ってイベントを追加して第２のパターンを生成する際に、第１の値が所定の閾値未満である場合に、当該イベントを追加して第２のパターンを生成し、
前記イベントが追加された場合に、前記第１の値に所定値を加算し、前記表の各列に対応付けられた第２の値のうち、追加されたイベントの端に対応する列の第２の値に前記所定値を加算し、
所定の条件を満たす前記第２のパターンを抽出し、
前記表において２列目以降のイベントを追加する際に、前記第１の値から、追加されるイベントの端の直前の列の前記第２の値を減算し、前記所定の閾値との比較対象である前記第１の値を更新する
各処理を実行することを特徴とする抽出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、抽出プログラム、抽出装置及び抽出方法に関する。
【背景技術】
【０００２】
イベントデータが示す実際に出現したイベントのパターンに含まれるパターンを抽出する抽出装置がある。イベントデータの一例としては、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンを示すイベントデータが挙げられる。イベントデータが、「アンケートの回答者は男性である」というイベントＡ、「アンケートの回答者は、年齢が３０代である」というイベントＢ及び「アンケートの質問１に対する回答内容は、「Ａ１」である」というイベントＣを含む場合について説明する。この場合には、抽出装置は、次のようなパターンを抽出する。例えば、抽出装置は、イベントＡのパターン、イベントＡ及びＢのパターン、イベントＡ、Ｂ及びＣのパターン、イベントＢのパターン、イベントＢ及びＣのパターン、イベントＣのパターンを抽出する。これらのパターンが抽出装置により抽出された場合、抽出装置を使用するユーザは、男性で年齢が３０代の回答者は、質問１に対して「Ａ１」という内容を回答したということを把握することができる。
【０００３】
また、上記の抽出装置の一例としては、次のような抽出装置がある。例えば、列挙木における親から子を生成しつつ、生成した子が、イベントデータが示す実際に出現したイベントのパターンに出現するか否かを判定することで、イベントデータが示す実際に出現したイベントのパターンに含まれるパターンを抽出する抽出装置がある。かかる抽出装置は、親のパターンにイベントを追加することで、子のパターンを生成する。そして、抽出装置は、新たに生成された子のパターンを親のパターンとして、再び子のパターンを生成する。このようにして、抽出装置は、所定の条件を満たすまで、繰り返し子のパターンを生成する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特表２００１−５２２０９５号公報
【特許文献２】特開平４−１２５７３４号公報
【特許文献３】特開平８−６９５７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記の抽出装置では、効率良くパターンを抽出することができないという問題がある。これを説明すると、かかる抽出装置は、抽出されるパターンとしてはあり得ないパターンを生成する。例えば、親のパターンに追加するイベントとして、上記のイベントＡ、Ｂ及びＣに加え、次のようなイベントがある場合について説明する。すなわち、「アンケートの回答者は女性である」というイベントＤ、「アンケートの回答者は、年齢が２０代である」というイベントＥ及び「アンケートの質問１に対する回答内容は、「Ａ２」である」というイベントＦがある場合について説明する。この場合、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンを示すイベントデータが示すイベントのパターンに、イベントＡとイベントＤとが出現することはあり得ない。回答者の性別は、男性か女性のいずれかであるからである。また、かかるイベントのパターンに、イベントＢとイベントＥとが出現することはあり得ない。回答者の年齢の世代が、２０代及び３０代の両世代であることはあり得ないからである。また、アンケートの質問１に対する回答の形式が１つの回答内容を回答する形式である場合には、かかるイベントのパターンに、イベントＣとイベントＦとが出現することはあり得ない。
【０００６】
しかしながら、上記の抽出装置は、親のパターンがイベントＡを有するパターンであっても、かかる親のパターンにイベントＤを追加してイベントＡ及びイベントＤを有する子のパターンを生成する。同様に、上記の抽出装置は、親のパターンがイベントＢを有するパターンであっても、かかる親のパターンにイベントＥを追加してイベントＢ及びイベントＥを有する子のパターンを生成する。また、上記の抽出装置は、親のパターンがイベントＣを有するパターンであっても、かかる親のパターンにイベントＦを追加してイベントＣ及びイベントＦを有する子のパターンを生成する。すなわち、上記の抽出装置は、イベントデータが示すイベントに出現しないようなイベントの組み合わせ、すなわち、互いに排他的なイベントを含むパターンを生成する。そして、上記の抽出装置は、イベントデータが示すイベントのパターンに出現しないイベントの組み合わせを含むパターンであるにもかかわらず、かかるパターンが、イベントデータが示すイベントのパターンに出現するか否かを判定するような無駄な処理を行う。そのため、上記の抽出装置は、効率良くパターンを抽出することができないという問題がある。
【０００７】
１つの側面では、効率良くパターンを抽出することができる抽出プログラム、抽出装置及び抽出方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本願の開示する抽出プログラムは、一つの態様において、コンピュータに、記憶部に記憶された、排他的なイベントが同列に配置され、同種の隣り合うイベントが繋げられ、出現順にイベントに順序が付与された表を参照し、次の処理を実行させる。すなわち、抽出プログラムは、コンピュータに、イベントを含む第１のパターンに対して順序に従ってイベントを追加して第２のパターンを生成する際に、第１の値が所定の閾値未満である場合に、イベントを追加して第２のパターンを生成する処理を実行させる。そして、抽出プログラムは、コンピュータに、イベントが追加された場合に、第１の値に所定値を加算し、表の各列に対応付けられた第２の値のうち、追加されたイベントの端に対応する列の第２の値に所定値を加算する処理を実行させる。そして、抽出プログラムは、コンピュータに、所定の条件を満たす第２のパターンを抽出する処理を実行させる。そして、抽出プログラムは、表において２列目以降のイベントを追加する際に、第１の値から、追加されるイベントの端の直前の列の第２の値を減算し、所定の閾値との比較対象である第１の値を更新する処理を実行させる。
【発明の効果】
【０００９】
抽出プログラム、抽出装置及び抽出方法の一つの態様によれば、効率良くパターンを抽出することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施例１に係る抽出装置の機能構成の一例を示す図である。
【図２】図２は、区間表の一例を示す図である。
【図３】図３は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図４】図４は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図５】図５は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図６】図６は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図７】図７は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図８】図８は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図９】図９は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図１０】図１０は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図１１】図１１は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図１２】図１２は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図１３】図１３は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【図１４】図１４は、実施例１に係る抽出処理の手順を示すフローチャートである。
【図１５】図１５は、実施例１に係る抽出処理の手順を示すフローチャートである。
【図１６】図１６は、実施例２に係る抽出装置の機能構成の一例を示す図である。
【図１７】図１７は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図１８】図１８は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図１９】図１９は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２０】図２０は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２１】図２１は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２２】図２２は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２３】図２３は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２４】図２４は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２５】図２５は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２６】図２６は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２７】図２７は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２８】図２８は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図２９】図２９は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図３０】図３０は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図３１】図３１は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【図３２】図３２は、実施例２に係る抽出処理の手順を示すフローチャートである。
【図３３】図３３は、実施例２に係る抽出処理の手順を示すフローチャートである。
【図３４】図３４は、実施例３に係る抽出装置の機能構成の一例を示す図である。
【図３５】図３５は、実施例３に係る抽出処理の手順を示すフローチャートの一部を示す図である。
【図３６】図３６は、抽出プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１１】
以下に、本願の開示する抽出プログラム、抽出装置及び抽出方法の各実施例を図面に基づいて詳細に説明する。なお、各実施例は開示の技術を限定するものではない。
【実施例１】
【００１２】
［抽出装置の構成］
実施例１に係る抽出装置について説明する。図１は、実施例１に係る抽出装置の機能構成の一例を示す図である。図１に示すように、抽出装置１０は、入力部１１と、表示部１２と、記憶部１３と、制御部１４とを有する。
【００１３】
入力部１１は、制御部１４に情報を入力する。例えば、入力部１１は、ユーザからの指示を受け付けて、制御部１４に、後述の抽出処理を実行する指示を入力する。また、入力部１１は、ユーザからの指示を受け付けて、制御部１４に、所定のサーバから後述のイベントデータ１３ａを取得する指示を入力する。また、入力部１１は、ユーザの操作を受け付けて、制御部１４に、後述の区間表１３ｂを入力する。入力部１１のデバイスの一例としては、キーボードやマウスなどが挙げられる。
【００１４】
表示部１２は、各種の情報を表示する。例えば、表示部１２は、後述の抽出部１４ｆにより抽出されたパターンを後述の表示制御部１４ｇの制御により表示する。
【００１５】
記憶部１３は、制御部１４で実行される各種プログラムを記憶する。また、記憶部１３には、後述の取得部１４ａにより、イベントデータ１３ａ及び区間表１３ｂが格納される。また、記憶部１３には、カウンタ１３ｃが記憶される。また、記憶部１３は、スタック１３ｄの記憶領域を有する。
【００１６】
イベントデータ１３ａについて説明する。イベントデータ１３ａは、実際に出現したイベントとイベントが出現した時刻とが対応付けられたデータである。以下、イベントデータ１３ａが、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンを示すデータを複数含む場合について説明する。そのため、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンを示すようなイベントデータにおいては、排他的なイベントの組合せのパターンが出現しないが、イベントデータ１３ａでは出現しうる。なお、イベントデータ１３ａはこれに限られず、様々なイベントを含むデータを採用することができる。
【００１７】
イベントデータ１３ａが示すイベントのパターンには、識別子Ａが示すイベント、識別子Ｂが示すイベント、識別子Ｃが示すイベント、識別子Ｄが示すイベント、識別子Ｅが示すイベント、識別子Ｆが示すイベント、識別子Ｇが示すイベントが含まれる。以下の説明では、識別子Ａが示すイベントを「イベントＡ」と表記する。また、同様に、識別子Ｂが示すイベントを「イベントＢ」と表記し、識別子Ｃが示すイベントを「イベントＣ」と表記し、識別子Ｄが示すイベントを「イベントＤ」と表記し、識別子Ｅが示すイベントを「イベントＥ」と表記する。また、同様に、識別子Ｆが示すイベントを「イベントＦ」と表記し、識別子Ｇが示すイベントを「イベントＧ」と表記する。
【００１８】
なお、本実施例では、イベントＡ、Ｃ及びＦが排他的なイベントの組合せである。また、本実施例では、イベントＡ、Ｄ及びＦが排他的なイベントの組合せである。また、本実施例では、イベントＡ、Ｄ及びＧが排他的なイベントの組合せである。また、本実施例では、イベントＢ、Ｄ及びＧが排他的なイベントの組合せである。また、本実施例では、イベントＢ、Ｅ及びＧが排他的なイベントの組合せである。例えば、イベントＡ、Ｃ及びＦが排他的なイベントの組合せであるため、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンには、イベントＡ及びＣの両イベントが出現することはあり得ない。また、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンには、イベントＡ及びＦの両イベントが出現することはあり得ないし、イベントＣ及びＦの両イベントが出現することはあり得ない。他の排他的なイベントの組合せについても同様である。
【００１９】
区間表１３ｂについて説明する。区間表１３ｂは、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しないようなイベントの組合せ、すなわち、排他的なイベントの組合せを示すイベントの識別子の組合せが登録されたものである。また、区間表１３ｂでは、あるエピソードにイベントを追加して新たなエピソードを生成する際における追加されるイベントの順序が定義されている。区間表１３ｂは、ユーザによって生成される。
【００２０】
図２は、区間表の一例を示す図である。図２の例に示す区間表１３ｂは、列方向に、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しないイベントの組合せが登録された場合を示す。図２の例の区間表１３ｂは、列方向に、イベントＡ、Ｃ及びＦの組合せが登録された場合を示す。また、図２の例の区間表１３ｂは、列方向に、イベントＡ、Ｄ及びＦの組合せが登録された場合を示す。また、図２の例の区間表１３ｂは、列方向に、イベントＡ、Ｄ及びＧの組合せが登録された場合を示す。また、図２の例の区間表１３ｂは、列方向に、イベントＢ、Ｄ及びＧの組合せが登録された場合を示す。また、図２の例の区間表１３ｂは、列方向に、イベントＢ、Ｅ及びＧの組合せが登録された場合を示す。
【００２１】
すなわち、区間表１３ｂは、イベントＡ及びＣの組合せが、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しないことを示す。また、区間表１３ｂは、イベントＡ及びＦの組合せが、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しないことを示す。また、区間表１３ｂは、イベントＣ及びＦの組合せが、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しないことを示す。また、区間表１３ｂは、イベントＡ及びＤの組合せが、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しないことを示す。また、区間表１３ｂは、イベントＤ及びＦの組合せが、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しないことを示す。また、区間表１３ｂは、イベントＡ及びＧの組合せが、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しないことを示す。また、区間表１３ｂは、イベントＤ及びＧの組合せが、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しないことを示す。また、区間表１３ｂは、イベントＢ及びＧの組合せが、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しないことを示す。また、区間表１３ｂは、イベントＢ及びＤの組合せが、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しないことを示す。また、区間表１３ｂは、イベントＢ及びＥの組合せが、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しないことを示す。また、区間表１３ｂは、イベントＥ及びＧの組合せが、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しないことを示す。
【００２２】
図２の例に示す区間表１３ｂは、排他的なイベントの１つの組合せに含まれる複数のイベントの識別子が３行×１列で登録され、かつ、排他的なイベントの組合せが５つ登録された場合を示す。なお、図２の例に示す区間表１３ｂにおいて、１番目の行が上端の行、３番目の行が下端の行、１番目の列が左端の列、５番目の列が右端の列となる。
【００２３】
また、図２の例では、イベントＡの識別子Ａが区間表１３ｂの１番目の行において１番目の列から３番目の列までに登録された場合が示されているが、実際には、次のように識別子Ａが登録されている。すなわち、実際には、区間表１３ｂの１番目の列から３番目の列までのそれぞれの列と１番目の行とが交差する位置にイベントＡの識別子Ａが登録されている。
【００２４】
また、図２の例では、イベントＦの識別子Ｆが区間表１３ｂの３番目の行において１番目の列から２番目の列までに登録された場合が示されているが、実際には、次のように識別子Ｆが登録されている。すなわち、実際には、区間表１３ｂの１番目の列から２番目の列までのそれぞれの列と３番目の行とが交差する位置にイベントＦの識別子Ｆが登録されている。
【００２５】
また、図２の例では、イベントＤの識別子Ｄが区間表１３ｂの２番目の行において２番目の列から４番目の列までに登録された場合が示されているが、実際には、次のように識別子Ｄが登録されている。すなわち、実際には、区間表１３ｂの２番目の列から４番目の列までのそれぞれの列と２番目の行とが交差する位置にイベントＤの識別子Ｄが登録されている。
【００２６】
また、図２の例では、イベントＧの識別子Ｇが区間表１３ｂの３番目の行において３番目の列から５番目の列までに登録された場合が示されているが、実際には、次のように識別子Ｇが登録されている。すなわち、実際には、区間表１３ｂの３番目の列から５番目の列までのそれぞれの列と３番目の行とが交差する位置にイベントＧの識別子Ｇが登録されている。
【００２７】
また、図２の例では、イベントＢの識別子Ｂが区間表１３ｂの１番目の行において４番目の列から５番目の列までに登録された場合が示されているが、実際には、次のように識別子Ｂが登録されている。すなわち、実際には、区間表１３ｂの４番目の列から５番目の列までのそれぞれの列と１番目の行とが交差する位置にイベントＢの識別子Ｂが登録されている。
【００２８】
また、区間表１３ｂは、あるエピソードにイベントを追加して新たなエピソードを生成する際における、追加されるイベントの順序が定義されている。イベントの追加される順序の一例について説明する。例えば、区間表１３ｂの１番目の行と１番目の列とが交差する位置（起点位置）に登録された識別子が示すイベントが１番目に追加されるイベントとなる。そして、区間表１３ｂの起点位置に対して行方向で近い位置に登録された識別子が示すイベントから順に追加される。なお、起点位置に対して行方向で同一の位置に登録された識別子については、起点位置に対して列方向で近い位置に登録された識別子が示すイベントから順に追加される。例えば、図２の例に示す区間表１３ｂは、１番目に追加されるイベントがイベントＡであり、２番目に追加されるイベントがイベントＣであり、３番目に追加されるイベントがイベントＦであり、４番目に追加されるイベントがイベントＤであることを示す。また、図２の例に示す区間表１３ｂは、５番目に追加されるイベントがイベントＧであり、６番目に追加されるイベントがイベントＢであり、７番目に追加されるイベントがイベントＥであることを示す。
【００２９】
また、区間表１３ｂには、排他的なイベントの組合せごとに、すなわち、列ごとにポイント管理変数が設けられている。
【００３０】
カウンタ１３ｃには、区間表１３ｂに登録された排他的なイベントの組合せに含まれる、イベントが追加されるパターンのイベントの数であるカウント値（値）が登録される。
【００３１】
スタック１３ｄの記憶領域には、カウンタ１３ｃの値が更新されるたびに、更新前の値が登録される。また、スタック１３ｄの記憶領域から値が取り出される場合には、最後に登録された値が取り出される。すなわち、かかる記憶領域に登録されたデータが、ＬＩＦＯ（Last  In  Fast  Out）方式で取り出される。このことから、スタック１３ｄは、スタック１３ｄの記憶領域が示す仮想的なスタックであるといえる。
【００３２】
記憶部１３は、例えば、フラッシュメモリなどの半導体メモリ素子、または、ハードディスク、光ディスクなどの記憶装置である。なお、記憶部１３は、上記の種類の記憶装置に限定されるものではなく、ＲＡＭ（Random  Access  Memory)、ＲＯＭ（Read  Only  Memory)であってもよい。
【００３３】
制御部１４は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。図１に示すように、制御部１４は、取得部１４ａと、初期化部１４ｂと、生成部１４ｃと、バックトラック処理部１４ｄと、カウンタ制御部１４ｅと、抽出部１４ｆと、表示制御部１４ｇとを有する。
【００３４】
取得部１４ａは、各種の情報を取得する。例えば、取得部１４ａは、所定のサーバからイベントデータ１３ａを取得する指示が入力部１１から入力された場合には、かかる指示に基づいて、次のような処理を行う。すなわち、取得部１４ａは、図示しないネットワークを介して図示しない所定のサーバにアクセスし、所定のサーバからイベントデータ１３ａを取得する。そして、取得部１４ａは、取得したイベントデータ１３ａを記憶部１３に格納する。また、取得部１４ａは、区間表１３ｂが入力部１１から入力された場合には、入力された区間表１３ｂを取得し、取得した区間表１３ｂを記憶部１３に格納する。
【００３５】
また、取得部１４ａは、抽出処理を実行する指示が入力部１１から入力された場合には、記憶部１３からイベントデータ１３ａ及び区間表１３ｂを取得する。
【００３６】
初期化部１４ｂは、各種の初期化を行う。例えば、初期化部１４ｂは、取得部１４ａによりイベントデータ１３ａ及び区間表１３ｂが取得された場合には、空のエピソード（空エピソード）を列挙木における最初の親、すなわち、根に設定する。ここで、エピソードとは、イベントが出現する順番（出現順序）を有向グラフで表現したものである。例えば、エピソードは、複数のパートを有する。複数のパートのそれぞれには、イベントが含まれる。各パートには、順番が定められている。エピソードが有するＮ番目のパートに含まれるイベントと、（Ｎ＋１）番目のパートに含まれるイベントとの関係について説明する。Ｎ番目のパートに含まれるイベントと、（Ｎ＋１）番目のパートに含まれるイベントとの関係は、Ｎ番目のパートに含まれるイベントの全てのイベントが出現した後に、（Ｎ＋１）番目のパートに含まれるイベントが出現するという関係である。図３は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。図３の例に示すように、初期化部１４ｂは、根のエピソード３０に空エピソード４０を設定する。
【００３７】
続いて、初期化部１４ｂは、エピソードにイベントを追加して新たなエピソードを生成する際に、追加されるイベントの候補である追加候補に、ｎｕｌｌ値を設定して、追加候補を初期化する。
【００３８】
そして、初期化部１４ｂは、区間表１３ｂの全ての列のポイント管理変数の値を「０」に設定することで、ポイント管理変数の初期化を行う。図４は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。例えば、図４の例に示すように、初期化部１４ｂは、区間表１３ｂの全ての列のポイント管理変数の値を「０」に設定する。
【００３９】
続いて、初期化部１４ｂは、処理対象の列に１番目の列を設定する。例えば、初期化部１４ｂは、図４の例に示す区間表１３ｂの１番目の列（イベントＡ、Ｃ及びＦの組合せが登録された列）に処理対象の列を設定する。処理対象の列には、追加候補に設定されたイベントを含むイベントの組合せが登録された列が設定される。詳細について説明すると、処理対象の列には、区間表１３ｂにおいて、追加候補に設定されたイベントの識別子が登録された行の左端の列が設定される。そのため、本実施例では、追加候補に設定されたイベントの変更に応じて、処理対象の列に設定される列も変更される。例えば、図４の例に示す区間表１３ｂのイベントＦが追加候補に設定された後に、新たにイベントＤが追加候補に設定された場合には、処理対象の列に設定される列は、１番目の列から２番目の列に変更される。なお、追加候補にｎｕｌｌ値が設定された場合には、処理対象の列に１番目の列が設定される。また、図４の例では、カウンタ１３ｃが１番目の列に対応する位置に設定されているが、これは、処理対象の列が１番目の列に設定されたことを模式的に表現したものである。以下の説明で用いる各図では、同様に、カウンタ１３ｃが区間表１３ｂのＮ番目の列に対応する位置に設定されている場合があるが、これは、処理対象の列がＮ番目の列に設定されたことを模式的に表現したものである。
【００４０】
そして、初期化部１４ｂは、カウンタ１３ｃの値を「０」に設定することで、カウンタ１３ｃの初期化を行う。続いて、初期化部１４ｂは、後述する生成部１４ｃが実行する、カウンタ１３ｃの値が閾値未満であるか否かを判定する処理に用いられる閾値の値を、次のような値に設定する。すなわち、初期化部１４ｂは、かかる閾値の値を、エピソードを抽出する際に用いられ、イベントデータ１３ａのイベントパターンを探索する際の時間的な幅であるウィンドウ幅の値に設定する。ウィンドウ幅とは、例えば、時刻「２」から時刻「３」までの時間（２〜３）に発生したイベントパターンを抽出したい場合には、ウィンドウ幅は、「２」となる。以下、ウィンドウ幅が「２」である場合について説明するが、ウィンドウ幅の値はこれに限られない。
【００４１】
生成部１４ｃは、各種のパターンを生成する。生成部１４ｃの一態様について説明する。生成部１４ｃは、まず、根のエピソード３０を選択する。
【００４２】
次に、生成部１４ｃは、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定する。なお、本実施例では、空エピソード３０が１番目のパート及び２番目のパートを有する場合について説明する。空エピソード３０が２つのパートを有するため、空エピソード３０の子孫のエピソードもこれらの２つのパートを有する。この場合、生成部１４ｃは、区間表１３ｂが示す追加するイベントの順序にしたがって、選択したエピソードに追加するイベントの候補を１つ特定する。そして、生成部１４ｃは、選択したエピソードのいずれかのパートとの組合せにおいて、特定したイベントの候補が未選択であるときに、選択したエピソードに追加するイベントの候補及びイベントが追加されるパートの候補があると判定する。なお、本実施例では、同一のイベントが同一のパートに含まれないものとする。一方、生成部１４ｃは、選択したエピソードのいずれのパートとの組合せにおいても未選択となるイベントの候補がない場合には、選択したエピソードに追加するイベントの候補がないと判定する。例えば、図３の例に示す根のエピソード３０が選択された場合には、エピソード３０のいずれのパートとの組合せにおいても、１番目に追加されるイベントであるイベントＡが未選択である。このため、生成部１４ｃは、選択したエピソード３０のパートに追加するイベントＡ、及び、イベントＡが追加されるパート（１番目のパート及び２番目のパートのいずれか）があると判定する。なお、生成部１４ｃは、表示制御部１４ｇによりエピソードが表示されるように表示部１２の表示が制御された場合にも、同様に、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定する。また、生成部１４ｃは、カウンタ制御部１４ｅによりポイント管理変数の値が１つデクリメントされた場合にも、同様に、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートがあるか否かを判定する。
【００４３】
選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートがある場合には、生成部１４ｃは、イベントの候補を１つ選択するとともに、パートの候補を１つ選択する。例えば、図３の例において、選択したエピソード３０に追加するイベントＡ及びイベントが追加される１番目のパート及び２番目のパートのいずれかがある場合には、生成部１４ｃは、イベントＡをイベントの候補として１つ選択する。これに加えて、生成部１４ｃは、イベントが追加することができる１番目のパート及び２番目のパートのうち、最も小さい順番の１番目のパートをパートの候補として選択する。なお、以下の説明では、イベントの候補を「イベントの候補ｅ」と表記する場合がある。
【００４４】
次に、生成部１４ｃは、区間表１３ｂにおいて、処理対象の列が、選択したイベントの候補ｅの識別子が登録された行の左端の列であるか否かを判定する。例えば、図４に示す場合において、処理対象の列が１番目の列であり、選択したイベントの候補ｅがイベントＡである場合について説明する。この場合、選択したイベントの候補ｅの識別子Ａが登録された行の左端の列が、１番目の列である。そのため、かかる場合、生成部１４ｃは、区間表１３ｂにおいて、処理対象の列が、選択したイベントの候補ｅの識別子Ａが登録された行の左端の列であると判定する。なお、カウンタ制御部１４ｅにより処理対象の列の位置が１つ右の列に移動された場合にも、生成部１４ｃは、処理対象の列が、選択したイベントの候補ｅの識別子が登録された行の左端の列であるか否かを判定する。
【００４５】
処理対象の列が、選択したイベントの候補ｅの識別子が登録された行の左端の列である場合には、生成部１４ｃは、追加候補に、選択したイベントの候補を設定する。そして、生成部１４ｃは、区間表１３ｂにおいて、カウンタ１３ｃの値が閾値「２」未満であるか否かを判定する。例えば、図４の例に示す場合では、カウンタ１３ｃの値が「０」であるため、生成部１４ｃは、カウンタ１３ｃの値「０」が閾値「２」未満であると判定する。
【００４６】
カウンタ１３ｃの値が閾値「２」未満でない場合には、生成部１４ｃは、選択したエピソードに追加するイベントの候補及びイベントが追加されるパートの候補があるか否かを判定する上述した処理を行い、かかる処理以降の処理を再び行う。
【００４７】
一方、カウンタ１３ｃの値が閾値「２」未満である場合には、生成部１４ｃは、選択したエピソードの選択したパートの候補に、選択したイベントの候補を追加して、エピソードを生成する。そして、生成部１４ｃは、生成したエピソードを選択する。図５は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。例えば、図５の例に示すように、生成部１４ｃは、選択したエピソード３０の選択したパートの候補に、選択したイベントの候補であるイベントＡを追加して、エピソード３１を生成する。そして、生成部１４ｃは、生成したエピソード３１を選択する。
【００４８】
このように、本実施例では、カウンタ１３ｃが閾値「２」未満である場合に、選択したエピソードの選択したパートの候補に、選択したイベントの候補ｅが追加されて、エピソードが生成される。また、本実施例では、カウンタ１３ｃが閾値「２」未満でない場合には、新しいエピソードを生成しない。これは、上述したが、イベントデータ１３ａは、複数のアンケートに対して回答した回答者の情報及び回答内容を含むデータが示すイベントのパターンを示すデータを含む。そのため、イベントデータ１３ａが示すイベントのパターンには、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しない排他的なイベントの組合せも出現する。そこで、本実施例では、１つのアンケートに対して回答した回答者の情報及び回答内容を含むデータが示すイベントのパターンに出現しないようなイベントの組み合わせをウィンドウ幅の大きさよりも多く含むパターンを生成しないようにする。そのため、本実施例では、排他的なイベントの組み合わせを含むパターンの頻度を算出する処理や、かかるパターンが頻出であるか否かを判定するような処理などの無駄な処理を行うことが抑制される。そのため、本実施例は、効率良くパターンを抽出することができる。なお、カウンタ１３ｃが閾値「２」未満でない場合に、エピソードを生成しないことを、「枝刈り」と称する場合もある。
【００４９】
また、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定した結果、追加するイベントの候補またはパートの候補がない場合には、生成部１４ｃは、次の処理を行う。すなわち、生成部１４ｃは、枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成されたか否かを判定する。枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成された場合には処理が終了される。
【００５０】
バックトラック処理部１４ｄは、バックトラックを行う。例えば、抽出部１４ｆにより頻出でないと判別された場合に、バックトラック処理部１４ｄは、生成部１４ｃにより生成されたエピソードから最後に追加されたイベントを削除したエピソードを生成する。そして、バックトラック処理部１４ｄは、生成したエピソードを選択する。
【００５１】
また、バックトラック処理部１４ｄは、生成部１４ｃにより、枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成されていないと判定された場合にも、同様の処理を行う。
【００５２】
カウンタ制御部１４ｅは、カウンタ１３ｃの値の増減を制御する。例えば、生成部１４ｃにより生成されたエピソードが選択された場合には、カウンタ制御部１４ｅは、カウンタ１３ｃの値をスタック１３ｄに格納する。図６は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。例えば、図４の例に示す場合では、カウンタ１３ｃの値が「０」である。そこで、カウンタ制御部１４ｅは、図６の例に示すように、カウンタ１３ｃの値「０」をスタック１３ｄに格納する。そして、カウンタ制御部１４ｅは、カウンタ１３ｃの値を１つインクリメントする。例えば、図６の例に示すように、カウンタ制御部１４ｅは、カウンタ１３ｃの値「０」を１つインクリメントして、カウンタ１３ｃの値を「１」に更新する。続いて、カウンタ制御部１４ｅは、区間表１３ｂで、選択したイベントの候補の識別子が登録された行の右端の列のポイント管理変数の値を１つインクリメントする。
【００５３】
また、カウンタ制御部１４ｅは、先の生成部１４ｃにより、処理対象の列が、選択したイベントの候補ｅの識別子が登録された行の左端の列でないと判定された場合には、次の処理を行う。すなわち、カウンタ制御部１４ｅは、カウンタ１３ｃの値から、処理対象の列のポイント管理変数の値を減算して、カウンタ１３ｃの値を更新する。そして、カウンタ制御部１４ｅは、処理対象の列の位置を１つ右の列に移動させる。
【００５４】
また、カウンタ制御部１４ｅは、先のバックトラック処理部１４ｄによりエピソードが選択された場合には、次のような処理を行う。すなわち、カウンタ制御部１４ｅは、スタック１３ｄに最後に格納されたカウント値を取得し、取得したカウント値をカウンタ１３ｃに設定して、カウンタ１３ｃの値をスタック１３ｄから復元する。その後、カウンタ制御部１４ｅは、区間表１３ｂにおいて、削除されたイベントの識別子が登録された行の右端に対応する列のポイント管理変数の値を１つデクリメントする。
【００５５】
抽出部１４ｆは、カウンタ制御部１４ｅによりポイント管理変数の値が１つインクリメントされた場合には、生成されたパターンの頻度を算出する。例えば、抽出部１４ｆは、生成されたエピソードの極小出現が存在する場合には「１」、存在しない場合には「０」の値を頻度として算出する。ここで、極小出現とは、エピソードの先頭のパートのイベントから、末尾のパートのイベントまでのイベントがイベントデータ１３ａが示すイベントのパターンにおいて存在する最小の時間の区間である。かかる頻度は、「バイナリ頻度」とも称される。そして、抽出部１４ｆは、算出した頻度が「１」であるか否かを判定する。そして、算出した頻度が「１」である場合には、抽出部１４ｆは、エピソードは、頻出であると判別する。一方、算出した頻度が「１」でない場合、すなわち「０」である場合には、抽出部１４ｆは、エピソードは、頻出でないと判別する。
【００５６】
以下、開示の装置が、頻度として「バイナリ頻度」を算出する場合について説明するが、開示の装置は、これに限定されるものではない。例えば、開示の装置は、列挙木における子の頻度が親の頻度以下となるような頻度であれば、バイナリ頻度以外の頻度を算出し、算出された頻度に基づいて、エピソードが頻出であるか否かを判別することができる。このような頻度の一例としては、「ウィンドウ頻度」が挙げられる。「ウィンドウ頻度」とは、予め定められた区間の集合に対して極小出現を含む区間の数、または、前後の区間で一部が重複するような複数の区間の集合に対して極小出現を含む区間の数を指す。頻度として「ウィンドウ頻度」を算出する場合には、抽出部１４ｆは、エピソードの「ウィンドウ頻度」が所定の閾値以上であるか否かを判定することにより、エピソードが頻出であるか否かを判別することができる。
【００５７】
また、他の例としては、「非重複極小出現頻度」が挙げられる。「非重複極小出現頻度」とは、時間がオーバーラップしていない（同じ時間を含まない）極小出現の最大数を指す。頻度として「非重複極小出現頻度」を算出する場合には、抽出部１４ｆは、エピソードの「非重複極小出現頻度」が所定の閾値以上であるか否かを判定することにより、エピソードが頻出であるか否かを判別することができる。抽出部１４ｆは、頻出であると判別されたエピソードを表示するエピソードとして抽出する。例えば、抽出部１４ｆは、頻出であると判別された図５に示すエピソード３１を表示するエピソードとして抽出する。
【００５８】
表示制御部１４ｇは、各種の情報を表示するように表示部１２の表示を制御する。例えば、表示制御部１４ｇは、抽出部１４ｆにより抽出されたエピソード、例えば、エピソード３１を表示するように表示部１２の表示を制御する。
【００５９】
次に、抽出装置１０が実行する処理の具体例について、図７〜図１４を参照して説明する。図７〜図１４は、実施例１に係る抽出装置が実行する処理の一例を説明するための図である。
【００６０】
例えば、エピソード３１が表示部１２に表示された後に、抽出装置１０は、選択したエピソード３１に追加するイベントの候補であるイベントＣを選択する。
【００６１】
ここで、図６に示すように、区間表１３ｂにおいて、処理対象の列が１番目の列であり、選択したイベントの候補の識別子Ｃが登録された行の左端の列が１番目の列である。そのため、抽出装置１０は、処理対象の列が選択したイベントの候補の左端の列であると判定し、追加候補に、選択したイベントの候補であるイベントＣを設定する。そして、図６に示すように、カウンタ１３ｃの値「１」が閾値「２」未満であるため、抽出装置１０は、次のような処理を行う。すなわち、抽出装置１０は、図７に示すように、選択したエピソード３１の選択したパートに、選択したイベントの候補（イベントＣ）を追加して、エピソード３２を生成する。
【００６２】
そして、図８に示すように、抽出装置１０は、カウンタ１３ｃの値「１」をスタック１３ｄに格納し、カウンタ１３ｃの値「１」を１つインクリメントして、カウンタ１３ｃの値を「２」に更新する。そして、抽出装置１０は、区間表１３ｂで、選択したイベントの候補の識別子Ｃの右端の列である３番目の列のポイント管理変数の値を１つインクリメントして、かかるポイント管理変数の値を「１」に設定する。
【００６３】
続いて、エピソード３２は頻出であるため、抽出装置１０は、エピソード３２を抽出する。そして、抽出装置１０は、エピソード３２を表示部１２に表示させる。
【００６４】
続いて、抽出装置１０は、選択したエピソード３２に追加するイベントの候補であるイベントＦを選択する。ここで、図８に示すように、区間表１３ｂにおいて、処理対象の列が１番目の列であり、選択したイベントの候補の識別子Ｆが登録された行の左端の列が１番目の列である。そのため、抽出装置１０は、処理対象の列が選択したイベントの候補の左端の列であると判定し、追加候補に、選択したイベントの候補であるイベントＦを設定する。
【００６５】
ここで、図８に示すように、カウンタ１３ｃの値「２」が閾値「２」未満でないため、抽出装置１０は、次のような処理を行う。すなわち、抽出装置１０は、イベントの候補としてイベントＤを選択する。このとき、図８に示すように、処理対象の列が１番目の列であり、選択したイベントの候補の識別子Ｄが登録された行の左端の列が２番目の列である。そのため、抽出装置１０は、処理対象の列が選択したイベントの候補の左端の列ではないと判定する。続いて、抽出装置１０は、カウンタ１３ｃの値「２」から処理対象の列のポイント管理変数の値「１」を減算した値「１」を、図９に示すように、カウンタ１３ｃに設定し、処理対象の列の位置を１つ右の列に移動させる。
【００６６】
そして、抽出装置１０は、再び、処理対象の列が、選択したイベントの候補の識別子が登録された行の左端の列であるか否かを判定する。このとき、図９に示すように、処理対象の列が２番目の列であり、選択したイベントの候補の識別子Ｄが登録された行の左端の列が２番目の列である。そのため、抽出装置１０は、処理対象の列が、選択したイベントの候補の識別子が登録された行の左端の列であると判定する。
【００６７】
続いて、図９に示すように、カウンタ１３ｃの値「１」が閾値「２」未満であるため、抽出装置１０は、図１０に示すように、選択したエピソード３２の選択したパートに、選択したイベントの候補（イベントＤ）を追加して、エピソード３３を生成する。
【００６８】
そして、図１１に示すように、抽出装置１０は、カウンタ１３ｃの値「１」をスタック１３ｄに格納し、カウンタ１３ｃの値「１」を１つインクリメントして、カウンタ１３ｃの値を「２」に更新する。そして、図１１に示すように、抽出装置１０は、区間表１３ｂで、選択したイベントの候補の識別子Ｄの右端の列である４番目の列のポイント管理変数の値を１つインクリメントして、かかるポイント管理変数の値を「１」に設定する。
【００６９】
このとき、エピソード３３は、頻出ではないため、抽出装置１０は、エピソード３３は頻出でないと判定する。そして、図１２に示すように、抽出装置１０は、エピソード３３から、選択したイベントの候補（イベントＤ）を削除してエピソード３２を生成し、エピソード３２を選択する。
【００７０】
続いて、図１３に示すように、抽出装置１０は、スタック１３ｄに最後に格納されたカウント値「１」を取得し、取得したカウント値「１」をカウンタ１３ｃに設定して、カウンタ１３ｃの値をスタック１３ｄから復元する。また、抽出装置１０は、区間表１３ｂにおいて、削除されたイベントの識別子Ｄが登録された行の右端に対応する列のポイント管理変数の値「１」を１つデクリメントして、図１３に示すように、かかるポイント管理変数の値を「０」に設定する。そして、抽出装置１０は、以降の処理を行う。
【００７１】
制御部１４は、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路またはＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などの電子回路である。  
【００７２】
［処理の流れ］
次に、本実施例に係る抽出装置１０の処理の流れを説明する。図１４及び図１５は、実施例１に係る抽出処理の手順を示すフローチャートである。この抽出処理の実行タイミングとしては様々なタイミングが考えられる。例えば、抽出処理は、抽出処理を実行する指示が入力部１１から入力された場合に、制御部１４により実行される。
【００７３】
図１４に示すように、取得部１４ａは、記憶部１３からイベントデータ１３ａを取得する（Ｓ１０１）。続いて、取得部１４ａは、記憶部１３から区間表１３ｂを取得する（Ｓ１０２）。
【００７４】
初期化部１４ｂは、根のエピソード３０に空エピソード４０を設定する（Ｓ１０３）。続いて、初期化部１４ｂは、追加候補に、ｎｕｌｌ値を設定して、追加候補を初期化する（Ｓ１０４）。
【００７５】
そして、初期化部１４ｂは、区間表１３ｂの全ての列のポイント管理変数の値を「０」に設定することで、ポイント管理変数の初期化を行う（Ｓ１０５）。続いて、初期化部１４ｂは、処理対象の列に１番目の列を設定する（Ｓ１０６）。
【００７６】
そして、初期化部１４ｂは、カウンタ１３ｃの値を「０」に設定することで、カウンタ１３ｃの初期化を行う（Ｓ１０７）。続いて、初期化部１４ｂは、閾値の値を、ウィンドウ幅の値に設定する（Ｓ１０８）。
【００７７】
次に、生成部１４ｃは、根のエピソード３０を選択する（Ｓ１０９）。続いて、生成部１４ｃは、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定する（Ｓ１１０）。
【００７８】
選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートがある場合（Ｓ１１０肯定）には、生成部１４ｃは、イベントの候補を１つ選択するとともに、パートの候補を１つ選択する（Ｓ１１１）。
【００７９】
次に、生成部１４ｃは、区間表１３ｂにおいて、処理対象の列が、選択したイベントの候補ｅの識別子が登録された行の左端の列であるか否かを判定する（Ｓ１１２）。処理対象の列が、選択したイベントの候補ｅの識別子が登録された行の左端の列である場合（Ｓ１１２肯定）には、生成部１４ｃは、追加候補に、選択したイベントの候補を設定する（Ｓ１１３）。続いて、生成部１４ｃは、区間表１３ｂにおいて、カウンタ１３ｃの値が閾値「２」未満であるか否かを判定する（Ｓ１１４）。
【００８０】
カウンタ１３ｃの値が閾値「２」未満でない場合（Ｓ１１４否定）には、Ｓ１１０に戻る。
【００８１】
一方、カウンタ１３ｃの値が閾値「２」未満である場合（Ｓ１１４肯定）には、生成部１４ｃは、選択したエピソードの選択したパートの候補に、選択したイベントの候補を追加して、エピソードを生成し、生成したエピソードを選択する（Ｓ１１５）。
【００８２】
続いて、カウンタ制御部１４ｅは、カウンタ１３ｃの値をスタック１３ｄに格納する（Ｓ１１６）。そして、カウンタ制御部１４ｅは、カウンタ１３ｃの値を１つインクリメントする（Ｓ１１７）。続いて、カウンタ制御部１４ｅは、区間表１３ｂで、選択したイベントの候補の識別子が登録された行の右端の列のポイント管理変数の値を１つインクリメントする（Ｓ１１８）。
【００８３】
そして、抽出部１４ｆは、生成されたパターンの頻度を算出する（Ｓ１１９）。そして、抽出部１４ｆは、算出した頻度が「１」であるか否かを判定することで、頻出であるか否かを判別する（Ｓ１２０）。頻出である場合（Ｓ１２０肯定）には、抽出部１４ｆは、頻出であると判別されたエピソードを表示するエピソードとして抽出する（Ｓ１２１）。そして、表示制御部１４ｇは、抽出されたエピソードを表示するように表示部１２の表示を制御し（Ｓ１２２）、Ｓ１１０に戻る。
【００８４】
一方、頻出でない場合（Ｓ１２０否定）には、バックトラック処理部１４ｄは、生成されたエピソードから選択したイベントの候補、すなわち、最後に追加されたイベントを削除したエピソードを生成し、生成したエピソードを選択する（Ｓ１２３）。
【００８５】
そして、カウンタ制御部１４ｅは、スタック１３ｄに最後に格納されたカウント値を取得し、取得したカウント値をカウンタ１３ｃに設定して、カウンタ１３ｃの値をスタック１３ｄから復元する（Ｓ１２４）。その後、カウンタ制御部１４ｅは、区間表１３ｂにおいて、削除されたイベントの識別子が登録された行の右端に対応する列のポイント管理変数の値を１つデクリメントし（Ｓ１２５）、Ｓ１１０に戻る。
【００８６】
また、処理対象の列が、選択したイベントの候補ｅの識別子が登録された行の左端の列でない場合（Ｓ１１２否定）には、カウンタ制御部１４ｅは、次の処理を行う。すなわち、カウンタ制御部１４ｅは、カウンタ１３ｃの値から、処理対象の列のポイント管理変数の値を減算して、カウンタ１３ｃの値を更新する（Ｓ１２６）。そして、カウンタ制御部１４ｅは、処理対象の列の位置を１つ右の列に移動させ（Ｓ１２７）、Ｓ１１２に戻る。
【００８７】
また、追加するイベントの候補またはパートの候補がない場合（Ｓ１１０否定）には、生成部１４ｃは、次の処理を行う。すなわち、生成部１４ｃは、枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成されたか否かを判定する（Ｓ１２８）。枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成された場合（Ｓ１２８肯定）には、処理を終了する。一方、枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成されていない場合（Ｓ１２８否定）には、Ｓ１２３へ進む。
【００８８】
上述してきたように、本実施例に係る抽出装置１０は、区間表１３ｂが記憶された記憶部１３を有する。区間表１３ｂは、排他的なイベントが同列に配置され、同種の隣り合うイベントが繋げられ、出現順にイベントに順序が付与された表である。抽出装置１０は、区間表１３ｂを参照し、イベントを含む選択したエピソードに対して順序に従ってイベントを追加して新たなエピソードを生成する際に、カウンタ１３ｃの値が閾値「２」未満である場合に、イベントを追加して新たなエピソードを生成する。そして、抽出装置１０は、イベントが追加された場合に、カウンタ１３ｃの値に所定値「１」を加算し、区間表１３ｂの各列に対応付けられたポイント管理変数の値のうち、追加されたイベントの右端の列のポイント管理変数の値に所定値「１」を加算する。そして、抽出装置１０は、所定の条件を満たす新たなエピソードを抽出する。続いて、抽出装置１０は、区間表１３ｂにおいて２列目以降のイベントを追加する際に、カウンタ１３ｃの値から、追加されるイベントの左端の直前の列のポイント管理変数の値を減算し、閾値「２」との比較対象であるカウンタ１３ｃの値を更新する。このように、抽出装置１０では、カウンタ１３ｃが閾値「２」未満である場合に、選択したエピソードの選択したパートの候補に、選択したイベントの候補ｅが追加されて、エピソードが生成される。また、抽出装置１０では、カウンタ１３ｃが閾値「２」未満でない場合には、新しいエピソードを生成しない。これは、上述したが、イベントデータ１３ａは、複数のアンケートに対して回答した回答者の情報及び回答内容を含むデータが示すイベントのパターンを示すデータを含む。そのため、イベントデータ１３ａが示すイベントのパターンには、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しない排他的なイベントの組合せも出現する。そこで、本実施例に係る抽出装置１０では、１つのアンケートに対して回答した回答者の情報及び回答内容を含むデータが示すイベントのパターンに出現しないようなイベントの組み合わせをウィンドウ幅の大きさよりも多く含むパターンを生成しないようにする。そのため、本実施例に係る抽出装置１０では、排他的なイベントの組み合わせを含むパターンの頻度を算出する処理や、かかるパターンが頻出であるか否かを判定するような処理などの無駄な処理を行うことが抑制される。そのため、本実施例に係る抽出装置１０によれば、効率良くパターンを抽出することができる。
【００８９】
また、本実施例に係る抽出装置１０によれば、１つのカウンタ１３ｃを用いて、閾値「２」との比較を行っているため、簡易な処理で閾値との比較を行うことができる。そのため、抽出装置１０によれば、簡易な処理でパターンを抽出することができる。
【実施例２】
【００９０】
［抽出装置の構成］
次に、実施例２に係る抽出装置について説明する。図１６に示すように、抽出装置４１は、記憶部４３および制御部４４を有する。記憶部４３には、図１に示す実施例１に係る記憶部１３の記憶内容と比較して、更に、最大値カウンタ４３ｄ、最大値スタック４３ｅ、ポイント管理変数スタック４３ｆ、閾値４３ｇが記憶された点が異なる。また、制御部４４は、図１に示す実施例１に係る制御部１４と比較して、初期化部４４ｂ、生成部４４ｃ、バックトラック処理部４４ｄ、カウンタ制御部４４ｅ、抽出部４４ｆを有する点が異なる。なお、以下では、上記の実施例１と同様の機能を果たす各部や機器については図１と同様の符号を付し、その説明を省略する場合がある。
【００９１】
入力部１１は、制御部４４に情報を入力する。例えば、入力部１１は、ユーザからの指示を受け付けて、制御部４４に、抽出処理を実行する指示を入力する。また、入力部１１は、ユーザからの指示を受け付けて、制御部４４に、所定のサーバから後述のイベントデータ１３ａを取得する指示を入力する。また、入力部１１は、ユーザの操作を受け付けて、制御部４４に、区間表１３ｂを入力する。入力部１１のデバイスの一例としては、キーボードやマウスなどが挙げられる。
【００９２】
表示部１２は、各種の情報を表示する。例えば、表示部１２は、後述の抽出部４４ｆにより抽出されたエピソードを後述の表示制御部１４ｇの制御により表示する。
【００９３】
記憶部４３には、実施例１と同様に、イベントデータ１３ａ、区間表１３ｂ、カウンタ１３ｃ、スタック１３ｄが記憶されている。これに加えて、記憶部４３には、最大値カウンタ４３ｄ、最大値スタック４３ｅ、ポイント管理変数スタック４３ｆ、閾値４３ｇが記憶されている。
【００９４】
最大値カウンタ４３ｄには、イベントが追加されるエピソードに含まれる排他的なイベントが、イベントデータ１３ａが示すイベントのパターンに出現する時間が登録される。
【００９５】
最大値スタック４３ｅには、最大値カウンタ４３ｄの値が更新されるたびに、更新前の最大値カウンタ４３ｄの値が格納される。
【００９６】
ポイント管理変数スタック４３ｆには、エピソードにイベントを追加して新たなエピソードを生成する際に、追加されるイベントが追加対象のエピソードのどのイベントよりも後ろである場合に、全ての列のポイント管理変数の値が格納される。
【００９７】
閾値４３ｇには、後述する生成部４４ｃが実行する、カウンタ１３ｃの値が閾値未満であるか否かを判定する処理に用いられる閾値の値が登録される。
【００９８】
制御部４４は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。制御部４４は、取得部１４ａと、初期化部４４ｂと、生成部４４ｃと、バックトラック処理部４４ｄと、カウンタ制御部４４ｅと、抽出部４４ｆと、表示制御部１４ｇとを有する。
【００９９】
初期化部４４ｂは、各種の初期化を行う。例えば、初期化部４４ｂは、取得部１４ａによりイベントデータ１３ａ及び区間表１３ｂが取得された場合には、空エピソードを列挙木における最初の親、すなわち、根に設定する。図１７は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。図１７の例に示すように、初期化部４４ｂは、根のエピソード４６に空エピソード４５を設定する。そして、初期化部４４ｂは、確定部分を空に設定する。
【０１００】
続いて、初期化部４４ｂは、エピソードにイベントを追加して新たなエピソードを生成する際に、追加されるイベントの候補である追加候補に、ｎｕｌｌ値を設定して、追加候補を初期化する。
【０１０１】
続いて、初期化部４４ｂは、最大値カウンタ４３ｄの値を「０」に設定することで、最大値カウンタ４３ｄの値を初期化する。そして、初期化部４４ｂは、区間表１３ｂの全ての列のポイント管理変数の値を「０」に設定することで、ポイント管理変数の初期化を行う。図１８は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。例えば、図１８の例に示すように、初期化部４４ｂは、区間表１３ｂの全ての列のポイント管理変数の値を「０」に設定する。
【０１０２】
続いて、初期化部４４ｂは、処理対象の列に１番目の列を設定する。例えば、初期化部４４ｂは、図１８の例に示す区間表１３ｂの１番目の列（イベントＡ、Ｃ及びＦの組合せが登録された列）に処理対象の列を設定する。
【０１０３】
そして、初期化部４４ｂは、図１８に示すように、カウンタ１３ｃの値を「０」に設定することで、カウンタ１３ｃの初期化を行う。続いて、初期化部４４ｂは、後述する生成部４４ｃによって実行される、カウンタ１３ｃの値が閾値４３ｇの値未満であるか否かを判定する処理に用いられる閾値４３ｇの値を、次のような値に設定する。すなわち、初期化部４４ｂは、かかる閾値４３ｇの値を、エピソードを抽出する際に用いられ、イベントデータ１３ａのイベントパターンを探索する際の時間的な幅であるウィンドウ幅の値に設定する。ウィンドウ幅とは、例えば、時刻「２」から時刻「４」までの時間（２〜４）に発生したイベントパターンを抽出したい場合には、ウィンドウ幅は、「３」となる。以下、ウィンドウ幅が「３」である場合について説明するが、ウィンドウ幅の値はこれに限られない。本実施例の初期化部４４ｂは、図１８に示すように、閾値４３ｇに、「３」の値を設定する。
【０１０４】
生成部４４ｃは、各種のパターンを生成する。生成部４４ｃの一態様について説明する。生成部４４ｃは、まず、根のエピソード４６を選択する。
【０１０５】
次に、生成部４４ｃは、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定する。ここで、本実施例では、確定部分にエピソードが設定された場合には、確定部分よりも後または前にイベントを追加する。ここで、確定部分とは、自身のエピソードを起点とした子孫のエピソードに新たにイベントが追加されないエピソードを指す。以下の説明では、確定部分にエピソードが設定された場合には、確定部分よりも後ろにイベントを追加する場合を例に挙げて説明する。また、本実施例では、確定部分にエピソードが設定された場合には、イベントの追加順序が初期化され、１番目に追加されるイベントがイベントの候補として選択される。なお、本実施例では、空エピソード４６が１番目のパート及び２番目のパートを有する場合について説明する。空エピソード４６が２つのパートを有するため、空エピソード４６の子孫のエピソードもこれらの２つのパートを有する。この場合、生成部４４ｃは、区間表１３ｂが示す追加するイベントの順序にしたがって、選択したエピソードに追加するイベントの候補を１つ特定する。そして、生成部４４ｃは、選択したエピソードのいずれかのパート、または、確定部分よりも後ろのパートとの組合せにおいて、特定したイベントの候補が未選択であるときに、次のように判定する。すなわち、生成部４４ｃは、選択したエピソードに追加するイベントの候補及びイベントが追加されるパートの候補があると判定する。なお、本実施例では、同一のイベントが同一のパートに含まれないものとする。一方、生成部４４ｃは、選択したエピソードのいずれのパート、または、確定部分よりも後ろのパートとの組合せにおいて未選択となるイベントの候補がない場合には、選択したエピソードに追加するイベントの候補がないと判定する。例えば、図１７の例に示す根のエピソード４６が選択された場合には、エピソード４６のいずれのパートとの組合せにおいても、１番目に追加されるイベントであるイベントＡが未選択である。このため、生成部４４ｃは、選択したエピソード４６のパートに追加するイベントＡ、及び、イベントＡが追加されるパート（１番目のパート及び２番目のパートのいずれか）があると判定する。
【０１０６】
なお、生成部４４ｃは、表示制御部１４ｇによりエピソードが表示されるように表示部１２の表示が制御された場合にも、同様に、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定する。また、生成部４４ｃは、カウンタ制御部４４ｅにより、閾値４３ｇの値にカウンタ最大値が加算された場合や、削除されたイベントが削除前のエピソードの最後のイベントでないと判定された場合にも、同様の処理を行う。すなわち、生成部４４ｃは、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートがあるか否かを判定する。
【０１０７】
選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートがある場合には、生成部４４ｃは、イベントの候補を１つ選択するとともに、パートの候補を１つ選択する。例えば、図１７の例において、選択したエピソード４６に追加するイベントＡ及びイベントが追加される１番目のパート及び２番目のパートのいずれかがある場合には、生成部４４ｃは、イベントＡをイベントの候補として１つ選択する。これに加えて、生成部４４ｃは、イベントが追加することができる１番目のパート及び２番目のパートのうち、最も小さい順番の１番目のパートをパートの候補として選択する。なお、以下の説明では、イベントの候補を「イベントの候補ｅ」と表記する場合がある。
【０１０８】
次に、生成部４４ｃは、区間表１３ｂにおいて、処理対象の列が、選択したイベントの候補ｅの識別子が登録された行の左端の列であるか否かを判定する。例えば、図１８に示す場合において、処理対象の列が１番目の列であり、選択したイベントの候補ｅがイベントＡである場合について説明する。この場合、選択したイベントの候補ｅの識別子Ａが登録された行の左端の列が、１番目の列である。そのため、かかる場合、生成部４４ｃは、区間表１３ｂにおいて、処理対象の列が、選択したイベントの候補ｅの識別子Ａが登録された行の左端の列であると判定する。なお、カウンタ制御部４４ｅにより処理対象の列の位置が１つ右の列に移動された場合にも、生成部４４ｃは、処理対象の列が、選択したイベントの候補ｅの識別子が登録された行の左端の列であるか否かを判定する。
【０１０９】
処理対象の列が、選択したイベントの候補ｅの識別子が登録された行の左端の列である場合には、生成部４４ｃは、追加候補に、選択したイベントの候補を設定する。
【０１１０】
続いて、生成部４４ｃは、選択したイベントの候補ｅの追加場所が、選択したエピソードに含まれる他のイベントよりも後ろであるか否かを判定する。選択したイベントの候補ｅの追加場所が、選択したエピソードに含まれる他のイベントよりも後ろである場合には、生成部４４ｃは、最大値カウンタ４３ｄの値が閾値４３ｇの値「３」未満であるか否かを判定する。例えば、図１８に示す場合では、生成部４４ｃは、最大値カウンタ４３ｄの値「０」が、閾値４３ｇの値「３」未満であると判定する。以下の説明では、最大値カウンタ４３ｄの値を、「カウンタ最大値」と表記する場合がある。カウンタ最大値が閾値４３ｇの値「３」未満でない場合には、生成部４４ｃは、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定する上述した処理を行って、かかる処理以降の処理を行う。
【０１１１】
一方、カウンタ最大値が閾値４３ｇの値「３」未満である場合には、生成部４４ｃは、閾値４３ｇの値「３」からカウンタ最大値を減算して、閾値４３ｇの値を更新する。例えば、図１８の例に示す場合において、生成部４４ｃは、閾値４３ｇの値「３」からカウンタ最大値「０」を減算する。
【０１１２】
続いて、生成部４４ｃは、全ての列のポイント管理変数の値をポイント管理変数スタック４３ｆに格納する。そして、生成部４４ｃは、全ての列のポイント管理変数の値を「０」に設定する。続いて、生成部４４ｃは、処理対象の列の位置を１つ右の列に移動させる。その後、生成部４４ｃは、選択したエピソードを確定部分とする。すなわち、生成部４４ｃは、確定部分にエピソードを設定する。
【０１１３】
生成部４４ｃは、確定部分にエピソードが設定された場合、及び、選択したイベントの候補ｅの追加場所が、選択したエピソードに含まれる他のイベントよりも後ろでない場合、次のような処理を行う。すなわち、生成部４４ｃは、区間表１３ｂにおいて、カウンタ１３ｃの値が閾値４３ｇの値「３」未満であるか否かを判定する。例えば、図１８の例に示す場合では、カウンタ１３ｃの値が「０」であるため、生成部４４ｃは、カウンタ１３ｃの値「０」が閾値４３ｇの値「３」未満であると判定する。
【０１１４】
カウンタ１３ｃの値が閾値４３ｇの値「３」未満でない場合には、生成部４４ｃは、選択したエピソードに追加するイベントの候補及びイベントが追加されるパートの候補があるか否かを判定する上述した処理を行い、かかる処理以降の処理を再び行う。
【０１１５】
一方、カウンタ１３ｃの値が閾値４３ｇの値「３」未満である場合には、生成部４４ｃは、選択したエピソードの選択したパートの候補に、選択したイベントの候補を追加して、エピソードを生成する。そして、生成部４４ｃは、生成したエピソードを選択する。図１９は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。例えば、図１９の例に示すように、生成部４４ｃは、選択したエピソード４６の選択したパートの候補に、選択したイベントの候補であるイベントＡを追加して、エピソード４７を生成する。そして、生成部４４ｃは、生成したエピソード４７を選択する。
【０１１６】
このように、本実施例では、カウンタ１３ｃが閾値４３ｇの値「３」未満である場合に、選択したエピソードの選択したパートの候補に、選択したイベントの候補ｅが追加されて、エピソードが生成される。また、本実施例では、カウンタ１３ｃが閾値４３ｇの値「３」未満でない場合には、新しいエピソードを生成しない。これは、上述したが、イベントデータ１３ａは、複数のアンケートに対して回答した回答者の情報及び回答内容を含むデータが示すイベントのパターンを示すデータを含む。そのため、イベントデータ１３ａが示すイベントのパターンには、１つのアンケートに対して回答した回答者の情報及び回答内容を示すイベントのパターンに出現しない排他的なイベントの組合せも出現する。そこで、本実施例では、１つのアンケートに対して回答した回答者の情報及び回答内容を含むデータが示すイベントのパターンに出現しないようなイベントの組み合わせをウィンドウ幅の大きさよりも多く含むパターンを生成しないようにする。そのため、本実施例では、排他的なイベントの組み合わせを含むパターンの頻度を算出する処理や、かかるパターンが頻出であるか否かを判定するような処理などの無駄な処理を行うことが抑制される。そのため、本実施例は、効率良くパターンを抽出することができる。なお、カウンタ１３ｃが閾値４３ｇの値「３」未満でない場合に、エピソードを生成しないことを、「枝刈り」と称する場合もある。
【０１１７】
また、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定した結果、追加するイベントの候補またはパートの候補がない場合には、生成部４４ｃは、次の処理を行う。すなわち、生成部４４ｃは、枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成されたか否かを判定する。枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成された場合には処理が終了される。
【０１１８】
バックトラック処理部４４ｄは、バックトラックを行う。例えば、抽出部４４ｆにより頻出でないと判別された場合に、バックトラック処理部４４ｄは、生成部４４ｃにより生成されたエピソードから最後に追加されたイベントを削除したエピソードを生成する。そして、バックトラック処理部４４ｄは、生成したエピソードを選択する。
【０１１９】
また、バックトラック処理部４４ｄは、生成部４４ｃにより、枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成されていないと判定された場合にも、同様の処理を行う。
【０１２０】
カウンタ制御部４４ｅは、カウンタ１３ｃの値の増減を制御する。例えば、生成部４４ｃにより生成されたエピソードが選択された場合には、カウンタ制御部４４ｅは、カウンタ１３ｃの値をスタック１３ｄに格納する。図２０は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。例えば、図１８の例に示す場合では、カウンタ１３ｃの値が「０」である。そこで、カウンタ制御部４４ｅは、図２０の例に示すように、カウンタ１３ｃの値「０」をスタック１３ｄに格納する。そして、カウンタ制御部４４ｅは、カウンタ１３ｃの値を１つインクリメントする。例えば、図２０の例に示すように、カウンタ制御部４４ｅは、カウンタ１３ｃの値「０」を１つインクリメントして、カウンタ１３ｃの値を「１」に更新する。
【０１２１】
続いて、カウンタ制御部４４ｅは、カウンタ最大値を最大値スタック４３ｅに格納する。例えば、図１８の例に示す場合では、カウンタ最大値、すなわち、最大値カウンタ４３ｄの値が「０」である。そこで、カウンタ制御部４４ｅは、図２０の例に示すように、カウンタ最大値「０」を最大値スタック４３ｅに格納する。そして、カウンタ制御部４４ｅは、最大値カウンタ４３ｄの値を１つインクリメントする。例えば、図２０の例に示すように、カウンタ制御部４４ｅは、最大値カウンタ４３ｄの値「０」を１つインクリメントして、カウンタ最大値を「１」に更新する。
【０１２２】
続いて、カウンタ制御部４４ｅは、区間表１３ｂで、選択したイベントの候補の識別子が登録された行の右端の列のポイント管理変数の値を１つインクリメントする。例えば、図２０に示す場合において、イベントの候補としてイベントＡが選択されているときには、カウンタ制御部４４ｅは、次の処理を行う。すなわち、カウンタ制御部４４ｅは、図２０に示すように、区間表１３ｂで、識別子Ａが登録された１番目の行の右端の列である３番目の列のポイント管理変数の値を１つインクリメントして、かかるポイント管理変数の値を「１」に更新する。
【０１２３】
また、カウンタ制御部４４ｅは、先の生成部４４ｃにより、処理対象の列が、選択したイベントの候補ｅの識別子が登録された行の左端の列でないと判定された場合には、次の処理を行う。すなわち、カウンタ制御部４４ｅは、カウンタ１３ｃの値から、処理対象の列のポイント管理変数の値を減算して、カウンタ１３ｃの値を更新する。そして、カウンタ制御部４４ｅは、処理対象の列の位置を１つ右の列に移動させる。
【０１２４】
また、カウンタ制御部４４ｅは、先のバックトラック処理部４４ｄによりエピソードが選択された場合には、次のような処理を行う。すなわち、カウンタ制御部４４ｅは、スタック１３ｄに最後に格納されたカウント値を取得し、取得したカウント値をカウンタ１３ｃに設定して、カウンタ１３ｃの値をスタック１３ｄから復元する。また、カウンタ制御部４４ｅは、最大値スタック４３ｅに最後に格納されたカウント最大値を取得し、取得したカウント最大値を最大値カウンタ４３ｄに設定して、最大値カウンタ４３ｄの値を最大値スタック４３ｅから復元する。その後、カウンタ制御部４４ｅは、区間表１３ｂにおいて、削除されたイベントの識別子が登録された行の右端に対応する列のポイント管理変数の値を１つデクリメントする。
【０１２５】
そして、カウンタ制御部４４ｅは、削除されたイベントが、削除前のエピソードの最後のイベントであるか否かを判定する。最後のイベントである場合には、カウンタ制御部４４ｅは、選択されたエピソードにおいて設定された確定部分を新たな確定部分として、確定部分を更新する。
【０１２６】
そして、カウンタ制御部４４ｅは、ポイント管理変数スタック４３ｆに最後に格納された全ての列のポイント管理変数の値を取得し、取得した全ての列のポイント管理変数の値のそれぞれをポイント管理変数のそれぞれに設定する。これにより、ポイント管理変数の値がポイント管理変数スタック４３ｆから復元される。そして、カウンタ制御部４４ｅは、閾値４３ｇの値に、カウンタ最大値を加算して、閾値４３ｇの値を更新する。
【０１２７】
抽出部４４ｆは、カウンタ制御部４４ｅによりポイント管理変数の値が１つインクリメントされた場合には、実施例１に係る抽出部１４ｆと同様に、生成されたパターンの頻度を算出する。そして、抽出部４４ｆは、実施例１に係る抽出部１４ｆと同様に、算出した頻度が「１」であるか否かを判定する。そして、算出した頻度が「１」である場合には、抽出部４４ｆは、エピソードは、頻出であると判別する。一方、算出した頻度が「１」でない場合、すなわち「０」である場合には、抽出部４４ｆは、エピソードは、頻出でないと判別する。例えば、図１９の例に示すエピソード４７の頻度が「１」である場合には、抽出部４４ｆは、エピソード４７は、頻出であると判定する。そして、抽出部４４ｆは、頻出であると判別されたエピソードを表示するエピソードとして抽出する。例えば、抽出部４４ｆは、エピソード４７を表示するエピソードとして抽出する。
【０１２８】
表示制御部１４ｇは、各種の情報を表示するように表示部１２の表示を制御する。例えば、表示制御部１４ｇは、抽出部４４ｆにより抽出されたエピソード、例えば、エピソード４７を表示するように表示部１２の表示を制御する。
【０１２９】
制御部４４は、ＡＳＩＣやＦＰＧＡなどの集積回路またはＣＰＵやＭＰＵなどの電子回路である。  
【０１３０】
次に、抽出装置４１が実行する処理の具体例について、図２１〜図３１を参照して説明する。図２１〜図３１は、実施例２に係る抽出装置が実行する処理の一例を説明するための図である。
【０１３１】
例えば、エピソード４７が表示部１２に表示された後に、抽出装置４１は、選択したエピソードに追加するイベントの候補であるイベントＣを選択する。
【０１３２】
ここで、図２０に示すように、区間表１３ｂにおいて、処理対象の列が１番目の列であり、選択したイベントの候補の識別子Ｃが登録された行の左端の列が１番目の列である。そのため、抽出装置４１は、処理対象の列が選択したイベントの候補の左端の列であると判定し、追加候補に、選択したイベントの候補であるイベントＣを設定する。そして、図２０に示すように、カウンタ１３ｃの値「１」が閾値４３ｇの値「３」未満であるため、抽出装置４１は、次のような処理を行う。すなわち、抽出装置４１は、図２１に示すように、選択したエピソード４７の選択したパートに、選択したイベントの候補（イベントＣ）を追加して、エピソード４８を生成する。この際、イベントＣは、エピソード４７のイベントＡを有するパートに追加される。
【０１３３】
そして、図２２に示すように、抽出装置４１は、カウンタ１３ｃの値「１」をスタック１３ｄに格納し、カウンタ１３ｃの値「１」を１つインクリメントして、カウンタ１３ｃの値を「２」に更新する。また、抽出装置４１は、最大値カウンタ４３ｄの値「１」を最大値スタック４３ｅに格納し、最大値カウンタ４３ｄの値「１」を１つインクリメントして、最大値カウンタ４３ｄの値を「２」に更新する。そして、抽出装置４１は、区間表１３ｂで、選択したイベントの候補の識別子Ｃの右端の列である１番目の列のポイント管理変数の値を１つインクリメントして、かかるポイント管理変数の値を「１」に設定する。
【０１３４】
続いて、エピソード４８は頻出であるため、抽出装置４１は、エピソード４８を抽出する。そして、抽出装置４１は、エピソード４８を表示部１２に表示させる。
【０１３５】
ここで、抽出装置４１が、選択したエピソード４８にイベントが追加されるパートの候補として２番目のパートを選択する場合について説明する。この場合、追加されるイベントは、エピソード４８の１番目のパートに含まれるイベントＡ及びＣよりも後ろに追加されることとなる。そのため、抽出装置４１は、まず、カウンタ最大値「２」が閾値４３ｇの値「３」未満であるか否かを判定する。カウンタ最大値「２」が閾値４３ｇの値「３」未満であるため、抽出装置４１は、図２３に示すように、閾値４３ｇの値「３」からカウンタ最大値「２」を減算した値「１」を閾値４３ｇに設定する。そして、図２３に示すように、抽出装置４１は、全ての列のポイント管理変数の値をポイント管理変数スタック４３ｆに格納する。そして、図２３に示すように、抽出装置４１は、全ての列のポイント管理変数の値を「０」に設定する。そして、図２３に示すように、抽出装置４１は、処理対象の列の位置を、１番目の列に移動させる。続いて、抽出装置４１は、選択したエピソード４８を確定部分に設定する。このとき、確定部分にエピソードが設定されたため、抽出装置４１は、１番目に追加されるイベント、すなわち、イベントＡをイベントの候補として選択する。ここで、図２３に示すように、カウンタ１３ｃの値「０」が閾値４３ｇの値「１」未満であるため、抽出装置４１は、次のような処理を行う。すなわち、抽出装置４１は、図２４に示すように、選択したエピソード４８の選択した２番目のパートに、選択したイベントの候補であるイベントＡを追加してエピソード４９を生成する。
【０１３６】
そして、抽出装置４１は、図２５に示すように、カウンタ１３ｃの値「０」をスタック１３ｄに格納する。続いて、抽出装置４１は、カウンタ１３ｃの値「０」を１つインクリメントして、図２５に示すように、カウンタ１３ｃの値を「１」に更新する。また、抽出装置４１は、図２５に示すように、最大値カウンタ４３ｄの値「０」を最大値スタック４３ｅに格納する。そして、抽出装置４１は、最大値カウンタ４３ｄの値「０」を１つインクリメントして、図２５に示すように、最大値カウンタ４３ｄの値を「１」に更新する。そして、抽出装置４１は、区間表１３ｂで、選択したイベントの候補の識別子Ａの右端の列である３番目の列のポイント管理変数の値を１つインクリメントして、図２５に示すように、かかるポイント管理変数の値を「１」に設定する。ここで、エピソード４９が頻出であるため、抽出装置１２は、エピソード４９を抽出し、エピソード４９を表示部１２に表示させる。
【０１３７】
そして、抽出装置４１は、２番目に追加されるイベントであるイベントＣを選択するが、図２５に示すように、カウンタ１３ｃの値が「１」であり、閾値４３ｇの値「１」と同じであるため、イベントＣをエピソード４９に追加しない。すなわち、抽出装置４１は、イベントＣをエピソード４９に追加して新たなエピソードを生成しない。この後、抽出装置４１は、イベントＦ、イベントＤ、イベントＧを順にイベントの候補として選択するが、同様の理由で、選択したイベントＦ、イベントＤ、イベントＧをエピソード４９に追加して新たなエピソードを生成しない。
【０１３８】
そして、抽出装置４１が、６番目に追加されるイベントであるイベントＢをイベントの候補として選択した場合について説明する。この場合には、カウンタ１３ｃの値が「１」であり、最大値カウンタ４３ｄの値が「１」である。また、処理対象の列が３番目の列である。そのため、抽出装置４１は、処理対象の列（３番目の列）が、選択したイベントの候補の識別子Ｂが登録された行の左端の列（４番目の列）でないと判定する。そこで、抽出装置４１は、カウンタ１３ｃの値「１」から、処理対象の列（３番目の列）のポイント管理変数の値「１」を減算した値を、カウンタ１３ｃに設定してカウンタ１３ｃの値を更新する。そして、抽出装置４１は、図２６に示すように、処理対象の列を１つ右の列（４番目の列）に移動させる。
【０１３９】
そして、図２７に示すように、抽出装置４１は、エピソード４９の２番目のパートに、イベントＢを追加してエピソード５０を生成する。エピソード５０が頻出でないため、図２７に示すように、抽出装置４９は、エピソード５０のイベントＢを削除してバックトラックし、エピソード４９の２番目のパートに、イベントＥを追加してエピソード５１を生成する。エピソード５１が頻出でないため、図２７に示すように、抽出装置４１は、エピソード５１のイベントＥを削除してバックトラックする。このときのポイント管理変数、カウンタ１３ｃ、最大値カウンタ４３ｄ、スタック１３ｄ、最大値スタック４３ｅ、ポイント管理変数スタック４３ｆ、閾値４３ｇのそれぞれの値は、図２８の例に示すような値となる。
【０１４０】
エピソード４９に追加できるイベントがないため、抽出装置４１は、図２９に示すように、エピソード４９に最後に追加されたイベントである２番目のパートに含まれるイベントＡをエピソード４９から削除してバックトラックする。そして、抽出装置４１は、スタック１３ｄに最後に格納されたカウント値「０」を取得し、取得したカウント値「０」をカウンタ１３ｃに設定し、最大値スタック４３ｅに最後に格納された値「０」を取得し、取得した値「０」を最大値カウンタ４３ｄに設定する。そして、抽出装置４１は、区間表１３ｂで、選択したイベントの候補の識別子Ａの右端の列である３番目の列のポイント管理変数の値「１」を１つデクリメントして、図３０に示すように、かかるポイント管理変数の値を「０」に設定する。これに加えて、抽出装置４１は、図３０に示すように、処理対象の列を１番目の列に移動させる。
【０１４１】
そして、抽出装置４１は、ポイント管理変数スタック４３ｆに最後に格納された全ての列のポイント管理変数の値を取得し、図３１に示すように、取得した全ての列のポイント管理変数の値のそれぞれを、全ての列のポイント管理変数のそれぞれに設定する。また、抽出装置４１は、スタック１３ｄに最後に格納されたカウント値「２」を取得し、図３１に示すように、取得したカウント値「２」をカウンタ１３ｃに設定する。また、抽出装置４１は、最大値スタック４３ｅに最後に格納された値「２」を取得し、図３１に示すように、取得した値「２」を最大値カウンタ４３ｄに設定する。また、抽出装置４１は、閾値４３ｇの値「１」に、カウンタ最大値「２」を加算した値「３」を閾値４３ｇに設定して、図３１に示すように、閾値４３ｇの値を更新する。そして、抽出装置４１は、以降の処理を行う。
【０１４２】
［処理の流れ］
次に、本実施例に係る抽出装置４１の処理の流れを説明する。図３２及び図３３は、実施例２に係る抽出処理の手順を示すフローチャートである。この抽出処理の実行タイミングとしては様々なタイミングが考えられる。例えば、抽出処理は、抽出処理を実行する指示が入力部１１から入力された場合に、制御部４４により実行される。
【０１４３】
図３２に示すように、取得部１４ａは、記憶部１３からイベントデータ１３ａを取得する（Ｓ２０１）。続いて、取得部１４ａは、記憶部１３から区間表１３ｂを取得する（Ｓ２０２）。
【０１４４】
そして、初期化部４４ｂは、空エピソードを列挙木における最初の親、すなわち、根に設定する（Ｓ２０３）。そして、初期化部４４ｂは、確定部分を空に設定する（Ｓ２０４）。
【０１４５】
続いて、初期化部４４ｂは、エピソードにイベントを追加して新たなエピソードを生成する際に、追加されるイベントの候補である追加候補に、ｎｕｌｌ値を設定して、追加候補を初期化する（Ｓ２０５）。続いて、初期化部４４ｂは、最大値カウンタ４３ｄの値を「０」に設定することで、最大値カウンタ４３ｄの値を初期化する（Ｓ２０６）。
【０１４６】
そして、初期化部４４ｂは、区間表１３ｂの全ての列のポイント管理変数の値を「０」に設定することで、ポイント管理変数の初期化を行う（Ｓ２０７）。
【０１４７】
続いて、初期化部４４ｂは、処理対象の列に１番目の列を設定する（Ｓ２０８）。そして、初期化部４４ｂは、カウンタ１３ｃの値を「０」に設定することで、カウンタ１３ｃの初期化を行う（Ｓ２０９）。続いて、初期化部４４ｂは、閾値４３ｇの値を、ウィンドウ幅の値に設定する（Ｓ２１０）。
【０１４８】
そして、生成部４４ｃは、根のエピソード４６を選択する（Ｓ２１１）。次に、生成部４４ｃは、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定する（Ｓ２１２）。
【０１４９】
選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートがある場合（Ｓ２１２肯定）には、生成部４４ｃは、イベントの候補を１つ選択するとともに、パートの候補を１つ選択する（Ｓ２１３）。次に、生成部４４ｃは、区間表１３ｂにおいて、処理対象の列が、選択したイベントの候補ｅの識別子が登録された行の左端の列であるか否かを判定する（Ｓ２１４）。
【０１５０】
処理対象の列が、選択したイベントの候補ｅの識別子が登録された行の左端の列である場合（Ｓ２１４肯定）には、生成部４４ｃは、追加候補に、選択したイベントの候補を設定する（Ｓ２１５）。
【０１５１】
続いて、生成部４４ｃは、選択したイベントの候補ｅの追加場所が、選択したエピソードに含まれる他のイベントよりも後ろであるか否かを判定する（Ｓ２１６）。選択したイベントの候補ｅの追加場所が、選択したエピソードに含まれる他のイベントよりも後ろである場合（Ｓ２１６肯定）には、生成部４４ｃは、最大値カウンタ４３ｄの値（カウンタ最大値）が閾値４３ｇの値「３」未満であるか否かを判定する（Ｓ２１７）。カウンタ最大値が閾値４３ｇの値「３」未満でない場合（Ｓ２１７否定）には、Ｓ２１２へ戻る。
【０１５２】
一方、カウンタ最大値が閾値４３ｇの値「３」未満である場合（Ｓ２１７肯定）には、生成部４４ｃは、閾値４３ｇの値「３」からカウンタ最大値を減算して、閾値４３ｇの値を更新する（Ｓ２１８）。
【０１５３】
続いて、生成部４４ｃは、全ての列のポイント管理変数の値をポイント管理変数スタック４３ｆに格納する（Ｓ２１９）。そして、生成部４４ｃは、全ての列のポイント管理変数の値を「０」に設定する（Ｓ２２０）。続いて、生成部４４ｃは、処理対象の列の位置を１つ右の列に移動させる（Ｓ２２１）。その後、生成部４４ｃは、確定部分にエピソードを設定して、選択したエピソードを確定部分とする（Ｓ２２２）。
【０１５４】
そして、生成部４４ｃは、区間表１３ｂにおいて、カウンタ１３ｃの値が閾値４３ｇの値「３」未満であるか否かを判定する（Ｓ２２３）。カウンタ１３ｃの値が閾値４３ｇの値「３」未満でない場合（Ｓ２２３否定）には、Ｓ２１２に戻る。
【０１５５】
一方、カウンタ１３ｃの値が閾値４３ｇの値「３」未満である場合（Ｓ２２３肯定）には、生成部４４ｃは、選択したエピソードの選択したパートの候補に、選択したイベントの候補を追加して、エピソードを生成し、生成したエピソードを選択する（Ｓ２２４）。
【０１５６】
そして、カウンタ制御部４４ｅは、カウンタ１３ｃの値をスタック１３ｄに格納する（Ｓ２２５）。そして、カウンタ制御部４４ｅは、カウンタ１３ｃの値を１つインクリメントする（Ｓ２２６）。
【０１５７】
続いて、カウンタ制御部４４ｅは、カウンタ最大値を最大値スタック４３ｅに格納する（Ｓ２２７）。そして、カウンタ制御部４４ｅは、最大値カウンタ４３ｄの値を１つインクリメントする（Ｓ２２８）。
【０１５８】
続いて、カウンタ制御部４４ｅは、区間表１３ｂで、選択したイベントの候補の識別子が登録された行の右端の列のポイント管理変数の値を１つインクリメントする（Ｓ２２９）。
【０１５９】
そして、抽出部４４ｆは、生成されたパターンの頻度を算出する（Ｓ２３０）。そして、抽出部４４ｆは、算出した頻度が「１」であるか否かを判定することにより、頻出であるか否かを判別する（Ｓ２３１）。頻出である場合（Ｓ２３１肯定）には、抽出部４４ｆは、頻出であると判別されたエピソードを表示するエピソードとして抽出する（Ｓ２３２）。
【０１６０】
そして、表示制御部１４ｇは、抽出部４４ｆにより抽出されたエピソードを表示するように表示部１２の表示を制御し（Ｓ２３３）、Ｓ２１２に戻る。
【０１６１】
一方、頻出でない場合（Ｓ２３１否定）に、バックトラック処理部４４ｄは、生成されたエピソードから最後に追加されたイベントを削除したエピソードを生成し、生成したエピソードを選択する（Ｓ２３４）。続いて、カウンタ制御部４４ｅは、スタック１３ｄに最後に格納されたカウント値を取得し、取得したカウント値をカウンタ１３ｃに設定して、カウンタ１３ｃの値をスタック１３ｄから復元する。これに加えて、カウンタ制御部４４ｅは、最大値スタック４３ｅに最後に格納されたカウント最大値を取得し、取得したカウント最大値を最大値カウンタ４３ｄに設定して、最大値カウンタ４３ｄの値を最大値スタック４３ｅから復元する（Ｓ２３５）。その後、カウンタ制御部４４ｅは、区間表１３ｂにおいて、削除されたイベントの識別子が登録された行の右端に対応する列のポイント管理変数の値を１つデクリメントする（Ｓ２３６）。
【０１６２】
そして、カウンタ制御部４４ｅは、削除されたイベントが、削除前のエピソードの最後のイベントであるか否かを判定する（Ｓ２３７）。最後のイベントでない場合（Ｓ２３７否定）には、Ｓ２１２に戻る。最後のイベントである場合（Ｓ２３７肯定）には、カウンタ制御部４４ｅは、選択されたエピソードにおいて設定された確定部分を新たな確定部分として、確定部分を更新する（Ｓ２３８）。
【０１６３】
そして、カウンタ制御部４４ｅは、ポイント管理変数スタック４３ｆに最後に格納された全ての列のポイント管理変数の値を取得し、取得した全ての列のポイント管理変数の値のそれぞれをポイント管理変数のそれぞれに設定する（Ｓ２３９）。そして、カウンタ制御部４４ｅは、閾値４３ｇの値に、カウンタ最大値を加算して、閾値４３ｇの値を更新し（Ｓ２４０）、Ｓ２１２に戻る。
【０１６４】
また、処理対象の列が、選択したイベントの候補ｅの識別子が登録された行の左端の列でない場合（Ｓ２１４否定）には、カウンタ制御部４４ｅは、次の処理を行う。すなわち、カウンタ制御部４４ｅは、カウンタ１３ｃの値から、処理対象の列のポイント管理変数の値を減算して、カウンタ１３ｃの値を更新する（Ｓ２４１）。そして、カウンタ制御部４４ｅは、処理対象の列の位置を１つ右の列に移動させ（Ｓ２４２）、Ｓ２１４に戻る。
【０１６５】
また、追加するイベントの候補またはパートの候補がない場合（Ｓ２１２否定）には、生成部４４ｃは、枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成されたか否かを判定する（Ｓ２４３）。枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成された場合（Ｓ２４３肯定）には、処理を終了する。一方、枝刈りによって生成されなくなったエピソードを除いた全てのエピソードが生成されていない場合（Ｓ２４３否定）には、Ｓ２３４へ進む。
【０１６６】
上述してきたように、抽出装置４１は、確定部分にエピソードが設定された場合には、閾値４３ｇの値から、確定部分に含まれる排他的なイベントが、イベントデータ１３ａが示すイベントのパターンに出現する回数に対応する値を減算する。そのため、抽出装置４１によれば、抽出されないようなエピソードを生成することを抑制することができる。
【実施例３】
【０１６７】
［抽出装置の構成］
次に、実施例３に係る抽出装置について説明する。図３４に示すように、抽出装置６０は、制御部４４を有する。実施例３に係る制御部４４は、図１６に示す実施例２に係る制御部４４と比較して、生成部４４ｃに代えて生成部６４ｃを有する点が異なる。なお、以下では、上記の実施例１、２と同様の機能を果たす各部や機器については図１及び図１６と同様の符号を付し、その説明を省略する場合がある。
【０１６８】
実施例３に係る生成部６４ｃは、選択したエピソードに追加するイベントの候補として、イベントを挙げる際に、確定部分より後ろにイベントが追加される場合には、任意のイベントを挙げることが可能である。これにより、エピソードに追加するイベントの順序が区間表１３ｂが示す追加順序に拘束されることなく、任意のイベントを追加してエピソードを生成することが可能となる。
【０１６９】
［処理の流れ］
次に、本実施例に係る抽出装置６０の処理の流れを説明する。図３５は、実施例３に係る抽出処理の手順を示すフローチャートの一部を示す図である。この抽出処理の実行タイミングとしては様々なタイミングが考えられる。例えば、抽出処理は、抽出処理を実行する指示が入力部１１から入力された場合に、実施例３に係る制御部４４により実行される。
【０１７０】
実施例３に係る抽出処理の手順を示すフローチャートでは、実施例２に係る抽出処理の手順を示すフローチャートと比較して、Ｓ２１２に代えてＳ３０１が実行される点が実施例２に係る抽出処理の手順を示すフローチャートと異なる。
【０１７１】
図３５に示すように、Ｓ２１１での処理の後に、生成部６４ｃは、選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補があるか否かを判定する（Ｓ３０１）。ここで、本実施例では、確定部分にエピソードが設定された場合には、確定部分よりも後または前にイベントを追加する。ここでは、確定部分にエピソードが設定された場合には、確定部分よりも後ろにイベントを追加する場合を例に挙げて説明する。また、生成部６４ｃは、確定部分にエピソードが設定された場合には、イベントの追加順序が初期化され、１番目に追加されるイベントがイベントの候補として選択される。その後、確定部分よりも後ろにイベントを追加する場合には、生成部６４ｃは、任意のイベントをイベントの候補として挙げる。
【０１７２】
選択したエピソードに追加するイベントの候補、及び、イベントが追加されるパートの候補がある場合（Ｓ３０１肯定）には、Ｓ２１３へ進む。一方、選択したエピソードに追加するイベントの候補、または、イベントが追加されるパートの候補がない場合（Ｓ３０１否定）には、Ｓ２４３へ進む。
【０１７３】
実施例３に係る抽出装置６０によれば、エピソードに追加するイベントの順序が区間表１３ｂが示す追加順序に拘束されることなく、任意のイベントを追加してエピソードを生成することができる。
【０１７４】
さて、これまで開示の装置に関する実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では、本発明に含まれる他の実施例を説明する。
【０１７５】
例えば、開示の装置が、確定部分よりも後ろにイベントを追加する場合を例に挙げて説明したが、開示の装置は、これに限定されない。開示の装置は、確定部分よりも前にイベントを追加して同様の処理を行うことができる。
【０１７６】
また、実施例などにおいて説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともできる。
【０１７７】
また、各種の負荷や使用状況などに応じて、実施例などにおいて説明した各処理の各ステップでの処理を任意に細かくわけたり、あるいはまとめたりすることができる。また、ステップを省略することもできる。
【０１７８】
また、各種の負荷や使用状況などに応じて、実施例などにおいて説明した各処理の各ステップでの処理の順番を変更できる。
【０１７９】
また、図示した装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、装置の分散・統合の具体的状態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【０１８０】
［抽出プログラム］
また、上記の抽出装置（１０、４１、６０）の抽出処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することもできる。そこで、以下では、図３６を用いて、上記の抽出装置と同様の機能を有する抽出プログラムを実行するコンピュータの一例を説明する。
【０１８１】
図３６は、抽出プログラムを実行するコンピュータを示す図である。図３６に示すように、コンピュータ３００は、ＣＰＵ（Central  Processing  Unit）３１０、ＲＯＭ（Read  Only  Memory）３２０、ＨＤＤ（Hard  Disk  Drive）３３０、ＲＡＭ（Random  Access  Memory）３４０を有する。これら３００〜３４０の各部は、バス３５０を介して接続される。
【０１８２】
ＨＤＤ３３０には、実施例１で示す各部１４ａ〜１４ｇ、実施例２で示す各部１４ａ、４４ｂ〜４４ｆ、１４ｇ、または、実施例３で示す各部１４ａ、４４ｂ、６４ｃ、４４ｄ〜４４ｆ、１４ｇと同様の機能を発揮する抽出プログラム３３０ａが予め記憶される。なお、抽出プログラム３３０ａについては、適宜分離しても良い。
【０１８３】
そして、ＣＰＵ３１０が、抽出プログラム３３０ａをＨＤＤ３３０から読み出して実行する。
【０１８４】
そして、ＨＤＤ３３０には、イベントデータ及び区間表などが設けられる。
【０１８５】
そして、ＣＰＵ３１０は、イベントデータ及び区間表を読み出してＲＡＭ３４０に格納する。さらに、ＣＰＵ３１０は、ＲＡＭ３４０に格納されたイベントデータ及び区間表を用いて、抽出プログラム３３０ａを実行する。なお、ＲＡＭ３４０に格納される各データは、常に全てのデータがＲＡＭ３４０に格納されなくともよく、全てのデータのうち処理に用いられるデータのみがＲＡＭ３４０に格納されれば良い。
【０１８６】
なお、上記した抽出プログラム３３０ａについては、必ずしも最初からＨＤＤ３３０に記憶させなくともよい。
【０１８７】
例えば、コンピュータ３００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」にプログラムを記憶させておく。そして、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。  
【０１８８】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ３００に接続される「他のコンピュータ（またはサーバ）」などにプログラムを記憶させておく。そして、コンピュータ３００がこれらからプログラムを読み出して実行するようにしてもよい。
【符号の説明】
【０１８９】
１０      抽出装置
１３      記憶部
１３ａ    イベントデータ
１３ｂ    区間表
１３ｃ    カウンタ
１４ｃ    生成部
１４ｅ    カウンタ制御部
１４ｆ    抽出部
【図１】
2014109879.tif 000003
【図２】
2014109879.tif 000004
【図３】
2014109879.tif 000005
【図４】
2014109879.tif 000006
【図５】
2014109879.tif 000007
【図６】
2014109879.tif 000008
【図７】
2014109879.tif 000009
【図８】
2014109879.tif 000010
【図９】
2014109879.tif 000011
【図１０】
2014109879.tif 000012
【図１１】
2014109879.tif 000013
【図１２】
2014109879.tif 000014
【図１３】
2014109879.tif 000015
【図１４】
2014109879.tif 000016
【図１５】
2014109879.tif 000017
【図１６】
2014109879.tif 000018
【図１７】
2014109879.tif 000019
【図１８】
2014109879.tif 000020
【図１９】
2014109879.tif 000021
【図２０】
2014109879.tif 000022
【図２１】
2014109879.tif 000023
【図２２】
2014109879.tif 000024
【図２３】
2014109879.tif 000025
【図２４】
2014109879.tif 000026
【図２５】
2014109879.tif 000027
【図２６】
2014109879.tif 000028
【図２７】
2014109879.tif 000029
【図２８】
2014109879.tif 000030
【図２９】
2014109879.tif 000031
【図３０】
2014109879.tif 000032
【図３１】
2014109879.tif 000033
【図３２】
2014109879.tif 000034
【図３３】
2014109879.tif 000035
【図３４】
2014109879.tif 000036
【図３５】
2014109879.tif 000037
【図３６】
2014109879.tif 000038