(57)【要約】【課題】ターンマッチングにおいて、特定の軸における範囲が指定されていないパターンを用いることができるパターンマッチング方法等を提供する。【解決手段】データの値が取りうる全範囲を複数に区分した木構造を表すように関連付け、前記データの値の取りうる全範囲に含まれる所定の範囲を示すパターンを識別するパターンＩＤを、前記木構造における所定の領域を識別する識別子に関連付ける。そして、データが入力されると入力されたデータの値に関わらず、前記木構造のルートにあたる領域を示す識別子に関連付けられたパターンＩＤを出力する。【選択図】図１
2009163564.tif 000002
【特許請求の範囲】
【請求項１】
データの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶し、
前記各識別子を当該識別子で識別される領域の包含関係を示す木構造を表すように関連付けて記憶し、
前記データの値の取りうる全範囲に含まれる所定の範囲を示すパターンを識別するパターンＩＤを、前記範囲が前記木構造における子にあたる領域を含みかつ前記木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶する記憶部と、
データが入力されると入力されたデータの値に関わらず、前記木構造のルートにあたる領域を示す識別子に関連付けられたパターンＩＤを出力するサーチ部と、
を少なくとも備える、情報処理装置。
【請求項２】
第１のデータの値が取りうる全範囲に含まれる所定の範囲と第２のデータの値が取りうる全範囲に含まれる所定の範囲とを示す一つ以上のパターンに基づいて第１のデータの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶し、
前記各識別子を当該識別子で識別される領域の包含関係を示す第１の木構造を表すように関連付けて記憶し、
前記パターンを識別するパターンＩＤを、当該パターンの示す第１のデータの値に対する範囲が前記第１の木構造における子にあたる領域を含みかつ前記第１の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶する第１の記憶部と、
第２のデータの値が取りうる全範囲を前記各パターンに基づいて複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶し、前記各識別子を当該識別子で識別される領域の包含関係を示す第２の木構造を表すように関連付けて記憶し、前記パターンを識別するパターンＩＤを、当該パターンの示す第２のデータの値に対する範囲が前記第２の木構造における子にあたる領域を含みかつ前記第２の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶する第２の記憶部と、を備え、
前記第１の記憶部は、前記各第２の木構造のルートにあたる領域を示す情報を、前記第１の記憶部における前記パターンＩＤが関連付けられた各識別子と関連付けて記憶し、
第１及び第２のデータが入力されると、入力された第１のデータの値に関わらず、前記第１の木構造のルートにあたる領域を示す識別子に関連付けられた前記第２の木構造を表すように関連付けられた各識別子を参照して前記第２のデータの値を含む範囲を示すパターンＩＤを少なくとも出力するサーチ部と、
をさらに備える、情報処理装置。
【請求項３】
前記サーチ部は、第１及び第２のデータが入力されると、入力された第２のデータの値に関わらず、前記第１のデータの値を含む領域を識別する識別子と関連付けられた前記第２の木構造のルートにあたる領域を示す識別子と関連付けられたパターンＩＤをさらに出力する、
請求項２に記載の情報処理装置。
【請求項４】
前記第１の記憶部は、前記各識別子が前記木構造における子にあたる領域を識別する識別子と関連付けられている場合に、当該識別子と前記子にあたる領域どうしの境界である閾値とを関連付けて記憶し、
前記第２の記憶部は、前記各識別子に、当該第２の記憶部で用いられる第２の木構造のルートにあたる領域を示す情報が関連付けられた前記第１の記憶部における識別子と関連付けられた前記閾値を、第１のデータに対する閾値として関連付けて記憶し、
前記各第２の記憶部は、当該第２の木構造の根又は葉にあたる第２の識別子に、当該第２の木構造のルートにあたる領域を示す情報と関連付けられた前記第１の記憶部における第１の識別子の前記第１の木構造における子にあたる第３の識別子と関連付けられた第２の木構造のルートにあたる領域を示す情報で特定される第２の木構造の根又は葉にあたる第４の識別子を、後継として関連付けて記憶し、
前記サーチ部は、第１及び第２のデータが入力されると、入力された第２のデータの値に関わらず、前記第２の木構造の根又は葉にあたる識別子に関連付けられた後継を辿り、前記後継に関連付けられたパターンＩＤをさらに出力する、
請求項３に記載の情報処理装置。
【請求項５】
データの値が取りうる全範囲に含まれる所定の範囲を示す一つ以上のパターンが入力されると、記憶部に、入力された一つ以上のパターンに基づいて前記データの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶させ、
前記各識別子を当該識別子で識別される領域の包含関係を示す木構造を表すように関連付けて記憶させ、
前記各パターンＩＤを、当該パターンの示す範囲が前記木構造における子にあたる領域を含みかつ前記木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶させる、ツリー生成部と、
を少なくとも備える、情報処理装置。
【請求項６】
第１のデータの値が取りうる全範囲に含まれる所定の範囲と第２のデータの値が取りうる全範囲に含まれる所定の範囲とを示す一つ以上のパターンが入力されると、第１の記憶部に、入力された一つ以上のパターンに基づいて第１のデータの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶させ、前記各識別子を当該識別子で識別される領域の包含関係を示す第１の木構造を表すように関連付けて記憶させ、前記パターンを識別するパターンＩＤを、当該パターンの示す第１のデータの値に対する範囲が前記第１の木構造における子にあたる領域を含みかつ前記第１の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶させ、
第２の記憶部に、第２のデータの値が取りうる全範囲を前記各パターンに基づいて複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶させ、前記各識別子を当該識別子で識別される領域の包含関係を示す第２の木構造を表すように関連付けて記憶させ、前記パターンを識別するパターンＩＤを、当該パターンの示す第２のデータの値に対する範囲が前記第２の木構造における子にあたる領域を含みかつ前記第２の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶させ、
前記各第２の木構造のルートにあたる領域を示す情報を、前記第１の記憶部における前記パターンＩＤが関連付けられた各識別子と関連付けて、第１の記憶部に記憶させる、ツリー生成部と、を少なくとも備える情報処理装置。
【請求項７】
前記ツリー生成部は、
前記第１の記憶部に、前記各識別子が前記木構造における子にあたる領域を識別する識別子と関連付けられている場合に、当該識別子と前記子にあたる領域どうしの境界である閾値とを関連付けて記憶させ、
前記第２の記憶部に、前記各識別子に、当該第２の記憶部で用いられる第２の木構造のルートにあたる領域を示す情報が関連付けられた前記第１の記憶部における識別子と関連付けられた前記閾値を、第１のデータに対する閾値として関連付けて記憶させ、
前記各第２の記憶部に、当該第２の木構造の根又は葉にあたる第２の識別子に、当該第２の木構造のルートにあたる領域を示す情報と関連付けられた前記第１の記憶部における第１の識別子の前記第１の木構造における子にあたる第３の識別子と関連付けられた第２の木構造のルートにあたる領域を示す情報で特定される第２の木構造の根又は葉にあたる第４の識別子を、後継として関連付けて記憶させる、
請求項６に記載の情報処理装置。
【請求項８】
データの値が取りうる全範囲に含まれる所定の範囲を示す一つ以上のパターンが入力されると、記憶部に、入力された一つ以上のパターンに基づいて前記データの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶させ、前記各識別子を当該識別子で識別される領域の包含関係を示す木構造を表すように関連付けて記憶させ、前記各パターンＩＤを、当該パターンの示す範囲が前記木構造における子にあたる領域を含みかつ前記木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶させる、ツリー生成部と、
データが入力されると入力されたデータの値に関わらず、前記記憶部を参照して、前記木構造のルートにあたる領域を示す識別子に関連付けられたパターンＩＤを出力するサーチ部と、
を少なくとも備える、情報処理装置。
【請求項９】
第１のデータの値が取りうる全範囲に含まれる所定の範囲と第２のデータの値が取りうる全範囲に含まれる所定の範囲とを示す一つ以上のパターンが入力されると、第１の記憶部に、入力された一つ以上のパターンに基づいて第１のデータの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶させ、前記各識別子を当該識別子で識別される領域の包含関係を示す第１の木構造を表すように関連付けて記憶させ、前記パターンを識別するパターンＩＤを、当該パターンの示す第１のデータの値に対する範囲が前記第１の木構造における子にあたる領域を含みかつ前記第１の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶させ、
第２の記憶部に、第２のデータの値が取りうる全範囲を前記各パターンに基づいて複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶させ、前記各識別子を当該識別子で識別される領域の包含関係を示す第２の木構造を表すように関連付けて記憶させ、前記パターンを識別するパターンＩＤを、当該パターンの示す第２のデータの値に対する範囲が前記第２の木構造における子にあたる領域を含みかつ前記第２の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶させ、
前記第１の記憶部に、前記各第２の木構造のルートにあたる領域を示す情報を、前記第１の記憶部における前記パターンＩＤが関連付けられた各識別子と関連付けて記憶させる、ツリー生成部と、
第１及び第２のデータが入力されると、入力された第１のデータの値に関わらず、前記第１の木構造のルートにあたる領域を示す識別子に関連付けられた前記第２の木構造を表すように関連付けられた各識別子を参照して前記第２のデータの値を含む範囲を示すパターンＩＤを少なくとも出力するサーチ部と、
を少なくとも備える情報処理装置。
【請求項１０】
前記サーチ部は、第１及び第２のデータが入力されると、入力された第２のデータの値に関わらず、前記第１のデータの値を含む領域を識別する識別子と関連付けられた前記第２の木構造のルートにあたる領域を示す識別子と関連付けられたパターンＩＤをさらに出力する、
請求項９に記載の情報処理装置。
【請求項１１】
前記ツリー生成部は、
前記第１の記憶部に、前記各識別子が前記木構造における子にあたる領域を識別する識別子と関連付けられている場合に、当該識別子と前記子にあたる領域どうしの境界である閾値とを関連付けて記憶させ、
前記第２の記憶部に、前記各識別子に、当該第２の記憶部で用いられる第２の木構造のルートにあたる領域を示す情報が関連付けられた前記第１の記憶部における識別子と関連付けられた前記閾値を、第１のデータに対する閾値として関連付けて記憶させ、
前記各第２の記憶部に、当該第２の木構造の根又は葉にあたる第２の識別子に、当該第２の木構造のルートにあたる領域を示す情報と関連付けられた前記第１の記憶部における第１の識別子の前記第１の木構造における子にあたる第３の識別子と関連付けられた第２の木構造のルートにあたる領域を示す情報で特定される第２の木構造の根又は葉にあたる第４の識別子を、後継として関連付けて記憶させ、
前記サーチ部は、第１及び第２のデータが入力されると、入力された第２のデータの値に関わらず、前記第２の木構造の根又は葉にあたる識別子に関連付けられた後継を辿り、前記後継に関連付けられたパターンＩＤをさらに出力する、
請求項１０または請求項１１に記載の情報処理装置。
【請求項１２】
コンピュータによる情報処理方法であって、
第１のデータの値が取りうる全範囲に含まれる所定の範囲と第２のデータの値が取りうる全範囲に含まれる所定の範囲とを示す一つ以上のパターンに基づいて第１のデータの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶し、
前記各識別子を当該識別子で識別される領域の包含関係を示す第１の木構造を表すように関連付けて記憶し、
前記パターンを識別するパターンＩＤを、当該パターンの示す第１のデータの値に対する範囲が前記第１の木構造における子にあたる領域を含みかつ前記第１の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶する第１の記憶ステップと、
第２のデータの値が取りうる全範囲を前記各パターンに基づいて複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶し、前記各識別子を当該識別子で識別される領域の包含関係を示す第２の木構造を表すように関連付けて記憶し、前記パターンを識別するパターンＩＤを、当該パターンの示す第２のデータの値に対する範囲が前記第２の木構造における子にあたる領域を含みかつ前記第２の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶する第２の記憶部ステップと、
前記第２の記憶ステップで記憶される、第２の木構造のルートにあたる領域を示す識別子を、前記第１の記憶ステップで記憶される前記パターンＩＤが関連付けられた各識別子と関連付けるステップと、
第１及び第２のデータが入力されると、入力された第１のデータの値に関わらず、前記第１の木構造のルートにあたる領域を示す識別子に関連付けられた前記第２の記憶ステップで記憶される前記第２のデータの値を含む範囲を示すパターンＩＤを少なくとも出力するサーチステップと、
を含む、情報処理方法。
【請求項１３】
コンピュータを、
第１のデータの値が取りうる全範囲に含まれる所定の範囲と第２のデータの値が取りうる全範囲に含まれる所定の範囲とを示す一つ以上のパターンに基づいて第１のデータの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶し、
前記各識別子を当該識別子で識別される領域の包含関係を示す第１の木構造を表すように関連付けて記憶し、
前記パターンを識別するパターンＩＤを、当該パターンの示す第１のデータの値に対する範囲が前記第１の木構造における子にあたる領域を含みかつ前記第１の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶する第１の記憶手段、
第２のデータの値が取りうる全範囲を前記各パターンに基づいて複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶し、前記各識別子を当該識別子で識別される領域の包含関係を示す第２の木構造を表すように関連付けて記憶し、前記パターンを識別するパターンＩＤを、当該パターンの示す第２のデータの値に対する範囲が前記第２の木構造における子にあたる領域を含みかつ前記第２の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶する第２の記憶手段、として機能させ、
前記第１の記憶手段は、前記各第２の木構造のルートにあたる領域を示す情報を、前記第１の記憶手段における前記パターンＩＤが関連付けられた各識別子と関連付けて記憶し、
第１及び第２のデータが入力されると、入力された第１のデータの値に関わらず、前記第１の木構造のルートにあたる領域を示す識別子に関連付けられた前記第２の木構造を表すように関連付けられた各識別子を参照して前記第２のデータの値を含む範囲を示すパターンＩＤを少なくとも出力するサーチ手段と、
としてさらに機能させるプログラム。
【請求項１４】
コンピュータにより用いられるデータ構造であって、
第１のデータの値が取りうる全範囲に含まれる所定の範囲と第２のデータの値が取りうる全範囲に含まれる所定の範囲とを示す一つ以上のパターンに基づいて第１のデータの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子とが関連付けられ、
前記各識別子が当該識別子で識別される領域の包含関係を示す第１の木構造を表すように関連付けられ、
前記パターンを識別するパターンＩＤが、当該パターンの示す第１のデータの値に対する範囲が前記木構造における子にあたる領域を含みかつ前記第１の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けられ、
第２のデータの値が取りうる全範囲を前記各パターンに基づいて複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子とが関連付けられ、前記各識別子が当該識別子で識別される領域の包含関係を示す第２の木構造を表すように関連付けられ、前記パターンを識別するパターンＩＤが、当該パターンの示す第２のデータの値に対する範囲が前記木構造における子にあたる領域を含みかつ前記第２の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けられ、
前記第２の木構造のルートにあたる領域を示す識別子は、前記第１の木構造を表すように関連付けられた各識別子において前記パターンＩＤが関連付けられたものと関連付けられる、データ構造。
【発明の詳細な説明】
【技術分野】
【０００１】
あらかじめ、要求するデータの条件と、要求するデータを受信した場合に実行する機能を登録しておき、外部システムから入力されるデータが要求するデータの条件に合致する場合に、登録された機能を実行するようなサーバプログラム（ルールエンジンと呼ばれる）がある。
【背景技術】
【０００２】
図６６は本発明の想定しているシステムの構成を表している。パターンマッチングサーバは本発明が適用されているサーバマシンである。パターンマッチングサーバは、前述のルールエンジンとしても機能し、入力されたデータがあらかじめ記憶する所定の条件に合致するかどうかを判定する。リーダはＲＦタグからＲＦタグＩＤを読み取る機器であり、ＲＦタグＩＤを読み取ると、ＲＦタグＩＤとリーダＩＤをパターンマッチングサーバに通知する。
【０００３】
パターンマッチングサーバは、通知されたＲＦタグＩＤやリーダＩＤといったデータが所定の条件を満たすかどうかを調べる。この動作をおこなうため、パターンマッチングサーバは、あらかじめ、データの条件を記憶している。ＲＦタグＩＤとリーダＩＤがパターンマッチングサーバに通知される例では、ＲＦタグＩＤの範囲とリーダＩＤの範囲がデータの条件として記憶されている。このようなデータの条件をパターンと呼ぶ。すなわち、パターンは、それを識別するための情報（パターンＩＤ）と、データの条件とが関連付けられた情報である。
【０００４】
パターンマッチングサーバは、リーダからデータを受け取ると、記憶しているパターンの内、マッチするものがあるかどうかを調べる。ＲＦタグＩＤとリーダＩＤとを含むデータが入力されるパターンマッチングサーバの例では、入力データのＲＦタグＩＤが所定のパターンに関連付けられているＲＦタグＩＤの範囲に含まれており、かつ、その入力データのリーダＩＤが、そのパターンに関連づけられているリーダＩＤの範囲に含まれている場合、その入力データが、そのパターンに「マッチする」という。つまり、受け取ったデータＸが、パターンＹに含まれるデータの条件を満たす場合、データＸはパターンＹにマッチしている。そして、マッチするものがある場合、パターンマッチングサーバは、そのことを検知する。
【０００５】
また、ルールエンジンとして機能するパターンマッチングサーバは、検知した後に何らかの機能を実行する。実行される機能として、例えば、特定のマシンに対する条件にマッチしたことの通知や、データの加工がある。また、それらの機能は、固定的に設定したり、指定するパターンに付随して設定することができる。
【０００６】
パターンマッチングサーバに対して、パターンを複数設定する（記憶させる）ことができる。
【０００７】
ＲＦタグＩＤとリーダＩＤは非特許文献１におけるｘ軸の値とｙ軸の値と考えることができる。
【０００８】
関連する技術が非特許文献１に記載されている。非特許文献１には、ｘ軸の値の範囲とｙ軸の値の範囲が条件として指定され、ｘ軸の値とｙ軸の値のペアが与えられたときに、それが条件にマッチするかどうかを判定する方法が記載されている。非特許文献１に記載される方法では、上記条件が複数指定されている場合に、与えられるｘ軸の値とｙ軸の値のペアがどの条件にマッチしているかを効率的に求める。
【０００９】
以降、ｘ軸の値の範囲とｙ軸の値の範囲が指定された条件をパターンと呼ぶ。
【非特許文献１】V. K. Vaishnavi, “Computing Point Enclosures”, IEEE TRANSACTIONS ON COMPUTERS, VOL. C-31. NO. 1. JANUARY 1982.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
非特許文献１では、ｘ軸の値とｙ軸の値とのペアに対する処理を行う場合には、パターンとしてｘ軸の範囲とｙ軸の範囲の両方が指定されていることを前提としており、どちらか一方のみが指定される場合は正しく機能しない。どちらか一方のみが指定される状況として、データを要求する者が、特定のＲＦタグＩＤに興味を持っているが、それがどのリーダで読み取られたかには、興味がないような状況が考えられる。
【００１１】
また、非特許文献１では、入力されるデータが、ｘ軸の値とｙ軸の値の両方を持っていることを前提としており、どちらか一方の値のみを持っている場合は正しく機能しない。入力されるデータが、どちらか一方のみの値を持っている状況として、あるリーダが、そのＩＤを通知したくないためにパターンマッチングサーバに読み取ったＲＦタグＩＤのみを通知するような状況が考えられる。また、特定のタグＩＤをアプリケーションに通知したくないために、リーダがリーダＩＤのみを通知するような状況が考えられる。
【００１２】
［発明の目的］
本発明は、上記課題を鑑みてなされたものであって、パターンマッチングにおいて、特定の軸における範囲が指定されていないパターンを用いることができるパターンマッチング方法等を提供することを目的とする。
【００１３】
また、本発明は、パターンマッチングにおいて、入力されるデータが特定の軸における値を持っていない場合にも機能するパターンマッチング方法等を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記課題を解決する発明の一態様は、データの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶し、前記各識別子を当該識別子で識別される領域の包含関係を示す木構造を表すように関連付けて記憶し、前記データの値の取りうる全範囲に含まれる所定の範囲を示すパターンを識別するパターンＩＤを、前記範囲が前記木構造における子にあたる領域を含みかつ前記木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶する記憶部と、データが入力されると入力されたデータの値に関わらず、前記木構造のルートにあたる領域を示す識別子に関連付けられたパターンＩＤを出力するサーチ部と、を少なくとも備える、情報処理装置である。
【００１５】
また、上記課題を解決する発明の他の態様は、第１のデータの値が取りうる全範囲に含まれる所定の範囲と第２のデータの値が取りうる全範囲に含まれる所定の範囲とを示す一つ以上のパターンに基づいて第１のデータの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶し、前記各識別子を当該識別子で識別される領域の包含関係を示す第１の木構造を表すように関連付けて記憶し、前記パターンを識別するパターンＩＤを、当該パターンの示す第１のデータの値に対する範囲が前記第１の木構造における子にあたる領域を含みかつ前記第１の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶する第１の記憶部と、第２のデータの値が取りうる全範囲を前記各パターンに基づいて複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶し、前記各識別子を当該識別子で識別される領域の包含関係を示す第２の木構造を表すように関連付けて記憶し、前記パターンを識別するパターンＩＤを、当該パターンの示す第２のデータの値に対する範囲が前記第２の木構造における子にあたる領域を含みかつ前記第２の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶する第２の記憶部と、を備え、前記第１の記憶部は、前記各第２の木構造のルートにあたる領域を示す情報を、前記第１の記憶部における前記パターンＩＤが関連付けられた各識別子と関連付けて記憶し、第１及び第２のデータが入力されると、入力された第１のデータの値に関わらず、前記第１の木構造のルートにあたる領域を示す識別子に関連付けられた前記第２の木構造を表すように関連付けられた各識別子を参照して前記第２のデータの値を含む範囲を示すパターンＩＤを少なくとも出力するサーチ部と、をさらに備える、情報処理装置である。
【００１６】
また、上記課題を解決する発明の他の態様は、データの値が取りうる全範囲に含まれる所定の範囲を示す一つ以上のパターンが入力されると、記憶部に、入力された一つ以上のパターンに基づいて前記データの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶させ、前記各識別子を当該識別子で識別される領域の包含関係を示す木構造を表すように関連付けて記憶させ、前記各パターンＩＤを、当該パターンの示す範囲が前記木構造における子にあたる領域を含みかつ前記木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶させる、ツリー生成部と、を少なくとも備える、情報処理装置である。
【００１７】
また、上記課題を解決する発明の他の態様は、第１のデータの値が取りうる全範囲に含まれる所定の範囲と第２のデータの値が取りうる全範囲に含まれる所定の範囲とを示す一つ以上のパターンが入力されると、第１の記憶部に、入力された一つ以上のパターンに基づいて第１のデータの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶させ、前記各識別子を当該識別子で識別される領域の包含関係を示す第１の木構造を表すように関連付けて記憶させ、前記パターンを識別するパターンＩＤを、当該パターンの示す第１のデータの値に対する範囲が前記第１の木構造における子にあたる領域を含みかつ前記第１の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶させ、第２の記憶部に、第２のデータの値が取りうる全範囲を前記各パターンに基づいて複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶させ、前記各識別子を当該識別子で識別される領域の包含関係を示す第２の木構造を表すように関連付けて記憶させ、前記パターンを識別するパターンＩＤを、当該パターンの示す第２のデータの値に対する範囲が前記第２の木構造における子にあたる領域を含みかつ前記第２の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶させ、前記各第２の木構造のルートにあたる領域を示す情報を、前記第１の記憶部における前記パターンＩＤが関連付けられた各識別子と関連付けて、第１の記憶部に記憶させる、ツリー生成部と、を少なくとも備える情報処理装置である。
【００１８】
また、上記課題を解決する発明の他の態様は、データの値が取りうる全範囲に含まれる所定の範囲を示す一つ以上のパターンが入力されると、記憶部に、入力された一つ以上のパターンに基づいて前記データの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶させ、前記各識別子を当該識別子で識別される領域の包含関係を示す木構造を表すように関連付けて記憶させ、前記各パターンＩＤを、当該パターンの示す範囲が前記木構造における子にあたる領域を含みかつ前記木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶させる、ツリー生成部と、データが入力されると入力されたデータの値に関わらず、前記記憶部を参照して、前記木構造のルートにあたる領域を示す識別子に関連付けられたパターンＩＤを出力するサーチ部と、を少なくとも備える、情報処理装置である。
【００１９】
また、上記課題を解決する発明の他の態様は、第１のデータの値が取りうる全範囲に含まれる所定の範囲と第２のデータの値が取りうる全範囲に含まれる所定の範囲とを示す一つ以上のパターンが入力されると、第１の記憶部に、入力された一つ以上のパターンに基づいて第１のデータの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶させ、前記各識別子を当該識別子で識別される領域の包含関係を示す第１の木構造を表すように関連付けて記憶させ、前記パターンを識別するパターンＩＤを、当該パターンの示す第１のデータの値に対する範囲が前記第１の木構造における子にあたる領域を含みかつ前記第１の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶させ、第２の記憶部に、第２のデータの値が取りうる全範囲を前記各パターンに基づいて複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶させ、前記各識別子を当該識別子で識別される領域の包含関係を示す第２の木構造を表すように関連付けて記憶させ、前記パターンを識別するパターンＩＤを、当該パターンの示す第２のデータの値に対する範囲が前記第２の木構造における子にあたる領域を含みかつ前記第２の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶させ、前記第１の記憶部に、前記各第２の木構造のルートにあたる領域を示す情報を、前記第１の記憶部における前記パターンＩＤが関連付けられた各識別子と関連付けて記憶させる、ツリー生成部と、第１及び第２のデータが入力されると、入力された第１のデータの値に関わらず、前記第１の木構造のルートにあたる領域を示す識別子に関連付けられた前記第２の木構造を表すように関連付けられた各識別子を参照して前記第２のデータの値を含む範囲を示すパターンＩＤを少なくとも出力するサーチ部と、を少なくとも備える情報処理装置である。
【００２０】
また、上記課題を解決する発明の他の態様は、コンピュータによる情報処理方法であって、第１のデータの値が取りうる全範囲に含まれる所定の範囲と第２のデータの値が取りうる全範囲に含まれる所定の範囲とを示す一つ以上のパターンに基づいて第１のデータの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶し、前記各識別子を当該識別子で識別される領域の包含関係を示す第１の木構造を表すように関連付けて記憶し、前記パターンを識別するパターンＩＤを、当該パターンの示す第１のデータの値に対する範囲が前記第１の木構造における子にあたる領域を含みかつ前記第１の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶する第１の記憶ステップと、第２のデータの値が取りうる全範囲を前記各パターンに基づいて複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶し、前記各識別子を当該識別子で識別される領域の包含関係を示す第２の木構造を表すように関連付けて記憶し、前記パターンを識別するパターンＩＤを、当該パターンの示す第２のデータの値に対する範囲が前記第２の木構造における子にあたる領域を含みかつ前記第２の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶する第２の記憶部ステップと、前記第２の記憶ステップで記憶される、第２の木構造のルートにあたる領域を示す識別子を、前記第１の記憶ステップで記憶される前記パターンＩＤが関連付けられた各識別子と関連付けるステップと、第１及び第２のデータが入力されると、入力された第１のデータの値に関わらず、前記第１の木構造のルートにあたる領域を示す識別子に関連付けられた前記第２の記憶ステップで記憶される前記第２のデータの値を含む範囲を示すパターンＩＤを少なくとも出力するサーチステップと、を含む、情報処理方法である。
【００２１】
また、上記課題を解決する発明の他の態様は、コンピュータを、第１のデータの値が取りうる全範囲に含まれる所定の範囲と第２のデータの値が取りうる全範囲に含まれる所定の範囲とを示す一つ以上のパターンに基づいて第１のデータの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶し、前記各識別子を当該識別子で識別される領域の包含関係を示す第１の木構造を表すように関連付けて記憶し、前記パターンを識別するパターンＩＤを、当該パターンの示す第１のデータの値に対する範囲が前記第１の木構造における子にあたる領域を含みかつ前記第１の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶する第１の記憶手段、第２のデータの値が取りうる全範囲を前記各パターンに基づいて複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子と関連付けて記憶し、前記各識別子を当該識別子で識別される領域の包含関係を示す第２の木構造を表すように関連付けて記憶し、前記パターンを識別するパターンＩＤを、当該パターンの示す第２のデータの値に対する範囲が前記第２の木構造における子にあたる領域を含みかつ前記第２の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けて記憶する第２の記憶手段、として機能させ、前記第１の記憶手段は、前記各第２の木構造のルートにあたる領域を示す情報を、前記第１の記憶手段における前記パターンＩＤが関連付けられた各識別子と関連付けて記憶し、第１及び第２のデータが入力されると、入力された第１のデータの値に関わらず、前記第１の木構造のルートにあたる領域を示す識別子に関連付けられた前記第２の木構造を表すように関連付けられた各識別子を参照して前記第２のデータの値を含む範囲を示すパターンＩＤを少なくとも出力するサーチ手段と、としてさらに機能させるプログラムである。
【００２２】
また、上記課題を解決する発明の他の態様は、コンピュータにより用いられるデータ構造であって、第１のデータの値が取りうる全範囲に含まれる所定の範囲と第２のデータの値が取りうる全範囲に含まれる所定の範囲とを示す一つ以上のパターンに基づいて第１のデータの値が取りうる全範囲を複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子とが関連付けられ、前記各識別子が当該識別子で識別される領域の包含関係を示す第１の木構造を表すように関連付けられ、前記パターンを識別するパターンＩＤが、当該パターンの示す第１のデータの値に対する範囲が前記木構造における子にあたる領域を含みかつ前記第１の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けられ、第２のデータの値が取りうる全範囲を前記各パターンに基づいて複数に区分した各領域、複数の前記領域の和集合である領域、前記領域と前記和集合との和集合である領域、又は、前記和集合どうしの和集合である領域を示す情報と当該領域を識別する識別子とが関連付けられ、前記各識別子が当該識別子で識別される領域の包含関係を示す第２の木構造を表すように関連付けられ、前記パターンを識別するパターンＩＤが、当該パターンの示す第２のデータの値に対する範囲が前記木構造における子にあたる領域を含みかつ前記第２の木構造における前記子にあたる領域の親にあたる領域を含まない場合に前記子にあたる領域を識別する識別子に関連付けられ、前記第２の木構造のルートにあたる領域を示す識別子は、前記第１の木構造を表すように関連付けられた各識別子において前記パターンＩＤが関連付けられたものと関連付けられる、データ構造である。
【発明の効果】
【００２３】
本発明によれば、パターンマッチングにおいて、特定の軸における範囲が指定されていないパターンを用いることができるパターンマッチング方法等が提供される。
【００２４】
また、本発明によれば、パターンマッチングにおいて、入力されるデータが特定の軸における値を持っていない場合にも機能する。パターンマッチング方法等が提供される。
【発明を実施するための最良の形態】
【００２５】
この明細書では、特定の軸に関して範囲が指定されなかった場合、その軸に関しては考慮しないことを示していることとする。例えば、パターンとしてｘ軸の範囲のみが指定されている場合、入力されるデータのｙ軸の値が何であろうとも、ｘ軸の値のみによって、そのデータがパターンにマッチするかどうかが決定する。
【００２６】
この明細書では、パターンにおいて、範囲の指定がないことを＊で表す。
【００２７】
この明細書では、入力されるデータにおいて、特定の軸に関して値が指定されなかった場合、その軸に関しては値が不明であることを示していることとする。
【００２８】
この明細書では、入力されるデータが特定の軸に関して値が指定されなかった場合（値が不明である場合）、その軸値を？で表す。例えば、ｘ軸の値を持たない場合、ｘ＝？と表記される。
【００２９】
［第１の実施の形態］
次に、第１の実施の形態について図面を参照して説明する。図１は、第１の実施の形態の構成例を示す図面である。図１によれば、第１の実施の形態の構成例は、ツリー生成部１１、定義域記憶部１２、ツリー記憶部１３を有する情報処理装置である。第１の実施の形態では、扱うデータが一次元（ここではｘ軸とする）の場合について説明する。
【００３０】
ツリー生成部１１は、一つ以上のパターンを入力として受け取る。また、ツリー生成部１１は、定義域記憶部１２からｘ軸の値として取りうる値の範囲を示す情報を読み出す。そして、ツリー生成部１１は、入力されたパターンと定義域記憶部１２から読み出した情報とを用いて、木構造のデータを生成し、ツリー記憶部１３へ出力する。
【００３１】
ツリー生成部１１は、木構造のデータを生成する際、スケルトン生成処理部１１１と、パターン挿入処理部１１２とを用いる。スケルトン生成処理部１１１、パターン挿入処理部１１２は後述される。
【００３２】
ツリー生成部１１は、例えば、半導体集積回路等によるハードウエアとして実現しても良い。また、コンピュータに備わるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）が所定のプログラムを読み込むことにより実現されても良い。
【００３３】
第１の実施の形態では、扱うデータが一次元の場合について説明するので、パターンは次のような情報となる。つまり、パターンは、パターンＩＤと、ｘ軸におけるデータの範囲とが関連付けられた情報である。パターンには、その範囲の最小値（以下、ｍｉｎと記載することがある）及び最大値（以下、ｍａｘと記載することがある）が関連付けられる。
【００３４】
ここで、表記について補足する。パターンUに対し、x軸において関連付けられた範囲の最小値を、「Ｕ．ｒａｎｇｅ［ｘ］．ｍｉｎ」と記載することがある。「Ｕ」はパターンＩＤを表す。「［ｘ］」はｘ軸におけるものであることを表す。「ｒａｎｇｅ［ｘ］」は、ｘ軸における範囲であることを表す。「ｍｉｎ」は上述の最小値であることを表す。
【００３５】
「．」はその左側の表記により特定される情報に、右側の表記により特定される情報が関連付けられていることを表す。
【００３６】
次に、定義域記憶部１２について説明する。定義域記憶部１２は、ｘ軸の値が取りうる範囲を示す情報を記憶する。例えば、定義域記憶部１２は、ｘ軸の値として指定できる値の最小値であるｘ−ｍｉｎと、ｘ軸の値として指定できる値の最大値であるｘ−ｍａｘとを記憶しても良い。
【００３７】
定義域記憶部１２は、例えば、半導体集積回路等によるメモリに上記のような情報を記憶させることで実現することができる。また、コンピュータで読み取り可能な記録媒体や、磁気記憶装置、ディスク装置等を用いて実現することも可能である。
【００３８】
ツリー生成部１１が入力として受け取るパターンの例について説明する。図２は、扱うデータが一次元（ｘ軸のみ）の場合の、入力されるパターンの例を示す図である。パターンＡは、パターンＩＤがＡであり、その範囲がＡ１からＡ２の範囲である。パターンＢは、パターンＩＤがＢであり、その範囲がＢ１からＢ２の範囲である。複数のパターンは、図２に例示するようにオーバーラップしてもよく、また、複数のパターンにおいて範囲の端点が一致していても良い。複数のパターンにおいて、それらの範囲の間で満たされるべき制約条件はない。
【００３９】
ツリー生成部１１が入力として受け取るパターンと、定義域記憶部１２から読み出した、ｘ軸の値が取りうる範囲との関係の例について説明する。図３は、これらの関係を例示する図である。ｘ−ｍｉｎはｘとして指定できる値の最小値、ｘ−ｍａｘはｘとして指定できる値の最大値として、ツリー生成部１１が定義域記憶部１２から読み出した値である。入力として図２に例示したパターンＡ及びＢを受け取った場合を仮定する。これらによりｘ軸は５つの範囲に区別されうる。すなわち、ｘ−ｍｉｎからＡ１までであるｈ１、パターンAが指定する範囲でパターンBとオーバーラップしない範囲であるｈ２、パターンAとパターンBがオーバーラップする部分であるｈ３、パターンBが指定する範囲でパターンAとオーバーラップしない範囲であるｈ４、パターンBが指定する範囲の最大値からｘ−ｍａｘであるｈ５、である。
【００４０】
次に、ツリー記憶部１３が記憶する情報について説明する。ツリー記憶部１３が記憶する情報は、ツリー生成部１１によって生成され、出力される。生成方法は後に詳述される。また、ツリー記憶部１３は、例えば、半導体集積回路等によるメモリに後述する情報を記憶させることで実現することができる。また、コンピュータで読み取り可能な記録媒体や、磁気記憶装置、ディスク装置等を用いて実現することも可能である。
【００４１】
図４は、ツリー記憶部１３が記憶する情報の構造を例示する概念図である。図２に示すパターンが入力された場合に、ツリー記憶部１３へ出力される木構造のデータ例が図４に例示される。図４に示すａ、ｂ、ｃ、ｄ、ｅ、ｆ、ｇ、ｈ、ｉは、木構造におけるノードを表している。この構造は、非特許文献１で定義されているsegment tree of order 1（以下、一次元セグメントツリーと記す）と類似している。
【００４２】
図５に示す表は、図４に示されたツリー構造における各ノードと関連付けられる情報を例示する表である。各ノードは二分木を形成する。このため、親ノードは、２つの子ノードへの参照と関連付けられる。２つの子ノードを区別するために、左子、右子と表現する（以下、左子のことをｌｅｆｔ、右子のことをｒｉｇｈｔと記載することがある）。子ノードへの参照は、例えばＣ言語に言うポインタや、Ｊａｖａ（登録商標）における参照型データであってもよい。当然ながら、これらに限定されない。
【００４３】
各ノードは閾値と関連付けられる（以下、閾値をｔｈｒｅｓｈｏｌｄと記載することがある）。閾値は後に説明される。
【００４４】
各ノードは、一つ以上のパターンＩＤと関連付けられる場合がある。これをノードセットと呼ぶ（以下、ノードセットをｎＳｅｔと記載することがある）。ノードセットは、空集合又は一つ以上のパターンＩＤを含む集合である。ノードセットは後に説明される。
【００４５】
各ノードは、データの値の範囲と関連付けられている。各ノードは、データの値の範囲の最小値（以下、ｍｉｎと記載することがある）及び最大値（以下、ｍａｘと記載することがある）と関連付けられる。
【００４６】
各ノードは、自身がルートノードであるか否かを示す情報（以下、ｆｌａｇと記載することがある）と関連付けられている。
【００４７】
図４に示された木構造のデータについて、図３を併用して説明する。図４における各ノードはデータの値の範囲と関連付けられている。図６に示すように、ノードａは、ｘ−ｍｉｎからｘ−ｍａｘまでの範囲と関連付けられている。このほか、ノードｂはｘ−ｍｉｎからＡ２までの範囲と、ノードｃはＡ２からｘ−ｍａｘまでの範囲と、ノードｄはｘ−ｍｉｎからＢ１までの範囲と、ノードｅはＢ１からＡ２までの範囲と、ノードｆはＡ２からＢ２までの範囲と、ノードｇはＢ２からｘ−ｍａｘまでと、ノードｈはｘ−ｍｉｎからＡ１までの範囲と、ノードｉはＡ１からＢ１までの範囲とそれぞれ関連付けられている。図４の例は、ｘ軸における値が小さい範囲と関連付けられる子ノードを左子とした例であるが、もちろんこれに限定されない。また、図４の例は、左側の方が木の深さが深くなっているが、もちろんこれに限定されない。
【００４８】
親ノードと関連付けられる範囲は、２つの子ノードと関連付けられた範囲をあわせた範囲である。同じ親ノードに関連付けられる２つの子ノードには、境界を境に隣あう範囲が関連付けられる。親ノードは、２つの子ノードの範囲の間の境界を、閾値として保持する。
【００４９】
図４において、各ノードの横に中括弧（｛｝）を表記し、その内側にパターンＩＤを列挙している。この列挙されたパターンＩＤが、そのノードに関連付けられたノードセットである。パターンＵの範囲がノードＶの範囲をカバーしており、かつ、ノードＶの親ノードの範囲をカバーしていない場合、パターンＵはノードＶのノードセットに含まれる。
【００５０】
次に、上記した構造を有する情報を生成するツリー生成部１１の動作について、図面を参照して詳細に説明する。
【００５１】
図７は、ツリー生成部１１の動作の一例を示すフローチャートである。ツリー生成部１１は、入力としてパターンと、データの次元の軸を示す情報（第１の実施の形態ではｘ軸）とを受け取ると、図７に示すような生成処理を実行する。なお、第１の実施の形態では、データが一次元の場合について説明するので、以降の第１の実施の形態の構成要素の説明において、データの次元の軸を示す情報の受け渡しを省略することも可能である。
【００５２】
ツリー生成部１１に入力されたパターンの集合をｐｌｉｓｔと、データの次元の軸を示す情報をａｘｉｓと表す。ツリー生成部１１は、ステップ５１において、ｐｌｉｓｔとａｘｉｓとに基づいて、スケルトン生成処理を行う。スケルトン生成処理は、スケルトン生成処理部１１１により実行される。スケルトン生成処理部１１１の動作は後に説明される。
【００５３】
ツリー生成部１１は、スケルトン生成処理部１１１にｐｌｉｓｔとａｘｉｓとを渡す。そして、ツリー生成部１１は、スケルトン生成処理部１１１から、ツリー記憶部１３に記憶された木構造のデータのルートノードを示す情報を取得する（ステップ５１）。スケルトン生成処理部１１１が生成する木構造のデータは、各ノードのｎＳｅｔが空集合となっている。
【００５４】
次に、ツリー生成部１１は、ｐｌｉｓｔに含まれるパターンの全てについて、パターン挿入処理を行う（ステップ５２〜５４）。パターン挿入処理は、パターン挿入処理部１１２を用いることにより実行される。パターン挿入処理部１１２の動作は後に説明される。
【００５５】
図７のステップ５３における、「ｐｌｉｓｔ．ｓｉｚｅ」という表記は、ｐｌｉｓｔに含まれる要素の数を意味する。また、ステップ５４における「ｐｌｉｓｔ［ｉ］」は、ｐｌｉｓｔに含まれる第ｉ番目の要素を意味し、パターンを特定する。ここで、ｐｌｉｓｔに含まれるパターンに順序付けはされていない。図７のステップ５２〜５４は、ツリー生成部１１が、変数ｉをインクリメントさせながらｐｌｉｓｔ［ｉ］を特定することにより、全ての要素についてパターン挿入処理を行うことを表している。
【００５６】
ツリー生成部１１は、ｐｌｉｓｔ［ｉ］と、木構造のデータのルートノードとａｘｉｓとをパターン挿入処理部１１２に渡す。
【００５７】
ツリー生成部１１は、ｐｌｉｓｔ．ｓｉｚｅ回のパターン挿入処理を終えると、ツリー記憶部１３に記憶された木構造のデータのルートノードのルートフラグを、ルートノードであることを示す情報に変更する。そして、ツリー生成部１１は、処理を終了する。
【００５８】
次に、スケルトン生成処理部１１１の動作について説明する。図８は、スケルトン生成処理部１１１の動作である。
【００５９】
スケルトン生成処理部１１１は、ステップ1で、ｐｌｉｓｔに含まれる各パターンについて、関連付けられた範囲（ｐｌｉｓｔ[ｉ]．ｒａｎｇｅ［ａｘｉｓ］と記載することがある（ｒａｎｇｅ［ａｘｉｓ］は取り扱うデータがｘ軸の値であることを示す）)の最小値から１を減じた値(ｐｌｉｓｔ[ｉ]．ｒａｎｇｅ［ａｘｉｓ］．ｍｉｎ−１、と記載することがある)と最大値(ｐｌｉｓｔ[ｉ]．ｒａｎｇｅ［ａｘｉｓ］．ｍａｘと記載することがある)を昇順に並べたリストを生成する。生成したリストをｌｉｓｔと記す。ｌｉｓｔ[ｊ]は、ｊ番目の要素を表す。要素数（ｌｉｓｔ．ｓｉｚｅ）がｎである場合、ｊは０からｎ−１となる。
【００６０】
次に、スケルトン生成処理部１１１は、定義域記憶部１２からｘ−ｍｉｎ及びｘ−ｍａｘを読み出し、ｌｉｓｔの先頭にｘ−ｍｉｎから１を減じた値を、ｌｉｓｔの末尾にｘ−ｍａｘを挿入する（ステップ１５）。
【００６１】
次に、スケルトン生成処理部１１１は、ノード生成処理を、（ｌｉｓｔ．ｓｉｚｅ−１）回行う（ステップ３〜６）。ノード生成処理によって、ツリー記憶部１３にノードｎとそれに関連付けられた情報が記憶される。この際、スケルトン生成処理部１１１は、第ｉ回目（ｉは０からｌｉｓｔ．ｓｉｚｅ−１）の処理において、ノードｎのｍｉｎにｌｉｓｔ［ｉ］＋１を、ｍａｘにｌｉｓｔ［ｉ］を関連付け、閾値、左子及び右子には何も関連付けない。
【００６２】
次に、スケルトン生成処理部１１１は、ノード生成処理で生成されたノードの数が０かどうかを判定する（ステップ７）。０である場合には、ツリー記憶部１３に記憶される木構造のデータのルートノードを示す情報としてｎｕｌｌ（存在しないことを意味する）出力し（ステップ８）、処理を終了する。
【００６３】
ステップ７の判定で０ではない場合、スケルトン生成処理部１１１は、生成した各ノードの親ノードを生成する処理を行う。スケルトン生成処理部１１１は，（ツリー記憶部１３に記憶されたノードの数）＜２ｎ＋１を満たす最小のｎを算出する（ステップ９）。ｎは必ず０以上となる。
【００６４】
ここで、親ノードを生成する処理を説明するに際し、その処理の対象となるノードの集合をｎｌｉｓｔで表す。ｎｌｉｓｔ．ｓｉｚｅはｎｌｉｓｔの要素の数を表す。また、ｎｌｉｓｔ［ｊ］はｊ番目の要素を表し、ノードを特定する。
【００６５】
スケルトン生成処理部１１１は、ステップ９でｎを算出すると、ツリー記憶部１３から各ノードを読み出し、ｎｌｉｓｔとして記憶する。ｎｌｉｓｔは、図示しない記憶部を一時的に用いて記憶されても良い。なお、以降の説明では、ｎｌｉｓｔ内の各ノードが、関連付けられる範囲が昇順となるようにソートされている例について説明する。勿論、これに限定されない。
【００６６】
次に、スケルトン生成処理部１１１は、ｎｌｉｓｔとｎとを用いて初回親生成処理を実行する。これは、ｎｌｉｓｔに含まれるノードの一部に関して親ノードを生成する処理である。初回親生成処理の実行結果は、２ｎ個のノードをその要素とするリストである。スケルトン生成処理部１１１は、初回親生成処理の実行結果を、ｎｌｉｓｔとして再び記憶する（ステップ１０）。初回親生成処理の詳細は後に詳述される。
【００６７】
次に、スケルトン生成処理部１１１は、ｎｌｉｓｔとｎとを用いて親生成処理を繰り返し実行する（ステップ１１〜１３）。スケルトン生成処理部１１１は、ｎをデクリメントする毎に（ステップ１２）、親生成処理を一度実行する（ステップ１３）。親生成処理の詳細は後に詳述される。親生成処理は、ｎｌｉｓｔ含まれる２ｎ＋１個の要素の親ノードを生成する。親生成処理の実行結果は、生成した２ｎ個の親ノードである。親生成処理の詳細は後に詳述される。
【００６８】
スケルトン生成処理部１１１は、ｎ＝０になると、ツリー記憶部１３に記憶される木構造のデータのルートノードを示す情報として、最後の親生成処理にて生成されたノードを示す情報を出力し、処理を終了する（ステップ１４）。
【００６９】
次に、スケルトン生成処理部１１１による初回親生成処理について説明する。図９は、スケルトン生成処理部１１１による初回親生成処理の一例を説明するためのフローチャートである。
【００７０】
スケルトン生成処理部１１１は、ｎｌｉｓｔとｎとに基づいて処理を開始する（ステップ３０）。ｎｌｉｓｔは、処理の対象となるノードの集合を意味する。ｎはツリー記憶部１３に記憶される木構造における木の深さを意味する。
【００７１】
次に、スケルトン生成処理部１１１は、ｎｌｉｓｔ．ｓｉｚｅ−２nをｎｆとして図示しない記憶部に一時的に記憶する（ステップ２１）。次に、スケルトン生成処理部１１１は、カウンタとして用いるｉを０に初期化する（ステップ２２）。
【００７２】
ステップ２３で、スケルトン生成処理部１１１は、ｉとｎｆを比較する。ｉ＜ｎｆならば、ステップ２４へ処理を進める。ｉ＜ｎｆでなければ、ステップ２７へ処理を進める。
【００７３】
ステップ２４で、スケルトン生成処理部１１１は、ノードを生成する。スケルトン生成処理部１１１は、生成した各ノードをツリー記憶部１３に記憶させる。生成するノードの最小値はｎｌｉｓｔ［２×ｉ］．ｍｉｎと、最大値はｎｌｉｓｔ［２×ｉ＋１］．ｍａｘと、閾値はｎｌｉｓｔ［２×ｉ］．ｍａｘと、左子はｎｌｉｓｔ［２×ｉ］と、右子はｎｌｉｓｔ［２×ｉ＋１］とそれぞれ関連付けられる。なお、ｎｌｉｓｔ［２×ｉ］は、ノードを特定し、「．ｍｉｎ」は特定されたノードに関連付けられている最小値を、「．ｍａｘ」は特定されたノードに関連付けられている最大値を意味している。
【００７４】
その後、スケルトン生成処理部１１１は、ステップ２５へ処理を進める。ステップ２５で、スケルトン生成処理部１１１は、ステップ２４で生成したノードをｏｌｉｓｔのｉ番目の要素とする。ｏｌｉｓｔは、初回親生成処理の出力となるノードの集合を記憶するバッファである。その後、スケルトン生成処理部１１１は、ステップ２６で、ｉをインクリメントする。そして、スケルトン生成処理部１１１は、ステップ２３へ処理を進める。
【００７５】
ステップ２７で、スケルトン生成処理部１１１は、ｉと２ｎを比較する。ｉ＜２ｎであれば、スケルトン生成処理部１１１は、ステップ２８へ処理を進める。ｉ＜２ｎでなければ、スケルトン生成処理部１１１は、初回親生成処理を終了する。
【００７６】
ステップ２８で、スケルトン生成処理部１１１は、ｏｌｉｓｔ［ｉ］をｎｌｉｓｔ［ｎｆ＋ｉ］とする。その後、ステップ２９で、スケルトン生成処理部１１１は、ｉをインクリメントする。そして、スケルトン生成処理部１１１は、ステップ２７へ処理を進める。
【００７７】
スケルトン生成処理部１１１は、初回親生成処理の結果として、ｏｌｉｓｔを得る（ステップ３１）。
【００７８】
次に、スケルトン生成処理部１１１による親生成処理について説明する。図１０は、スケルトン生成処理部１１１による親生成処理の一例を説明するためのフローチャートである。
【００７９】
スケルトン生成処理部１１１は、ｎｌｉｓｔとｎとに基づいて処理を開始する（ステップ４６）。ｎｌｉｓｔが処理の対象となるノードの集合を意味し、ｎがツリー記憶部１３に記憶される木構造における木の深さを意味する点は、初回親生成処理と同じである。
【００８０】
次に、スケルトン生成処理部１１１は、カウンタとして用いるｉを０に初期化する（ステップ４１）。
【００８１】
ステップ４２で、スケルトン生成処理部１１１は、ｉと２ｎを比較する。ｉ＜２ｎであれば、スケルトン生成処理部１１１は、ステップ４３へ処理を進める。ｉ＜２ｎでなければ、スケルトン生成処理部１１１は、親生成処理を終了する。
【００８２】
ステップ４３で、スケルトン生成処理部１１１は、２つのノードからそれらの親ノードを生成する。スケルトン生成処理部１１１は、生成した親ノードをツリー記憶部１３に記憶させる。生成される親ノードは、最小値がｎｌｉｓｔ［２×ｉ］．ｍｉｎと、最大値がｎｌｉｓｔ［２×ｉ＋１］．ｍａｘと、閾値がｎｌｉｓｔ［２×ｉ］．ｍａｘと、左子がｎｌｉｓｔ［２×ｉ］と、右子がｎｌｉｓｔ［２×ｉ＋１］とそれぞれ関連付けられる。
【００８３】
そして、ステップ４４で、スケルトン生成処理部１１１は、生成した親ノードをｏｌｉｓｔ［ｉ］とする。ｏｌｉｓｔは、親生成処理で生成されたノードの集合を記憶するバッファである。初回親生成処理の際と同じ表記を用いているが処理毎に異なるバッファであっても良い。
【００８４】
その後、ステップ４５で、スケルトン生成処理部１１１は、ｉをインクリメントする。その後、スケルトン生成処理部１１１は、ステップ４２へ処理を進める。
【００８５】
スケルトン生成処理部１１１は、親生成処理の結果として、ｏｌｉｓｔを得る（ステップ４７）。
【００８６】
次に、パターン挿入処理部１１２の動作について図面を参照して説明する。図１１は、パターン挿入処理部１１２の動作例を説明するためのフローチャートである。
【００８７】
パターン挿入処理部１１２は、一つのパターン（ｐａｔ）と、そのパターンに関連付けられている範囲が表現されている軸（ｘ軸、ｙ軸等）と、処理開始の起点となるノード（ｎｏｄｅ）とに基づいて、動作を行う（ステップ６６）。なお、図７のステップ５４において、ツリー生成部１１が、パターン挿入処理部１１２に渡す情報は、一つのパターン（ｐａｔ）と、そのパターンに関連付けられている範囲が表現されている軸を示す情報（ａｘｉｓ（第１の実施の形態ではｘ））と、ツリー記憶部１３における木構造のルートノードを示す情報（ｒｏｏｔ）である。
【００８８】
ステップ６１で、パターン挿入処理部１１２は、ｎｏｄｅ．ｍｉｎ≦ｐａｔ．ｒａｎｇｅ［ａｘｉｓ］．ｍａｘかつｐａｔ．ｒａｎｇｅ［ａｘｉｓ］．ｍｉｎ≦ｎｏｄｅ．ｍａｘであるかを判定する。この処理で、パターン挿入処理部１１２は、ｐａｔに関連付けられた範囲（ｐａｔ．ｒａｎｇｅ［ａｘｉｓ］）が、ｎｏｄｅの範囲をオーバーラップしているかを判定している。
【００８９】
条件が満たされる場合、パターン挿入処理部１１２は、ステップ６２へ処理を進める。条件が満たされない場合、パターン挿入処理部１１２は、処理を終了する。
【００９０】
ステップ６２で、パターン挿入処理部１１２は、ｐａｔ．ｒａｎｇｅ［ａｘｉｓ］．ｍｉｎ≦ｎｏｄｅ．ｍｉｎかつｎｏｄｅ．ｍａｘ≦ｐａｔ．ｒａｎｇｅ［ａｘｉｓ］．ｍａｘであるかを判定する。この処理で、パターン挿入処理部１１２は、ｐａｔに関連付けられた範囲が、ｎｏｄｅの範囲をカバーしているかを判定している。
【００９１】
条件が満たされる場合、パターン挿入処理部１１２は、ステップ６３へ処理を進める。条件が満たされない場合、パターン挿入処理部１１２は、ステップ６４へ処理を進める。
【００９２】
ステップ６３で、パターン挿入処理部１１２は、ｐａｔをｎｏｄｅ．ｎＳｅｔの末尾に挿入する。その後、パターン挿入処理部１１２は、処理を終了する。
【００９３】
ステップ６４で、パターン挿入処理部１１２は、ｐａｔとａｘｉｓとｎｏｄｅ．ｌｅｆｔとに基づいて、パターン挿入処理部１１２を再帰的に動作させる。その後、パターン挿入処理部１１２は、ステップ６５へ処理を進める。ステップ６５で、パターン挿入処理部１１２は、ｐａｔとａｘｉｓとｎｏｄｅ．ｒｉｇｈｔとに基づいて、パターン挿入処理部１１２を再帰的に動作させる。その後、パターン挿入処理部１１２は、処理を終了する。
【００９４】
比較のため、非特許文献１に記載された技術により図２の入力から生成される一次元セグメントツリーを図１２に示す。ルートノードａがｈ２、ｈ３、ｈ４の範囲（Ａ１からＢ２の範囲）にしか関連付けられていない点等が図４のツリー構造と異なっている。
【００９５】
第１の実施の形態における入力されるパターンの例について説明する。図１３は、扱うデータが一次元（ｘ軸のみ）の場合のパターンの例を示している。パターンＡでは、A１以上、A２以下が指定されている。パターンとして指定できる範囲の最小値をｘ−ｍｉｎ、最大値をｘ−ｍａｘであり、ｘ−ｍｉｎ≦ｘ１≦ｘ２≦ｘ−ｍａｘが成り立つ。パターンＢは、特に値の範囲を指定していない。
【００９６】
第１の実施の形態では、図１３のパターンＢのように値の範囲が指定されていない場合、全ての範囲が指定されていると解釈する。図１４は、図１３に示すパターンＡ及びＢがカバーする範囲を図示する概念図である。図１５は、図１３に示すパターンＡ及びＢを入力として受け取った際に、ツリー生成部１１１が生成し、ツリー記憶部１３に記憶される木構造を持つデータを示す概念図である。
【００９７】
第１の実施の形態により生成される木構造では、図４に例示するように、ノードａがｘ−ｍｉｎからｘ−ｍａｘの範囲と、ノードｇはＢ２からｘ−ｍａｘと、ノードｈはｘ−ｍｉｎからＡ１の範囲とそれぞれ関連付けられており、木構造の各ノードと関連付けられる範囲との意味を崩すことなく、ルートノードａに、データの値の取りうる全範囲が関連付けられている。
【００９８】
第１の実施の形態による木構造を持つデータは、ルートノードａに特定の軸におけるデータの取りうる全範囲が関連付けられているので、木構造の各ノードに関連付けられる範囲と該ノードに関連付けられるｎＳｅｔの意味を崩すことなく、ルートノードのｎＳｅｔに特定の軸における範囲が指定されていないパターンを含めることができる。つまり、第１の実施の形態で生成される木構造を持つデータは、特定の軸における範囲が指定されていないパターンを用いるパターンマッチング方法に利用できる。
【００９９】
また、第１の実施の形態による木構造を持つデータは、ルートノードａに特定の軸におけるデータの取りうる全範囲が関連付けられているので、入力されたデータの値が指定されていない場合や不明である場合にもマッチするパターンを検知することができるパターンマッチングに用いることができる。
【０１００】
［第２の実施の形態］
次に、第２の実施の形態について図面を参照して説明する。図１６は、第２の実施の形態の構成例を示す図面である。図１６によれば、第２の実施の形態の構成例は、ツリー記憶部１３、ツリーサーチ部２１を有する情報処理装置である。第２の実施の形態では、第１の実施の形態と同じく、扱うデータが一次元（ここではｘ軸とする）の場合について説明する。
【０１０１】
ツリー記憶部１３は、第１の実施の形態におけるツリー生成部１１が生成した情報を記憶している。ここでは、図４に示す情報が記憶されているとして説明を行う。その意味は第１の実施の形態にて説明したとおりである。
【０１０２】
ツリーサーチ部２１は、特定の軸における値を持つデータとツリー記憶部１３に記憶された木構造におけるノードを示す情報を受け取ると、ツリー記憶部１３に記憶された木構造の情報を探索し、その値にマッチするパターンのリストを出力する。また、ツリーサーチ部は、出力用のデータを一時的に記憶するバッファ（図示しない）を備えていても良い。
【０１０３】
次に、第２の実施の形態の情報処理装置の動作の例について説明する。
【０１０４】
特定の軸における値を持つデータを受け取ると、ツリーサーチ部２１は動作を開始する。ツリーサーチ部２１は、当初、データと、ツリー記憶部１３に記憶された木構造のデータのルートノードを示す情報を入力として受け取る。そして、ツリーサーチ部２１は、ツリー記憶部１３に記憶された木構造のデータを探索し、その値にマッチするパターンのリストを出力する。
【０１０５】
ツリーサーチ部２１の動作について、図面を参照して説明する。図１７は、ツリーサーチ部２１の動作を説明するためのフローチャートである。ツリーサーチ部２１は、データとノードを示す情報とを受け取ると、その位置からツリー記憶部１３に記憶された木構造のデータを探索し始める。
【０１０６】
ツリーサーチ部２１は、処理対象たるノードのｎＳｅｔをマッチパターンＩＤリストに追加する（ステップ１）。マッチパターンＩＤリストは、ツリーサーチ部２１が用いるバッファである。
【０１０７】
次に、ステップ６で、ツリーサーチ部２１は、処理対象たるノードがルートノードであるか否かを調べる。ルートノードでない場合、ツリーサーチ部２１は、ステップ２へ処理を進める。ルートノードである場合には、入力されたデータの値ｘを調べ、ｘ＝？であるかどうかを調べる（ステップ７）。条件を満たす場合、ツリーサーチ部２１は、処理を終了する。条件を満たさない場合、ツリーサーチ部２１は、ステップ２へ処理を進める。
【０１０８】
次に、ステップ２で、ツリーサーチ部２１は，処理対象たるノードがリーフノードかどうかを調べる。処理対象のノードに閾値が関連付けられているかどうか、あるいは、左子又は右子が関連付けられているかどうかを調べることにより行う。例えば、左子が関連付けられていればリーフノードでなく、左子が関連付けられていなければリーフノードである。リーフノードである場合、ツリーサーチ部２１は処理を終了する。リーフノードでない場合、ツリーサーチ部２１は、ステップ３へ処理を進める。
【０１０９】
次に、ステップ３で、ツリーサーチ部２１は、処理対象たるノードの閾値とｘとを比較する。ｘ≦閾値である場合、ツリーサーチ部２１は、ｘと左子とをツリーサーチ部２１に入力し再帰探索をさせる（ステップ４）。ｘ≦閾値でない場合、ツリーサーチ部２１は、ｘと右子とをツリーサーチ部２１に入力し再帰探索をさせる（ステップ５）。
【０１１０】
その後、ツリーサーチ部２１は、一次元サーチを終了する。
【０１１１】
第２の実施の形態によれば、ツリー記憶部１３の記憶する木構造を持つデータが、ルートノードａに特定の軸におけるデータの取りうる全範囲が関連付けられているので、木構造の各ノードに関連付けられる範囲と該ノードに関連付けられるｎＳｅｔの意味を崩すことなく、ルートノードのｎＳｅｔに特定の軸における範囲が指定されていないパターンを含めることができる。ツリーサーチ部２１は、この木構造を持つデータを用いて、入力されたデータにマッチするパターンのリストを出力するので、特定の軸における範囲が指定されていないパターンを用いるパターンマッチング方法を提供することができる。
【０１１２】
また、第２の実施の形態によれば、ツリー記憶部１３の記憶する木構造のルートノードａを処理する際に、入力されたデータが値を持つか否かを調べ、持たない場合にはルートノードのｎＳｅｔをマッチング結果とする。このため、そのことが木構造の各ノードに関連付けられる範囲と該ノードに関連付けられるｎＳｅｔの意味を崩さずに、データが特定の軸における値を持たない場合であっても、その軸に関する範囲が指定されていないパターンにマッチさせることができる。したがって、第２の実施の形態によれば、入力されるデータが特定の軸における値を持っていない場合にも機能するパターンマッチング方法を提供することができる。
【０１１３】
［第３の実施の形態］
次に、第３の実施の形態について図面を参照して説明する。図１８は、第３の実施の形態の構成例を示す図面である。図１８によれば、第３の実施の形態の構成例は、ツリー生成部３１、定義域記憶部３２、ツリー記憶部３３を有する情報処理装置である。第１及び第２の実施の形態では、扱うデータが一次元の場合について説明した。第３の実施の形態では、扱うデータが二次元（ここではｘ軸及びｙ軸とする）の場合について説明する。
【０１１４】
ツリー生成部３１は、一つ以上のパターンを入力として受け取る。また、ツリー生成部３１は、定義域記憶部３２からｘ軸及びｙ軸の値として取りうる値の範囲を示す情報を読み出す。そして、ツリー生成部３１は、入力されたパターンと定義域記憶部３２から読み出した情報とを用いて、ツリー構造のデータを作成し、ツリー記憶部３３へ出力する。
【０１１５】
ツリー生成部３１は、例えば、半導体集積回路等によるハードウエアとして実現しても良い。また、コンピュータに備わるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）が所定のプログラムを読み込むことにより実現されても良い。
【０１１６】
第３の実施の形態では、扱うデータが二次元の場合について説明するので、パターンは次のような情報となる。つまり、パターンは、パターンＩＤと、ｘ軸におけるデータの範囲及びｙ軸におけるデータの範囲とが関連付けられた情報である。パターンＰは、ｘ軸における値範囲の最小値（Ｐ．ｒａｎｇｅ［ｘ］．ｍｉｎ）、ｘ軸における値範囲の最大値（Ｐ．ｒａｎｇｅ［ｘ］．ｍａｘ）、ｙ軸における値範囲の最小値（Ｐ．ｒａｎｇｅ［ｙ］．ｍｉｎ）、ｙ軸における値範囲の最大値（Ｐ．ｒａｎｇｅ［ｙ］．ｍａｘ）と関連付けられる。
【０１１７】
次に、定義域記憶部３２について説明する。定義域記憶部３２は、ｘ軸及びｙ軸の値が取りうる範囲を示す情報を記憶する。例えば、定義域記憶部３２は、ｘ軸の値として指定できる値の最小値であるｘ−ｍｉｎと、ｘ軸の値として指定できる値の最大値であるｘ−ｍａｘと、ｙ軸の値として指定できる値の最小値であるｙ−ｍｉｎと、ｙ軸の値として指定できる値の最大値であるｙ−ｍａｘと、を記憶しても良い。
【０１１８】
定義域記憶部３２は、例えば、半導体集積回路等によるメモリに上記のような情報を記憶させることで実現することができる。また、コンピュータで読み取り可能な記録媒体や、磁気記憶装置、ディスク装置等を用いて実現することも可能である。
【０１１９】
次に、ツリー生成部３１が入力として受け取るパターンと、定義域記憶部３２から読み出した範囲との関係の例について説明する。図１９は、入力として受け取ったパターンの集合を例示する表である。この例では、パターンＩＤとしてＡをもつパターンＡは、ｘ軸の範囲としてＡｘ１からＡｘ２までを、ｙ軸の範囲として＊を指定されている。パターンＩＤとしてＢをもつパターンＢは、ｘ軸の範囲としてＢｘ１からＢｘ２までを、ｙ軸の範囲としてＢｙ１からＢｙ２までを指定されている。
【０１２０】
図２０は、これらの関係を例示する図である。ｘ−ｍｉｎ、ｘ−ｍａｘ、ｙ−ｍｉｎ、ｙ−ｍａｘは、ツリー生成部３１が定義域記憶部３２から読み出す値である。入力として図１９に示すパターンの集合をうけとると、これらにより図２０に示すように各範囲が定まる。
【０１２１】
次に、ツリー記憶部３３が記憶する情報について説明する。ツリー記憶部３３が記憶する情報は、ツリー生成部３１によって生成され、出力される。生成方法は後に詳述される。また、ツリー記憶部３３は、例えば、半導体集積回路等によるメモリに後述する情報を記憶させることで実現することができる。また、コンピュータで読み取り可能な記録媒体や、磁気記憶装置、ディスク装置等を用いて実現することも可能である。
【０１２２】
ツリー記憶部３３が記憶する情報は、２次元のデータを取り扱うために、インナーツリーとアウターツリーという２種類の、木構造を持つデータから構成される。これらをそれぞれ記憶するために、ツリー記憶部３３は、内部的に、ツリー記憶部３３１とツリー記憶部３３２を有していても良い。
【０１２３】
アウターツリーは、２次元のデータのいずれかの次元（例えば、ｘ軸）と関連付けられる木構造のデータである。インナーツリーは、２次元のデータの残りの次元（例えば、ｙ軸）と関連付けられる木構造のデータである。
【０１２４】
図２１に示す表は、アウターツリーの各ノードに関連付けられる情報を例示する表である。アウターツリーの各ノードは二分木を形成する。図５に示す表（第１の実施の形態におけるツリーの各ノードに関連付けられる情報）と比較して、各ノードが、インナーツリーを参照するための情報が加えられている。
【０１２５】
アウターツリーの各ノードは、インナーツリーを参照するための情報と関連付けられる（以下、ｉｒｏｏｔと記載することがある）。対応するインナーツリーが存在しない場合、関連付けられる対象はない。ｉｒｏｏｔは、そのノードに関連付けられたインナーツリーのルートノードを示す情報である。したがって、インナーツリーは一つ以上存在することがある。
【０１２６】
インナーツリーの各ノードは、第１の実施の形態で説明した図５に例示する各情報と関連付けられる。なお、インナーツリーの各ノードにおいて、それらと関連付けられる閾値の説明を、「左子に対してインナーサーチを行うか、右子に対してインナーサーチを行うかを判定するための値。ｙが閾値以下ならば、左子ノードに対してインナーサーチを行い、それ以外ならば、右子ノードに対してインナーサーチを行う。リーフノードは閾値を持たない。」と読み替える。
【０１２７】
次に、上記した構造を有する情報を生成するツリー生成部３１について説明する。ツリー生成部３１は、パターンの集合ｐｌｉｓｔを受け取り、ツリー記憶部３３に、アウターツリーとインナーツリーとを含む情報を記憶させる。
【０１２８】
ツリー生成部３１は、アウターツリー生成部３１１と、インナーツリー生成部３１２とから構成される。ツリー生成部３１は、ｐｌｉｓｔを受け取ると、アウターツリー生成部３１１を用いて、アウターツリーを生成する。その後、ツリー生成部３１は、インナーツリー生成部３１２を用いて、インナーツリーを生成する。そして、ツリー生成部３１は生成したアウターツリーとインナーツリーとを含む情報をツリー記憶部３３に記憶させる。
【０１２９】
アウターツリー生成部３１１は、ツリー生成部３１からｐｌｉｓｔとアウターツリーで扱うべき次元の軸を示す情報（例えばｘ軸）と、を受け取ると、アウターツリーを生成すると共にツリー記憶部３３に記憶させ、そのルートノードを示す情報をツリー生成部３１に出力する。アウターツリー生成部３１１は、ｐｌｉｓｔに含まれるパターンの範囲のうちいずれか一方の軸についてしか範囲が指定されていないものと仮定して（例えば、ｘ軸の範囲を生成処理に用いる場合、ｙ軸の範囲についてはこれを無視する）、第１の実施の形態におけるツリー生成部１１と同じ動作を行う。なお、ツリー生成部１１においてノードを生成する際に、ツリー生成部３１はｉｒｏｏｔに何も関連付けない（ｉｒｏｏｔを無視する）。
【０１３０】
インナーツリー生成部３１２は、アウターツリーにおけるノードを示す情報と、インナーツリーで扱うべき次元の軸を示す情報（例えばｙ軸）と、を受け取ると、そのノードにおけるインナーツリーを生成するとともに、ツリー記憶部３３に記憶させる。また、インナーツリー生成部３１２は、生成したインナーツリーのルートノードを示す情報を、受け取ったアウターツリーにおけるノードを示す情報で特定されるノードのｉｒｏｏｔに関連付ける。インナーツリーの生成方法は後述される。
【０１３１】
次に、第３の実施の形態の情報処理装置の動作の例について説明する。図２２は、第３の実施の形態の情報処理装置の動作の例を説明するためのフローチャートである。
【０１３２】
ツリー生成部３１は、パターンの集合ｐｌｉｓｔを受け取る（ステップ８１）。次に、ツリー生成部３１は、各パターンの持つ２つの次元の軸のうちいずれかの軸を選択し（ここではｘ軸）、アウターツリー生成部３１１に、ｐｌｉｓｔとｘ軸を示す情報とを渡す。アウターツリー生成部３１１は、アウターツリーを生成し、アウターツリーのルートノードを示す情報（ｒｏｏｔ）をツリー生成部３１に出力する（ステップ８２）。
【０１３３】
そして、ツリー生成部３１は、ステップ８３で、ｒｏｏｔとｙ軸を示す情報（ｙ）とをインナーツリー生成部３１２に渡す。インナーツリー生成部３１２は、ｒｏｏｔについてインナーツリーを生成し、ツリー記憶部３３に記憶させる（ステップ８３）。
【０１３４】
次に、インナーツリー生成部３１２の動作について図面を参照して説明する。図２３は、インナーツリー生成部３１２の動作例を説明するためのフローチャートである。インナーツリー生成部３１２は、アウターツリーのノードを示す情報ｎｏｄｅと、軸を示す情報（ａｘｉｓ）とを受け取る（ステップ９１）。
【０１３５】
ステップ９２で、インナーツリー生成部３１２は、ｎｏｄｅ．ｎＳｅｔが空集合(φ)かどうかを判定する。空集合である場合、インナーツリー生成部３１２は、ステップ９４へ処理を進める。空集合でない場合、インナーツリー生成部３１２は、ステップ９３へ処理を進める。
【０１３６】
ステップ９３で、インナーツリー生成部３１２は、ｎｏｄｅ．ｎＳｅｔとａｘｉｓとを用いてツリー生成を行う。ツリー生成は、例えば、ｎｏｄｅ．ｎＳｅｔに含まれるパターンの範囲のうちａｘｉｓで示される軸についてしか範囲が指定されていないものと仮定して（例えば、ｙ軸の範囲を生成処理に用いる場合、ｘ軸の範囲についてはこれを無視する）、第１の実施の形態におけるツリー生成部１１と同じ動作を行う。この動作の結果、インナーツリー生成部３１２は、生成されたインナーツリーのルートノードを示す情報を取得する。そして、インナーツリー生成部３１２は、取得したインナーツリーのルートノードを示す情報を、ｎｏｄｅ．ｉｒｏｏｔとする。
【０１３７】
ステップ９４で、インナーツリー生成部３１２は、ｎｏｄｅがリーフノードかどうかを調べる。例えば、ｎｏｄｅ．ｌｅｆｔに関連付けられているノードがあるかどうかを調べる。リーフノードである場合、インナーツリー生成部３１２は、インナーツリー生成を終了する。リーフノードではない場合、インナーツリー生成部３１２は、ステップ９５へ処理を進める。
【０１３８】
ステップ９５で、インナーツリー生成部３１２は、ｎｏｄｅ．ｌｅｆｔとａｘｉｘとをインナーツリー生成部３１２に入力し再帰的に動作させる。また、ステップ９６で、インナーツリー生成部３１２は、ｎｏｄｅ．ｒｉｇｈｔとａｘｉｓとをインナーツリー生成部３１２に入力し再帰的に動作させる。
【０１３９】
次に、第３の実施の形態のツリー生成部３１が生成する情報の例について説明する。図２４は、図１９に示すパターンの集合が入力された場合に生成されるアウターツリーの概念図である。図２４において、ノードｅ、ｆ、ｉからｅａ、ｆａ、ｉａへ矢印状の線分が記載されており、この線分は、ノードｅ、ｆ、ｉのそれぞれがｉｒｏｏｔとしてインナーツリーのルートノードであるｅａ、ｆａ、ｉａと関連付けられていることを意味する。
【０１４０】
図２５は、図２４のノードｅと関連付けられているインナーツリーである。図２６は、図２４のノードｆと関連付けられているインナーツリーである。図２７は、図２４のノードｉと関連付けられているインナーツリーである。
【０１４１】
図２４の例では、ルートノードａがｘ−ｍｉｎからｘ−ｍａｘの範囲と、ノードｇはＢ２からｘ−ｍａｘと、ノードｈはｘ−ｍｉｎからＡ１の範囲と、それぞれ関連付けられている。このように、第３の実施の形態により生成されるアウターツリーでは、木構造の各ノードと関連付けられる範囲との意味を崩すことなく、ルートノードに、データの値の取りうる全範囲が関連付けられている。
【０１４２】
また、図２５、図２６、図２７の例では、ルートノードｅａ、ｆａ、ｉａがｙ−ｍｉｎからｙ−ｍａｘの範囲と、ノードｅｃ及びｆｂはＢｙ２からｙ−ｍａｘと、ノードｅｄ及びｆｃはｙ−ｍｉｎからＢｙ１の範囲と、それぞれ関連付けられている。このように、第３の実施の形態により生成されるインナーツリーでは、木構造の各ノードと関連付けられる範囲との意味を崩すことなく、各ルートノードに、データの値の取りうる全範囲が関連付けられている。
【０１４３】
第３の実施の形態による木構造を持つデータは、ルートノードに特定の軸におけるデータの取りうる全範囲が関連付けられているので、木構造の各ノードに関連付けられる範囲と該ノードに関連付けられるｎＳｅｔの意味を崩すことなく、ルートノードのｎＳｅｔに特定の軸における範囲が指定されていないパターンを含めることができる。つまり、第３の実施の形態で生成される木構造を持つデータは、特定の軸における範囲が指定されていないパターンを用いるパターンマッチング方法に利用できる。
【０１４４】
また、第３の実施の形態による木構造を持つデータは、ルートノードに特定の軸におけるデータの取りうる全範囲が関連付けられているので、入力されたデータの値が指定されていない場合や不明である場合にもマッチするパターンを検知することができるパターンマッチングに用いることができる。
【０１４５】
［第４の実施の形態］
次に、第４の実施の形態について図面を参照して説明する。図２８は、第４の実施の形態の構成例を示す図面である。図２８によれば、第４の実施の形態の構成例は、ツリー記憶部３３、ツリーサーチ部４１を有する情報処理装置である。第４の実施の形態では、第３の実施の形態と同じく、扱うデータが二次元（ここではｘ軸及びｙ軸とする）の場合について説明する。
【０１４６】
ツリー記憶部３３は、第３の実施の形態におけるツリー生成部３１が生成した情報を記憶している。ここでは、図２４乃至２７に示す情報が記憶されているとして説明を行う。その意味は第３の実施の形態にて説明したとおりである。
【０１４７】
ツリーサーチ部４１は、２次元の値を持つデータとツリー記憶部３３に記憶された木構造におけるノードを示す情報を受け取ると、ツリー記憶部３３に記憶された木構造の情報を探索し、その値にマッチするパターンのリストを出力する。
【０１４８】
ツリーサーチ部４１は、ツリー記憶部３３に記憶されているアウターツリーを探索するアウターツリーサーチ部４１１と、ツリー記憶部３３に記憶されているインナーツリーを探索するインナーツリーサーチ部４１２とから構成される。アウターツリーサーチ部４１１は、データと、アウターツリーのノードを示す情報と、を入力として受け取る。アウターツリーサーチ部４１１は、入力されたデータの値とマッチするパターンのリストを出力する。アウターツリーサーチ部４１１は、インナーツリーサーチ部４１２を用いる。動作は後述される。
【０１４９】
インナーツリーサーチ部４１２は、データと、インナーツリーのノードを示す情報と、を入力として受け取る。インナーツリーサーチ部４１２は，入力されたデータの値にマッチするパターンのリストを出力する。動作は後述される。
【０１５０】
次に、第４の実施の形態の情報処理装置の動作の例について説明する。
【０１５１】
２次元の値を持つデータを受け取ると、ツリーサーチ部４１は動作を開始する。ツリーサーチ部４１は、当初、データと、ツリー記憶部３３に記憶された木構造におけるルートノードを示す情報を入力として受け取る。そして、ツリーサーチ部４１は、ツリー記憶部３３に記憶された木構造を探索し、その値にマッチするパターンのリストを出力する。
【０１５２】
ツリーサーチ部４１の動作について説明する。ツリーサーチ部４１の受け取るデータは２次元の値を持つ（図２９）。
ツリーサーチ部４１は、データを受け取るとアウターツリーサーチ部４１１にデータと、ツリー記憶部３３に記憶されたアウターツリーのルートノードを示す情報（ｒｏｏｔ）とを渡し、探索を開始する。
【０１５３】
図３０は、アウターツリーサーチ部４１１の動作の例を説明するためのフローチャートである。
【０１５４】
アウターツリーサーチ部４１１は、データとアウターツリーのノードを示す情報（ｎｏｄｅ）とを入力として受け取ると、ｎｏｄｅのｉｒｏｏｔにインナーツリーが関連付けられているかどうかを調べる（ステップｏ１）。インナーツリーが関連付けられている場合には、アウターツリーサーチ部４１１は、入力されたデータとｎｏｄｅ．ｉｒｏｏｔとをインナーツリーサーチ部４１２に渡し、インナーツリーを探索させる（ステップｏ２）。
【０１５５】
アウターツリーサーチ部４１１は、ステップｏ１の判定結果がＮｏであった場合、あるいは、ステップｏ２の処理を完了した場合、次に、ｎｏｄｅ．ｆｌａｇを調べる（ステップｏ７）。ルートフラグがルートノードでないことを示す場合、アウターツリーサーチ部４１１はステップｏ３へ処理を進める。ステップｏ７において、ルートフラグがルートノードであることを示す場合、入力されたデータのｘ軸の値が？であるかどうかを調べる（ステップｏ８）。ｘ＝？である場合、アウターツリーサーチ部４１１は、処理を終了する。ｘ＝？でない場合、アウターツリーサーチ部は、ステップｏ３へ処理を進める。
【０１５６】
次に、アウターツリーサーチ部４１１は、ｎｏｄｅがリーフノードかどうかを調べる（ステップｏ３）。ノードに閾値が関連付けられているかどうか、左子が関連付けられているかどうか、あるいは、右子が関連付けられているかどうかを確認することによって調べることができる。例えば、左子が関連付けられていればリーフノードではなく、左子が関連付けられていなければリーフノードである。リーフノードであれば、アウターツリーサーチ部４１１は処理を終了する。リーフノードでなければ、アウターツリーサーチ部４１１は、ステップｏ４へ処理を進める。
【０１５７】
次に、ステップｏ４で、アウターツリーサーチ部４１１は、閾値と入力されたデータのｘ軸の値ｘとを比較する。ｘが閾値以下である場合、アウターツリーサーチ部４１１は、データと左子とをアウターツリーサーチ部４１１に入力し再帰探索を行う（ステップｏ５）。ｘが閾値より大きい場合、アウターツリーサーチ部４１１は、データと右子とをアウターツリーサーチ部４１１に入力し再帰探索を行う（ステップｏ６）。
【０１５８】
その後、アウターツリーサーチ部４１１は、処理を終了する。アウターツリーサーチ部４１１は、処理を終了する際、マッチパターンＩＤリストを出力する。マッチパターンＩＤリストは後述される。
【０１５９】
次に、インナーツリーサーチ部４１２の動作の例について説明する。図３１は、インナーツリーサーチ部４１２の動作の例を説明するためのフローチャートである。
【０１６０】
インナーツリーサーチ部４１２は、データとインナーツリーのノードを示す情報とを入力として受け取ると、入力されたノードを示す情報で特定されるノードｉｎｏｄｅのｎＳｅｔをマッチパターンＩＤリストに追加する（ステップｉ１）。マッチパターンＩＤリストは、ツリーサーチ部４１が用いるバッファである。
【０１６１】
次に、インナーツリーサーチ部４１２は、ｉｎｏｄｅ．ｆｌａｇを調べる（ステップｉ６）。ルートノードでないことを示す場合、インナーツリーサーチ部４１２は、ステップｉ２へ処理を進める。ルートノードであることを示す場合、インナーツリーサーチ部４１２は、入力されたデータのｙ軸の値ｙが？であるかどうかを調べる（ステップｉ７）。ｙ＝？である場合、インナーツリーサーチ部４１２は、処理を終了する。ｙ＝？でない場合、インナーツリーサーチ部４１２は、ステップｉ２へ処理を進める。
【０１６２】
次に、インナーツリーサーチ部４１２は、ｉｎｏｄｅがリーフノードかどうかを調べる（ステップｉ２）。リーフノードである場合、インナーツリーサーチ部４１２は、処理を終了する。リーフノードでない場合、インナーツリーサーチ部４１２は、ステップｉ３へ処理を進める。
【０１６３】
ステップｉ３で、インナーツリーサーチ部４１２は、閾値とｙを比較する。ｙ≦閾値であれば、データと左子とをインナーツリーサーチ部４１２に入力し再帰的に探索を行う（ステップｉ４）。ｙ≦閾値でなければ、データと右子とをインナーツリーサーチ部４１２に入力し再帰的に探索を行う（ステップｉ５）。
【０１６４】
その後、インナーツリーサーチ部４１２は、処理を終了する。インナーツリーサーチ部４１２は、処理を終了する際、マッチパターンＩＤリストを出力する。
【０１６５】
第４の実施の形態によれば、ツリー記憶部３３の記憶する木構造を持つデータが、ルートノードａに特定の軸におけるデータの取りうる全範囲が関連付けられているので、木構造の各ノードに関連付けられる範囲と該ノードに関連付けられるｎＳｅｔの意味を崩すことなく、ルートノードのｎＳｅｔに特定の軸における範囲が指定されていないパターンを含めることができる。ツリーサーチ部４１は、この木構造を持つデータを用いて、入力されたデータにマッチするパターンのリストを出力するので、特定の軸における範囲が指定されていないパターンを用いるパターンマッチング方法を提供することができる。
【０１６６】
また、第４の実施の形態によれば、ツリー記憶部３３の記憶するインナーツリーのルートノードを処理する際に、入力されたデータが値を持つか否かを調べ、持たない場合にはルートノードのｎＳｅｔをマッチング結果とする。このため、そのことが木構造の各ノードに関連付けられる範囲と該ノードに関連付けられるｎＳｅｔの意味を崩さずに、データが特定の軸における値を持たない場合であっても、その軸に関する範囲が指定されていないパターンにマッチさせることができる。したがって、第４の実施の形態によれば、入力されるデータが特定の軸における値を持っていない場合にも機能するパターンマッチング方法を提供することができる。
【０１６７】
［第５の実施の形態］
次に、第５の実施の形態について図面を参照して説明する。図３２は、第５の実施の形態の構成例を示す図面である。図３２によれば、第５の実施の形態の構成例は、Ｓツリー生成部５１、定義域記憶部３２、Ｓツリー記憶部５３を有する情報処理装置である。第５の実施の形態では、第３の実施の形態と同様に扱うデータが二次元（ここではｘ軸及びｙ軸とする）の場合について説明する。定義域記憶部３２は、第３の実施の形態におけるものと同一である。
【０１６８】
第５の実施の形態では、２次元のデータを扱うに当たり、第３の実施の形態とは異なり、非特許文献１で定義されているＳ−ｔｒｅｅに類するＳツリーを用いる。
【０１６９】
Ｓツリー生成部５１は、一つ以上のパターンを入力として受け取る。また、Ｓツリー生成部５１は、定義域記憶部３２からｘ軸及びｙ軸の値として取りうる値の範囲を示す情報を読み出す。そして、Ｓツリー生成部５１は、入力されたパターンと定義域記憶部３２から読み出した情報とを用いて、Ｓツリー構造のデータを作成し、Ｓツリー記憶部５３へ出力する。
【０１７０】
Ｓツリー生成部５１は、例えば、半導体集積回路等によるハードウエアとして実現しても良い。また、コンピュータに備わるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）が所定のプログラムを読み込むことにより実現されても良い。
【０１７１】
第５の実施の形態では、扱うデータが二次元の場合について説明するので、パターンは第３の実施の形態におけるものと同様である。
【０１７２】
次に、Ｓツリー記憶部５３が記憶する情報について説明する。Ｓツリー記憶部５３が記憶する情報は、Ｓツリー生成部５１によって生成される。生成方法は後に詳述される。また、Ｓツリー記憶部５３は、例えば、半導体集積回路等によるメモリに後述する情報を記憶させることで実現することができる。また、コンピュータで読み取り可能な記録媒体や、磁気記憶装置、ディスク装置等を用いて実現することも可能である。
【０１７３】
Ｓツリー記憶部５３が記憶する情報は、２次元のデータを取り扱うために、インナーツリーとアウターツリーという２種類の、木構造を持つデータから構成される。これらをそれぞれ記憶するために、Ｓツリー記憶部５３は、内部的に、アウターツリーを記憶するためのＳツリー記憶部５３１と、インナーツリーを記憶するためのＳツリー記憶部５３２とを有していても良い。第５の実施の形態では、アウターツリーとインナーツリーとを区分せずに記憶するＳツリー記憶部５３を用いる態様について説明する。
【０１７４】
図３３に、第５の実施の形態におけるアウターツリーの各ノードと関連付けられる各情報を例示する。第３の実施の形態と比較すると、ａＳｅｔが追加されている。ａＳｅｔはインナーツリー生成時に利用される。
【０１７５】
図３４に、第５の実施の形態におけるインナーツリーの各ノードと関連付けられる各情報を例示する。第３の実施の形態と比較すると、ｘ閾値（ｘｔｈｒｅｓｈｏｌｄ）、左後継（ｌｓｕｃｃｅｓｓｏｒ）、右後継（ｒｓｕｃｃｅｓｓｏｒ）、先祖（ａｎｃｅｓｔｏｒ）が追加されている。
【０１７６】
ｘ閾値は、アウターツリーで利用されている次元の値である。ｘが左子にあたるインナーツリーに対応するか右子にあたるインナーツリーに対応するかを判定するために用いられる。第３の実施の形態でアウターツリーのノードに関連付けられていた閾値に相当する。一つのインナーツリーに属する各ノードは、同じｘ閾値を持つ。最下層にあたるインナーツリーのノードには、この値は関連付けられない。
【０１７７】
左後継は、左子にあたるツリーのリーフノードを示す。左子にあたるツリーのリーフノードは、このノードの範囲を包含している。リーフノード以外は参照を持たない。最下層にあたるインナーツリーのノードは値を持たない。リーフノードの場合、左子にあたるツリーが存在すれば、参照を持つ。
【０１７８】
右後継は、右子にあたるツリーのリーフノードを示す。右子にあたるツリーのリーフノードは、このノードの範囲を包含している。リーフノード以外は参照を持たない。最下層にあたるインナーツリーのノードは値を持たない。リーフノードの場合、右子にあたるツリーが存在すれば、参照を持つ。
【０１７９】
先祖は、ノードセットの要素を一つ以上持つ先祖ノードのうち、もっとも近い先祖ノードへの参照である。
【０１８０】
次に、上記した構造を有する情報を生成するＳツリー生成部５１について説明する。Ｓツリー生成部５１は、パターンの集合ｐｌｉｓｔを受け取り、アウターツリーとインナーツリーとを含むＳツリーを生成すると共に、Ｓツリー記憶部５３に記憶させる。
【０１８１】
次に、第５の実施の形態の情報処理装置の動作の例について説明する。
【０１８２】
図３５から図４７の図面を用いて、Ｓツリー生成部５１の動作の例について説明する。図３５から図４７の図面は、Ｓツリー生成部５１の動作例について説明するためのフローチャートである。Ｓツリー生成部５１は、その動作において、Ｓツリーアウターセグメントツリー生成、Ｓツリーインナーツリー生成、Ｓツリーインナーセグメントツリー生成、Ｓツリーインナースケルトン生成、Ｓツリー初回親生成、Ｓツリー親生成、先祖ノード設定、インナーツリー接続、リーフノード取得、リーフノード左接続、リーフノード右接続と呼ばれる各処理及びスケルトン生成、パターン挿入と呼ばれる各処理を実行する。なお、第５の実施の形態では、上記の各処理を実行する構成要素としてＳツリー生成部５１を設ける態様について説明するが、これらの各処理を実行するための構成要素を個別に設ける態様であっても良いことは言うまでもない。例えば、第５の実施の形態として、Ｓツリーアウターセグメントツリー生成処理を実行する処理部、Ｓツリーインナーツリー生成処理を実行する処理部、Ｓツリーインナーセグメントツリー生成処理を実行する処理部、Ｓツリーインナースケルトン生成処理を実行する処理部、Ｓツリー初回親生成処理を実行する処理部、Ｓツリー親生成処理を実行する処理部、先祖ノード設定処理を実行する処理部、インナーツリー接続処理を実行する処理部、リーフノード取得処理を実行する処理部、リーフノード左接続処理を実行する処理部、リーフノード右接続処理を実行する処理部、スケルトン生成処理を行う処理部、パターン挿入処理を行う処理部を備えるように構成しても良い。また、処理毎に処理部を設けてもよいし、複数の処理を実行するための一つの処理部を設けても良い。
【０１８３】
Ｓツリー生成部５１（又は、上記した各処理部）は、例えば、半導体集積回路等によるハードウエアとして実現しても良い。また、コンピュータに備わるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）が所定のプログラムを読み込むことにより実現されても良い。
【０１８４】
スケルトン生成処理は、第１の実施の形態におけるスケルトン生成処理部１１１の動作と同じ処理である。
【０１８５】
パターン挿入処理は、第１の実施の形態におけるパターン挿入処理部１１２の動作と同じ処理である。
【０１８６】
図３５は、Ｓツリー生成処理を説明するためのフローチャートである。Ｓツリー生成部５１は、パターンを受け取ると、Ｓツリー生成処理を実行する。
【０１８７】
ステップ１１１では、受け取ったパターンをｐｌｉｓｔとする。その後、ステップ１１２へ進む。
【０１８８】
ステップ１１２では、ｐｌｉｓｔとアウターツリーを生成するために参照するｘ軸を引数としてＳツリーアウターセグメントツリー生成を実行する。Ｓツリーアウターセグメントツリー生成では、Ｓツリーを構成するアウターセグメントツリーを生成し、そのツリーのルートを戻り値として返す。その後、ステップ１１３に進む。
【０１８９】
ステップ１１３では、アウターツリーのルート（ｒｏｏｔ）と、インナーツリーを生成するために参照するｙ軸を引数としてＳツリーインナーツリー生成を実行する。Ｓツリーインナーツリー生成では、アウターセグメントツリーの各ノードに対応するインナーセグメントツリーを生成する。その後、ステップ１１４に進む。
【０１９０】
ステップ１１４では、アウターツリーのルート（ｒｏｏｔ）を引数として、インナーツリー接続を行う。インナーツリー接続では、２つのインナーツリーのリーフノード同士を接続する。接続する２つのインナーツリーは、アウターツリーにおいて、親子関係になっている２つのノードに対応する。
【０１９１】
次に、Ｓツリーアウターセグメントツリー生成処理について説明する。図３６は、Ｓツリーアウターセグメントツリー生成処理の動作例を示している。Ｓツリーアウターセグメントツリー生成処理では、第１の実施の形態におけるツリー生成部１１の動作と似た動作を行う。両者を対比して説明すると、図７との違いは、ステップ５４がステップ５７に置きかわっている点である。
【０１９２】
ステップ５７では、登録するパターンと、アウターセグメントツリーを生成する上で参照する値軸と、パターンを登録するためにあらかじめ生成してあるパターンが登録されていない状態のアウターセグメントツリーのルート（ｒｏｏｔ）を引数として、Ｓツリーアウターノードパターン挿入を実行する。Ｓツリーアウターノードパターン挿入では、ノードセット（ｎＳｅｔ）と拡張ノードセット（ａＳｅｔ）の設定を行う。
【０１９３】
図３７は、Ｓツリーアウターノードパターン挿入処理の動作例を示している。Ｓツリーアウターノードパターン挿入処理では、第１の実施の形態におけるパターン挿入処理部１１２の動作を似た動作を行う。両者を対比して説明すると、図１１との違いは、ステップ６７がステップ６２の直前に挿入されている点と、ステップ６４がステップ６８に置き換わっている点、ステップ６５がステップ６９に置き換わっている点である。
【０１９４】
ステップ６７では、登録するパターン（ｐａｔ）をｎｏｄｅ．ａＳｅｔの末尾に挿入する。ｎｏｄｅ．ａＳｅｔは、そのノードに対応するインナーセグメントツリーのスケルトンを生成するために使用される。
【０１９５】
ステップ６８では、登録するパターン（ｐａｔ）と左子（ｎｏｄｅ．ｌｅｆｔ）を引数としてＳツリーアウターノードパターン挿入を実行する。
【０１９６】
ステップ６９では、登録するパターン（ｐａｔ）と左子（ｎｏｄｅ．ｒｉｇｈｔ）を引数としてＳツリーアウターノードパターン挿入を実行する。
【０１９７】
次に、Ｓツリーインナーツリー生成処理について説明する。図３８は、Ｓツリーインナーツリー生成処理の動作例を示すフローチャートである。Ｓツリーインナーツリー生成処理では、第３の実施の形態におけるインナーツリー生成部３１２と似た動作を行う。両者を対比して説明すると、図２３との違いは、ステップ９２がステップ９７に置き換わっている点、ステップ９３がステップ９８に置き換わっている点、ステップ１０９１がステップ９８の後に挿入されている点、ステップ９５がステップ９９に置き換わっている点、ステップ９６がステップ１００に置き換わっている点である。
【０１９８】
ステップ９８では、Ｓツリーインナーセグメントツリー生成を行う。拡張ノードセット（ｎｏｄｅ．ａＳｅｔ）とインナーセグメントツリーを生成するために参照する値の軸（ａｘｉｓ）とアウターノードが保持する閾値（ｎｏｄｅ．ｔｈｒｅｓｈｏｌｄ）を引数とする。Ｓツリーインナーセグメントツリー生成では、アウターノード（ｎｏｄｅ）に対応するインナーセグメントツリーを生成し、戻り値として、生成したインナーセグメントツリーのルートを返す。
【０１９９】
ステップ１０９１では、先祖ノード設定を行う。引数として、先祖ノードの設定を行う対象であるインナーツリーのルート（ｎｏｄｅ．ｉｒｏｏｔ）と、第１引数のノードから見て、ｎＳｅｔの要素を1つ以上持っている最も近い親ノードを第２引数として渡す。ただし、そのような親ノードが存在しない場合、ｎｕｌｌを渡す。ｎｕｌｌは参照が無いことを意味している。
【０２００】
ステップ９９では、Ｓツリーインナーツリー生成を行う。引数として、左子（ｎｏｄｅ．ｌｅｆｔ）とインナーツリーを生成するときに参照する値の軸（ａｘｉｓ）を渡す。
【０２０１】
ステップ１００では、Ｓツリーインナーツリー生成を行う。引数として、右子（ｎｏｄｅ．ｒｉｇｈｔ）とインナーツリーを生成するときに参照する値の軸（ａｘｉｓ）を渡す。
【０２０２】
次に、Ｓツリーインナーセグメントツリー生成処理の動作例について説明する。図３９は、Ｓツリーインナーセグメントツリー生成処理の動作例を説明するためのフローチャートである。Ｓツリーインナーセグメントツリー生成処理では、第１の実施の形態におけるツリー生成部１１の動作と似た動作を行う。両者を対比して説明すると、図７との違いは、ステップ５５がステップ５８に置き換わっている点、ステップ５１がステップ５９に置き換わっている点である。
【０２０３】
ステップ５８では、ステップ５５で示している第１引数、第２引数に加えて、第３引数を取得する。第３引数をｔｈｒｅｓｈｏｌｄと置く。
【０２０４】
ステップ５９では、Ｓツリーインナースケルトン生成を実行する。スケルトン生成との違いは、第３引数として、閾値（ｔｈｒｅｓｈｏｌｄ）を渡しており、それが、生成されるインナーノードに設定される。
【０２０５】
次に、Ｓツリーインナースケルトン生成処理での動作例について説明する。図４０は、Ｓツリーインナースケルトン生成処理での動作例を示している。Ｓツリーインナースケルトン生成処理では、第１の実施の形態におけるスケルトン生成処理部１１１の動作を似た動作を行う。両者を対比して説明すると、図８との違いは、ステップ１６がステップ１８に置き換わっている点、ステップ４がステップ１９に置き換わっている点、ステップ１０がステップ２０に置き換わっている点、ステップ１３がステップ１０２１に置き換わっている点である。
【０２０６】
ステップ１８では、ステップ１６の第１引数、第２引数に加えて、第３引数を受けとっている。第３引数をｔｈｒｅｓｈｏｌｄと置く。
【０２０７】
ステップ１９では、Ｓツリーノード生成を行う。ノード生成との違いは、第６引数が追加されている点である。第６引数で指定された値は、ｘｔｈｒｅｓｈｏｌｄとして生成したノードと関連付けられる。この他、生成するノードの最小値はｎｌｉｓｔ［２×ｉ］．ｍｉｎと、最大値はｎｌｉｓｔ［２×ｉ＋１］．ｍａｘと、閾値はｎｌｉｓｔ［２×ｉ］．ｍａｘと、左子はｎｌｉｓｔ［２×ｉ］と、右子はｎｌｉｓｔ［２×ｉ＋１］とそれぞれ関連付けられる。Ｓツリー生成部５１は、生成したノードをＳツリー記憶部５３に記憶させる。
【０２０８】
ステップ２０では、Ｓツリー初回親生成を行う。ステップ１０の初回親生成との違いは、第３引数として閾値（ｔｈｒｅｓｈｏｌｄ）を渡している点であり、閾値は、親ノードを生成するときのｘｔｈｒｅｓｈｏｌｄとして設定される。
【０２０９】
ステップ１０２１では、Ｓツリー親生成を行う。ステップ１３の親生成との違いは、第３引数として閾値（ｔｈｒｅｓｈｏｌｄ）を渡している点であり、閾値は、親ノードを生成するときのｘｔｈｒｅｓｈｏｌｄとして設定される。
【０２１０】
次に、Ｓツリー初回親生成処理での動作について説明する。図４１は、Ｓツリー初回親生成処理での動作例を説明するためのフローチャートである。Ｓツリー初回親生成処理での動作は、第１の実施の形態におけるスケルトン生成処理部１１１での初回親生成処理と似ている。両者を対比して説明すると、図２０との違いは、ステップ３０がステップ３２に置き換わっている点、ステップ２４がステップ３３に置き換わっている点である。
【０２１１】
ステップ３２では、ステップ３０で示している第１引数、第２引数に加えて、第３引数を受ける。第３引数をｔｈｒｅｓｈｏｌｄと置く。
【０２１２】
ステップ３３では、Ｓツリーノード生成を行う。図４０のステップ１９と同様である。
【０２１３】
次に、Ｓツリー親生成処理での動作について説明する。図４２は、Ｓツリー親生成処理での動作例を説明するためのフローチャートである。Ｓツリー親生成処理での動作は、第１の実施の形態におけるスケルトン生成処理部１１１での親生成処理と似ている。両者を対比して説明すると、図１９との違いは、ステップ４６がステップ４８に置き換わっている点、ステップ４３がステップ４９に置き換わっている点である。
【０２１４】
ステップ４８では、ステップ４６で示している第１引数、第２引数に加えて、第３引数を受ける。第３引数をｔｈｒｅｓｈｏｌｄと置く。
【０２１５】
ステップ４９では、Ｓツリーノード生成を行う。図４０のステップ１９と同様である。
【０２１６】
次に先祖ノード設定処理での動作例について説明する。図４３は、先祖ノード設定処理での動作例を説明するためのフローチャートである。
【０２１７】
ステップ１３１では、第１引数をｎｏｄｅ、第2引数をａｎｏｄｅと置く。
【０２１８】
ステップ１３２では、ｎｏｄｅ．ｌｅｆｔがｎｕｌｌかどうかの判定を行う。これは、ｎｏｄｅがリーフノードかどうかの判定を行っている。ｎｏｄｅ．ｌｅｆｔがｎｕｌｌであればリーフノードである。ｎｏｄｅ．ｌｅｆｔがｎｕｌｌであれば、ステップ１３３に進む。ｎｏｄｅ．ｌｅｄｔがｎｕｌｌでなければ、ステップ１３４に進む。
【０２１９】
ステップ１３３では、先祖ノードとしてａｎｏｄｅをセットする。その後、先祖ノード設定を終了する。ステップ１３４では、ｎｏｄｅ．ｎＳｅｔが空集合(φ)かどうかを判定する。空集合であれば、ステップ１３７に進む。空集合でなければ、ステップ１３５に進む。
【０２２０】
ステップ１３５では、先祖ノードとしてａｎｏｄｅをセットする。その後、ステップ１３６に進む。
【０２２１】
ステップ１３６では、ａｎｏｄｅとしてｎｏｄｅを設定する。その後、ステップ１３７に進む。
【０２２２】
ステップ１３７では、左子（ｎｏｄｅ．ｌｅｆｔ）とａｎｏｄｅを引数として先祖ノード設定を行う。その後、ステップ１３８に進む。
【０２２３】
ステップ１３８では、右子（ｎｏｄｅ．ｒｉｇｈｔ）とａｎｏｄｅを引数として先祖ノード設定を行う。その後、先祖ノード設定を終了する。
【０２２４】
次に、インナーツリー接続処理での動作について説明する。図４４は、インナーツリー接続処理での動作を説明するためのフローチャートである。
【０２２５】
ステップ１５１では、第１引数をｎｏｄｅと置く。その後、ステップ１５２へ進む。
【０２２６】
ステップ１６０では、インナーツリーのルート（ｎｏｄｅ．ｉｒｏｏｔ）の左後継として、アウターツリーにおける左子に関連付けられたインナーツリーのルート（ｎｏｄｅ．ｌｅｆｔ．ｉｒｏｏｔ）を関連付ける。
【０２２７】
ステップ１６１では、インナーツリーのルート（ｎｏｄｅ．ｉｒｏｏｔ）の右後継として、アウターツリーにおける右子に関連付けられたインナーツリーのルート（ｎｏｄｅ．ｒｉｇｈｔ．ｉｒｏｏｔ）を関連付ける。
【０２２８】
ステップ１６０および１６１で、アウターツリーにおいて親子関係を有するノードにそれぞれ関連付けられた、インナーツリーのルート同士が接続される。
【０２２９】
ステップ１５２では、ｎｏｄｅ．ｌｅｆｔがｎｕｌｌかどうかを判定する。これは、ｎｏｄｅがリーフノードかどうかの判定をしている。ｎｏｄｅ．ｌｅｆｔがｎｕｌｌであれば、ｎｏｄｅはリーフノードである。ｎｏｄｅがリーフノードであれば、インナーツリー接続を終了する。ｎｏｄｅがリーフノードでなければ、ステップ１５３へ進む。
【０２３０】
ステップ１５３では、リーフノード取得を行う。引数として、リーフノード取得の対象となるツリーのルート（ｎｏｄｅ．ｉｒｏｏｔ）を指定する。戻り値としてリーフノードのリストを取得する。その後、ステップ１５４へ進む。
【０２３１】
ステップ１５４では、リーフノード取得を行う。ここでは、左子（ｎｏｄｅ．ｌｅｆｔ）に対してリーフノード取得を行う。その後、ステップ１５５へ進む。
【０２３２】
ステップ１５５では、リーフノード取得を行う。ここでは、右子（ｎｏｄｅ．ｒｉｇｈｔ）に対してリーフノード取得を行う。その後、ステップ１５６へ進む。
【０２３３】
ステップ１５６では、リーフノード左接続を行う。引数として、２つのリーフノードリストを渡す。第１引数として渡すリーフノードリストは、２つのアウターノードのうち、親ノードに対応するインナーツリーのリーフノードである。第２引数として渡すリーフノードリストは、２つのアウターノードのうち、左子ノードに対応するインナーツリーのリーフノードである。その後、ステップ１５７へ進む。
【０２３４】
ステップ１５７では、リーフノード右接続を行う。引数として、２つのリーフノードリストを渡す。第１引数として渡すリーフノードリストは、２つのアウターノードのうち、親ノードに対応するインナーツリーのリーフノードである。第２引数として渡すリーフノードリストは、２つのアウターノードのうち、右子ノードに対応するインナーツリーのリーフノードである。その後、ステップ１５８へ進む。
【０２３５】
ステップ１５８では、左子（ｎｏｄｅ．ｌｅｆｔ）に対してインナーツリー接続を実施する。その後、ステップ１５９へ進む。
【０２３６】
ステップ１５９では、右子（ｎｏｄｅ．ｒｉｇｈｔ）に対してインナーツリー接続を実施する。その後、インナーツリー接続を終了する。
【０２３７】
次に、リーフノード取得処理での動作例について説明する。図４５は、リーフノード取得処理での動作例を説明するためのフローチャートである。
【０２３８】
ステップ１７１では、第１引数をｎｏｄｅと置く。
【０２３９】
ステップ１７２では、ｎｏｄｅ．ｌｅｆｔがｎｕｌｌかどうかを判定する。ｎｕｌｌである場合、ステップ１７６へ進む。ｎｕｌｌでない場合、ステップ１７３へ進む。
【０２４０】
ステップ１７３では、左子（ｎｏｄｅ．ｌｅｆｔ）を引数としてリーフノード取得を行う。戻り値をｌｌｅａｖｅｓとする。その後、ステップ１７４へ進む。
【０２４１】
ステップ１７４では、右子（ｎｏｄｅ．ｒｉｇｈｔ）を引数としてリーフノード取得を行う。戻り値をｒｌｅａｖｅｓとする。その後、ステップ１７５へ進む。
【０２４２】
ステップ１７５では、ｌｌｅａｖｅｓとｒｌｅａｖｅｓをマージし、ｌｅａｖｅｓとする。その後、ステップ１７７へ進む。
【０２４３】
ステップ１７６では、ｎｏｄｅを唯一の要素として、それをｌｅａｖｅｓとする。その後、ステップ１７７へ進む。
【０２４４】
ステップ１７７では、ｌｅａｖｅｓを戻り値として返す。
【０２４５】
次に、リーフノード左接続処理での動作例について説明する。図４６は、リーフノード左接続処理での動作例を説明するためのフローチャートである。
【０２４６】
ステップ１９１では、第１引数をｐｌｉｓｔ、第２引数をｃｌｉｓｔとおく。その後、ステップ１９２へ進む。
【０２４７】
ステップ１９２では、カウンタとして用いるｉとｊをそれぞれ０に初期化する。その後、ステップ１９３へ進む。
【０２４８】
ステップ１９３では、ｉとｐｌｉｓｔの要素数（ｐｌｉｓｔ．ｓｉｚｅ）を比較する。i<ｐｌｉｓｔ．ｓｉｚｅであれば、リーフノード左接続を終了する。i<ｐｌｉｓｔ．ｓｉｚｅであれば、ステップ１９４に進む。このステップによって、ステップ１９４からステップ１９６の処理がｐｌｉｓｔ．ｓｉｚｅ回繰り返される。
【０２４９】
ステップ１９４では、ｃｌｉｓｔ［ｊ］．ｍｉｎとｐｌｉｓｔ［ｉ］．ｍｉｎとを比較する。ｃｌｉｓｔ［ｊ］．ｍｉｎ＜ｐｌｉｓｔ［ｉ］．ｍｉｎであれば、ステップ１９５へ進む。ｃｌｉｓｔ［ｊ］．ｍｉｎ＜ｐｌｉｓｔ［ｉ］．ｍｉｎでなければ、ステップ１９６へ進む。このステップでは、ｐｌｉｓｔのｉ番目の要素（ｐｌｉｓｔ［ｉ］）の範囲（ｐｌｉｓｔ［ｉ］．ｍｉｎからｐｌｉｓｔ［ｉ］．ｍａｘ）を、ｃｌｉｓｔのｊ番目の要素（ｃｌｉｓｔ［ｊ］）の範囲（ｃｌｉｓｔ［ｊ］．ｍｉｎからｃｌｉｓｔ［ｊ］．ｍａｘ）がカバーしているかどうかを判定するためのものである。
【０２５０】
ステップ１９５では、ｊをインクリメントする。その後、ステップ１９６へ進む。
【０２５１】
ステップ１９６では、ｐｌｉｓｔ［ｉ］．ｌｓｕｃｃｅｓｓｏｒとしてｃｌｉｓｔ［ｊ］を設定する。ここで、リーフノード同士の接続が行われている。その後、ステップ１９７でiをインクリメントし、ステップ１９３へ進む。
【０２５２】
次に、リーフノード右接続処理での動作例について説明する。図４７は、リーフノード右接続処理での動作例を説明するためのフローチャートである。図１２７との違いは、ステップ１９６がステップ１９８に置き換わっている点である。ステップ１９８では、ｐｌｉｓｔ［ｉ］．ｒｓｕｃｃｅｓｓｏｒとしてｃｌｉｓｔ［ｊ］を設定する。
【０２５３】
次に、第５の実施の形態により生成されるＳツリーの例について説明する。第５の実施の形態におけるＳツリー生成部５１は、図２０に示すパターンを入力として受け取ると、図４８に示すようなアウターツリーを生成する。
【０２５４】
図４８は、図２０に示すパターンを入力として受け取った際にＳツリー生成部５１により生成されるアウターツリーを示す概念図である。図４８において、各ノードの脇に記載されたａＳｅｔはそのノードと関連付けられた拡張ノードセットを、ｎＳｅｔはそのノードと関連付けられたノードセットをそれぞれ示している。
【０２５５】
図４９は、Ｓツリー生成部５１により生成されるアウターツリーの各ノードと関連付けられる範囲を示す表である。図４９に示すように、第５の実施形態では、ｘ軸における全ての範囲をカバーするｈ１、ｈ２、ｈ３、ｈ４、ｈ５が考慮されている。
【０２５６】
図５０は、図４８のノードａと関連付けられているインナーツリーを示す概念図である。第５の実施形態により生成されるインナーツリーは、ルートノードが左後継ノードと右後継ノードへの参照をと関連付けられる。例えば、ノードａａは左後継ノードｂａへの参照及び右後継ノードｃａへの参照と関連付けられる。尚、図５０においてノードａａからノードｂａへの矢印の形状は、ノードｂａがノードａａの左後継であることを意味している。また、ノードａａからノードｃａへの矢印の形状は、ノードｃａがノードａａの右後継であることを意味している。また、ノードａｄの下にあるｖ１は、そのノードに範囲ｖ１（図２０に示す範囲ｖ１）が対応付けられていることを意味する。
【０２５７】
図５１は、図４８のノードｂと関連付けられているインナーツリーを示す概念図である。図５２は、図４８のノードｃと関連付けられているインナーツリーを示す概念図である。図５３は、図４８のノードｄと関連付けられているインナーツリーを示す概念図である。図５４は、図４８のノードｅと関連付けられているインナーツリーを示す概念図である。図５４において、ノードｅａの脇の「｛Ａ｝」という記載は、ノードｅａのｎＳｅｔがパターンＩＤがＡであるパターンを一つ要素として持つことを示している。また、図５４において、ノードｅｄからノードｅａへの矢印の形状は、ノードｅａがノードｅｄの先祖であることを意味している。
【０２５８】
図５５は、図４８のノードfと関連付けられているインナーツリーを示す概念図である。図５６は、図４８のノードｇと関連付けられているインナーツリーを示す概念図である。図５７は、図４８のノードｈと関連付けられているインナーツリーを示す概念図である。図５８は、図４８のノードｉと関連付けられているインナーツリーを示す概念図である。図５６、図５７、図５８において、一つのノードと関連付けられた範囲が、複数の範囲からなる場合には、「，」を用いて列挙してあり、ノードｇａ、ｈａ、ｉａはそれぞれｙ軸における全範囲と関連付けられている。
【０２５９】
第５の実施の形態により生成されるＳツリーでは、木構造の各ノードと関連付けられる範囲との意味を崩すことなく、ルートノードに、データの値の取りうる全範囲が関連付けられている。
【０２６０】
第５の実施の形態による木構造を持つデータは、ルートノードに特定の軸におけるデータの取りうる全範囲が関連付けられているので、木構造の各ノードに関連付けられる範囲と該ノードに関連付けられるｎＳｅｔの意味を崩すことなく、ルートノードのｎＳｅｔに特定の軸における範囲が指定されていないパターンを含めることができる。つまり、第５の実施の形態で生成される木構造を持つデータは、特定の軸における範囲が指定されていないパターンを用いるパターンマッチング方法に利用できる。
【０２６１】
また、第５の実施の形態による木構造を持つデータは、ルートノードに特定の軸におけるデータの取りうる全範囲が関連付けられているので、入力されたデータの値が指定されていない場合や不明である場合にもマッチするパターンを検知することができるパターンマッチングに用いることができる。
【０２６２】
［第６の実施の形態］
次に、第６の実施の形態について図面を参照して説明する。図５９は、第６の実施の形態の構成例を示す図面である。図５９によれば、第６の実施の形態の構成例は、Ｓツリー記憶部５３、Ｓツリーサーチ部６１を有する情報処理装置である。第６の実施の形態では、第５の実施の形態と同じく、扱うデータが二次元（ここではｘ軸及びｙ軸とする）の場合について説明する。
【０２６３】
Ｓツリー記憶部５３は、第５の実施の形態におけるＳツリー生成部５１が生成した情報を記憶している。ここでは、図５０乃至５８に示す情報が記憶されているとして説明を行う。その意味は第５の実施の形態にて説明したとおりである。
【０２６４】
Ｓツリーサーチ部６１は、２次元の値を持つデータとＳツリー記憶部５３に記憶された木構造におけるノードを示す情報を受け取ると、Ｓツリー記憶部５３に記憶された木構造の情報を探索し、その値にマッチするパターンのリストを出力する。Ｓツリーサーチ部６１は、マッチしたパターンの出力先とマッチパターンＩＤリストを記憶する記憶部を備える。
【０２６５】
Ｓツリーサーチ部６１は、Ｓツリー記憶部５３に記憶されている情報を探索するインナーツリーサーチ部６１１、ルートサーチ部６１２、アンセスターサーチ部６１３とから構成される。
【０２６６】
インナーツリーサーチ部６１１は、データと、インナーツリーのノードを示す情報と、を入力として受け取る。インナーツリーサーチ部６１１は，入力されたデータの値にマッチするパターンのリストをマッチパターンＩＤリストに出力する。動作は後述される。
【０２６７】
ルートサーチ部６１２は、データと、インナーツリーのルーチノードを示す情報と、を入力として受け取る。ルートサーチ部６１２は，入力されたデータの値にマッチするパターンのリストをマッチパターンＩＤリストに出力する。動作は後述される。
【０２６８】
アンセスターサーチ部６１３は、データと、インナーツリーのノードを示す情報と、を入力として受け取り。アンセスターサーチ部６１３は、入力されたデータの値にマッチするパターンのリストをマッチパターンＩＤリストに出力する。動作は後述される。
【０２６９】
次に、第６の実施の形態の情報処理装置の動作の例について説明する。
【０２７０】
２次元の値を持つデータを受け取ると、Ｓツリーサーチ部６１は動作を開始する。Ｓツリーサーチ部６１は、当初、データと、Ｓツリー記憶部５３に記憶された木構造のデータにおけるルートノードを示す情報を入力として受け取る。そして、Ｓツリーサーチ部６１は、Ｓツリー記憶部５３に記憶された木構造を探索し、その値にマッチするパターンのリストを出力する。
【０２７１】
Ｓツリーサーチ部６１の動作について説明する。ツリーサーチ部４１の受け取るデータは２次元の値を持つ（図２９）。Ｓツリーサーチ部６１は、データを受け取ると、インナーツリーサーチ部６１１に、データと、アウターツリーのルートノードに関連付けられたインナーツリーのルートを示す情報（ｒｏｏｔ．ｉｒｏｏｔ）とを渡し、探索を開始する。
【０２７２】
図６０は、インナーツリーサーチ部６１１の動作の例を説明するためのフローチャートである。
【０２７３】
インナーツリーサーチ部６１１は、入力されたインナーツリーのルートを示す情報で特定されるノード（ｉｎｏｄｅ）がルートノードであるか否かを調べる（ステップｉ１２）。これは、ｉｎｏｄｅ．ｆｌａｇを調べることで可能である。ルートノードでない場合、インナーツリーサーチ部６１１は、ステップｉ１へ処理を進める。
【０２７４】
ルートノードである場合、インナーツリーサーチ部６１１は、入力されたデータのｙ軸の値が？であるかを調べる（ステップｉ１３）。ｙ軸の値が？でなければ、インナーツリーサーチ部６１１は、ステップｉ１へ処理を進める。ｙ軸の値が？であれば、インナーツリーサーチ部６１１は、ステップｉ１４へ処理を進める。
【０２７５】
インナーツリーサーチ部６１１は、ステップｉ１４で、ルートサーチ部に、ｉｎｏｄｅを渡し、動作させる。その後、インナーツリーサーチ部６１１は処理を終了する。
【０２７６】
ステップｉ１へ進むと、インナーツリーサーチ部６１１は、入力されたインナーツリーのノードを示す情報で特定されるノード（ｉｎｏｄｅ）のｎＳｅｔをマッチパターンＩＤリストに追加する（ステップｉ１）。ここで、マッチパターンＩＤリストは、Ｓツリーサーチ部６１が用いる出力用のバッファであってもよい。
【０２７７】
次に、インナーツリーサーチ部６１１は、ｉｎｏｄｅがリーフノードかどうかを判定する（ステップｉ２）。判定方法は上述の通りである。
【０２７８】
ステップｉ２でリーフノードであると判定した場合、インナーツリーサーチ部６１１は、入力されたデータのｘ軸の値が？であるかどうかの判定を行う（ｉ１５）。ｘ軸の値が？であれば、インナーツリーサーチ部６１１は処理を終了する。？でなければ、インナーツリーサーチ部６１１は、ステップｉ６へ処理を進める。
【０２７９】
ステップｉ２の結果、ｉｎｏｄｅがリーフノードでなければ、インナーツリーサーチ部６１１は、ｙ軸の値とｉｎｏｄｅ．ｔｈｒｅｓｈｏｌｄとを比較する（ステップｉ３）。ｙ≦ｉｎｏｄｅ．ｔｈｒｅｓｈｏｌｄの場合、インナーツリーサーチ部６１１は、入力されたデータと左子とをインナーツリーサーチ部６１１に入力して再帰的に探索を行う（ステップｉ４）。ｙ≦ｉｎｏｄｅ．ｔｈｒｅｓｈｏｌｄでなければ、インナーツリーサーチ部６１１は、入力されたデータと右子とをインナーツリーサーチ部６１１に入力して再帰的に探索を行う（ステップｉ５）。ステップｉ４又はｉ５の後、インナーツリーサーチ部６１１は処理を終了する。
【０２８０】
ステップｉ２の結果、ｉｎｏｄｅがリーフノードであれば、インナーツリーサーチ部６１１は、ｉｎｏｄｅにｘｔｈｒｅｓｈｏｌｄが関連付けられているかどうかを調べる（ステップｉ６）。関連付けられている場合、インナーツリーサーチ部６１１は、ｘ軸の値とｉｎｏｄｅ．ｘｔｈｒｅｓｈｏｌｄとを比較する（ステップｉ７）。関連付けられていない場合、インナーツリーサーチ部６１１は、処理を終了する。
【０２８１】
ステップｉ７で、ｘ≦ｉｎｏｄｅ．ｘｔｈｒｅｓｈｏｌｄであるならば、インナーツリーサーチ部６１１は、ｉｎｏｄｅに左後継が関連付けられているかどうかを調べる（ステップｉ８）。左後継と関連付けられている場合、インナーツリーサーチ部６１１は、入力されたデータと左後継の情報とをアンセスターサーチ部に渡し、アンセスターサーチ部を動作させる（ステップｉ９）。左後継と関連付けられていない場合、インナーツリーサーチ部６１１は、処理を終了する。
【０２８２】
ステップｉ７で、ｘ≦ｉｎｏｄｅ．ｘｔｈｒｅｓｈｏｌｄでなければ、インナーツリーサーチ部６１１は、ｉｎｏｄｅに右後継が関連付けられているかどうかを調べる（ステップｉ１０）。右後継と関連付けられている場合、インナーツリーサーチ部６１１は、入力されたデータと右後継の情報とをアンセスターサーチ部に渡し、アンセスターサーチ部を動作させる（ステップｉ１１）。右後継と関連付けられていない場合、インナーツリーサーチ部６１１は、処理を終了する。
【０２８３】
次に、ルートサーチ部６１２の動作例について説明する。図６１は、ルートサーチの動作例を説明するためのフローチャートである。
【０２８４】
ルートサーチ部６１２は、データとインナーツリーのノードを示す情報とを受け取ると、受け取ったノードを示す情報で特定されるノード（ｒｎｏｄｅ）のｎＳｅｔをマッチパターンＩＤリストに追加する（ステップｒ１）。
【０２８５】
次に、ルートサーチ部６１２は、ｒｎｏｄｅがｘ閾値と関連付けられているかどうかを調べる(ステップｒ２)。関連付けられていなければ、ルートサーチ部６１２は、処理を終了する。関連付けられていれば、ルートサーチ部６１２は、処理をステップｒ３へ進める。
【０２８６】
ステップｒ３で、ルートサーチ部６１２は、入力されたデータのｘ軸の値とｒｎｏｄｅ．ｘｔｈｒｅｓｈｏｌｄとを比較する（ステップｒ３）ｘ≦ｒｎｏｄｅ．ｘｔｈｒｅｓｈｏｌｄであれば、ルートサーチ部６１２は、入力されたデータと左後継とをルートサーチ部６１２に入力し、再帰的に探索を行う（ステップｒ４）。ｘ≦ｒｎｏｄｅ．ｘｔｈｒｅｓｈｏｌｄでなければ、ルートサーチ部６１２は、入力されたデータと右後継とをルートサーチ部６１２に入力し、再帰的に探索を行う（ステップｒ５）。その後、ルートサーチ部６１２は処理を終了する。
【０２８７】
次に、アンセスターサーチ部６１３の動作例について説明する。図６２は、アンセスターサーチ部の動作例を説明するためのフローチャートである。
【０２８８】
アンセスターサーチ部６１３は、データとインナーツリーのノードを示す情報を受け取ると、受け取ったインナーツリーのノードを示す情報で特定されるノード（ｎｏｄｅ）のｎＳｅｔをマッチパターンＩＤリストに追加する（ステップａ１）。
【０２８９】
次に、アンセスターサーチ部６１３は、ｎｏｄｅが先祖と関連付けられているかどうかを調べる（ステップａ２）。関連付けられている場合、アンセスターサーチ部６１３は、データと先祖とをアンセスターサーチ部６１３に入力し再帰的に探索を行う（ステップａ３）。関連付けられていない場合、アンセスターサーチ部６１３は、ステップａ４へ処理を進める。
【０２９０】
次に、アンセスターサーチ部６１３は、ｎｏｄｅがリーフノードかどうかを判定する（ステップａ４）判定方法は上述の通りである。リーフノードでなければ、アンセスターサーチ部６１３は、処理を終了する。リーフノードであれば、アンセスターサーチ部６１３は、ステップａ５へ処理を進める。
【０２９１】
次に、アンセスターサーチ部６１３は、ｎｏｄｅがｘ閾値と関連付けられているかどうかを調べる（ステップａ５）。関連付けられていなければ、アンセスターサーチ部６１３は処理を終了する。関連付けられていれば、入力されたデータのｘ軸の値とｎｏｄｅ．ｘｔｈｒｅｓｈｏｌｄとを比較する（ステップａ６）。
【０２９２】
ステップａ６で、ｘ≦ｎｏｄｅ．ｘｔｈｒｅｓｈｏｌｄであるならば、アンセスターサーチ部６１３は、ｎｏｄｅが左後継と関連付けられているかどうかを調べる（ステップａ７）。関連付けられていれば、アンセスターサーチ部６１３は、データと左後継を示す情報とをアンセスターサーチ部６１３に入力し、再帰的に探索を行う（ステップａ８）。関連付けられていなければ、アンセスターサーチ部６１３は処理を終了する。
【０２９３】
ステップａ６で、ｘ≦ｎｏｄｅ．ｘｔｈｒｅｓｈｏｌｄでなければ、アンセスターサーチ部６１３は、ｎｏｄｅが右後継と関連付けられているかどうかを調べる（ステップａ９）。関連付けられていなければ、アンセスターサーチ部６１３は、データと右後継を示す情報とをアンセスターサーチ部６１３に入力し、再帰的に探索を行う（ステップａ１０）。関連付けられていなければ、アンセスターサーチ部６１３は処理を終了する。
【０２９４】
第６の実施の形態によれば、Ｓツリー記憶部５３の記憶する木構造を持つデータが、ルートノードに特定の軸におけるデータの取りうる全範囲が関連付けられているので、木構造の各ノードに関連付けられる範囲と該ノードに関連付けられるｎＳｅｔの意味を崩すことなく、ルートノードのｎＳｅｔに特定の軸における範囲が指定されていないパターンを含めることができる。ツリーサーチ部Ｆ１は、この木構造を持つデータを用いて、入力されたデータにマッチするパターンのリストを出力するので、特定の軸における範囲が指定されていないパターンを用いるパターンマッチング方法を提供することができる。
【０２９５】
また、第６の実施の形態によれば、Ｓツリー記憶部５３の記憶するインナーツリーのルートノードを処理する際に、入力されたデータが値を持つか否かを調べ、持たない場合にはルートノードのｎＳｅｔをマッチング結果とする。このため、そのことが木構造の各ノードに関連付けられる範囲と該ノードに関連付けられるｎＳｅｔの意味を崩さずに、データが特定の軸における値を持たない場合であっても、その軸に関する範囲が指定されていないパターンにマッチさせることができる。したがって、第６の実施の形態によれば、入力されるデータが特定の軸における値を持っていない場合にも機能するパターンマッチング方法を提供することができる。
【０２９６】
［第７の実施の形態］
次に、第７の実施の形態について図面を参照して説明する。図６３は、第７の実施の形態の構成例を示す図面である。図６３によれば、第７の実施の形態の構成例は、ツリー生成部１１、定義域記憶部１２、ツリー記憶部１３、ツリーサーチ部２１と、を有する情報処理装置である。第１の実施の形態又は第２の実施の形態と同一の構成要素については同一の番号を付した。
【０２９７】
次に、第７の実施の形態の動作について説明する。第７の実施の形態である情報処理装置は、一つ以上のパターンを受け取ると、ツリー生成部１１が第１の実施の形態において説明した動作を行い、ツリー記憶部１３に木構造のデータを記憶させる。その後、データを受け取ると、ツリーサーチ部２１が第２の実施の形態において説明した動作を行い、そのデータにマッチするパターンのリストを出力する。
【０２９８】
第７の実施の形態によれば、ツリー記憶部１３の記憶する木構造を持つデータが、ルートノードに特定の軸におけるデータの取りうる全範囲が関連付けられているので、木構造の各ノードに関連付けられる範囲と該ノードに関連付けられるｎＳｅｔの意味を崩すことなく、ルートノードのｎＳｅｔに特定の軸における範囲が指定されていないパターンを含めることができる。ツリーサーチ部２１は、この木構造を持つデータを用いて、入力されたデータにマッチするパターンのリストを出力するので、特定の軸における範囲が指定されていないパターンを用いるパターンマッチング方法を提供することができる。
【０２９９】
また、第７の実施の形態によれば、ツリー記憶部１３の記憶する木構造のルートノードａを処理する際に、入力されたデータが値を持つか否かを調べ、持たない場合にはルートノードのｎＳｅｔをマッチング結果とする。このため、そのことが木構造の各ノードに関連付けられる範囲と該ノードに関連付けられるｎＳｅｔの意味を崩さずに、データが特定の軸における値を持たない場合であっても、その軸に関する範囲が指定されていないパターンにマッチさせることができる。したがって、第７の実施の形態によれば、入力されるデータが特定の軸における値を持っていない場合にも機能するパターンマッチング方法を提供することができる。
【０３００】
［第８の実施の形態］
次に、第８の実施の形態について図面を参照して説明する。図６４は、第８の実施の形態の構成例を示す図面である。図６４によれば、第８の実施の形態の構成例は、ツリー生成部３１、定義域記憶部３２、ツリー記憶部３３、ツリーサーチ部４１と、を有する情報処理装置である。第３の実施の形態又は第４の実施の形態と同一の構成要素については同一の番号を付した。
【０３０１】
次に、第８の実施の形態の動作について説明する。第８の実施の形態である情報処理装置は、一つ以上のパターンを受け取ると、ツリー生成部３１が第３の実施の形態において説明した動作を行い、ツリー記憶部３３に木構造のデータを記憶させる。その後、データを受け取ると、ツリーサーチ部４１が第４の実施の形態において説明した動作を行い、そのデータにマッチするパターンのリストを出力する。
【０３０２】
第８の実施の形態によれば、ツリー記憶部３３の記憶する木構造を持つデータが、ルートノードに特定の軸におけるデータの取りうる全範囲が関連付けられているので、木構造の各ノードに関連付けられる範囲と該ノードに関連付けられるｎＳｅｔの意味を崩すことなく、ルートノードのｎＳｅｔに特定の軸における範囲が指定されていないパターンを含めることができる。ツリーサーチ部４１は、この木構造を持つデータを用いて、入力されたデータにマッチするパターンのリストを出力するので、特定の軸における範囲が指定されていないパターンを用いるパターンマッチング方法を提供することができる。
【０３０３】
また、第８の実施の形態によれば、ツリー記憶部３３の記憶するインナーツリーのルートノードを処理する際に、入力されたデータが値を持つか否かを調べ、持たない場合にはルートノードのｎＳｅｔをマッチング結果とする。このため、そのことが木構造の各ノードに関連付けられる範囲と該ノードに関連付けられるｎＳｅｔの意味を崩さずに、データが特定の軸における値を持たない場合であっても、その軸に関する範囲が指定されていないパターンにマッチさせることができる。したがって、第８の実施の形態によれば、入力されるデータが特定の軸における値を持っていない場合にも機能するパターンマッチング方法を提供することができる。
【０３０４】
［第９の実施の形態］
次に、第９の実施の形態について図面を参照して説明する。図６５は、第９の実施の形態の構成例を示す図面である。図６５によれば、第９の実施の形態の構成例は、Ｓツリー生成部５１、定義域記憶部３２、Ｓツリー記憶部５３、Ｓツリーサーチ部６１と、を有する情報処理装置である。第５の実施の形態又は第６の実施の形態と同一の構成要素については同一の番号を付した。
【０３０５】
次に、第９実施の形態の動作について説明する。第９の実施の形態である情報処理装置は、一つ以上のパターンを受け取ると、Ｓツリー生成部５１が第５の実施の形態において説明した動作を行い、Ｓツリー記憶部３３に木構造のデータを記憶させる。その後、データを受け取ると、Ｓツリーサーチ部６１が第６の実施の形態において説明した動作を行い、そのデータにマッチするパターンのリストを出力する。
【０３０６】
第９の実施の形態によれば、Ｓツリー記憶部５３の記憶する木構造を持つデータが、ルートノードに特定の軸におけるデータの取りうる全範囲が関連付けられているので、木構造の各ノードに関連付けられる範囲と該ノードに関連付けられるｎＳｅｔの意味を崩すことなく、ルートノードのｎＳｅｔに特定の軸における範囲が指定されていないパターンを含めることができる。ツリーサーチ部Ｆ１は、この木構造を持つデータを用いて、入力されたデータにマッチするパターンのリストを出力するので、特定の軸における範囲が指定されていないパターンを用いるパターンマッチング方法を提供することができる。
【０３０７】
また、第９の実施の形態によれば、Ｓツリー記憶部５３の記憶するインナーツリーのルートノードを処理する際に、入力されたデータが値を持つか否かを調べ、持たない場合にはルートノードのｎＳｅｔをマッチング結果とする。このため、そのことが木構造の各ノードに関連付けられる範囲と該ノードに関連付けられるｎＳｅｔの意味を崩さずに、データが特定の軸における値を持たない場合であっても、その軸に関する範囲が指定されていないパターンにマッチさせることができる。したがって、第６の実施の形態によれば、入力されるデータが特定の軸における値を持っていない場合にも機能するパターンマッチング方法を提供することができる。
【産業上の利用可能性】
【０３０８】
本発明は、例えば、登録したパターンへの一致を検知する処理を行うシステムに用いることができる。例えば、株価の変動を検知したり、その検知に基づく操作を行うシステム、株価の変動を観測するシステムや、プレゼンス情報の検知を行うシステムに用いることができる。他の例としては、環境情報の検知を行うシステムなどにも好適に利用することができる。
【図面の簡単な説明】
【０３０９】
【図１】第１の実施の形態の構成例を示すブロック図である。
【図２】第１の実施の形態の説明に用いる図である。
【図３】第１の実施の形態の説明に用いる図である。
【図４】第１の実施の形態の説明に用いる図である。
【図５】第１の実施の形態の説明に用いる図である。
【図６】第１の実施の形態の説明に用いる図である。
【図７】第１の実施の形態の動作の説明に用いる図である。
【図８】第１の実施の形態の動作の説明に用いる図である。
【図９】第１の実施の形態の動作の説明に用いる図である。
【図１０】第１の実施の形態の動作の説明に用いる図である。
【図１１】第１の実施の形態の動作の説明に用いる図である。
【図１２】関連する技術の説明に用いる図である。
【図１３】第１の実施の形態の説明に用いる図である。
【図１４】第１の実施の形態の説明に用いる図である。
【図１５】第１の実施の形態により生成されるデータの例を示す概念図である。
【図１６】第２の実施の形態の構成例を示すブロック図である。
【図１７】第２の実施の形態の動作の説明に用いるフローチャートである。
【図１８】第３の実施の形態の構成例を示すブロック図である。
【図１９】第３の実施の形態における入力例を示す表である。
【図２０】第３の実施の形態の説明に用いる図である。
【図２１】第３の実施の形態で用いられるデータ構造の例を示す表である。
【図２２】第３の実施の形態の動作の説明に用いるフローチャートである。
【図２３】第３の実施の形態の動作の説明に用いるフローチャートである。
【図２４】第３の実施の形態において生成されるデータの例を示す概念図である。
【図２５】第３の実施の形態において生成されるデータの例を示す概念図である。
【図２６】第３の実施の形態において生成されるデータの例を示す概念図である。
【図２７】第３の実施の形態において生成されるデータの例を示す概念図である。
【図２８】第４の実施の形態の構成例を示すブロック図である。
【図２９】第４の実施の形態における入力データの構造の例を示す図である。
【図３０】第４の実施の形態の動作の説明に用いるフローチャートである。
【図３１】第４の実施の形態の動作の説明に用いるフローチャートである。
【図３２】第５の実施の形態の構成例を示すブロック図である。
【図３３】第５の実施の形態で用いられるデータ構造の例を示す表である。
【図３４】第５の実施の形態で用いられるデータ構造の例を示す表である。
【図３５】第５の実施の形態の動作の説明に用いるフローチャートである。
【図３６】第５の実施の形態の動作の説明に用いるフローチャートである。
【図３７】第５の実施の形態の動作の説明に用いるフローチャートである。
【図３８】第５の実施の形態の動作の説明に用いるフローチャートである。
【図３９】第５の実施の形態の動作の説明に用いるフローチャートである。
【図４０】第５の実施の形態の動作の説明に用いるフローチャートである。
【図４１】第５の実施の形態の動作の説明に用いるフローチャートである。
【図４２】第５の実施の形態の動作の説明に用いるフローチャートである。
【図４３】第５の実施の形態の動作の説明に用いるフローチャートである。
【図４４】第５の実施の形態の動作の説明に用いるフローチャートである。
【図４５】第５の実施の形態の動作の説明に用いるフローチャートである。
【図４６】第５の実施の形態の動作の説明に用いるフローチャートである。
【図４７】第５の実施の形態の動作の説明に用いるフローチャートである。
【図４８】第５の実施の形態において生成されるデータの例を示す概念図である。
【図４９】第５の実施の形態において生成されるデータの例を示す概念図である。
【図５０】第５の実施の形態において生成されるデータの例を示す概念図である。
【図５１】第５の実施の形態において生成されるデータの例を示す概念図である。
【図５２】第５の実施の形態において生成されるデータの例を示す概念図である。
【図５３】第５の実施の形態において生成されるデータの例を示す概念図である。
【図５４】第５の実施の形態において生成されるデータの例を示す概念図である。
【図５５】第５の実施の形態において生成されるデータの例を示す概念図である。
【図５６】第５の実施の形態において生成されるデータの例を示す概念図である。
【図５７】第５の実施の形態において生成されるデータの例を示す概念図である。
【図５８】第５の実施の形態において生成されるデータの例を示す概念図である。
【図５９】第６の実施の形態の構成例を示すブロック図である。
【図６０】第６の実施の形態の動作の説明に用いるフローチャートである。
【図６１】第６の実施の形態の動作の説明に用いるフローチャートである。
【図６２】第６の実施の形態の動作の説明に用いるフローチャートである。
【図６３】第７の実施の形態の構成例を示すブロック図である。
【図６４】第８の実施の形態の構成例を示すブロック図である。
【図６５】第９の実施の形態の構成例を示すブロック図である。
【図６６】関連する技術の説明に用いる図である。
【符号の説明】
【０３１０】
１  情報処理装置
２  情報処理装置
３  情報処理装置
４  情報処理装置
５  情報処理装置
６  情報処理装置
７  情報処理装置
８  情報処理装置
９  情報処理装置
１１  ツリー生成部
１２  定義域記憶部
１３  ツリー記憶部
２１  ツリーサーチ部
３１  ツリー生成部
３２  定義域記憶部
３３  ツリー記憶部
４１  ツリーサーチ部
５１  Ｓツリー生成部
５３  Ｓツリー記憶部
６１  Ｓツリーサーチ部
１１１  スケルトン生成処理部
１１２  パターン挿入部
３１１  アウターツリー生成部
３１２  インナーツリー生成部
４１１  アウターツリーサーチ部
４１２  インナーツリーサーチ部
６１１  インナーツリーサーチ部
６１２  ルートサーチ部
６１３  アンセスターサーチ部
【図１】
2009163564.tif 000003
【図２】
2009163564.tif 000004
【図３】
2009163564.tif 000005
【図４】
2009163564.tif 000006
【図５】
2009163564.tif 000007
【図６】
2009163564.tif 000008
【図７】
2009163564.tif 000009
【図８】
2009163564.tif 000010
【図９】
2009163564.tif 000011
【図１０】
2009163564.tif 000012
【図１１】
2009163564.tif 000013
【図１２】
2009163564.tif 000014
【図１３】
2009163564.tif 000015
【図１４】
2009163564.tif 000016
【図１５】
2009163564.tif 000017
【図１６】
2009163564.tif 000018
【図１７】
2009163564.tif 000019
【図１８】
2009163564.tif 000020
【図１９】
2009163564.tif 000021
【図２０】
2009163564.tif 000022
【図２１】
2009163564.tif 000023
【図２２】
2009163564.tif 000024
【図２３】
2009163564.tif 000025
【図２４】
2009163564.tif 000026
【図２５】
2009163564.tif 000027
【図２６】
2009163564.tif 000028
【図２７】
2009163564.tif 000029
【図２８】
2009163564.tif 000030
【図２９】
2009163564.tif 000031
【図３０】
2009163564.tif 000032
【図３１】
2009163564.tif 000033
【図３２】
2009163564.tif 000034
【図３３】
2009163564.tif 000035
【図３４】
2009163564.tif 000036
【図３５】
2009163564.tif 000037
【図３６】
2009163564.tif 000038
【図３７】
2009163564.tif 000039
【図３８】
2009163564.tif 000040
【図３９】
2009163564.tif 000041
【図４０】
2009163564.tif 000042
【図４１】
2009163564.tif 000043
【図４２】
2009163564.tif 000044
【図４３】
2009163564.tif 000045
【図４４】
2009163564.tif 000046
【図４５】
2009163564.tif 000047
【図４６】
2009163564.tif 000048
【図４７】
2009163564.tif 000049
【図４８】
2009163564.tif 000050
【図４９】
2009163564.tif 000051
【図５０】
2009163564.tif 000052
【図５１】
2009163564.tif 000053
【図５２】
2009163564.tif 000054
【図５３】
2009163564.tif 000055
【図５４】
2009163564.tif 000056
【図５５】
2009163564.tif 000057
【図５６】
2009163564.tif 000058
【図５７】
2009163564.tif 000059
【図５８】
2009163564.tif 000060
【図５９】
2009163564.tif 000061
【図６０】
2009163564.tif 000062
【図６１】
2009163564.tif 000063
【図６２】
2009163564.tif 000064
【図６３】
2009163564.tif 000065
【図６４】
2009163564.tif 000066
【図６５】
2009163564.tif 000067
【図６６】
2009163564.tif 000068