(57)【要約】【課題】ＸＭＬデータ中のクエリの指定箇所を特定する場合の計算効率を向上させること。【解決手段】検索装置１００は、イベント木作成部１６０ｄが、イベント木データ１５０ｆを構成するノード構造体の述部（述部ノードに対応）に、クエリの制約条件を満たしている旨を示す「真」または、クエリの制約条件を満たしていない旨を示す「偽」を設定する。そして、イベント木走査部１６０ｅが、イベント木データ１５０ｆを走査する場合に、ノード構造体の述部を参照し、述部が「真」の場合には、所定の順序規則に従って走査を継続し、「偽」の場合には、配下に接続されたノード構造体の走査をスキップする。【選択図】        図７
2010140258.tif 000002
【特許請求の範囲】
【請求項１】
検索装置が、
複数のノードにより階層構造を成す文書データの検索式を取得した場合に、前記検索式に基づいて、前記検索式の述部の条件を満たしている旨を示す真フラグまたは前記検索式の述部の条件を満たしていない旨を示す偽フラグを前記文書データの述部ノードに設定したリストを作成する真偽フラグ設定ステップと、
前記リストを走査して、前記検索式によって指定されるデータを前記文書データから検索する検索ステップと
を含んだ検索方法。
【請求項２】
前記検索ステップは、前記リストを走査する場合に、述部ノードに設定されたフラグの真偽判定を行い、述部ノードに設定されたフラグが真フラグの場合には所定の順序規則に従って走査を行い、述部ノードに設定されたフラグが偽フラグの場合には、偽フラグを設定された述部ノードの配下に接続されたノードの走査をスキップし、配列の次の要素に移動することで、前記検索式によって指定されるデータを前記文書データから検索する請求項１に記載の検索方法。
【請求項３】
複数のノードにより階層構造を成す文書データの検索式を取得した場合に、前記検索式に基づいて、前記検索式の述部の条件を満たしている旨を示す真フラグまたは前記検索式の述部の条件を満たしていない旨を示す偽フラグを前記文書データの述部ノードに設定したリストを作成する真偽フラグ設定手段と、
前記リストを走査して、前記検索式によって指定されるデータを前記文書データから検索する検索手段と
を有する検索装置。
【請求項４】
前記検索手段は、前記リストを走査する場合に、述部ノードに設定されたフラグの真偽判定を行い、述部ノードに設定されたフラグが真フラグの場合には所定の順序規則に従って走査を行い、述部ノードに設定されたフラグが偽フラグの場合には、偽フラグを設定された述部ノードの配下に接続されたノードの走査をスキップし、配列の次の要素に移動することで、前記検索式によって指定されるデータを前記文書データから検索する請求項３に記載の検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、検索式に対応する文書データを検索する検索方法および検索装置に関するものである。
【背景技術】
【０００２】
近年、コンピュータで処理される文書データとして、ＸＭＬ（Extensible  Markup  Language）等のマークアップ言語が利用されている。このＸＭＬは、異なる情報システムの間で、特にインターネットを介して、構造化された文書や構造化されたデータの共有を容易にすることが出来るため、コンピュータにおいてますます多用されてきている（以下、ＸＭＬに基づいて記述された階層構造をなす文書データをＸＭＬデータと表記する）。
【０００３】
そして、ＸＭＬデータから所望のデータを検出するものとして、ＸＰａｔｈ（XML  Path  Language）クエリが用いられる（以下、クエリと表記する）。この、クエリは、ＸＭＬデータのための標準クエリ言語であり、ＸＭＬの複雑な木構造に対して検索式を記述する能力を持つ。
【０００４】
クエリに基づいてＸＭＬデータからデータを検出する場合には、例えば、ＸＭＬデータをスキャンして、階層リストを構築した後に、階層リスト構造をスキャンして、クエリの埋め込みを求めることで、ＸＭＬデータ中のクエリの指定箇所を特定し、指定箇所のデータを検出している（例えば、非特許文献１参照）。
【０００５】
【非特許文献１】TwigList[Qin  et  al.;DASFAA'07]
【非特許文献２】TwigStack[Bruno  et  al.;SIGMOD'02]
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述した従来の技術では、ＸＭＬデータ中のクエリの指定箇所を特定する場合に、階層リスト構造のスキャンを何度も無駄に繰り返す場合があり、計算効率が悪いという問題があった。
【０００７】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、ＸＭＬデータ中のクエリの指定箇所を特定する場合の計算効率を向上させることができる検索方法および検索装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するため、この検索方法は、検索装置が、複数のノードにより階層構造を成す文書データの検索式を取得した場合に、前記検索式に基づいて、前記検索式の述部の条件を満たしている旨を示す真フラグまたは前記検索式の述部の条件を満たしていない旨を示す偽フラグを前記文書データの述部ノードに設定したリストを作成する真偽フラグ設定ステップと、前記リストを走査して、前記検索式によって指定されるデータを前記文書データから検索する検索ステップとを含むことを要件とする。
【発明の効果】
【０００９】
この検索方法によれば、従来技術のように、真フラグおよび偽フラグに基づいて走査を行うので、クエリの制約条件を満たしているにもかかわらず、同一のノードを複数回スキャンするという無駄を省き、計算効率を向上させることができる。
【発明を実施するための最良の形態】
【００１０】
以下に添付図面を参照して、この発明に係る検索方法および検索装置の好適な実施の形態を詳細に説明する。
【実施例】
【００１１】
まず、本実施例で使用するＸＭＬ（Extensible  Markup  Language）データについて説明する。図１は、ＸＭＬデータのデータ構造の一例を示す図である。同図に示すように、このＸＭＬデータは、要素識別子「＜」、「＜／」等により要素が区切られた階層構造を有している。そして、図１のＸＭＬデータの木表現は、図２のように表すことが出来る。
【００１２】
図２は、ＸＭＬデータの木表現の一例を示す図である。同図に示すように、ＸＭＬの木構造では、ＸＭＬデータはノードＩＤ１，３，４，５，７，９，１０，１２，１３，１４，１６，１８，１９，２１，２２，２３，２５の要素ノードと、ノードＩＤ２，６，８，１１，１５，１７，２０，２４，２６のテキストノードとを有し、それぞれの要素ノード、テキストノードをそれぞれ接続している。例えば、要素ノードのSyain１は、テキストノードの「シグマ戦隊中原ジャー」２、要素ノードのACT３，１２，２１に接続されている。
【００１３】
そして、ＸＰａｔｈ（XML  Path  Language）クエリ（以下、クエリと表記する）を指定することによって、上記のＸＭＬデータからクエリの照合位置のデータを検出することが可能となる。なお、Ｗ３Ｃ（World  Wide  Web  Consortium）によるクエリのサブセット（Ｗ３ＣによるＸＰａｔｈ２．０のサブセット）は、下記のように定義される。
Path::="/"RPath
RPath::=Step("/"Step)*
Step::=Axis"::"Ntest("["Pred"]")＊
Axis::="child"
Ntest::=tagname|"*"|"text()"|"node()"
Pred::=Expr|Expr"and"Expr| Expr"or"Expr|"not"Expr
Expr::=RPath|func"("RPath")"
ここで、「tagname」は、任意のタグ名を表すものとする。また、「func」は、データ中の各ノードに０または１を割当てる関数とする。すなわち、ＸＭＬデータのノード集合をＶとすると、func:Vは、｛0,1｝となる。
【００１４】
例えば、クエリが、
Q=/Syain/ACT[cast/name]/chara[id]/name
と指定された場合には、図２の要素ノードname７，１６が指定箇所となり、指定箇所に対応したデータを取得することが出来る。図３は、上記クエリによって取得するデータを示す図である。図３に示すように、クエリ「Q=/Syain/ACT[cast/name]/chara[id]/name」により、ＸＭＬデータから「<name>シグマレッド</name>」「<name>シグマブルー</name>」を取得することが出来る。なお、上記クエリの［］は制約条件を表し、例えば、ACT[cast/name]は、配下にcast/nameを有するACTを示すものであり、chara[id]は、配下にidを有するcharaを示す。
【００１５】
次に、クエリを評価する従来技術（例えば、TwigList[Qin  et  al.; DASFAA'07]）について説明する。図４は、従来技術を説明するための図である。ここでは説明の便宜上、ＸＭＬデータ１０ａの木構造を図４の左上に示す木構造とし、クエリを「Q=/a[b]c[d]e」とする（クエリの木構造は、図４の左下参照）。また、ＸＭＬデータ１０ａの各ラベルａ〜ｅに付した番号は、ノードＩＤとする。
【００１６】
従来技術では、まず、ＸＭＬデータ１０ａをスキャンして、クエリを評価するための階層リストを構築する。図４の右側に示す階層リストは、ＸＭＬデータ１０ａの階層リストを示す。この階層リストは、ＸＭＬデータ１０ａの各ラベルａ〜ｅに対応したList_a〜List_eを有する。そして、List_a〜List_eは、ＸＭＬデータ１０ａのラベルに付されたノードＩＤを保持すると共に、ＸＭＬデータ１０ａに対応して接続している。
【００１７】
具体的には、List_aは、ノードＩＤ「１」を保持し、List_bは、ノードＩＤ「２，５」を保持し、List_cは、ノードＩＤ「３，６」を保持し、List_dは、ノードＩＤ「４，７」を保持し、List_eは、ノードＩＤ「８，９」を保持している。
【００１８】
そして、List_aのノードＩＤ「１」は、List_bのノードＩＤ「２，５」、List_c「３，６」に接続されている。また、List_cのノードＩＤ「３」は、List_dのノードＩＤ「４」に接続され、List_cのノードＩＤ「６」は、List_dのノードＩＤ「４」およびList_eのノードＩＤ「８，９」に接続されている。
【００１９】
次に、従来技術では、階層リストをスキャンして、クエリの埋め込みを求める。クエリ「Q=/a[b]c[d]e」の埋め込みを求めると、かかるクエリの条件にヒットするノードＩＤ列は、（１，２，６，７，８）、（１，２，６，７，９）、（１，５，６，７，８）、（１，５，６，７，９）となる。
【００２０】
ここで、（１，２，６，７，８）と（１，５，６，７，８）との照合箇所は、ノードＩＤ「８」となり、（１，２，６，７，９）と（１，４，６，７，９）との照合箇所は、ノードＩＤ「９」となるので、クエリ「Q=/a[b]c[d]e」の埋め込みによって得られる文脈ノードは、ノードＩＤ「８，９」となる。
【００２１】
ところで、従来の技術では、例えば、階層リスト中のList_bのように、同一のラベルに複数のノードＩＤが含まれている場合には、List_bに保持されたノードＩＤの数だけクエリのスキャンを無駄に繰り返し実行する必要がある。階層リストを構成するListに複数のノードＩＤが含まれるということは、ＸＭＬデータで言えば、同じラベルを持つ節点が、同一兄弟中に複数含まれることと同じである（例えば、ＸＭＬデータ１０ａのノードＩＤ２のノードと、ノードＩＤ５のノードとを参照）。
【００２２】
すなわち、階層リストをスキャンして、クエリ「Q=/a[b]c[d]e」の埋め込みを求める場合に、例えば、List_bに含まれるノードＩＤ「２」を参照した時点で、List_aに含まれるノードＩＤ「１」の制約条件（ここでは、Q=/a[b]までの制約条件）を満たすことが確定するので、List_bのノードＩＤ「５」を再度参照することに意味が無く、計算効率が悪いという問題があった。
【００２３】
次に、本実施例にかかる検索装置の概要および特徴について説明する。図５は、本実施例にかかる検索装置の概要および特徴を説明するための図である。ここでは説明の便宜上、ＸＭＬデータおよびクエリは、図５に示したＸＭＬデータ１０ａとクエリ「Q=/a[b]c[d]e」とを用いて説明する。
【００２４】
図５に示すように、本実施例にかかる検索装置は、従来技術の階層リストを作成する代わりに、クエリの述部（制約条件）に対応するＸＭＬデータの述部ノード（制約条件を満たしているか否かを確認する部分）を「真」または「偽」によって表したイベント木を作成することで、クエリの埋め込みを求める場合の計算効率を向上させる。
【００２５】
ここで、イベント木に含まれる「真」は、クエリの制約条件を満たしている旨を示すフラグであり、「偽」は、クエリの制約条件を満たしていない旨を示すフラグである。例えば、図４のList_bに保持されたノードＩＤ「２，５」は、Q=/a[b]までの制約条件を満たしているので、List_aのノードＩＤ「１」に接続されるList_bを、bit_b「真」とする。
【００２６】
また、図４のList_dに保持されたノードＩＤ「４」は、Q=/a[b]c[d]までの制約条件を満たしているので、List_cのノード「３」に接続されるList_dを、bit_d「真」とする。また、図４のList_dに保持されたノードＩＤ「７」は、Q=/a[b]c[d]までの制約条件を満たしているので、List_cのノード「６」に接続されるList_dを、bit_d「真」とする。なお、図５のイベント木に含まれる「．」は、ノードの終端を示すものである。
【００２７】
本実施例にかかる検索装置は、図５に示すイベント木を作成した後に、イベント木をスキャンして、クエリの埋め込みを求める。具体的に、図５に示すイベント木を用いて、クエリ「Q=/a[b]c[d]e」の埋め込みを求める処理を説明する。まず、検索装置は、List_aに移行し、bit_bを参照すると、「真」であるため、List_cに移行する。
【００２８】
そして、検索装置は、ノードＩＤ「３」の配下に接続されたbit_dを参照すると、「真」であるが、ノードＩＤ「３」は「．」に接続されているため（終端ノードであるため）、ノードＩＤ「６」に移行する。
【００２９】
検索装置は、ノードＩＤ「６」に移行し、bit_dを参照すると、「真」であるため、List_eに移行する。List_eに含まれるノードＩＤ「８，９」には接続先が無いため、ノードＩＤ「８，９」がクエリ「Q=/a[b]c[d]e」の指定箇所（文脈ノード）となる。
【００３０】
図５に示す例では、全て「真」の場合について説明したが、Listの配下に接続された
bitが「偽」の場合には、そのList以降のスキャンはスキップされることになる。例えば、図５のbit_bに「偽」が登録されている場合には、List_a以降のスキャンは中断される。
【００３１】
このように、本実施例にかかる検索装置は、各List_a〜eが制約条件を満たしているか否かを配下に接続されたbitの「真」または「偽」を一度参照し、参照結果に基づいて、該当List以降のスキャンを継続する、あるいは中断することで、照合箇所を判定するので、図４で説明した従来技術のように複数回スキャンを無駄に繰り返す必要がなくなり、計算効率を向上させることが出来る。
【００３２】
図６は、従来技術と比較した本実施例にかかる検索装置の効果を説明するための図である。ここでは説明の便宜上、ＸＭＬデータ１０ｂの木構造を図６の左上に示す木構造とし、クエリを「Q=/a[b]c[d]e」とする（クエリの木構造は、図６の左下参照）。また、ＸＭＬデータ１０ｂの各ラベルａ〜ｅに付した番号は、ノードＩＤとする。
【００３３】
図６の右上に示す階層リストは、図４の場合と同様にしてＸＭＬデータ１０ｂをスキャンして構築された階層リストである。図６の右下に示すイベント木は、図５の場合と同様にして、階層リストの代わりに作成されたイベント木である。
【００３４】
図６の階層リストでは、List_bに複数のノードＩＤ「２，３，４，５」（４通り）が含まれており、List_dに複数のノードＩＤ「９，１０，１１，１２」（４通り）が含まれているので、List_bとList_dとの組合せにより、同じ指定箇所「ノード１３」を得るために、１６回スキャンする必要がある。
【００３５】
一方、図６のイベント木では、述部ノード（制約条件を満たしているか否かを確認する部分）をまとめて「真」または「偽」によって表現しているので、ＸＭＬデータ１０ｂに対するクエリ「Q=/a[b]c[d]e」の解は１つだけとなり、図６の階層リストのように複数回スキャンを実行する必要がなくなる。
【００３６】
ＸＭＬデータのデータサイズをｎ、クエリサイズをｑとすると、従来技術の計算量は、Ｏ（ｑ・ｎｑ）となり、本実施例にかかる検索装置の計算量は、Ｏ（ｑ・ｎ）となる。すなわち、クエリサイズｑが大きくなればなるほど、従来技術と比較して本実施例にかかる検索装置の計算量が格段に少なくなる。また、ＸＭＬデータに含まれる同一ラベルの節点が、同一兄弟中に大量に出現する場合には、従来技術では、解候補の組合せが増加するが、本実施例の検索装置の解は一つのままなので、計算効率を向上させるという効果が特に大きくなる。
【００３７】
次に、本実施例にかかる検索装置の構成について説明する。図７は、本実施例にかかる検索装置の構成を示す機能ブロック図である。図７に示すように、この検索装置１００は、入力部１１０と、出力部１２０と、通信制御ＩＦ部１３０と、入出力制御ＩＦ部１４０と、記憶部１５０と、制御部１６０とを有する。なお、この検索装置１００は、ネットワークを介して端末装置（図示略）に接続しているものとする。
【００３８】
このうち、入力部１１０は、各種の情報を入力する入力手段であり、キーボードやマウス、マイクなどによって構成され、例えば、上述したＸＭＬデータに関する各種の情報を受け付けて入力する。なお、後述するモニタ（出力部１２０）も、マウスと協働してポインティングデバイス機能を実現する。
【００３９】
出力部１２０は、各種の情報を出力する出力手段であり、モニタ（若しくはディスプレイ、タッチパネル）やスピーカなどによって構成され、例えば、上述したＸＭＬデータに関する各種の情報を出力する。
【００４０】
通信制御ＩＦ部１３０は、端末装置（図示略）との間における通信を制御する手段である。入出力制御ＩＦ部１４０は、入力部１１０、出力部１２０、通信制御ＩＦ部１３０、記憶部１５０、制御部１６０によるデータの入出力を制御する手段である。
【００４１】
記憶部１５０は、制御部１６０による各種処理に必要なデータおよびプログラムを記憶する記憶手段（格納手段）であり、特に本発明に密接に関連するものとしては、図７に示すように、ＸＭＬデータ１５０ａ、パスＩＤテーブル１５０ｂ、ＢＩＮデータ１５０ｃ、イベント定義表１５０ｅ、イベント列データ１５０ｅ、イベント木データ１５０ｆを格納する。
【００４２】
このうち、ＸＭＬデータ１５０ａは、上述したように要素識別子「＜」、「＜／」等により要素が区切られた階層構造を有する文書データである（図１参照）。パスＩＤテーブル１５０ｂは、ＸＭＬデータ１５０ａに含まれるパスとパスＩＤ（Identification）とを対応付けたデータである。
【００４３】
図８は、パスＩＤテーブルのデータ構造の一例を示す図である。図８に示すように、このパスＩＤテーブル１５０ｂでは、パスとパスＩＤとが対応付けられており、例えば、パス「/Syain」は、パスＩＤ「１」に対応付けられている。
【００４４】
ＢＩＮデータ１５０ｃは、ＸＭＬデータ１５０ａに含まれる各要素をパスＩＤテーブル１４０ｂのパスＩＤに置き換えたデータである。図９は、ＢＩＮデータのデータ構造の一例を示す図である。例えば、ＸＭＬデータ１５０ａ（図１参照）の１段目に位置する「<Syain>シグマ戦隊中原ジャー」の「<Syain>」は、パスＩＤテーブル（図８参照）のパス「/Syain」（パスＩＤ「１」）に対応するため、ＢＩＮデータ１５０ｃの１段目のように「[1シグマ戦隊中原ジャー」と変換される。このように、ＸＭＬデータ１５０ａをＢＩＮデータ１５０ｃに変換することにより、パス照合におけるタグ階層の管理を省くことが出来る。
【００４５】
イベント定義表１５０ｄは、クエリに含まれるイベント種類とパスとを対応付けたデータである。図１０は、イベント定義表１５０ｄのデータ構造の一例を示す図である。図１０に示すように、このイベント定義表１５０ｄは、定義ＩＤと、パスと、パスＩＤと、イベント種類とを対応付けて記憶している。なお、定義ＩＤは、パスと、パスＩＤと、イベント種類との組合せを識別する情報である。
【００４６】
イベント種類となる集合ETYPE(Q)は、パスヒットイベントＺ１、・・・、Ｚｎ、述部ヒットイベントＰ１、・・・Ｐｎ、クエリ開始イベントＳ、文脈ノードイベントＣを有する。ここで、パスヒットイベントは、該当パスにヒットした旨を示すイベントであり、述部ヒットイベントは、述部にヒットした旨の示すイベントである。また、クエリ開始イベントは、クエリの開始パスにヒットした旨を示すイベントであり、文脈ノードイベントは、クエリの終了パスにヒットした旨を示すイベントである。
【００４７】
例えば、クエリが、
Q=/Syain/ACT[cast/name]/chara[id]/name
と指定され、イベント種類の集合が、
ETYPE(Q)={Z1,P1,Z2,P2,Z3}
と指定されている場合には、図１０に示したイベント定義表１５０ｄが生成される。
【００４８】
イベント列データ１５０ｅは、ＢＩＮデータ１５０ｃおよびイベント定義表１５０ｄを基にして生成されるデータであり、イベント定義表１５０ｄにヒットしたＢＩＮデータ１５０ｃの各種情報を記憶する。図１１は、イベント列データ１５０ｅのデータ構造の一例を示す図である。図１１に示すように、このイベント列データ１５０ｅは、イベントＩＤと、イベント種類と、オフセットとを対応付けて記憶している。このうち、イベントＩＤは、イベントを識別する情報であり、オフセットは、イベントが発生した時点でのデータ位置を示す。本実施例では一例として、オフセットを、ノードＩＤで指定する。
【００４９】
イベント木データ１５０ｆは、イベント列データ１５０ｅに基づいて作成されるイベント木である。このイベント木データ１５０ｆは、各ノード構造体が互いに接続することにより構成されている。図１２は、ノード構造体のデータ構造の一例を示す図である。図１２に示すように、ノード構造体は、イベントＩＤと、他のノード構造体へのポインタ（ポインタ配列）と、述部とから構成される。述部の初期値は偽（文脈ノードの場合はＮｕｌｌ（-））となり、クエリに応じて真に変更される。
【００５０】
なお、ポインタ配列に複数のポインタが格納されている場合には、左端のポインタに接続されたノード構造体から順に走査が実行される。
【００５１】
図１３は、イベント木データ１５０ｆのデータ構造の一例を示す図である。図１３に示すように、このイベント木データ１５０ｆは、仮想ルート５０と、ノード構造体６０〜６８とを有する。図１３のイベント木データ１５０ｆを作成する手法は、イベント木作成部１６０ｄ（後述する）の説明を行う場合にあわせて説明する。
【００５２】
制御部１６０は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する制御手段であり、特に本発明に密接に関連するものとしては、図７に示すように、ＢＩＮデータ生成部１６０ａと、イベント定義表作成部１６０ｂと、イベント列作成部１６０ｃと、イベント木生成部１６０ｄと、イベント木走査部１６０ｅとを有する。
【００５３】
このうち、ＢＩＮデータ生成部１６０ａは、ＸＭＬデータ１５０ａとパスＩＤテーブル１５０ｂとを比較して、ＸＭＬデータ１５０ａに含まれる各要素をパスＩＤに置き換えることにより、ＢＩＮデータ１５０ｃを生成する手段である。
【００５４】
例えば、ＢＩＮデータ生成部１６０ａは、図１において、ＸＭＬデータ１５０ａの１段目に位置する「<Syain>シグマ戦隊中原ジャー」の「<Syain>」は、パスＩＤテーブル１５０ｂのパス「/Syain」（パスＩＤ「１」）に対応するため、ＢＩＮデータ１５０ｃの１段目を「[1シグマ戦隊中原ジャー」とする。ＢＩＮデータ生成部１６０ａは、他の段も同様に、パスＩＤテーブル１５０ｂと比較して、各要素をパスＩＤに置き換えていくことで、ＢＩＮデータ１５０ｃを生成する。
【００５５】
イベント定義表作成部１６０ｂは、クエリを取得した場合に、クエリに対応したイベント定義表を作成する処理部である。イベント定義表作成部１６０ｂは、例えば、クエリが、
Q=/Syain/ACT[cast/name]/chara[id]/name
と指定され、イベント種類の集合が、
ETYPE(Q)={Z1,P1,Z2,P2,Z3}
と指定されている場合には、クエリの各パスと、イベント種類の集合とを対応させることにより、図１０に示したイベント定義表１５０ｄを作成する。
【００５６】
上記の条件では、パス「/Syain/ACT」がイベント種類「Ｚ１」に対応し、パス「/Syain/ACT/cast/name」がイベント種類「Ｐ１」に対応し、パス「/Syain/ACT/chara」がイベント種類「Ｚ２」に対応する。また、パス「/Syain/ACT/chara/id」がイベント種類「Ｐ２」に対応し、パス「/Syain/ACT/chara/id/name」がイベント種類「Ｚ３」に対応する。また、パス「/Syain/ACT」は、クエリの開始パスとし、イベント種類に「Ｓ」を含ませる。また、パス「/Syain/ACT/chara/id/name」は、クエリの終了パスであるため、イベント種類に「Ｃ」を含ませる。
【００５７】
イベント列作成部１６０ｃは、ＢＩＮデータ１５０ｃとイベント定義表１５０ｄとを基にして、イベント列データ１５０ｅを作成する処理部である。図１４は、イベント列作成部１６０ｃの処理を説明するための図である。図１４に示すように、イベント列作成部１６０ｃは、ＢＩＮデータ１５０ｃを１文字ずつスキャンして、タグ開始記号「［」を検出するたびに、オフセットの値を１だけ加算する。なお、本実施例では、説明の便宜上、オフセットの値を、イベントが発生した際の、ノードのノードＩＤ（図２参照）をオフセットとする。
【００５８】
また、イベント列作成部１６０ｃは、タグ開始記号「［」の後ろ（直後）に、イベント定義表１５０ｄに含まれるパスＩＤを検出した場合には、イベントＩＤに１を加算して、イベント列に現在のイベントＩＤ、イベント種類、オフセットを登録する。以下において、イベント列作成部１６０ｃの処理を、図１４を用いて説明する。
【００５９】
まず、ＢＩＮデータ１５０ｃの位置「１００１」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤは検出されない。ＢＩＮデータ１５０ｃの位置「１００２」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤ「２」が検出されるので、イベント（１）が発生し、イベント列作成部１６０ｃは、イベントＩＤ「１」、イベント種類「Ｚ１、Ｓ」、オフセット「３」（図２のノードＩＤ「３」のACTに対応）をイベント列データ１５０ｅに登録する（図１１の１段目参照）。なお、イベント（１）とは、イベント定義表１５０ｄの定義ＩＤ（１）に対応したイベントを示す。他のイベント（ｎ）も同様である。
【００６０】
ＢＩＮデータ１５０ｃの位置「１００３」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤ「３」が検出されるので、イベント（３）が発生し、イベント列作成部１６０ｃは、イベントＩＤ「２」、イベント種類「Ｚ２」、オフセット「４」（図２のノードＩＤ「４」のcharaに対応）をイベント列データ１５０ｅに登録する（図１１の２段目参照）。
【００６１】
ＢＩＮデータ１５０ｃの位置「１００４」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤ「４」が検出されるので、イベント（４）が発生し、イベント列作成部１６０ｃは、イベントＩＤ「３」、イベント種類「Ｐ２」、オフセット「５」（図２のノードＩＤ「５」のidに対応）をイベント列データ１５０ｅに登録する（図１１の３段目参照）。
【００６２】
ＢＩＮデータ１５０ｃの位置「１００５」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤ「５」が検出されるので、イベント（５）が発生し、イベント列作成部１６０ｃは、イベントＩＤ「４」、イベント種類「Ｚ３、Ｃ」、オフセット「７」（図２のノードＩＤ「７」のidに対応）をイベント列データ１５０ｅに登録する（図１１の４段目参照）。
【００６３】
ＢＩＮデータ１５０ｃの位置「１００６」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤは検出されない。ＢＩＮデータ１５０ｃの位置「１００７」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤは検出されない。
【００６４】
ＢＩＮデータ１５０ｃの位置「１００８」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤ「７」が検出されるので、イベント（２）が発生し、イベント列作成部１６０ｃは、イベントＩＤ「５」、イベント種類「Ｐ１」、オフセット「１０」（図２のノードＩＤ「１０」のnameに対応）をイベント列データ１５０ｅに登録する（図１１の５段目参照）。
【００６５】
ＢＩＮデータ１５０ｃの位置「１００９」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤは検出されない。ＢＩＮデータ１５０ｃの位置「１０１０」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤは検出されない。
【００６６】
ＢＩＮデータ１５０ｃの位置「１０１１」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤ「２」が検出されるので、イベント（１）が発生し、イベント列作成部１６０ｃは、イベントＩＤ「６」、イベント種類「Ｚ１、Ｓ」、オフセット「１２」（図２のノードＩＤ「１２」のACTに対応）をイベント列データ１５０ｅに登録する（図１１の６段目参照）。
【００６７】
ＢＩＮデータ１５０ｃの位置「１０１２」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤ「３」が検出されるので、イベント（３）が発生し、イベント列作成部１６０ｃは、イベントＩＤ「７」、イベント種類「Ｚ２」、オフセット「１３」（図２のノードＩＤ「１３」のcharaに対応）をイベント列データ１５０ｅに登録する（図１１の７段目参照）。
【００６８】
ＢＩＮデータ１５０ｃの位置「１０１３」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤ「４」が検出されるので、イベント（４）が発生し、イベント列作成部１６０ｃは、イベントＩＤ「８」、イベント種類「Ｐ２」、オフセット「１４」（図２のノードＩＤ「１４」のidに対応）をイベント列データ１５０ｅに登録する（図１１の８段目参照）。
【００６９】
ＢＩＮデータ１５０ｃの位置「１０１４」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤ「５」が検出されるので、イベント（５）が発生し、イベント列作成部１６０ｃは、イベントＩＤ「９」、イベント種類「Ｚ３、Ｃ」、オフセット「１６」（図２のノードＩＤ「１６」のnameに対応）をイベント列データ１５０ｅに登録する（図１１の９段目参照）。
【００７０】
ＢＩＮデータ１５０ｃの位置「１０１５」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤは検出されない。ＢＩＮデータ１５０ｃの位置「１０１６」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤは検出されない。
【００７１】
ＢＩＮデータ１５０ｃの位置「１０１７」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤ「７」が検出されるので、イベント（２）が発生し、イベント列作成部１６０ｃは、イベントＩＤ「１０」、イベント種類「Ｐ１」、オフセット「１９」（図２のノードＩＤ「１９」のnameに対応）をイベント列データ１５０ｅに登録する（図１１の１０段目参照）。
【００７２】
ＢＩＮデータ１５０ｃの位置「１０１８」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤは検出されない。ＢＩＮデータ１５０ｃの位置「１０１９」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤは検出されない。
【００７３】
ＢＩＮデータ１５０ｃの位置「１０２０」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤ「２」が検出されるので、イベント（１）が発生し、イベント列作成部１６０ｃは、イベントＩＤ「１１」、イベント種類「Ｚ１、Ｓ」、オフセット「２１」（図２のノードＩＤ「２１」のACTに対応）をイベント列データ１５０ｅに登録する（図１１の１１段目参照）。
【００７４】
ＢＩＮデータ１５０ｃの位置「１０２１」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤ「３」が検出されるので、イベント（３）が発生し、イベント列作成部１６０ｃは、イベントＩＤ「１２」、イベント種類「Ｚ２」、オフセット「２２」（図２のノードＩＤ「２２」のcharaに対応）をイベント列データ１５０ｅに登録する（図１１の１２段目参照）。
【００７５】
ＢＩＮデータ１５０ｃの位置「１０２２」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤ「４」が検出されるので、イベント（４）が発生し、イベント列作成部１６０ｃは、イベントＩＤ「１３」、イベント種類「Ｐ２」、オフセット「２３」（図２のノードＩＤ「２３」のidに対応）をイベント列データ１５０ｅに登録する（図１１の１３段目参照）。
【００７６】
ＢＩＮデータ１５０ｃの位置「１０２３」において、タグ開始記号「［」の直後に、イベント定義表１５０ｄに含まれるパスＩＤ「５」が検出されるので、イベント（５）が発生し、イベント列作成部１６０ｃは、イベントＩＤ「１４」、イベント種類「Ｚ３、Ｃ」、オフセット「２５」（図２のノードＩＤ「２５」のnameに対応）をイベント列データ１５０ｅに登録する（図１１の１４段目参照）。
【００７７】
なお、ＢＩＮデータ１５０ｃの位置「１０２４」〜「１０２６」において、タグ開始記号「［」の後に、イベント定義表１５０ｄに含まれるパスＩＤは検出されない。このように、イベント列作成部１６０ｃは、ＢＩＮデータ１５０ｃの位置「１００１」〜「１０２６」と、イベント定義表１５０ｄとを比較することで、イベント列データ１５０ｅを作成する。
【００７８】
イベント木作成部１６０ｄは、イベント列データ１５０ｅ（図１１参照）を基にして、イベント木データ１５０ｆ（図１３参照）を作成する処理部である。イベント木作成部１６０ｄは、イベント列データ１５０ｅをイベントＩＤに沿って順次参照し、イベント種類がパスヒットイベント（Ｚｎ；ｎは自然数）の場合には、ノード構造体を作成する。また、イベント種類が述部ヒットイベントの場合には、処理対象に設定されたノード構造体の述部を「真」に設定する。以下において、イベント木作成部１６０ｄの処理を、具体例を用いて説明する。
【００７９】
図１５〜図１７は、イベント木作成部１６０ｄの処理手順を説明するための図である。まず、イベント木作成部１６０ｄは、初期木（仮想ルート）５０を設定し（ステップＳ１０）、イベント列データ１５０ｅのイベントＩＤ「１」を参照する。イベントＩＤ「１」のイベント種類はパスヒットイベント「Ｚ１」であるため、イベント木作成部１６０ｄは、ノード構造体６０を作成する。この時点におけるノード構造体６０のイベントＩＤは、「１」、ポインタ（他のノード構造体へのポインタ）はブランク、述部は初期値の「偽」となる。なお、イベント木作成部１６０ｄは、初期木５０の配下にノード構造体６０を接続する（ステップＳ１１）。
【００８０】
イベント木作成部１６０ｄは、イベント列データ１５０ｅのイベントＩＤ「２」を参照する。イベントＩＤ「２」のイベント種類はパスヒットイベント「Ｚ２」であるためイベント木作成部１６０ｄは、ノード構造体６１を作成し、ノード構造体６０のポインタをノード構造体６１に設定する（ステップＳ１２）。また、この時点におけるノード構造体６１のイベントＩＤは「２」、ポインタはブランク、述部は初期値の「偽」となる。
【００８１】
イベント木作成部１６０ｄは、イベント列データ１５０ｅのイベントＩＤ「３」を参照する。イベントＩＤ「３」のイベント種類は述部ヒットイベント「Ｐ２」であるためイベント木作成部１６０ｄは、ノード構造体６１の述部を「真」に設定する（ステップＳ１３）。
【００８２】
イベント木作成部１６０ｄは、イベント列データ１５０ｅのイベントＩＤ「４」を参照する。イベントＩＤ「４」のイベント種類はパスヒットイベント「Ｚ３」であるためイベント木作成部１６０ｄは、ノード構造体６２を作成し、ノード構造体６１のポインタをノード構造体６２に設定する（ステップＳ１４）。また、この時点におけるノード構造体６２のイベントＩＤは「４」、ポインタはブランク、述部はNullに設定する（イベント種類にＣ＜文脈ノード＞が含まれているため）と共に、親ノードに対応するノード構造体６０に移行する。
【００８３】
イベント木作成部１６０ｄは、イベント列データ１５０ｅのイベントＩＤ「５」を参照する。イベントＩＤ「５」のイベント種類は述部ヒットイベント「Ｐ１」であるため、イベント木作成部１６０ｄは、ノード構造体６０の述部を偽から真に変更する（ステップＳ１５）。また、親ノードに対応する初期木に移動する。
【００８４】
イベント木作成部１６０ｄは、イベント列データ１５０ｅのイベントＩＤ「６」を参照する。イベントＩＤ「６」のイベント種類はパスヒットイベント「Ｚ１」であるためイベント木作成部１６０ｄは、ノード構造体６３を作成する。この時点におけるノード構造体６３のイベントＩＤは「６」、ポインタはブランク、述部は初期値の「偽」となる。なお、イベント木作成部１６０ｄは、初期木５０の配下にノード構造体６３を接続する（ステップＳ１６）。
【００８５】
なお、イベント木作成部１６０ｄは、イベント列データ１５０ｅのイベントＩＤ「７〜１０」の処理をイベントＩＤ「２〜５」と同様の処理を実行することにより、ステップＳ１７に示すイベント木が作成される。図１７の上段に示すように、初期木５０の配下にノード構造体６０，６３が接続され、ノード構造体６０の配下にノード構造体６１が接続され、ノード構造体６１の配下にノード構造体６２が接続される。ノード構造体６３の配下にノード構造体６４が接続され、ノード構造体６４の配下にノード構造体６５が接続される。また、ノード構造体６０，６１，６３，６４の述部は「真」となり、ノード構造体６２，６５の述部は「Null」となる。
【００８６】
また、イベント木作成部１６０ｄは、イベント列データ１５０ｅのイベントＩＤ「１１〜１４」の処理をイベントＩＤ「１〜４」と同様の処理を実行することにより、ステップＳ１８に示すイベント木が作成される。図１７の下段に示すように、初期木５０の配下にノード構造体６０，６３，６６が接続され、ノード構造体６０の配下にノード構造体６１が接続され、ノード構造体６１の配下にノード構造体６２が接続される。
【００８７】
ノード構造体６３の配下にノード構造体６４が接続され、ノード構造体６４の配下にノード構造体６５が接続される。ノード構造体６６の配下にノード構造体６７が接続され、ノード構造体６７の配下にノード構造体６８が接続される。また、ノード構造体６０，６１，６３，６４，６７の述部は「真」となり、ノード構造体６６の述部は「偽」となり、ノード構造体６２、６５、６８の述部は「Null」となる。イベント木作成部１６０ｄは、作成したイベント木をイベント木データ１５０ｆとして記憶部１５０に格納する。
【００８８】
このように、イベント木作成部１６０ｄは、イベント列データ１５０ｅ（例えば、図１１参照）を順次参照し、イベント種類に応じてノード構造体を作成すると共に、各ノード構造体を接続、ノード構造体の述部の設定（真または偽の設定）を行うことで、イベント木データ１５０ｆ（例えば、図１３参照）を作成する。
【００８９】
図７の説明に戻ると、イベント木走査部１６０ｅは、イベント木データ１５０ｆに基づいて、クエリによるＸＭＬデータ１５０ａの指定位置を判定し、判定した指定位置に対応するデータを出力する処理部である。イベント木走査部１６０ｅは、イベント木データ１５０ｆを構成するノード構造体の述部を参照し、述部が真に設定されているか否かによって配下のイベント構造体に移行し、文脈ノード（クエリの指定箇所）を特定する。
【００９０】
具体的に、イベント木走査部１６０ｅは、ノード構造体の述部を参照し、述部が「真」の場合に、配下のノード構造体に移行する。一方、イベント木走査部１６０ｅは、述部が「偽」の場合には、それ以降の検索を中止する。また、イベント木走査部１６０ｅは、ノード構造体の述部が「Null」の場合には、かかるノード構造体のノードＩＤに対応するノードＩＤを、クエリの指定箇所（文脈ノード）として判定する。
【００９１】
イベント木走査部１６０ｅは、文脈ノードを判定するたびに、文脈ノードに対応するノード構造体のノードＩＤを、集合Ｒに登録していく。例えば、図１３において、文脈ノードに対応するノード構造体をノード構造体６２，６５とすると、スキャン後の集合Ｒは、集合Ｒ＝｛４，９｝となる。
【００９２】
図１８は、イベント木走査部１６０ｅの処理手順を説明するための図である。図１８に示すように、イベント木走査部１６０ｅは、初期の走査位置を仮想ルート（ルートノード）５０に設定する（ステップＳ２０）。
【００９３】
イベント木走査部１６０ｅは、走査位置をノード構造体６０に移行させる。ノード構造体６０は、文脈ノードではなく、述部が「真」であるため、配下に接続されたノード構造体６１に走査位置を移行する（ステップＳ２１）。
【００９４】
ノード構造体６１は、文脈ノードではなく、述部が「真」であるため、イベント木走査部１６０ｅは、配下に接続されたノード構造体６２に走査位置を移行させる（ステップＳ２２）。ノード構造体６２は、文脈ノードであり、述部が「Null」であるため、集合ＲにノードＩＤ「４」を追加し、仮想ルート５０に戻る（ステップＳ２３）。
【００９５】
イベント木走査部１６０ｅは、走査位置をノード構造体６３に移行させる。ノード構造体６３は、文脈ノードではなく、述部が「真」であるため、配下に接続されたノード構造体６４に走査位置を移行する（ステップＳ２４）。
【００９６】
ノード構造体６４は、文脈ノードではなく、述部が「真」であるため、イベント木走査部１６０ｅは、配下に接続されたノード構造体６５に走査位置を移動させる（ステップＳ２５）。ノード構造体６５は、文脈ノードであり、述部が「Null」であるため、集合ＲにノードＩＤ「９」を追加し、仮想ルート５０に戻る（ステップＳ２６）。
【００９７】
イベント木走査部１６０ｅは、走査位置をノード構造体６６に移行させる。ノード構造体６６は、文脈ノードではなく、述部が「偽」であるため、イベント木走査部１６０ｅは、仮想ルート５０に接続されたノード構造体のうち、未走査のノード構造体を検索する。しかし、未走査のノード構造体は存在しないので、処理を終了する（ステップＳ２７）。
【００９８】
イベント木走査部１６０ｅは、イベント木データ１５０ｆに対する走査を終了した後、集合Ｒに格納されたノードＩＤに基づいて、クエリの指定箇所に対応するデータを抽出し、抽出したデータを出力する。
【００９９】
例えば、イベント木走査部１６０ｅは、集合Ｒに格納されたノードＩＤが「４，９」の場合には、イベントＩＤ４，９に対応するノードＩＤは、ノードＩＤ７，１６となる（図１１参照）ので、ノードＩＤ７のnameとノードＩＤ１６のnameがクエリの指定箇所となる。従って、イベント木走査部１６０ｅは、ノードＩＤ７のnameに対応するデータ「<name>シグマレッド<name>」とノードＩＤ１６のnameに対応するデータ「<name>シグマブルー<name>」を出力する（例えば、図３参照）。
【０１００】
次に、本実施例にかかる検索装置１００の処理手順について説明する。図１９は、本実施例にかかる検索装置１００の処理手順を示すフローチャートである。図１９に示すように、検索装置１００は、クエリを取得し（ステップＳ１０１）、イベント定義表作成部１６０ｂがイベント定義表１５０ｄを作成する（ステップＳ１０２）。
【０１０１】
続いて、イベント列作成部１６０ｃが、イベント列データ作成処理を実行し（ステップＳ１０３）、イベント木作成部１６０ｄが、イベント木作成処理を実行する（ステップＳ１０４）。
【０１０２】
そして、イベント木走査部１６０ｅが、イベント木走査処理を実行し（ステップＳ１０５）、検出結果を出力する（ステップＳ１０６）。
【０１０３】
次に、図１９のステップＳ１０３に示したイベント列データ作成処理の処理手順について説明する。このイベント列作成処理は、イベント列作成部１６０ｃが、ＢＩＮデータ１５０ｃ（図９参照）をスキャンして、イベント列データ１５０ｅ（図１１参照）を作成する処理である。図２０は、イベント列データ作成処理の処理手順を示すフローチャートである。
【０１０４】
図２０に示すように、イベント列作成部１６０ｃが、イベント列データ１５０ｅを空テーブルとして初期化し、オフセットを初期化する（ステップＳ２０１）。そして、イベント列作成部１６０ｃは、ＢＩＮデータ１５０ｃを文字ずつスキャンし、タグ開始記号「［」を検出するたびに、オフセットに１を加算する。
【０１０５】
また、イベント列作成部１６０ｃは、タグ開始記号「［」の直後にイベント定義表１５０ｄに含まれるパスＩＤを検出した場合に、イベント列データ１５０ｅのイベントＩＤに１を加算し、イベント列データ１５０ｅに（イベントＩＤ、イベント種類、オフセット）を登録し（ステップＳ２０２）、イベント列データ１５０ｅを出力する（ステップＳ２０３）。
【０１０６】
なお、図２０のステップＳ２０２において、イベント列データ１５０ｅに登録されるイベント種類は、タグ開始記号「［」の直後に検出されたパスＩＤと、イベント定義表１５０ｄとを比較することで特定される。また、説明の便宜上、図１１に示すイベント列データ１５０ｅのオフセットは、タグ開始記号「［」の直後に検出されたパスＩＤに対応するノードのノードＩＤとする。
【０１０７】
次に、図１９のステップＳ１０４に示したイベント木作成処理の処理手順について説明する。このイベント木作成処理は、イベント木作成部１６０ｄが、イベント列データ１５０ｅ（図１１参照）をスキャンして、イベント木データ１５０ｆ（図１３参照）を作成する処理である。図２１は、イベント木作成処理の処理手順を示すフローチャートである。
【０１０８】
図２１に示すように、イベント木作成部１６０ｄは、ｅをイベント列データ１５０ｅの最初のイベントに設定し（ステップＳ３０１）、イベント木Ｔを初期木に設定し、ｖ＝ｒｏｏｔ（Ｔ）とする（ステップＳ３０２）。
【０１０９】
イベント木作成部１６０ｄは、ｅのイベント種類がパスヒットイベントであるか否かを判定し（ステップＳ３０３）、パスヒットイベントでない場合（述部ヒットイベントの場合）には（ステップＳ３０４，Ｎｏ）、ｖのブール値（ノード構造体の述部に対応；図１２参照）が偽の場合に、ｖのブール値を真に変更し（ステップＳ３０５）、ステップＳ３０８に移行する。
【０１１０】
一方、イベント木作成部１６０ｄは、パスヒットイベントの場合には（ステップＳ３０４，Ｙｅｓ）、ノード構造体ｗを作成し、ｗのイベントＩＤにｅのイベントＩＤを書込み（ステップＳ３０６）、ｖのポインタ配列の最終要素として、ノード構造体ｗへのリンクを書き込む（ステップＳ３０７）。
【０１１１】
イベント木作成部１６０ｄは、ｅの次のイベントがイベント列データ１５０ｅに存在するか否かを判定し（ステップＳ３０８）、ｅの次のイベントが存在する場合には（ステップＳ３０９，Ｙｅｓ）、ｅ＝nextevent(E)とし（ステップＳ３１０）、ｖ＝parnode(e,T)とし（ステップＳ３１１）、ステップＳ３０３に移行する。
【０１１２】
ここで、ｅ＝nextevent(E)は、現在のイベントの次のイベントを与える関数である。例えば、図１１において、現在のイベントがイベントＩＤ「１」のイベントである場合には、ｅ＝nextevent(E)によって特定されるイベントは、イベントＩＤ「２」のイベントとなる。また、ｖ＝parnode(e,T)は、現在のｅに指定されるノード構造体の親となるノード構造体を特定する関数である。例えば、現在のｅに指定されるノード構造体がノード構造体６２の場合には、ｖ＝parnode(e,T)により、ノード構造体６１が与えられる。
【０１１３】
一方、ｅの次のイベントがイベント列データ１５０ｅに存在しない場合には（ステップＳ３０９，Ｎｏ）、イベント木Ｔ（イベント木データ１５０ｆ）を出力する（ステップＳ３１２）。
【０１１４】
次に、図２１のステップＳ３１１に示した関数parnode(e,T)に対応する処理について説明する。図２２は、関数parnode(e,T)に対応する処理のフローチャートである。図２２に示すように、イベント木作成部１６０ｄは、ｖ＝root(T)とし、ｉ＝１とし（ステップＳ４０１）、ｉ＜Ｈ（ｅ）の条件を満たすか否かを判定する（ステップＳ４０２）。
【０１１５】
ここで、イベントｅのイベント種類がＺｎまたはＰｎのとき、ｅの高さをＨ（ｅ）＝ｎと定義する。例えば、ｅがイベントＩＤ「４」のイベントの場合には、イベント種類が「Ｚ３」であるため、Ｈ（ｅ）＝３となる。
【０１１６】
イベント木作成部１６０ｄは、ｉ＜Ｈ（ｅ）となる場合には（ステップＳ４０３，Ｙｅｓ）、ｖのポインタ列の右端が示すノードを新たなｖに設定し、ｉ＝ｉ＋１とし（ステップＳ４０４）、ステップＳ４０２に移行する。一方、ｉ≧Ｈ（ｅ）となる場合には（ステップＳ４０３，Ｎｏ）、ｖを出力する（ステップＳ４０５）。
【０１１７】
次に、図１９のステップＳ１０５に示したイベント木走査処理の処理手順について説明する。このイベント木走査処理は、イベント木走査部１６０ｅが、イベント木データ１５０ｆをスキャンすることにより、クエリの指定箇所を判定する処理である。図２３は、イベント木走査処理の処理手順を示すフローチャートである。
【０１１８】
図２３に示すように、イベント木走査部１６０ｅは、ｖ＝root(T)とし、Ｒ＝φ（空集合）とし（ステップＳ５０１）、ｖが文脈ノードであるか否かを判定する（ステップＳ５０２）。ｖが文脈ノードの場合には（ステップＳ５０３，Ｙｅｓ）、ｖの述部が真またはNullであるか否かを判定する（ステップＳ５０４）。
【０１１９】
イベント木走査部１６０ｅは、ｖの述部が真またはNullの場合には（ステップＳ５０５，Ｙｅｓ）、Ｒ∪｛ｖ｝とし（ステップＳ５０６）、nextnode(T,v)が存在するか否かを判定する（ステップＳ５０７）。ここで、nextnode(T,v)は、イベント木データ１５０ｆのプリオーダ順において、ｖの次のノードを与える関数である。
【０１２０】
例えば、図１３において、現在のノード構造体（ノード）が、ノード構造体６０の場合には、nextnode(T,v)により、ノード構造体６１が与えられる。木構造のプリオーダ順の定義と、プリオーダ順の巡回方法については、例えば、従来技術（エイホ・ウルマン・ホップクロフト著（大野訳）「情報処理シリーズ１１  データ構造とアルゴリズム」（培風館））に記載されている。
【０１２１】
図２３の説明に戻ると、イベント木走査部１６０ｅは、nextnode(T,v)が存在しない場合には（ステップＳ５０８，Ｎｏ）、Ｒを出力し（ステップＳ５０９）、イベント走査処理を終了する。
【０１２２】
ところで、イベント木走査部１６０ｅは、ステップＳ５０３において、ｖが文脈ノードではない場合に（ステップＳ５０３，Ｎｏ）、ｖ＝root(T)またはｖの述部が真であるか否かを判定する（ステップＳ５１０）。そして、条件を満たす場合（すなわち、ｖ＝root（T）またはｖの述部が真の場合）には（ステップＳ５１１，Ｙｅｓ）、ステップＳ５０７に移行する。
【０１２３】
一方、条件を満たさない場合（すなわち、ｖ≠root（T）かつ述部が偽の場合）には（ステップＳ５１１，Ｎｏ）、skipnode(T,v)が存在するか否かを判定する（ステップＳ５１２）。ここで、skipnode(T,v)は、ｖからnextnode(T,v)の適用を繰り返し得られるノードのうち、ｖの部分木に含まれない最初のノードを定義する関数である。例えば、図１３において、ｖにより指定されるノード構造体がノード構造体６２の場合には、skipnode(T,v)により、ノード構造体６３が与えられる。
【０１２４】
図２３の説明に戻ると、イベント木走査部１６０ｅは、skipnode(T,v)が存在しない場合には（ステップＳ５１３，Ｎｏ）、ステップＳ５０９に移行する。一方、skipnode(T,v)が存在する場合には（ステップＳ５１３，Ｙｅｓ）、ｖ＝skipnode(T,v)とし（ステップＳ５１４）、ステップＳ５０２に移行する。
【０１２５】
ところで、イベント木走査部１６０ｅは、ステップＳ５０８において、nextnode(T,v)が存在する場合には（ステップＳ５０８，Ｙｅｓ）、ｖ＝nextnode(T,v)とし（ステップＳ５１５）、ステップＳ５０２に移行する。
【０１２６】
次に、図２３に示した関数skipnode(T,v)に対応する処理について説明する。図２４は、関数skipnode(T,v)に対応する処理のフローチャートである。図２４に示すように、イベント木走査部１６０ｅは、ｖの親ノードｐが存在するか否かを判定し（ステップＳ６０１）、存在しない場合には（ステップＳ６０２，Ｎｏ）、「該当ノードは存在せず」を出力する（ステップＳ６０３）。
【０１２７】
一方、イベント木走査部１６０ｅは、ｖの親ノードｐが存在する場合には（ステップＳ６０２，Ｙｅｓ）、ｖの親ノードｐのポインタ配列において、ｖへのポインタの右隣にポインタが存在するか否かを判定する（ステップＳ６０４）。
【０１２８】
イベント木走査部１６０ｅは、ｖへのポインタの右隣にポインタが存在しない場合には（ステップＳ６０５，Ｎｏ）、ｖに親ノードｐを代入し（ステップＳ６０６）、ステップＳ６０１に移行する。
【０１２９】
一方、イベント木走査部１６０ｅは、ｖへのポインタの右隣にポインタが存在する場合には（ステップＳ６０５，Ｙｅｓ）、右隣のポインタ先となるノードをｖとし（ステップＳ６０７）、ｖを出力する（ステップＳ６０８）。
【０１３０】
上述してきたように、本実施例にかかる検索装置１００は、イベント木作成部１６０ｄが、イベント木データ１５０ｆを構成するノード構造体の述部（述部ノードに対応）に、クエリの制約条件を満たしている旨を示す「真」または、クエリの制約条件を満たしていない旨を示す「偽」を設定する。そして、イベント木走査部１６０ｅが、イベント木データ１５０ｆを走査する場合に、ノード構造体の述部を参照し、述部が「真」の場合には、所定の順序規則に従って走査を継続して文脈ノードを特定することでデータを検出するので、従来技術のように、クエリの制約条件を満たしているにもかかわらず、同一のノード構造体（ノード）を複数回スキャンするという無駄を省き、計算効率を向上させることができる。
【０１３１】
また、本実施例にかかる検索装置１００は、イベント木走査部１６０ｅが、ノード構造体の述部を参照し、述部が「偽」の場合には、述部「偽」を備えるノード構造体の配下に接続されたノード構造体に対する走査をスキップするので、従来技術と同様にしてクエリに指定された文脈ノードを正確に特定することができる。
【０１３２】
また、本実施例にかかる検索装置１００は、例えば図６に示したように、同じラベルを持つ接点が同一兄弟中に複数含まれる場合でも、述部ノードを「真」または「偽」の１ビットで表現するので、記憶装置に記憶させるべきデータ量を削減することができる。
【０１３３】
ところで、本実施例において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部あるいは一部を公知の方法で自動的に行うこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【０１３４】
また、図７に示した検索装置１００の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行われる各処理機能は、その全部または任意の一部がＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０１３５】
図２５は、本実施例にかかる検索装置１００を構成するコンピュータ２００のハードウェア構成を示す図である。図２５に示すように、このコンピュータ（検索装置）２００は、入力装置２０１、モニタ２０２、ＲＡＭ（Random  Access  Memory）２０３、ＲＯＭ（Read  Only  Memory）２０４、記憶媒体からデータを読み取る媒体読取装置２０５、他の装置（例えば、端末装置）との間でデータの送受信を行う通信装置２０６、ＣＰＵ（Central  Processing  Unit）２０７、ＨＤＤ（Hard  Disk  Drive）２０８をバス２０９で接続して構成される。
【０１３６】
そして、ＨＤＤ２０８には、上記した検索装置１００の機能と同様の機能を発揮する検索プログラム２０８ｂが記憶されている。ＣＰＵ２０７が、検索プログラム２０８ｂを読み出して実行することにより、検索プロセス２０７ａが起動される。ここで、検索プロセス２０７ａは、図７に示したＢＩＮデータ生成部１６０ａ、イベント定義表作成部１６０ｂ、イベント列作成部１６０ｃ、イベント木作成部１６０ｄ、イベント木走査部１６０ｅに対応する。
【０１３７】
また、ＨＤＤ２０８は、記憶部１５０に格納されたデータに対応する各種データ２０８ａを記憶する。ＣＰＵ２０７は、ＨＤＤ２０８に格納された各種データ２０８ａを読み出して、ＲＡＭ２０３に格納し、ＲＡＭ２０３に格納された各種データ２０３ａを利用して、クエリ木データを作成し、クエリの指定箇所に対応するデータを検出する。
【０１３８】
ところで、図２５に示した検索プログラム２０８ｂは、必ずしも最初からＨＤＤ２０８に記憶させておく必要はない。たとえば、コンピュータに挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」、または、コンピュータの内外に備えられるハードディスクドライブ（ＨＤＤ）などの「固定用の物理媒体」、さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータに接続される「他のコンピュータ（またはサーバ）」などに検索プログラム２０８ｂを記憶しておき、コンピュータがこれらから検索プログラム２０８ｂを読み出して実行するようにしてもよい。
【図面の簡単な説明】
【０１３９】
【図１】ＸＭＬデータのデータ構造の一例を示す図である。
【図２】ＸＭＬデータの木表現の一例を示す図である。
【図３】上記クエリによって取得するデータを示す図である。
【図４】従来技術を説明するための図である。
【図５】本実施例にかかる検索装置の概要および特徴を説明するための図である。
【図６】従来技術と比較した本実施例にかかる検索装置の効果を説明するための図である。
【図７】本実施例にかかる検索装置の構成を示す機能ブロック図である。
【図８】パスＩＤテーブルのデータ構造の一例を示す図である。
【図９】ＢＩＮデータのデータ構造の一例を示す図である。
【図１０】イベント定義表のデータ構造の一例を示す図である。
【図１１】イベント列データのデータ構造の一例を示す図である。
【図１２】ノード構造体のデータ構造の一例を示す図である。
【図１３】イベント木データのデータ構造の一例を示す図である。
【図１４】イベント列作成部の処理を説明するための図である。
【図１５】イベント木作成部の処理手順を説明するための図（１）である。
【図１６】イベント木作成部の処理手順を説明するための図（２）である。
【図１７】イベント木作成部の処理手順を説明するための図（３）である。
【図１８】イベント木走査部の処理手順を説明するための図である。
【図１９】本実施例にかかる検索装置の処理手順を示すフローチャートである。
【図２０】イベント列データ作成処理の処理手順を示すフローチャートである。
【図２１】イベント木作成処理の処理手順を示すフローチャートである。
【図２２】関数parnode(e,T)に対応する処理のフローチャートである。
【図２３】イベント木走査処理の処理手順を示すフローチャートである。
【図２４】関数skipnode(T,v)に対応する処理のフローチャートである。
【図２５】本実施例にかかる検索装置を構成するコンピュータのハードウェア構成を示す図である。
【符号の説明】
【０１４０】
１００    検索装置
１１０    入力部
１２０    出力部
１３０    通信制御ＩＦ部
１４０    入出力制御ＩＦ部
１５０    記憶部
１５０ａ  ＸＭＬデータ
１５０ｂ  パスＩＤテーブル
１５０ｃ  ＢＩＮデータ
１５０ｄ  イベント定義表
１５０ｅ  イベント列データ
１５０ｆ  イベント木データ
１６０    制御部
１６０ａ  ＢＩＮデータ生成部
１６０ｂ  イベント定義表作成部
１６０ｃ  イベント列作成部
１６０ｄ  イベント木作成部
１６０ｅ  イベント木走査部
２００    コンピュータ
２０１    入力装置
２０２    モニタ
２０３    ＲＡＭ
２０３ａ，２０８ａ  各種データ
２０４    ＲＯＭ
２０５    媒体読取装置
２０６    通信装置
２０７    ＣＰＵ
２０７ａ  検索プロセス
２０８    ＨＤＤ
２０８ｂ  検索プログラム
【図１】
2010140258.tif 000003
【図２】
2010140258.tif 000004
【図３】
2010140258.tif 000005
【図４】
2010140258.tif 000006
【図５】
2010140258.tif 000007
【図６】
2010140258.tif 000008
【図７】
2010140258.tif 000009
【図８】
2010140258.tif 000010
【図９】
2010140258.tif 000011
【図１０】
2010140258.tif 000012
【図１１】
2010140258.tif 000013
【図１２】
2010140258.tif 000014
【図１３】
2010140258.tif 000015
【図１４】
2010140258.tif 000016
【図１５】
2010140258.tif 000017
【図１６】
2010140258.tif 000018
【図１７】
2010140258.tif 000019
【図１８】
2010140258.tif 000020
【図１９】
2010140258.tif 000021
【図２０】
2010140258.tif 000022
【図２１】
2010140258.tif 000023
【図２２】
2010140258.tif 000024
【図２３】
2010140258.tif 000025
【図２４】
2010140258.tif 000026
【図２５】
2010140258.tif 000027