JP5695586B2 - Ｘｍｌ文書検索装置及びプログラム - Google Patents

Description

本発明は、複数のＸＭＬ（Extensible Markup Language）文書から、ユーザが指定した検索条件に合致する箇所を探索する装置及びプログラムに関する。

データ交換及び蓄積に用いるデータの記述方法として、ＸＭＬが広く普及している。ＸＭＬを用いることにより、多様なデータを高い自由度で、機械的に処理しやすいテキストフォーマットで記述できる。図１に、ＸＭＬ文書の例を示す。この文書の内容は「<」と「>」で囲まれたタグにより複数の部分に区切られている。タグには、「<タグ名>」の形式で書かれている開始タグ１０１と、「</タグ名>」の形式で書かれた終了タグ１０２がある。同じタグ名の開始タグと終了タグで区切られた領域を、要素又はＸＭＬ要素と呼ぶ。

なお、開始タグおよび終了タグに挟まれるタグやテキスト領域がない場合、ＸＭＬでは、開始タグおよび終了タグの代わりに「<タグ名/>」という形式のタグを使用できる。本明細書では、このようなタグは、「<タグ名></タグ名>」と記述した場合と同様に扱う。また、開始タグでは、「<タグ名 属性1=属性の値1 属性2=属性の値2 ...>」の形式で、タグに属性値を与えることができる。本明細書では、このようなタグが与えられると、「<タグ名> <＠属性1>属性の値1<＠属性1> <＠属性2>属性の値2</＠属性2>」と書かれた場合と同様に扱う。また、本明細書では、テキスト領域は、タグ名が「＃」である要素であるとみなす。また、親をもたない要素をルート要素と呼ぶ。各ＸＭＬ文書は、ただ１つのルート要素を持つ。

ＸＭＬでは、複数の要素を入れ子にすることで、複雑なデータ構造を記述することができる。終了タグのタグ名は、ＸＭＬ文章を先頭から末尾へ読み進めたとき、まだ対応する終了タグが出現していない開始タグのうち最も直前に現れた開始タグのタグ名と、同一でなければならない。従って、任意の２つの要素は、一方が他方を完全に包含するか、全く重なりがないかのいずれかに限られる。ある要素Ａが「要素Ｂを包含し」、かつ、「要素Ａに包含され、かつ、要素Ｂを包含する別の要素Ｃが存在しない」とき、要素Ｂは要素Ａの子であるといい、要素Ａは要素Ｂの親であるという。親を順次辿って到達可能な要素は先祖と呼ばれ、子を順次辿って到達可能な要素は子孫と呼ばれる。また、同じ親の子である要素を、兄弟と呼ぶ。

この要素間の関係は、一般に、木構造により表される。図２に、木構造の一例を示す。図２に示す木構造は、各要素に対応するノード２０１を用意し、親要素に対応するノードから子要素に対応するノードへ有向エッジ２０２を張ることで得られる。この木構造は、ＤＯＭ木(document object model tree)と呼ばれる。ＤＯＭ木の根から、各ノードへ至る経路上にある要素のタグ名を「／」を挟んで連結し、さらに先頭に「／」を付与して得られる文字列を、本明細書では構造パスと呼ぶ。例えば図２の場合、もっとも右側の「ｃ」の構造パスは、「／ａ／ｃ」である。構造パスに含まれるタグの数を、その要素の深さと定義する。

特開２００６−２２８１５５号公報

清水敏之、鬼塚真、江田毅晴、吉川正俊、XMLデータの管理とストリーム処理に関する技術、電子情報通信学会論文誌D J90-D(2):159-184, 2007. R. Kaushik, R. Krishnamurthy, J.F. Naughton, R. Ramakrishnan, On the integration of structure indexes and inverted lists, Proc. ACM SIGMOD, pp 779-790, 2004. 江田毅晴、鬼塚真、山室雅司、XML データの要約情報を用いた高速な XPath 処理方法、電子情報通信学会論文誌D、J89-D(2): 139-150, 2006. 萩尾一仁、御手洗秀一、石野明、竹田正幸、漸増的なパストライ構築に基づく高速・軽量XML文書フィルタリング、DBSJ Letters 6(2):1-4, 2007. Navarro, G. and Makinen, V., Compressed full-text indexes, ACM Computing Surveys 39(1): Article 2, 2007. Managing Gigabytes,I.Witten,A.Moffat,and T.Bell,Morgan Kaufmann

ＸＭＬ文書を検索対象とする検索クエリの記述方法として、ＸＰａｔｈと呼ばれる規格が普及している（非特許文献１）。例えばＸＰａｔｈは、「要素ａの子である要素ｂ」を指定する検索クエリを「ａ／ｂ」と書く。ＸＰａｔｈでは、このような検索クエリの記述方法が規格化されている。また、ＸＰａｔｈで記述した検索クエリでは、親、子、先祖、子孫、兄弟等の関係にある複数の要素の組み合わせも指示することができる。

ＸＰａｔｈにより記述された検索クエリによる検索処理においては、その検索処理を効率化する方法として、(1) 検索対象とするＸＭＬデータに現れる構造と、(2) 各構造の出現位置とを記録したインデックスとを事前に構築し、それらを参照して検索クエリに合致する箇所を探す方法が広く用いられる（特許文献１、非特許文献２、３を参照）。この他、ＸＰａｔｈにより記述された検索クエリによる検索処理においては、前述した事前処理は実行せず、検索実行時に検索対象とするＸＭＬ文書に現れる構造をリアルタイムで分析する方法も用いられる（非特許文献４を参照）。ただし、こちらの方法は、検索インデックスを事前に計算する方法に比べ、検索速度の点で不利となる。

ＸＰａｔｈにより記述された検索クエリによる検索を効率よく実行するためには、ＸＭＬ文書に現れる構造情報を分析して各構造パスに該当する箇所がどこにあるかを記録すると共に、親、子、先祖、子孫、兄弟といった要素間の関係を効率よく計算できるデータ構造が必要となる。さらに、大規模なＸＭＬ文書を扱う場合には、このようなデータを極力小さいデータサイズで表現できることと、高速に読み取れることが必要となる。

そこで、本発明は、ＸＭＬ文書の検索処理で使用する検索用データのデータサイズを極力小さくし、検索クエリで指定された条件を満たす箇所の検索を高速に計算可能にする。このために、本発明は、ＸＭＬ文書分析部において、(1) 要素の出現順に、当該要素の深さを表す数値の列を部分列として含む第一の数列Ｓと、(2) ＤＯＭ木の各ノードに対応する構造パスの種類を記録する１つ以上の数列からなる数列群Ｔとで与えられるＸＭＬ文書のＤＯＭ木の形状を記録する検索用データを作成する。そして、数列Ｓと数列群Ｔを走査し、検索クエリとして与えられた構造パスに合致する箇所を計算する。

本発明によれば、ＸＰａｔｈにより記述された検索クエリによる検索処理を高速化することができる。上記した以外の課題、構成及び効果は、以下の実施形態の説明により明らかにされる。

ＸＭＬデータの一例を示す図。 ＤＯＭ木の一例を示す図。 ＸＭＬ要素に割り当てる要素番号を説明する図。 第１の形態例に係るＸＭＬ文書検索装置のブロック構成例を示す図。 第１の形態例に係る前処理実行時の各構成間の連携を説明する図。 第１の形態例に係る前処理動作の流れを説明するフローチャート。 第１の形態例に係る前処理動作の概念を示す図。 第１の形態例に係るＸＭＬ文書分析部で実行される処理動作（分析動作）の流れを説明するフローチャート。 第１の形態例に係る検索実行時の各構成間の連携を説明する図。 第１の形態例に係るＸＭＬ文書検索装置による検索処理の流れを説明するフローチャート。 第１の形態例に係る検索処理の処理例を説明する図。 ｒａｎｋ演算及びｓｅｌｅｃｔ演算を説明する図。 第１の形態例に係る構造パス分析部の動作の流れを説明するフローチャート。 第１の形態例に係る要素探索部の動作の流れを説明するフローチャート。 ビットベクトルを説明する図。 Ｗａｖｅｌｅｔ木を説明する図。 第２の形態例に係るＸＭＬ文書検索装置のブロック構成例を示す図。 第２の形態例に係る前処理実行時の各構成間の連携を説明する図。 第２の形態例に係る前処理の流れを説明するフローチャート。 第３の形態例において親要素を計算する動作の流れを説明するフローチャート。 第３の形態例において１つ前の兄弟要素を計算する動作の流れを説明するフローチャート。 第３の形態例において１つ後の兄弟要素を計算する動作の流れを説明するフローチャートで。

以下、図面に基づいて、本発明の実施の形態を説明する。なお、本発明は、後述する形態例に限定されるものではなく、その技術思想の範囲において、種々の変形が可能である。

［第１の形態例］
本形態例に係るＸＭＬ文書検索装置は、ＸＭＬ文書集合を前処理して作成した検索用データと検索クエリとを照合し、検索クエリが指定する構造パスに合致する要素を探索結果として出力する。探索結果の出力は、ＸＭＬ文書に出現する全ての要素（ＸＭＬ要素）について割り当てられている要素番号により行う。

［要素番号］
図３に、ＸＭＬ文書を構成する各要素（ＸＭＬ要素）に対する要素番号の割り当て例を示す。図３では、要素番号３０１に対応する数字を四角形の枠内に表している。要素番号３０１は、検索処理の前処理において、全てのＸＭＬ要素に割り当てられる、各要素を一意に識別する番号である。要素番号は、ＸＭＬ文書を先頭からスキャンしたとき、それまでに出会った要素数と文書数の合計値とする。ｉ番目のＸＭＬ文書のｊ番目の要素の要素番号は、ｉ−１番目のＸＭＬ文書の要素番号の最大値をＥ（ｉ−１）とするとき、Ｅ（ｉ−１）＋１＋ｊとなる。なお、Ｅ（０）＝０とする。

［装置構成］
図４に、本形態例に係るＸＭＬ文書検索装置４００のブロック構成を示す。ＸＭＬ文書検索装置４００は、ＣＰＵ（Central Processing Unit）４０１、主記憶装置４０２、補助記憶装置４０３、リムーバブルドライブ４０４、ユーザインタフェース４０６及びネットワークインタフェース４０７を備える。各構成部は、内部バス等によって互いに接続される。

また、ＸＭＬ文書検索装置４００は、ＬＡＮ（Local Area Network）等のネットワーク４４０を介して外部記憶装置４３０と接続される。本形態例は、ネットワーク４４０の種別に限定されない。ネットワーク４４０は、有線接続でも、無線接続でも構わない。

ＣＰＵ４０１は、主記憶装置４０２に格納されたプログラムを実行する演算装置である。ＣＰＵ４０１による主記憶装置４０２に格納されるプログラムの実行により、ＸＭＬ文書検索装置４００が有する機能が実現される。以下の説明においてプログラムを主語として説明する処理動作は、ＣＰＵ４０１上での該当プログラムの実行を通じて実現される。

主記憶装置４０２は、ＣＰＵ４０１によって実行されるプログラム及び当該プログラムの実行に必要な情報を格納する。主記憶装置４０２は、例えばＲＡＭ（Random Access Memory）等のメモリを想定する。

主記憶装置４０２には、プログラムとして、ＸＭＬ文書分析部４１０、構造パス分析部４１２及び要素探索部４１３を格納し、データとして、ＸＭＬ文書集合４２０、パストライ４２１、数列化されたＤＯＭ木４２２及びテキストデータ４２４を格納する。

ＸＭＬ文書分析部４１０は、ＸＭＬ文書集合４２０に含まれる各ＸＭＬ文書をパース（parse）し、タグを認識するとともにテキストデータ４２４を抽出する。そして、分析結果に基づき、ＸＭＬ文書分析部４１０は、パストライ４２１及び数列化されたＤＯＭ木４２２を生成する。

構造パス分析部４１２は、検索クエリである構造パスの深さ及びパス種別を、パストライ４２１を用いて計算する。なお、パス種別とは、各構造パスを識別するために割り当てる識別番号である。その詳細については後述する。

要素探索部４１３は、構造パス分析部４１２が計算した深さ及びパス種別に基づき、検索クエリに合致する箇所をＸＭＬ文書集合４２０から全て列挙し、検索結果とする。

ＸＭＬ文書集合４２０は、検索対象となる１つ又は複数のＸＭＬ文書のデータである。パストライ４２１は、ＸＭＬ文書集合４２０に含まれる構造情報の要約である。その詳細については後述する。数列化されたＤＯＭ木４２２は、ＸＭＬ文書集合４２０に含まれる構造情報を検索しやすい形式で抽出したものであり、これの詳細も後述する。テキストデータ４２４は、ＸＭＬ文書集合４２０においてタグに挟まれたテキストの情報を抽出したものである。

なお、ＸＭＬ文書集合４２０は、主記憶装置４０２に格納される必要はなく、例えば補助記憶装置４０３、リムーバブルメディア又は外部記憶装置４３０に格納されていてもよい。この場合、ＣＰＵ４０１が、補助記憶装置４０３、リムーバブルメディア又は外部記憶装置４３０からＸＭＬ文書集合４２０を読み出し、主記憶装置４０２に格納する。

同様に、パストライ４２１、数列化されたＤＯＭ木４２２、テキストデータ４２４も、主記憶装置４０２に格納される必要はなく、例えば補助記憶装置４０３及びリムーバブルメディアに格納されてもよい。この場合、ＣＰＵ４０１は、必要に応じ、これらのデータを、補助記憶装置４０３及びリムーバブルメディア４０４から読み出す。

本形態例においては、ＸＭＬ文書分析部４１０、構造パス分析部４１２、要素探索部４１３をいずれもプログラムにより実現しているが、本発明はこれに限定されない。例えばこれらの機能を専用のハードウェアとして実現してもよい。すなわち、ＸＭＬ文書検索装置４００が、ＸＭＬ文書分析装置、構造パス分析装置、要素探索装置を備える構成でもよい。

補助記憶装置４０３は、情報を永続的に保持することが可能な装置であり、例えばＨＤＤ（Hard Disk Drive）等が考えられる。リムーバブルドライブ４０４は、リムーバブルメディアへのデータの書込処理及び読出処理を実行する装置である。リムーバブルメディアには、ＣＤ−ＲＯＭ、ＤＶＤなどの光学ディスク、フロッピー（登録商標）ディスクなどの磁気ディスクが含まれる。

ユーザインタフェース４０６は、ＸＭＬ文書検索装置４００の利用者が、データの入力と処理結果の出力に使用するインタフェースである。ユーザインタフェース４０６は、ディスプレイ装置、キーボード及びマウスなどが含まれる。ネットワークインタフェース４０７は、ネットワーク４４０を介して外部装置と接続するためのインタフェースである。

次に、ＸＭＬ文書検索装置４００の具体的な処理内容を説明する。ただし、以下の説明では、ＸＭＬ文書集合４２０は、補助記憶装置４０３に格納されているものとする。

［前処理時の構成間連携］
図５に、本形態例に係るＸＭＬ文書検索装置１００がＸＭＬ文書を前処理する際の各構成間の連携動作を示す。

まず、ＸＭＬ文書検索装置４００の利用者が、ユーザインタフェース４０６を用いて、処理の開始を指示する（ステップＳ１０１）。

処理の開始指示を受け付けたＣＰＵ４０１は、補助記憶装置４０３からＸＭＬ文書集合４２０を読み出す（ステップＳ１０２）。読み出されたＸＭＬ文書集合４２０は、主記憶装置４０２に格納される。

次に、ＸＭＬ文書分析部４１０（ＣＰＵ４０１）は、ＸＭＬ文書集合４２０に含まれる各ＸＭＬ文書を分析し、パストライ４２１、数列化されたＤＯＭ木４２２、テキストデータ４２４を生成する（ステップＳ１０３）。この後、ＣＰＵ４０１は、パストライ４２１、数列化されたＤＯＭ木４２２、テキストデータ４２４を補助記憶装置４０３に出力する（ステップＳ１０４）。

なお、ステップＳ１０１では、利用者が、ＸＭＬ文書集合４２０を直接入力してもよい。この場合には、ステップＳ１０２の省略が可能である。ＸＭＬ文書集合４２０は、外部記憶装置４３０から読み出してもよい。

［前処理の概要］
図６に、本形態例に係るＸＭＬ文書検索装置４００が検索前に実行する前処理の流れを説明するフローチャートを示す。

ＣＰＵ４０１は、ＸＭＬ文書集合４２０が入力されると、ＸＭＬ文書分析部４１０による分析処理を実行する（ステップＳ２０１）。ＸＭＬ文書分析部４１０は、ＸＭＬ文書集合４２０に含まれる各ＸＭＬ文書を分析し、パストライ４２１、数列化されたＤＯＭ木４２２、テキストデータ４２４を生成する。ＸＭＬ文書分析部４１０が実行する前処理の詳細については後述する。処理が終了すると、ＣＰＵ４０１は、パストライ４２１、数列化されたＤＯＭ木４２２、テキストデータ４２４を、補助記憶装置４０３に出力する（ステップＳ２０２）。

［数列化されたＤＯＭ木］
図７を参照し、ＸＭＬ文書分析部４１０が生成する、数列化されたＤＯＭ木４２２の例を説明する。なお、図７には、パストライ４２１の例も表している。ＤＯＭ木に出現する各ノードの接続関係（すなわち、ＤＯＭ木の形状）は、数列Ｓに記録される。数列Ｓには、次のルールに従って数値が格納される。
・各文書に対応する情報（部分数列）は、数値０で開始される。
・各文書に対応する情報（部分数列）を構成する数値は、ＸＭＬ文書を先頭から順に読み出す場合に発見される開始タグに対応する要素の深さ位置を表す。なお、テキストについては、前述した通り、タグ名が「＃」である開始タグ・終了タグに囲まれている場合と同様の処理を行なう。

図７に示す例の場合、第１のＸＭＬ文書（上段左側）を先頭から読むと、<ａ>、「テキスト１」、<ｂ>、「テキスト２」、<／ｂ>、<ｃ>、「テキスト３」、<／ｃ>、<／ａ>の順にタグやテキストが出現する。終了タグ以外の要素の深さは、1,2,2,3,2,3である。従って、数列Ｓには、ＸＭＬ文書の先頭を表す０を考慮すると、０,１,２,２,３,２,３が追加される。同様に、第２のＸＭＬ文書（上段右側）については、０,１,２,３,２,２,３が追加される。

このように、数列Ｓは、ＤＯＭ木の形状を記録することができる。ただし、検索用データとして使用するには、タグの種類で特定される情報（パス種別）も必要である。そこで、任意の構造パスに割り当てた番号で識別されるパス種別を、深さ別のＤＯＭ木構造に対応する数列Ｔ[d]に記録する。パス種別を与える数値は、同じ深さを有する構造パスに対して一意に割り当てられた番号である。

パス種別の番号は、パストライ４２１に基づいて記録される。パストライ４２１とは、ＸＭＬ文書集合４２０を構成する全てのＸＭＬ文書について出現する構造パスの全てを含むように構築された木構造のデータである。パストライ４２１は、公知の方法（例えば非特許文献４）により構築することができる。本形態例の場合、パストライ４２１の構築時に新規ノードを追加する必要が生じた場合、その新規ノードに新たなパス種別の番号を割り当てる処理機能を、公知の構築機能に追加する。番号の割り当て方法については後述する。図７の場合、括弧で囲まれた数値７０３が、パス種別の番号に相当する。

［数列ＳとＴの生成］
図８に、本形態例に係るＸＭＬ文書分析部４１０において実行される分析動作の詳細を示す。この分析動作において、数列Ｓと数列Ｔ［d］が作成される。

まず、ＸＭＬ文書分析部４１０は、数列Ｓ，Ｔ[1],…,Ｔ[D]を空の数列に初期化する（ステップＳ３００）。ここでの［D］は、ＸＭＬ文書集合４２０で最も深い位置の要素の深さを表している。また、ＸＭＬ文書分析部４１０は、配列Ｒの要素Ｒ[1],…,Ｒ[D]を全て「１」に初期化する（ステップＳ３００）。また、ＸＭＬ文書分析部４１０は、パストライ４２１を、ルートノード７０１（図７）のみを持つように初期化する。

次に、ＸＭＬ文書分析部４１０は、ＸＭＬ文書集合４２０に含まれる全ての文書の処理が完了したか否かを判定する（ステップＳ３０１）。肯定結果が得られるまで、後述するステップＳ３０２〜Ｓ３０９の処理が繰り返し実行される。

ステップＳ３０１で否定結果が得られた場合、ＸＭＬ文書分析部４１０は、未処理の文書を読み込む（ステップＳ３０２）。以下、この文書をＸとする。ステップＳ３０２において、ＸＭＬ文書分析部４１０は、数列Ｓに文書の先頭を表す「０」を追加する。また、ＸＭＬ文書分析部４１０は、変数ｄを用意し、初期値として「０」をセットする。さらに、ＸＭＬ文書分析部４１０は、変数ｖを用意し、パストライのルートノード７０１を指すように初期化する。

次に、ＸＭＬ文書分析部４１０は、文書Ｘを最後まで読んだか否か判定する（ステップ３０３）。肯定結果が得られるまで、後述するステップＳ３０４〜Ｓ３０９が繰り返し実行される。

ステップＳ３０３で否定結果が得られると、ＸＭＬ文書分析部４１０は、現在の読み位置にあるタグが「終了タグ」か否か判定する（ステップＳ３０４）。肯定結果が得られた場合、ＸＭＬ文書分析部４１０は、変数ｖをパストライ４２１上で親ノードを指すように変更し、変数ｄから１を減じる（ステップＳ３０４−１）。そして、ＸＭＬ文書分析部４１０は、読み位置を終了タグの直後まで進め、ステップＳ３０４に戻る。

ステップＳ３０４で否定結果が得られた場合、ＸＭＬ文書分析部４１０は、文書Ｘにおいて、現在の読み位置が「タグ」でなく「テキスト」であるか否かを判定する（ステップＳ３０５）。肯定結果が得られた場合、ＸＭＬ文書分析部４１０は、そのテキストを読み込み、その内容をテキストデータ４２４に追加する（ステップＳ３０５−１）。さらに、ＸＭＬ文書分析部４１０は、変数ｔに「＃」をセットし、ステップＳ３０７に進む（ステップＳ３０５−１）。

ステップＳ３０５で否定結果が得られた場合、ＸＭＬ文書分析部４１０は、開始タグを読み、その直後まで読み位置を進める。また、ＸＭＬ文書分析部４１０は、この開始タグのタグ名を、変数ｔにセットする（ステップＳ３０６）。

ステップＳ３０５−１の後又はステップＳ３０６の後、ＸＭＬ文書分析部４１０は、パストライ４２１上のノードｖに、タグ名が変数ｔの値に一致する子ノードｖ’が存在するか否か判定する（ステップＳ３０７）。否定結果が得られた場合、ＸＭＬ文書分析部４１０は、新規に子ノード（以下「ｖ’」という）を作成し、ｖ’のパス種別をＲ[d]の値とした後、Ｒ[d]に１を加える（ステップＳ３０７−１）。

ステップＳ３０７で肯定結果が得られた場合、ＸＭＬ文書分析部４１０は、ｖの子ノードｖ’を指すように変数ｖを更新し、変数ｄに１を加える（ステップＳ３０８）。

ステップＳ３０７−１の後又はステップＳ３０８の後、ＸＭＬ文書分析部４１０は、数列Ｓに変数ｄの値を追加し、さらに数列Ｔ[d]に更新された変数ｖのパス種別を追加し、ステップＳ３０３に戻る（ステップＳ３０９）。

［検索動作時の構成間連携］
図９に、本形態例に係るＸＭＬ文書検索装置４００がＸＭＬ文書を検索する際の各構成間の連携動作を示す。

まず、ＸＭＬ文書検索装置４００は、検索に使用するパストライ４２１と数列化されたＤＯＭ木４２２を、補助記憶装置４０３から主記憶装置４０２に予め読み出す（ステップＳ４０１）。これらのデータは、前述した前処理により事前に作成されたデータである。

ＸＭＬ文書検索装置４００の利用者が、ユーザインタフェース４０６を通じ、検索クエリとしての構造パスを投入する（ステップＳ４０２）。検索クエリを受け取ったＣＰＵ４０１は、パストライ４２１を使用し、ＸＭＬ文書集合４２０において、検索クエリに含まれる構造パスに該当する要素の深さｄとパス種別ｔを計算する（ステップＳ４０３）。

次に、要素探索部４１３（ＣＰＵ４０１）は、数列化されたＤＯＭ木４２２を使用し、検索クエリに含まれる構造パスに合致する要素番号をすべて列挙する（ステップＳ４０４）。その後、ＣＰＵ４０１は、得られた要素番号をユーザへ送信する（ステップＳ４０５）。

［検索動作の詳細］
図１０に、本形態例に係るＸＭＬ文書検索装置４００がＸＭＬ文書を検索する際の処理の流れを示す。なお、ＣＰＵ４０１は、検索に用いるパストライ４２１、数列化されたＤＯＭ木４２２、テキストデータ４２４を、補助記憶装置４０３から主記憶装置４０２に事前に読み出しているものとする。

まず、ユーザがユーザインタフェース４０６を通じ、検索クエリとしての構造パスをＸＭＬ文書検索装置４００に投入する。この後、構造パス分析部４１２は、ＸＭＬ文書集合４２０について作成されたパストライ４２１にアクセスし、検索クエリとして指定された構造パスに該当する要素の深さｄとパス種別ｔを計算する（ステップＳ５０１）。

次に、要素探索部４１３は、数列化されたＤＯＭ木４２２にアクセスし、当該構造パスに該当する要素の番号を列挙する（ステップＳ５０２）。

図１１に、前述した検索処理の概要を示す。図１１は、検索クエリとして、「／ａ／ｂ」で表される構造パスが与えられた場合について、この構造パスが出現する要素の番号を計算する概念を表している。

この構造パスは、「／ａ／ｂ」でｂが２番目のタグ名なので、深さが「２」である。さらに、パストライ４２１において、ルートノード７０１から「ａ」、「ｂ」と辿っていくと、「ｂ（２）」と書かれたノードに到達する。「（２）」は、このノードのパス種別が「２」であることを表している。従って、「／ａ／ｂ」の出現位置を全て知るためには、深さ「２」にあるパス種別が「２」の要素の全てについて、要素番号を計算すればよい。そのために、後述するｒａｎｋ演算及びｓｅｌｅｃｔ演算を実行する。
（１）ｒａｎｋ（Ａ，ｃ，ｉ）＝数列Ａのｉ番目までの要素にあるｃの数
（２）ｓｅｌｅｃｔ（Ａ，ｃ，ｊ）＝数列Ａにｊ番目に出現するｃの位置

図１２に、ｒａｎｋ演算およびｓｅｌｅｃｔ演算の例を示す。図１２の例の場合、数列Ｘの１０番目までの要素にある「３」の数を与えるｒａｎｋ（Ｘ，３，１０）は「２」である。また、数列Ｘについて「３」が２番目に出現する位置を与えるｓｅｌｅｃｔ（Ｘ，３，２）は「７」である。

図１１の説明に戻る。前述の「／ａ／ｂ」を検索する処理動作は、深さが「２」でパス種別が「２」の要素を抽出する処理である。

まず、深さが「２」でパス種別が「２」の要素の総数ｎは、ｎ＝ｒａｎｋ（Ｔ[2]，２，｜Ｔ[2]｜）により計算することができる。ただし、｜Ｔ[d]｜は、数列Ｔ[d]の要素数である。

次に、１≦ｋ≦ｎである全ての整数ｋについて、ｋ’＝ｓｅｌｅｃｔ（Ｔ[2]，２，ｋ）を計算する。この計算で得られる値ｋ’の集合は、深さが「２」の要素に限定した場合、パス種別が「２」の要素が何番目に出現するかを表している。図１１の例では、２番目と６番目である。

さらに、ｋ”＝ｓｅｌｅｃｔ（Ｓ，２，ｋ’）を計算すれば、検索対象であるＸＭＬ文書集合４２０のＤＯＭ木の形状を現す数列Ｓにおいて、深さが「２」の要素の中でｋ’番目に出現する要素が全体の何番目に位置するかを計算することができる。図１１の例では、４番目と１３番目である。この「４」と「１３」が、要素探索部４１３の検索結果となる。

［構造パスの分析動作］
図１３に、構造パス分析部４１２が実行する構造パスの分析動作を示す。ここでは、構造パスに含まれる左からｄ番目のタグ名をＰ[d]，タグの総数を｜Ｐ｜とする。

まず、構造パス分析部４１２は、変数ｖをパストライ４２１のルート７０１にセットし、変数ｄを「０」にセットする（ステップＳ６０１）。

次に、構造パス分析部４１２は、ｄ≧｜Ｐ｜か否かを判定する（ステップＳ６０２）。ステップＳ６０２で肯定結果が得られるまで、構造パス分析部４１２は、ステップＳ６０３〜Ｓ６０５の処理を繰り返す。因みに、肯定結果が得られた場合（ｄ≧｜Ｐ｜の場合）、構造パス分析部４１２は、深さを与える情報として「ｄ」を出力し、パス種別７０３を与える情報として変数ｖが指すノードのパス種別を出力し、分析処理を終了する（ステップＳ６０６）。

これに対し、ステップＳ６０２で否定結果が得られた場合、構造パス分析部４１２は、変数ｄに「１」を加える（ステップＳ６０３）。

続いて、構造パス分析部４１２は、変数ｖの指すノードの子にタグ名がＰ[d]のものがあるか否か判定する（ステップＳ６０４）。否定結果が得られた場合（子が存在しない場合）、構造パス分析部４１２は、「当該構造無し」と出力し、検索処理自体を終了する（ステップＳ６０７）。

一方、ステップＳ６０４において肯定結果が得られた場合（子が存在する場合）、構造パス分析部４１２は、変数ｖをタグ名がＰ[i]である子に変更する(ステップＳ６０５)。

［要素探索動作］
図１４に、要素探索部４１３において実行される検索動作の詳細を示す。

要素探索部４１３はまず変数ｎに、深さがｄであり、かつ、パス種別がｔである要素の「総数」をセットする。この総数は、ｒａｎｋ（Ｔ[d]，ｔ，｜Ｔ[d]｜）の計算値として与えられる。さらに、要素探索部４１３は、変数ｋを初期値「０」にセットする。

次に、要素探索部４１３は、ｋ＞ｎか否かを判定する（ステップＳ７０２）。肯定結果が得られるまで、要素探索部４１３は、後述するステップＳ７０３〜Ｓ７０６の処理を繰り返し実行する。

要素探索部４１３は、検索クエリに合致する次の要素が、深さｄの要素の中で何番目に位置するかを、ｓｅｌｅｃｔ（Ｔ[d]，ｔ，ｋ）により計算し、計算結果を変数ｋ’にセットする（ステップＳ７０３）。

次に、要素探索部４１３は、検索クエリに合致する次の要素（ステップＳ７０３と同じ要素）が、ＸＭＬ文書全体に対応する数列Ｓの何番目の要素に位置するかを、ｓｅｌｅｃｔ（Ｓ，ｄ，ｋ’）により計算し、計算結果を変数ｋ”にセットする（ステップＳ７０４）。

要素探索部４１３は、変数ｋ”の値を出力する（ステップＳ７０５）。
この後、要素探索部４１３は、変数ｋに「１」を加え、ステップＳ７０２に戻る（ステップＳ７０６）。

［計算処理の高速化］
前述の処理により構造パスに合致するＸＭＬ要素の計算を高速化するには、ｒａｎｋ演算とｓｅｌｅｃｔ演算を高速に処理する必要がある。

まず、本形態例の場合、ｒａｎｋ演算は、ステップＳ７０１において、Ｔ[d]に値ｔが幾つあるかを数えるためにしか使用しない。処理の高速化のため、本実施例では、数列化されたＤＯＭ木４２２を補助記憶装置４０３から読み出す際に、予め深さ別に各要素が何回出現したかを数え、パス種別（値ｔ）の順に当該構造パスの出現回数を並べた２次元配列Ｎ ７０２（図７）を作成する。Ｎのうち、特定の深さｄに対応する配列Ｎ[d]の内容は、（Ｔ［ｄ］における値１の数、値２の数、…、値ｔの数、…）で与えられる。例えば図７の場合、深さが「２」のパス種別の構造を表す数列Ｔ[2]には、値１が２回、値２が２回、値３が１回、値４が１回出現する。このため、２次元配列Ｎのd=2の部分はＮ[2]＝（２,２,１,１）のように作成される。

続く、ステップＳ７０３のｓｅｌｅｃｔ演算では、ｋの値が１、２、３、…と順に変化し、Ｔ[d]において値がｔとなる箇所を順に計算する。この処理は、単純に数列Ｔ[d]を先頭から順に読み、値ｔが出現する箇所を計算することで実現できる。数列Ｔ[d]に値ｔが頻出すれば、この処理の計算効率は十分に良い。ただし、数列Ｔ[d]に値ｔが頻出しない場合は、数列を走査する処理時間が性能劣化を招く可能性がある。従って、数列Ｔ[d]に値ｔが頻出しないことが予測される場合には、後述する第２の形態例で説明する手法を用いることが好ましい。なお、繰り返し回数ｎは上述の方法で計算してステップＳ７０２で用いても良いが、ｋ＞ｎかを判定する代わりに、数列Ｔ[d]の要素をすべて読み終わった時点で要素探索部４１３を終了する手法を採用してもよい。

ステップＳ７０４のｓｅｌｅｃｔ演算についても、やはり数列を先頭から順番に読み、値ｄがｋ’（＝ｓｅｌｅｃｔ（Ｔ［d］，ｔ，ｋ））回目に出現する位置を求めることで計算できる。

ここで、１＜ｋ≦ｎならば、ｋ’＝ｓｅｌｅｃｔ(Ｔ［d］，ｔ，ｋ)の値が、ｋについて単調に増加する。このため、次の不等式が成立する。

ｓｅｌｅｃｔ（Ｔ［d］，ｔ，ｋ−１）＜ｓｅｌｅｃｔ（Ｔ［d］，ｔ，ｋ）
同様に、ｓｅｌｅｃｔ（Ｓ，ｄ，ｋ’）の値も、ｋ’について単調に増加する。このため、次の不等式が成立する。

ｓｅｌｅｃｔ（Ｓ，ｄ，ｓｅｌｅｃｔ（Ｔ［d］，ｔ，ｋ−１））
＜ ｓｅｌｅｃｔ（Ｓ，ｄ，ｓｅｌｅｃｔ（Ｔ［d］，ｔ，ｋ））

このため、ステップＳ７０４では、前回出力した値であるｓｅｌｅｃｔ（Ｓ，ｄ，ｓｅｌｅｃｔ（Ｔ［d］，ｔ，ｋ−１））を保存しておき、その位置から数列Ｓを走査してｓｅｌｅｃｔ（Ｓ，ｄ，ｓｅｌｅｃｔ（Ｔ［d］，ｔ，ｋ））を計算すれば、計算時間を短縮することができる。

［変形例］
本実施形態で例示した種々のソフトウェアは、電磁的、電子的及び光学式等の種々の記録媒体に格納可能であり、インターネット等の通信網を通じて、コンピュータにダウンロード可能である。

以上の説明では、数列化されたＤＯＭ木４２２の全体を主記憶装置４０２に読み込んで処理する方法を説明した。しかし、実際の運用では、主記憶装置４０２に入りきらない膨大なデータを処理可能とするため、データを補助記憶装置４０３に配置し、処理に必要な箇所をその都度、主記憶装置４０２へ読み込むことが好ましい。

［第１の形態例の効果］
本形態例に係るＸＭＬ文書検索装置４００を用いれば、ＸＰａｔｈにより記述された検索クエリによるＸＭＬ文書の検索処理を高速化することができる。

［第２の形態例］
［Ｗａｖｅｌｅｔ木］
数列をコンパクトに圧縮し、さらにデータを圧縮したままでｒａｎｋ演算及びｓｅｌｅｃｔ演算を効率よく計算できるデータ構造として、Ｗａｖｅｌｅｔ木が知られている（例えば、Navarro, G. and Makinen, V., Compressed full-text indexes, ACM Computing Surveys 39(1): Article 2, 2007.）。

Ｗａｖｅｌｅｔ木は、０と１の任意の並びであるビットベクトルと呼ばれるデータ構造を用いて構築される。ビットベクトルの例を、図１５に示す。ビットベクトルを数列と見たときに効率よくｒａｎｋ演算及びｓｅｌｅｃｔ演算を行うために、一定間隔でｒａｎｋ演算及びｓｅｌｅｃｔ演算の結果をサンプリングし格納するとともに、サンプリングされていない箇所の値は、短いビットベクトルのｒａｎｋ演算及びｓｅｌｅｃｔ演算の結果を事前計算して格納した１５０１のような表を併用し、高速に計算する手法が知られている（例えば非特許文献５を参照)。

図１６に、数列Ｓ「０１２２２３２３０１２３２２３」に対するＷａｖｅｌｅｔ木の構造例を示す。Ｗａｖｅｌｅｔ木は、木のノードにビットベクトルを格納し、全体として数列と同等の情報を記録できるデータ構造である。

ルートノード１６０１には、数列に格納された値を２つのグループに分割するとき、各値がどちらのグループに属すかを記録したビットベクトルＢ１が格納される。図１６の例では、値が「２」であるか、「２」でないかでグループ分けを行っている。ルートノード１６０１の下にあるノード１６０２では、ルートノードでグループ分けされた「２」以外の値を、さらにグループ分けし、「３」であるか、「３」でないかでグループ分けしたビットベクトルＢ２が格納されている。同様に、その下のノード１６０３は、残った「０」と「１」を区別している。

Ｗｅｖｅｌｅｔ木に対するｒａｎｋ演算は、ルートノード１６０１から木を辿ることによって行う。例えばｒａｎｋ（Ｓ，３，７）を計算する場合を説明すると以下のようになる。

まず、「３」はルートノード１６０１では、「１」にグループ分けされている。このため、ｒａｎｋ（Ｂ１，１，７）を計算し、「４」を得る。この結果は、数列Ｓの７番目までに０，１，３が計４個あることを意味する。

次のビットベクトルＢ２では、「３」が「１」にグループ分けされている。このため、ｒａｎｋ（Ｂ２，１，４）を計算し、「２」を得る。この結果は、数列Ｓの７番目までに出現する４個の０，１，３のうち、「３」が計２個であることを表す。このように、ｒａｎｋ（Ｓ，３，７）の結果として、正しく「２」が計算できたことが分かる。

これに対し、ｓｅｌｅｃｔ演算は、リーフからルートノードに木を辿ることによって計算する。例えばｓｅｌｅｃｔ（Ｓ，３，２）を計算する場合を説明すると以下のようになる。

まず、「３」を表すリーフの親ノードであるノード１６０２において、２番目の「３」に該当する位置を計算する。「３」は、ノード１６０２において、「１」にグループ分けされている。このため、ｓｅｌｅｃｔ（Ｂ２，１，２）を計算すると、「４」が得られる。この結果は、２番目の「３」が、０，１，３だけを取り出した部分数列では４番目の値であることを意味する。

さらに、この値が数列Ｓの中で何番目に位置するかを求めるには、ｓｅｌｅｃｔ（Ｂ１，１，４）を計算すれば良い。この場合、「７」が得られる。この結果は、０、１又は３が４番目に現れる位置が全体では７番目の値であることを表す。すなわち、この「７」がｓｅｌｅｃｔ（Ｓ，３，２）の計算結果となる。

このように、Ｗａｖｅｌｅｔ木を用いると、ビットベクトルに対するｒａｎｋ演算やｓｅｌｅｃｔ演算を、最大でも木の高さに等しい回数分の処理の繰り返しにより実現できる。すなわち、最大でも木の高さに等しい計算処理の回数の実行により、数列に対するｒａｎｋ演算及びｓｅｌｅｃｔ演算の解を得ることができる。

Ｗａｖｅｌｅｔ木の高さは、数列の長さよりも遥かに小さな値であり、特に数列の長さが非常に長く、ｒａｎｋ演算又はｓｅｌｅｃｔ演算の第二引数の値の出現頻度が小さいとき、数列を直接走査する場合に比して効率がよい。また、Ｗａｖｅｌｅｔ木は、格納される数列において各値の出現頻度に偏りがあると、圧縮が可能であることが知られている。

［装置構成］
本形態例では、第１の形態例において、ｒａｎｋ演算及びｓｅｌｅｃｔ演算を実行していた箇所に、Ｗａｖｅｌｅｔ木を適用する手段を提供する。

図１７に、本形態例に係るＸＭＬ文書検索装置１７００のブロック構成を示す。図１７には、図４との対応部分に同一符号を付して示している。ＸＭＬ文書検索装置１７００は、Ｗａｖｅｌｅｔ木構築部４１１と、Ｗａｖｅｌｅｔ木群４２３を有する点で、第１の形態例と異なる。

図１８に、本形態例に係るＸＭＬ文書検索装置１７００がＸＭＬ文書を前処理する際の各構成間の連携動作を示す。

まず、ＸＭＬ文書検索装置４００の利用者が、ユーザインタフェース４０６を用いて、処理の開始を指示する（ステップＳ８０１）。

処理の開始指示を受け付けたＣＰＵ４０１は、補助記憶装置４０３からＸＭＬ文書集合４２０を読み出す（ステップＳ８０２）。読み出されたＸＭＬ文書集合４２０は、主記憶装置４０２に格納される。

次に、ＸＭＬ文書分析部４１０（ＣＰＵ４０１）は、ＸＭＬ文書集合４２０に含まれる各ＸＭＬ文書を分析し、パストライ４２１、数列化されたＤＯＭ木４２２、テキストデータ４２４を生成する（ステップＳ８０３）。ここまでは、第１の形態例と同じである。

Ｗａｖｅｌｅｔ木構築部４１１は、ＸＭＬ文書分析部４１０が生成した数列化されたＤＯＭ木４２２に含まれる各数列を、Ｗａｖｅｌｅｔ木群４２３に変換する（ステップＳ８０４）。Ｗａｖｅｌｅｔ木構築部４１１は、公知の方法（例えば非特許文献５を参照）を使用し、数列化されたＤＯＭ木４２２をＷａｖｅｌｅｔ木群４２３に変換する。そして、数列化されたＤＯＭ木４２２に代わり、Ｗａｖｅｌｅｔ木群４２３を補助記憶装置に出力し、同様にパストライ４２１、テキストデータ４２４も出力する（ステップＳ８０５）。数列化されたＤＯＭ木４２２は、Ｗａｖｅｌｅｔ木群４２３を構築した後に消去してもよい。

［前処理の概要］
図１９に、本形態例に係るＸＭＬ文書検索装置４００が検索前に実行する前処理の流れを説明するフローチャートを示す。

ＣＰＵ４０１は、ＸＭＬ文書集合４２０が入力されると、ＸＭＬ文書分析部４１０による分析処理を実行する（ステップＳ９０１）。ＸＭＬ文書分析部４１０は、ＸＭＬ文書集合４２０に含まれる各ＸＭＬ文書を分析し、パストライ４２１、数列化されたＤＯＭ木４２２、テキストデータ４２４を生成する。

この処理が終了すると、ＣＰＵ４０１は、前述したようにＷａｖｅｌｅｔ木群４２３を構築する（ステップＳ９０２）。

この後、ＣＰＵ４０１は、パストライ４２１、Ｗａｖｅｌｅｔ木群１２３、テキストデータ４２４を補助記憶装置４０３に出力する（ステップＳ９０３）。

［検索処理］
本形態例に係るＸＭＬ文書検索装置１７００は、検索の際、まず、パストライ４２１およびＷａｖｅｌｅｔ木群４２３を補助記憶装置４０３から読み出す。前述の通り、数列化されたＤＯＭ木４２２は不要である。

検索動作は、第１の形態例と同様、図１４に従って実行される。第１の形態例との違いは、検索クエリである構造パスが与えられた後に実行されるステップＳ７０１（図１４）のｒａｎｋ演算と、ステップＳ７０３（図１４）及びＳ７０４（図１４）のｓｅｌｅｃｔ演算にＷａｖｅｌｅｔ木を用いる点と、２次元配列Ｎ７０２（図７）が不要な点である。ただし、ｒａｎｋ演算よりも配列参照の処理の方が速いため、本形態例の場合にも、２次元配列Ｎ７０２を使用してもよい。

［第２の形態例の効果］
本形態例に係るＸＭＬ文書検索装置１７００を用いれば、数列Ｔ[d]に値ｔが頻出しない場合にも、ＸＰａｔｈにより記述された検索クエリによるＸＭＬ文書の検索処理を高速に実行することができる。

［第３の形態例］
ＸＰａｔｈによる検索では、親要素、子要素、兄弟要素等に関する制約条件が検索クエリに盛り込まれる場合がある。そこで、本形態例では、親要素、子要素、兄弟要素等を探索する機能と、任意の２つの要素ｉ、ｊが、指定された関係にあるか否かを検査するための機能について説明する。以下の説明では、要素ｉ、ｊの深さをｄｉ、ｄｊとし、パス種別をそれぞれｔｉ、ｔｊとする。

（１）要素ｉの親要素の計算
深さｄｉ≦１の場合、要素ｉの親要素は存在しない。それ以外の場合、親要素は深さがｄｉ−１で与えられる、ｉ未満でｉに最も近い要素番号の要素である。従って、親要素の要素番号は、ｓｅｌｅｃｔ（Ｓ，ｄｉ−１，ｒａｎｋ（Ｓ，ｄｉ−１，ｉ））を計算することにより取得することができる。

（２）要素ｉの最初の子要素の計算
子要素が存在すれば、要素番号はｉ＋１で与えられる。ただし、子要素が存在しない場合があり、その場合、要素番号ｉ＋１の要素の深さはｄｉ＋１以外である。第１の形態例で述べたように数列化されたＤＯＭ木４２２を使用している場合はＳ［ｉ＋１］＝ｄｉ＋１か否かを判定すればよいが、第２の形態例で述べたようにＷａｖｅｌｅｔ木群４２３しか使用できない場合は、ｒａｎｋ（Ｓ，ｄｉ＋１，ｉ＋１）＝ｒａｎｋ（Ｓ，ｄｉ＋１，ｉ）＋１か否かを判定すればよい。後者の場合ＣＰＵ４０１は、図２０に示す処理手順により、子要素の存在を判定し（ステップＳ１００１）、存在する場合にはその要素番号ｉ＋１を出力し（ステップＳ１００２）、存在しない場合には「子要素無し」と出力する（ステップＳ１００３）。

（３）要素ｉの兄弟要素の計算
要素ｉよりも前に兄弟要素が存在する場合、１つ前の兄弟要素は、要素ｉと同じ深さｄｉであり、ｉ未満でｉに最も近い要素番号の要素となる。従って、その要素番号ｊは、ｊ＝ｓｅｌｅｃｔ（Ｓ，ｄｉ，ｒａｎｋ（Ｓ，ｄｉ，ｉ−１））として与えることができる。

これに対し、要素ｉよりも後に兄弟要素が存在する場合、１つ後の兄弟要素は、要素ｉと同じ深さｄｉであり、ｉより大きくｉに最も近い要素番号の要素となる。従って、その要素番号ｊは、ｊ＝ｓｅｌｅｃｔ（Ｓ，ｄｉ，ｒａｎｋ（Ｓ，ｄｉ，ｉ）＋１）として与えることができる。

一方、そのような兄弟要素が存在しない場合、いずれの場合にも、要素ｉと要素ｊの間には、ｉ及びｊのいずれか一方だけの親要素が存在する。よって、ｒａｎｋ（Ｓ，ｄｉ−１，ｉ）＝ｒａｎｋ（Ｓ，ｄｉ−１，ｊ）ならばｊは兄弟要素であり、それ以外の場合は当該兄弟要素が存在しないことになる。

この判定処理をフローチャートで表すと図２１及び図２２となる。図２１は、１つ前の兄弟要素を探すためのフローチャートであり、図２２は、１つ後の兄弟要素を探すためのフローチャートである。

まず、図２１に示すフローチャートについて説明する。前述したように、１つ前の兄弟要素ｊは、要素ｉと同じ深さｄｉであり、ｉ未満でｉに最も近い要素番号の要素となる。従って、ステップＳ１１０１では、ｊ＝ｓｅｌｅｃｔ（Ｓ，ｄｉ，ｒａｎｋ（Ｓ，ｄｉ，ｉ−１））を計算する。次に、要素ｉの深さｄｉよりも１つ浅い深さについてｉ番目までの数（＝ｒａｎｋ（Ｓ，ｄｉ−１，ｉ）と、ｊ番目までの数（＝ｒａｎｋ（Ｓ，ｄｉ−１，ｉ）を比較する（ステップＳ１１０２）。２つの値が同じであれば、同じ親要素の子なのでステップＳ１１０１で計算されたｊを出力する（ステップＳ１１０３）。２つの値が異なれば、兄弟要素無しと出力する（ステップＳ１１０４）。

次に、図２２に示すフローチャートについて説明する。前述したように、１つ後の兄弟要素ｊは、要素ｉと同じ深さｄｉであり、ｉより大きくｉに最も近い要素番号の要素となる。従って、ステップＳ１２０１では、ｊ＝ｓｅｌｅｃｔ（Ｓ，ｄｉ，ｒａｎｋ（Ｓ，ｄｉ，ｉ）＋１）を計算する。次に、要素ｉより１つ浅い深さについてｉ番目までの数（＝ｒａｎｋ（Ｓ，ｄｉ−１，ｉ）と、ｊ番目までの数（＝ｒａｎｋ（Ｓ，ｄｉ−１，ｊ）を比較する（ステップＳ１２０２）。２つの値が同じであれば、同じ親要素の子なのでステップＳ１２０１で計算されたｊを出力する（ステップＳ１２０３）。２つの値が異なれば、兄弟要素無しと出力する（ステップＳ１２０４）。

（４）要素ｉが要素ｊの親か否かの判定
上記（１）の方法で要素ｊの親要素を計算し、計算された親要素の値が要素ｉに一致するか否かで判定する。

（５）要素ｉがｊの先祖であるか否かの判定
以下の条件を同時に満たせば先祖であり、そうでなければ先祖でないと判定する。
（５−１） ｉ＜ｊ
この条件を満たせば、要素ｉの開始タグは、要素ｊの開始タグよりも先に出現する。
（５−２） ｒａｎｋ（Ｓ，ｉ，ｄｉ）＝ｒａｎｋ（Ｓ，ｊ，ｄｉ）
この条件を満たせば、要素ｉと要素ｊの間には、深さがｄｉ以下である要素ｉ以外の要素はない。

（６）要素ｉ、ｊが兄弟要素であるか否かの判定
要素ｉと要素ｊの親要素を計算し、一致するか否かを判定する。

ｒａｎｋ（Ｓ，ｉ，ｄｉ−１）＝ｒａｎｋ（Ｓ，ｊ，ｄｊ−１）であれば、兄弟要素であると判定してもよい。

［第４の形態例］
ＸＰａｔｈに規定されている検索クエリは、複数の構造パスに合致する場合がある。例えば、「／ａ／／ｔｅｘｔ（）」という検索クエリは、タグ名が「ａ」であるルート要素の子孫であるテキストノードの全てに合致する。このような検索クエリが与えられた場合、パストライ上でクエリに合致する構造パスを全て計算し、それらの検索結果の和集合を取ればよい。

［第５の形態例］
ＸＰａｔｈに規定されている検索クエリは、テキストに関する条件を含む場合がある。例えば「”／ａ／／ｔｅｘｔ()[ｃｏｎｔａｉｎｓ(.,”ａｂｃ"）]」という検索クエリは、タグ名が「ａ」であるルート要素の子孫であるテキストで"ａｂｃ"を含むものに合致する。このような検索クエリが与えられた場合、前述したＸＭＬ要素に関する検索結果と、テキストデータ４２４に対するテキスト検索の結果を照合し、両方の条件に合致する箇所を検索結果とすればよい。

テキスト検索の処理には、公知の任意の手法が使用できる（例えば非特許文献６を参照）。

［他の形態例］
前述の形態例は、本発明の適用例を例示したものであり、本発明の技術的範囲を前述した各形態例の具体的構成に限定する趣旨ではない。本発明の要旨を逸脱しない範囲において種々の変更可能である。例えば本発明は、前述した各形態例の全ての構成要素を備える必要はない。また、ホン発明は、ある形態例の一部を他の形態例の構成に置き換えることもでき、ある形態例の構成に他の形態例の構成を加えることもできる。

また、上述した各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路その他のハードウェアとして実現しても良い。また、各処理機能を実現するプログラム、テーブル、ファイル等の情報は、メモリやハードディスク、SSD（Solid State Drive）等の記憶装置、ICカード、SDカード、DVD等の記憶媒体に格納することができる。

４００ ＸＭＬ文書検索装置
４０１ ＣＰＵ
４０２ 主記憶装置
４０３ 補助記憶装置
４０４ リムーバブルドライブ
４０６ ユーザインタフェース
４０７ ネットワークインタフェース
４１０ ＸＭＬ文書分析部
４１１ Ｗａｖｅｌｅｔ木構築部
４１２ 構造パス分析部
４１３ ノード探索部
４２０ ＸＭＬ文書集合
４２１ パストライ
４２２ 数列化されたＤＯＭ木
４２３ Ｗａｖｅｌｅｔ木
４２４ テキストデータ
４３０ 外部記憶装置
４４０ ネットワーク
１７００ ＸＭＬ文書検索装置

Claims (8)

1. プロセッサと、主記憶装置と、ＸＭＬ文書を入出力する入出力装置とを有し、検索クエリとして、ＸＭＬ文書の要素及びその要素の祖先要素をルート要素から順にすべて列挙したものである構造パスが与えられたとき、その構造パスに合致する箇所を探索するＸＭＬ文書検索装置において、
   前記入出力装置は、検索対象のＸＭＬ文書集合の入力を受け付け、
   前記ＸＭＬ文書検索装置は、
   前記ＸＭＬ文書を分析し、タグの種類および包含関係を認識し数列群に変換するとともにパストライを構築するＸＭＬ文書分析部と、
   前記パストライを用いて、検索クエリである構造パスの深さおよびパス種別を計算する構造パス分析部と、
   前記構造パスの深さ及びパス種別に基づき、検索クエリである構造パスに合致する要素が出現する箇所を計算する要素探索部とを有し、
   前記ＸＭＬ文書分析部は、
   ＸＭＬ文書のＤＯＭ木の形状を記録するために、ＸＭＬ文書の出現する要素の出現順に、当該要素の深さを表す数値の列を部分列として含む第一の数列Ｓと、
   前記ＤＯＭ木の各ノードに対応する構造パスの種類を記録する１つ以上の数列からなる数列群Ｔとを作成し、数列群Ｔに含まれる数列Ｔ［ｄ］が深さｄである構造パスの種類を記録したものであるとき、
   前記要素探索部は、
   前記数列Ｓと、前記数列群Ｔを走査することにより、検索クエリである構造パスに合致する箇所を計算する
   ことを特徴とするＸＭＬ文書検索装置。
2. 請求項１に記載のＸＭＬ文書検索装置において、
   前記要素探索部は、
   数列Ａにおいてｊ番目に値ｃが出現する位置をｓｅｌｅｃｔ（Ａ，ｃ，ｊ）と表記し、この値を計算する処理をｓｅｌｅｃｔ演算と呼び、前記検索クエリの構造パスの深さをｄ、パス種別をｔとし、当該構造パスの出現総数をｎとするとき、１≦ｋ≦ｎである整数ｋに対し、式（１）を適用して得られるｋ”の値を計算することにより、前記検索クエリに合致する箇所を前記ＸＭＬ文書集合から探索する
   ことを特徴とするＸＭＬ文書検索装置。
   ［数１］
   ｋ”＝ｓｅｌｅｃｔ（Ｓ，ｄ，ｓｅｌｅｃｔ（Ｔ[d]，ｔ，ｋ）） …式（１）
3. 請求項２に記載のＸＭＬ文書検索装置において、
   前記ＸＭＬ文書分析部の処理に引き続き、前記数列Ｓ及び前記数列群Ｔに含まれる各数列をＷａｖｅｌｅｔ木に変換するＷａｖｅｌｅｔ木構築部を有し、
   前記ｓｅｌｅｃｔ演算に、前記Ｗａｖｅｌｅｔ木を用いる
   ことを特徴とするＸＭＬ文書検索装置。
4. 請求項１に記載のＸＭＬ文書検索装置において、
   ＸＭＬ文書のＤＯＭ木の形状を記録するために、ＸＭＬ文書の出現する要素の出現順に、当該要素の深さを表す数値の列を部分列として含む数列を構築する手段を有し、
   前記数列Ｓにおいてｉ番目までにある値ｃの数をｒａｎｋ（Ｓ，ｃ，ｉ）と表記し、この値を計算する処理をｒａｎｋ演算と呼び、
   数列Ｓにおいてｊ番目に値ｃが出現する位置をｓｅｌｅｃｔ（Ｓ，ｃ，ｊ）と表記し、この値を計算する処理をｓｅｌｅｃｔ演算と呼び、
   前記数列においてｉ番目の値に対応するＸＭＬ文書の要素に対し、その要素の構造パスの深さをｄとするとき、
   前記要素の親である要素の番号を式（２）によって計算し、
   前記要素の最初の子である要素の番号を式（３）によって計算し、
   前記要素に最も近い先行する兄弟要素の番号を式（４）によって計算し、
   前記要素に最も近い後続の兄弟要素の番号を式（５）によって計算する
   ことを特徴とするＸＭＬ文書検索装置。
   ［数２］
   ｓｅｌｅｃｔ（Ｓ，ｄ−１，ｒａｎｋ（Ｓ，ｄ−１，ｉ）） …式（２）
   ［数３］
   ｉ＋１ …式（３）
   ［数４］
   ｓｅｌｅｃｔ（Ｓ，ｄ，ｒａｎｋ（Ｓ，ｄ，ｉ−１）） …式（４）
   ［数５］
   ｓｅｌｅｃｔ（Ｓ，ｄ，ｒａｎｋ（Ｓ，ｄ，ｉ）＋１） …式（５）
5. 請求項４に記載のＸＭＬ文書検索装置において、
   前記ＸＭＬ文書分析部の処理に引き続き、前記数列Ｓおよび前記数列群Ｔに含まれる各数列をＷａｖｅｌｅｔ木に変換するＷａｖｅｌｅｔ木構築部を有し、
   前記ｒａｎｋ演算及び前記ｓｅｌｅｃｔ演算に、前記Ｗａｖｅｌｅｔ木を用いる
   ことを特徴とするＸＭＬ文書検索装置。
6. 検索クエリとして、ＸＭＬ文書の要素及びその要素の祖先要素をルート要素から順にすべて列挙したものである構造パスが与えられたときに、その構造パスに合致する箇所を探索する処理をコンピュータに実行させるプログラムにおいて、
   前記プログラムは、
   前記ＸＭＬ文書を分析し、タグの種類および包含関係を認識し数列群に変換しパストライを構築する第１の処理と、
   前記パストライを用いて、検索クエリである構造パスの深さおよびパス種別を計算する第２の処理と、
   前記構造パスの深さ及びパス種別に基づき、検索クエリである構造パスに合致する要素が出現する箇所を計算する第３の処理とを前記コンピュータに実行させ、
   前記第１の処理は、
   ＸＭＬ文書のＤＯＭ木の形状を記録するために、ＸＭＬ文書の出現する要素の出現順に、当該要素の深さを表す数値の列を部分列として含む第一の数列Ｓと、ＤＯＭ木における各ノードに対応する構造パスの種類を記録する１つ以上の数列からなる数列群Ｔとを作成し、数列群Ｔに含まれる数列Ｔ［ｄ］が深さｄである構造パスの種類を記録したものであるとき、
   前記第３の処理は、
   前記数列Ｓと、前記数列群Ｔを走査することにより、検索クエリである構造パスに合致する箇所を計算する
   ことを特徴とするプログラム。
7. 請求項６に記載のプログラムにおいて、
   前記第３の処理は、
   数列Ａにおいてｊ番目に値ｃが出現する位置をｓｅｌｅｃｔ（Ａ，ｃ，ｊ）と表記し、この値を計算する処理をｓｅｌｅｃｔ演算と呼び、前記検索クエリの構造パスの深さをｄ、パス種別をｔとし、当該構造パスの出現総数をｎとするとき、１≦ｋ≦ｎである整数ｋに対し、式（６）を適用して得られるｋ”の値を計算することにより、前記検索クエリに合致する箇所を前記ＸＭＬ文書集合から探索する
   ことを特徴とするプログラム。
   ［数６］
   ｋ”＝ｓｅｌｅｃｔ（Ｓ，ｄ，ｓｅｌｅｃｔ（Ｔ[d]，ｔ，ｋ）） …式（６）
8. 請求項７に記載のプログラムにおいて、
   前記第１の処理に引き続き、前記数列Ｓ及び前記数列群Ｔに含まれる各数列をＷａｖｅｌｅｔ木に変換する第４の処理を有し、
   前記ｓｅｌｅｃｔ演算に、前記Ｗａｖｅｌｅｔ木を用いる
   ことを特徴とするプログラム。

Images