(57)【要約】  本発明は、ツリー状構造を有し、文書構造定義群の少なくとも１つの文書構造定義に従う文書群における検索方法に関する。本方法は、（１）特定のブランチを受け付けるステップと、（３）特定のブランチが文書構造定義に従う文書内に存在することを許容する文書構造定義群のサブセットを決定するステップと、（５）サブセットの文書構造定義の何れか１つに従う文書群のすべての文書を有する文書群のサブセットを決定するステップと、（７）各文書において特定のブランチの少なくとも一部を検索するステップとを有する。本発明はさらに、本発明の文書群における検索方法を容易にするため、文書群をインデックス処理する方法に関する。本発明はまた、本発明の上記方法をプログラム可能な装置が実行することを可能にするコンピュータプログラムプロダクトと、本発明の上記方法を実行するための電子装置とに関する。
2006528382.tif 000002
【特許請求の範囲】
【請求項１】
ツリー状構造を有する文書群における検索方法であって、前記文書群の各文書は、文書構造定義群の少なくとも１つの文書構造定義に従い、
当該方法は、
特定のブランチを受け付けるステップと、
当該サブセットの各文書構造定義が該定義に従う文書内に前記特定のブランチが存在することを許容する前記文書構造定義群のサブセットを決定するステップと、
前記サブセットの文書構造定義の何れか１つに従う前記文書群のすべての文書を有する前記文書群のサブセットを決定するステップと、
各文書において前記特定のブランチの少なくとも一部を検索するステップと、
を有することを特徴とする方法。
【請求項２】
請求項１記載の方法であって、さらに、
前記文書群のサブセットの各暗号化文書を解読しようとするステップを有することを特徴とする方法。
【請求項３】
請求項１記載の方法であって、
前記文書群のサブセットを決定するステップは、前記特定のブランチの少なくとも一部に対する番号を、該少なくとも一部にハッシュ関数を適用することにより計算し、番号から文書へのマッピングにおいて前記計算された番号にマッピングされる文書を検索することを有し、
前記マッピングは、前記文書構造定義のサブセットの文書構造定義及び該文書構造定義に従うマッピングにおける前記文書を関連付ける、
ことを特徴とする方法。
【請求項４】
請求項３記載の方法であって、さらに、
前記特定のブランチに係る値を受け付けるステップを有し、
前記マッピングはさらに、該マッピングにおける文書と値域パーティションとの間の関連付けを有し、
前記文書群のサブセットを決定するステップはさらに、前記計算された番号にマッピングされる文書に係る値域パーティションが前記受け付けた値を有するさらなる値域パーティションに一致するかチェックする、
ことを特徴とする方法。
【請求項５】
請求項１記載の方法であって、
前記文書群のサブセットを決定するステップは、文書構造定義から文書へのマッピングにおいて、前記文書構造定義のサブセットの何れか１つに従う文書を検索することを特徴とする方法。
【請求項６】
請求項１記載の方法であって、
前記文書構造定義群のサブセットを決定するステップは、前記特定のブランチの少なくとも一部に対するさらなる番号を、該少なくとも一部にさらなるハッシュ関数を適用することにより計算し、番号から文書構造定義へのマッピングにおいて前記計算された番号にマッピングされる文書構造定義を検索することを特徴とする方法。
【請求項７】
請求項１記載の方法であって、
前記文書構造定義群のサブセットを決定するステップは、前記文書構造定義群の各暗号化文書構造定義を解読し、各文書構造定義に対し、該文書構造定義により前記特定のブランチが該文書構造定義に従う文書内に存在することを許容するか決定しようとすることを特徴とする方法。
【請求項８】
請求項１記載の方法をプログラム可能な装置が実行することを可能にするコンピュータプログラム。
【請求項９】
電子回路を有し、文書群における検索を実行する電子装置であって、
前記電子回路は、
特定のブランチを受け付ける入力受付器と、
当該サブセットの各文書構造定義が該定義に従う文書内に前記特定のブランチが存在することを許容する文書構造定義群のサブセットを決定する定義サブセット決定装置と、
前記サブセットの文書構造定義の何れか１つに従う前記文書群のすべての文書を有する前記文書群のサブセットを決定する文書サブセット決定装置と、
各文書において前記特定のブランチの少なくとも一部を検索する検索装置と、
を機能的に有することを特徴とする電子装置。
【請求項１０】
ツリー状構造を有する文書群をインデックス処理する方法であって、前記文書群の各文書は、文書構造定義群の少なくとも１つの文書構造定義に従い、
当該方法は、
前記文書構造定義群の各文書構造定義に対し、ある整数範囲からの整数を前記文書群の文書にマッピングするエンプティインデックスを生成するステップと、
前記文書群の文書のブランチの少なくとも一部に対する番号を、該少なくとも一部にハッシュ関数を適用することにより計算するステップと、
前記文書が従う文書構造定義に対するインデックスへの前記計算された番号から前記ブランチの少なくとも一部を有する文書へのマッピングを有するエントリを生成するステップとを有し、
前記番号は、前記整数範囲に限定され、前記計算はおそらく異なるブランチに同一番号を生成することを特徴とする方法。
【請求項１１】
請求項１０記載の方法であって、
前記インデックスへのエントリを生成するステップは、前記ブランチに係る値を有する値域パーティションと前記マッピングにおける文書を関連付けることを特徴とする方法。
【請求項１２】
請求項１０記載の方法であって、さらに、
さらなる整数範囲からの各整数が文書構造定義にマッピング可能なさらなるエンプティインデックスを生成するステップと、
前記ブランチの少なくとも一部に対するさらなる番号を、該ブランチにさらなるハッシュ関数を適用することにより計算するステップと、
前記計算されたさらなる番号から前記文書が従う文書構造定義へのマッピングを有する前記さらなるインデックスへのエントリを生成するステップとを有し、
前記さらなる番号は、前記さらなる整数範囲に限定され、前記計算はおそらく異なるブランチに対し同一のさらなる番号を生成することを特徴とする方法。
【請求項１３】
請求項１０記載の方法をプログラム可能な装置が実行することを可能にするコンピュータプログラム。
【請求項１４】
電子回路を有し、文書群をインデックス処理する電子装置であって、
前記電子回路は、
文書構造定義群の各文書構造定義に対し、ある整数範囲からの整数を前記文書群の文書にマッピングするエンプティインデックスを生成するインデックス生成装置と、
前記文書群の文書のブランチの少なくとも一部に対する番号を、該少なくとも一部にハッシュ関数を適用することにより計算するハッシュ計算装置と、
前記文書が従う文書構造定義に対するインデックスへの前記計算された番号から前記ブランチの少なくとも一部を有する文書へのマッピングを有するエントリを生成するインデックス充填装置とを有し、
前記番号は、前記整数範囲に限定され、前記計算はおそらく異なるブランチに同一番号を生成することを特徴とする電子装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ツリー状の構造を有する文書群における検索方法に関し、当該文書群の各文書は、文書構造定義群の少なくとも１つの文書構造に従うものであって、より詳細には特定のブランチを受け付けるステップと、文書群において当該特定のブランチの少なくとも一部を検索するステップとを有する方法に関する。
【０００２】
本発明はさらに、プログラム可能な装置が文書群における検索方法を実行することを可能にするコンピュータプログラムプロダクトに関する。
【０００３】
本発明はまた、文書群における検索を行う電子装置に関する。
【０００４】
本発明はさらに、文書群をインデックス処理する方法に関し、より詳細には、構造化された文書群における検索を可能にする方法に関する。
【０００５】
本発明はまた、プログラム可能な装置が文書群をインデックス処理する方法を実行することを可能にするコンピュータプログラムプロダクトに関する。
【０００６】
本発明はさらに、構造化された文書群をインデックス処理する電子装置に関する。
【背景技術】
【０００７】
ＸＰａｔｈと呼ばれるワールドワイドウェブコンソーシアム規格から、上記文書群における検索方法の一例が知られている。当該規格は、特定のパスを含むＸＭＬ文書の検索を開示している。ＸＭＬ文書は、各ノードがタグとおそらくある値を有するツリー状の構造を有する。２つのノードの間には複数のパスは存在しない。各ＸＭＬ文書における検索を行うことにより、ＸＭＬ文書におけるパスを検索することが一般的である。文書群における既知の検索方法の問題点は、特に文書が暗号化され、解読が必要な場合、検索に時間がかかるということである。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の第１の課題は、より効率的な検索を可能にする文書群における検索方法を提供することである。
【０００９】
本発明の第２の課題は、より効率的な検索を可能にする文書群におけるインデックス処理方法を提供することである。
【課題を解決するための手段】
【００１０】
本発明によると、第１の課題は、文書群における検索方法が、特定のブランチを受け付けるステップと、当該サブセットの各文書構造定義が該定義に従う文書内に前記特定のブランチが存在することを許容する前記文書構造定義群のサブセットを決定するステップと、前記サブセットの文書構造定義の何れか１つに従う前記文書群のすべての文書を有する前記文書群のサブセットを決定するステップと、各文書において前記特定のブランチの少なくとも一部を検索するステップとを有することにより実現される。ブランチは、複数のノードにおいてスタート又はエンドするものであってもよい。パスとブランチの両方が１以上のタグを有し、パスもまたブランチである。パスは、例えば、“ｂｏｏｋ／ｎａｍｅ”又は“ｂｏｏｋ．ｎａｍｅ”などにより表されてもよい。ブランチは、例えば、“ｂｏｏｋ／ｎａｍｅ”、“ｂｏｏｋ．ｎａｍｅ”又は“ｂｏｏｋ（ｎａｍｅ＋ａｕｔｈｏｒ（ｎａｍｅ＋ａｇｅ））”により表されてもよい。ブランチは、｛“ｂｏｏｋ．ｎａｍｅ”，“ｂｏｏｋ．ａｕｔｈｏｒ．ｎａｍｅ”，“ｂｏｏｋ．ａｕｔｈｏｒ．ａｇｅ”｝などの複数のパスにより表されてもよい。文書は、例えば、ＸＭＬ又はＳＧＭＬ文書であってもよい。文書構造定義は、例えば、ＸＭＬ  ＤＴＤ（Ｄａｔａ  Ｔｙｐｅ  Ｄｅｆｉｎｉｔｉｏｎ）又はＸＭＬ  Ｓｃｈｅｍａであってもよい。文書構造定義を用いて候補文書群を決定することにより、検索がより効率的なものとされる。もはやすべての文書において検索を行う必要はない。
【００１１】
本発明の文書群における検索方法の実施例では、さらに、前記文書群のサブセットの各暗号化文書を解読しようとするステップを有する。必ずしもすべての暗号化文書が解読される必要がなく、サブセットの暗号化文書のみが解読されればよいため、暗号化文書の不必要な解読が減らされる。
【００１２】
前記文書群のサブセットを決定するステップは、前記特定のブランチの少なくとも一部に対する番号を、該少なくとも一部にハッシュ関数を適用することにより計算し、番号から文書へのマッピングにおいて前記計算された番号にマッピングされる文書を検索することを有し、前記マッピングは、前記文書構造定義のサブセットの文書構造定義及び該文書構造定義に従うマッピングにおける前記文書を関連付けされる。これはセキュリティを与えるだけでなく（マッピングは、どのブランチがどの文書内に存在するか示してはいない）、効率的な文書検索を可能にする。ハッシュマッピングのサイズは（ハッシュ関数により返される最も可能性のある最大数）、文書群に基づき適応されてもよい。
【００１３】
あるいは、ブランチ名のハッシュを格納する代わりに、ブランチ名自体がブランチ名から文書へのマッピングに格納することも可能である。これはまた、インデックスを用いない検索と比較して、より効率的な検索を可能にするが、ハッシュマッピングを利用する場合より効果は低くなる。セキュリティを提供するため、追加的手段がとられる必要がある。ブランチが文書に明確にマッピングされないことを保証するため、ブランチは、当該ブランチを含まない文書にマッピングされる必要があるかもしれない。これは、検索をさらに非効率なものとするが、ある程度の秘匿性を提供する。
【００１４】
本方法は、さらに、前記特定のブランチに係る値を受け付けるステップを有するようにしてもよい。前記マッピングはさらに、該マッピングにおける文書と値域パーティションとの間の関連付けを有するようにしてもよい。前記文書群のサブセットを決定するステップはさらに、前記計算された番号にマッピングされる文書に係る値域パーティションが前記受け付けた値を有するさらなる値域パーティションに一致するかチェックするようにしてもよい。マッピングにおいて値ではなく、値域パーティションのみをおくことにより、セキュリティが提供される。値域パーティションは、可能な値の弱い表示のみを与えるが、より効率的な検索を可能にする。値域パーティションは、例えば、“ａ−ｅ”、“ａ，ｂ，ｃ，ｄ，ｅ”、“１−５”、“１，２，３，４，５”、“ヨーロッパ”、“オランダ，ドイツ，フランス，．．．”などであってもよい。
【００１５】
前記文書群のサブセットを決定するステップは、文書構造定義から文書へのマッピングにおいて、前記文書構造定義のサブセットの何れか１つに従う文書を検索するものであってもよい。効果的には、各文書構造定義に対するマッピングを生成したり、文書と値域パーティションとを関連付ける必要はないため、文書構造定義から文書へのマッピングは、手動により容易に作成可能である（例えば、テキストエディタを用いて）。
【００１６】
前記文書構造定義群のサブセットを決定するステップは、前記特定のブランチの少なくとも一部に対するさらなる番号を、該少なくとも一部にさらなるハッシュ関数を適用することにより計算し、番号から文書構造定義へのマッピングにおいて前記計算された番号にマッピングされる文書構造定義を検索する。ハッシュマッピングは（例えば、ハッシュテーブルによるなど）、もはや文書構造定義を解読する必要がないため、文書構造定義群のサブセットを決定するステップをより効率的にする。ハッシュマッピングはどのブランチがどの文書構造定義により存在するか明らかにしないため、ハッシュマッピングはまたセキュリティを提供する。
【００１７】
前記文書構造定義群のサブセットを決定するステップは、前記文書構造定義群の各暗号化文書構造定義を解読し、各文書構造定義に対し、該文書構造定義により前記特定のブランチが該文書構造定義に従う文書内に存在することを許容するか決定しようとしてもよい。インデックス処理量は、検索において既存のＸＭＬ  ＤＴＤ又はＳｃｈｅｍａファイルを用いることにより限定することが可能である。ＸＭＬ  ＤＴＤ又はＳｃｈｅｍａファイルは、実際の検索の実行前にメモリのツリーにより表されるようにしてもよい。当該ツリーは、ＸＭＬ  ＤＴＤにより特定のブランチがＸＭＬ  ＤＴＤに従うＸＭＬ文書に存在することを許容するか決定するためトラバースされてもよい。
【００１８】
本発明の他の特徴では、文書群における検索を実行する電子装置は、特定のブランチを受け付ける入力受付器と、当該サブセットの各文書構造定義が該定義に従う文書内に前記特定のブランチが存在することを許容する文書構造定義群のサブセットを決定する定義サブセット決定装置と、前記サブセットの文書構造定義の何れか１つに従う前記文書群のすべての文書を有する前記文書群のサブセットを決定する文書サブセット決定装置と、各文書において前記特定のブランチの少なくとも一部を検索する検索装置とを機能的に有する電子回路を有する。
【００１９】
本発明によると、第２の課題は、文書群をインデックス処理する方法が、前記文書構造定義群の各文書構造定義に対し、ある整数範囲からの整数を前記文書群の文書にマッピングするエンプティインデックスを生成するステップと、前記文書群の文書のブランチの少なくとも一部に対する番号を、該少なくとも一部にハッシュ関数を適用することにより計算するステップと、前記文書が従う文書構造定義に対するインデックスへの前記計算された番号から前記ブランチの少なくとも一部を有する文書へのマッピングを有するエントリを生成するステップとを有し、前記番号は、前記整数範囲に限定され、前記計算はおそらく異なるブランチに同一番号を生成することにより実現される。これはセキュリティを提供するだけでなく（インデックスは、どのブランチがどの文書に存在するか示していない）、効率的な文書検索を可能にする（候補文書構造定義に従う各文書を抽出／読む必要がない）。
【００２０】
文書群をインデックス処理する他の方法では、１つの文書構造定義からいくつかの文書への複数インデックスマッピングの代わりに、すべての文書構造定義からいくつかの文書への単一インデックスマッピングが生成されてもよい。この１つのインデックスは、例えば、セキュリティと効率性の両方を提供することが可能なハッシュテーブルであってもよい。当該テーブルに用いられる他の整数範囲は、当該整数範囲又はさらなる整数範囲より大きなものである可能性が高い。
【００２１】
本発明の文書群をインデックス処理する方法の実施例では、前記インデックスへのエントリを生成するステップは、前記ブランチに係る値を有する値域パーティションと前記マッピングにおける文書を関連付ける。
【００２２】
本方法はさらに、さらなる整数範囲からの各整数が文書構造定義にマッピング可能なさらなるエンプティインデックスを生成するステップと、前記ブランチの少なくとも一部に対するさらなる番号を、該ブランチにさらなるハッシュ関数を適用することにより計算するステップと、前記計算されたさらなる番号から前記文書が従う文書構造定義へのマッピングを有する前記さらなるインデックスへのエントリを生成するステップとを有し、前記さらなる番号は、前記さらなる整数範囲に限定され、前記計算はおそらく異なるブランチに対し同一のさらなる番号を生成するようにしてもよい。
【００２３】
本発明の他の特徴では、文書群をインデックス処理する電子装置は、文書構造定義群の各文書構造定義に対し、ある整数範囲からの整数を前記文書群の文書にマッピングするエンプティインデックスを生成するインデックス生成装置と、前記文書群の文書のブランチの少なくとも一部に対する番号を、該少なくとも一部にハッシュ関数を適用することにより計算するハッシュ計算装置と、前記文書が従う文書構造定義に対するインデックスへの前記計算された番号から前記ブランチの少なくとも一部を有する文書へのマッピングを有するエントリを生成するインデックス充填装置とを機能的に有する電子回路を有し、前記番号は、前記整数範囲に限定され、前記計算はおそらく異なるブランチに同一番号を生成する。
【００２４】
本発明の方法及び電子装置の上記及び他の特徴は、図面を参照してさらに説明及び明らかにされる。
【発明を実施するための最良の形態】
【００２５】
図１において、本発明による文書群のインデックス処理方法が示される。本方法は、少なくとも３つのステップを有する。ステップ５１は、文書構造定義群の各文書構造定義に対し、ある範囲の整数からの整数を文書群のある文書にマッピングするエンプティインデックスを生成することを有する。ステップ５３は、文書群のある文書におけるブランチの少なくとも一部に対する番号を、当該ブランチの少なくとも一部にハッシュ関数を適用することによって計算することを有する。ここで、当該番号は、上記整数範囲に限定され、当該計算によりおそらく異なるブランチに対し同一の番号が生成される。最後に、ステップ５５は、上記文書が従う文書構造定義に対しインデックスのエントリを生成することを有し、当該エントリは、上記計算された番号から上記ブランチの少なくとも一部を有する文書へのマッピングを有する。
【００２６】
ＸＭＬ  ＤＴＤやＸＭＬスキーマなどの１つの文書構造定義に従うＸＭＬ文書などの文書は、類似の構造を有するが、おそらく異なる文書を区別するため異なる要素コンテンツ及び／又は属性値を有する。例えば、図２に示される”ｄｔｄ１”の準拠する文書”ｄｏｃ１”は、簡単化のため”ｌｉｍｉｔ＝１０００”として表される”ｌｉｍｉｔ”属性値１０００を有する。それの要素である”ｎｕｍｂｅｒ”、”ｎａｍｅ”、”ａｄｄｒｅｓｓ”及び”ａｍｏｕｎｔ”は、それぞれ”１２３４５６７８９”、”Ａｌｉｃｅ”、”Ｔｗｅｎｔｅ，Ｅｎｓｃｈｅｄｅ，Ｎｅｔｈｅｒｌａｎｄｓ”及び”１００．０”を有する。
【００２７】
ＸＭＬ  ＤＴＤ又はＸＭＬスキーマは、文書においてどの要素、属性などが許可されているかなど、それの準拠するＸＭＬ文書の正当な構成ブロックを規定する。上記コンポーネントは、文書のコンテンツの基礎となる階層的なツリー構造を構成し、当該ツリーの各パスは文書の一部をアドレス指定する。”パス”及び”パス長”の概念が以下において規定される。
［定義１］
パスｐは、任意の連続する２つのノードｎｉ及びｎｉ＋１（１≦ｉ≦ｋ−１，ｋ≧１）に対し、それらの間にエッジが存在するようなノードｎ１，ｎ２，．．．，ｎｋのシーケンスであり、ｐ＝（ｎ１／ｎ２／．．．／ｎｋ）により示される。
【００２８】
パスｐのパス長とは、当該パスのエッジの総数であり、｜ｐ｜として示される。すなわち、｜ｐ＝（ｎ１／ｎ２／．．．／ｎｋ）｜＝ｋ−１である。
【００２９】
図３は、図２においてＤＴＤの一例であるｄｔｄ１から抽出された各種長さのパスを列挙している。ここで、破線の下のコンテンツノードは、ｄｔｄ１には表されていないため、考察から除外される。
【００３０】
文書群のインデックス処理は、各ｄｔｄｉに対して文書ハッシュテーブルＤＯＣＨａｓｈＴａｂｌｅｄｔｄｉを構成することを有するようにしてもよい。図４において、ｄｔｄ１からの各ペアｃ＝（ｃｎａｍｅ，ｃｖａｌ）（ただし、”ｃｎａｍｅ”は要素／属性を示し、”ｃｖａｌ”は対応する要素コンテンツ／属性値を示す）は、ハッシュテーブルＤＯＣＨａｓｈＴａｂｌｅｄｔｄ１に符号化される（あるいは、”ｃｎａｍｅ”が”ｃｖａｌ”なしにハッシュテーブルＤＯＣＨａｓｈＴａｂｌｅｄｔｄ１に符号化される）。各ペアのハッシュアドレスは、ＳｉｚｅＤＴＤＨａｓｈＴａｂｌｅ｜ｐ｜ではなくハッシュテーブルのトータルサイズであるＳｉｚｅＤＯＣＨａｓｈＴａｂｌｅｄｔｄ１を用いて、関数”ＨａｓｈＦｕｎｃ（ｐ）”を介し計算される（アルゴリズム１）。同一のハッシュ関数が、文書構造定義に対するハッシュテーブルを生成するのに利用可能である。本例では、パスｐは常に１つのみのノードを有し、ｐ＝（ｃｎａｍｅ）かつ｜ｐ｜＝０である。例えば、ｓ＝４とし、ハッシュテーブルのサイズＳｉｚｅＤＯＣＨａｓｈＴａｂｌｅｄｔｄ１を４とする（すなわち、ＳｉｚｅＤＯＣＨａｓｈＴａｂｌｅｄｔｄ１＝４）。これにより、ＣｈｏｐＮａｍｅ（”ｌｉｍｉｔ”）＝”ｌｉｍｉ”、Ｂａｓｅ２６ＶａｌｕｅＯｆ（”ｌｉｍｉ”）＝１１×２６３＋８×２６２＋１２×２６＋８＝１９９０６４、及びＨａｓｈＦｕｎｃ（ｌｉｍｉｔ）＝１９９０６４×１００ｍｏｄ４＝０となる。
【００３１】
【表１】
2006528382.tif 000003
アルゴリズム１は、パスｐ＝（ｎ１／ｎ２／．．．／ｎｋ）のハッシュ値を計算する手順を説明する。それは、以下の３つのステップにより進められる。
【００３２】
第１に、異なる長さを有し得るパスｐのノード名が、関数ＣｈｏｐＮａｍｅ（アルゴリズム１，ステップａ）を介しユーザにより入力パラメータとして与えられる同一のサイズｓに一様に分断される。例えば、ｓ＝４、ＣｈｏｐＮａｍｅ（”ｃｒｅｄｉｔＣａｒｄ”，４）＝”ｃｒｅｄ”、ＣｈｏｐＮａｍｅ（”ｐａｙＩｎｆｏ”，４）＝”ｐａｙＩ”、ＣｈｏｐＮａｍｅ（”ｎａｍｅ”，４）＝”ｎａｍｅ”とする。
【００３３】
第２に、ステップａの後に固定されたサイズを有する分断されたノード名文字列がさらに、関数Ｂａｓｅ２６ＶａｌｕｅＯｆ（アルゴリズム１，ステップｂ）を介し１０進数の整数に変換される。例１は、ノード名文字列のサイズが４に設定されるとき、それがどのように機能するか示す。
【００３４】
例１
ケースに影響されない４文字のノード名”ｘ１ｘ２ｘ３ｘ４”がベース２６の整数を表すとき、”ａ”の文字が０桁値を表し、”ｂ”の文字が１桁値、”ｃ”の文字が２桁値を表し、”ｄ”の文字が３桁値を表し、以下同様にして、”ｚ”の文字が２５桁値を表す。ある文字が与えられると、関数”ｏｆｆｓｅｔ”が当該桁値を返す。従って、４文字のノード名”ｘ１ｘ２ｘ３ｘ４”は、以下の式を用いて１０進数に変換することができる。
【００３５】
【数１】
2006528382.tif 000004
ｘ１ｘ２ｘ３ｘ４＝”ｎａｍｅ”と仮定すると、”ｎ”、”ａ”、”ｍ”及び”ｅ”の桁値はそれぞれ、ｏｆｆｓｅｔ（”ｎ”）＝１３、ｏｆｆｓｅｔ（”ａ”）＝０、ｏｆｆｓｅｔ（”ｍ”）＝１２及びｏｆｆｓｅｔ（”ｅ”）＝４であるため、Ｂａｓｅ２６ＶａｌｕｅＯｆ（”ｎａｍｅ”）＝１３×２６３＋０×２６２＋１２×２６１＋４×２６０＝１３×１７５７６＋０＋３１２＋４＝２２８８０２となる。同様にして、Ｂａｓｅ２６ＶａｌｕｅＯｆ（”ｃｒｅｄ”）＝２×２６３＋１７×２６２＋４×２６１＋３×２６０＝２×１７５７６＋１７×６７６＋１０４＋３＝３５１５２＋１１４９２＋１０４＋３＝４６７５１となる。Ｂａｓｅ２６ＶａｌｕｅＯｆの一般的な計算は、
【００３６】
【数２】
2006528382.tif 000005
となる。
【００３７】
最後に、ハッシュ関数”ＨａｓｈＦｕｎｃ”は、各ノードｎｉに対する関数”Ｂａｓｅ２６ＶａｌｕｅＯｆ”から返される値Ｖｎｉに基づき、パスｐ＝（ｎ１／ｎ２／．．．／ｎｋ）のハッシュ値を導出する（アルゴリズム１、ステップｃ）。
【００３８】
【数３】
2006528382.tif 000006
例２
ｋ＝２、｜ｐ｜＝１であるパスｐ＝（ｃｒｅｄｉｔＣａｒｄ／ｎａｍｅ）が与えられると、ｓ＝４及びＳｉｚｅＤＴＤＨａｓｈＴａｂｌｅ｜ｐ｜＝ＳｉｚｅＤＴＤＨａｓｈＴａｂｌｅ１＝８とする。
【００３９】
【表２】
2006528382.tif 000007
インデックスへのエントリの生成は、値域パーティションへのマッピングにおける文書の関連付けを有し、当該値域パーティションはブランチに係る値を有する。文書のブランチ（”ｃｎａｍｅ”など）の少なくとも一部に対する番号を計算し、当該文書をこの番号にマッピングした後、文書を値域パーティションに関連付けすることが可能である。例えば、値域パーティションは文書識別子として同一のバケット（ｂｕｃｋｅｔ）におかれる。図４を参照されたい。本例において、図４及び５を参照するに、パスのノード部分のみがハッシュ処理される。バケットにおかれるエントリは、Ｈ．ｈａｃｉｇｕｍｕｓ、Ｂ．Ｌｙｅｒ、Ｃ．Ｌｉ及びＳ．Ｍｅｈｒｏｔｒａによる”Ｅｘｅｃｕｔｉｎｇ  ＳＱＬ  ｏｖｅｒ  ｅｎｃｒｙｐｔｅｄ  ｄａｔａ  ｉｎ  ｔｈｅ  ｄａｔａｂａｓｅ−ｓｅｒｖｉｃｅ−ｐｒｏｖｉｄｅｒ  ｍｏｄｅｌ”（Ｐｒｏｃ．ｔｈｅ  ＡＣＭ  ＳＩＧＭＯＤ  Ｉｎｔｌ．Ｃｏｎｆ．ｏｎ  Ｍａｎａｇｅｍｅｎｔ  ｏｆ  Ｄａｔａ，ページ２１６−２２７，Ｗｉｓｃｏｎｓｉｎ，ＵＳＡ，Ｊｕｎｅ  ２００２）において開発された手法を用いて、”ｃｎａｍｅ”及び”ｃｖａｌ”に基づき計算可能である。基本的アイデアは、まず、ノード”ｃｎａｍｅ”のドメインを完備かつ互いに素なパーティション群に分割する。すなわち、これらのパーティションは、ドメイン全体から抽出され、任意の２つのパーティションは重複するものでない。各パーティションには、一意的な整数識別子が割り当てられる。その後、要素／属性ノード”ｃｎａｍｅ”の値”ｃｖａｌ”が、それが属するパーティションに対応する整数にマッピングされる。例えば、属性”ｌｉｍｉｔ”のドメインは、識別子”０”、”１”及び”２”のそれぞれの範囲［０，５００］、（５００，１０００］及び（１０００，∞）に分割可能である。従って、”ｌｉｍｉｔ”の”１０００”の値は整数”１”にマッピングされ、ＨａｓｈＦｕｎｃ（ｌｉｍｉｔ）＝０であるため、ＤＯＣＨａｓｈＴａｂｌｅｄｔｄ１の第１バケットに格納される。例となる文書の他のペアのハッシュ値は、図５に示されるように、同様にして計算される。
【００４０】
ドメインのパーティションは、データ及び該当するアプリケーションのセマティックに基づき行うことができるということに留意されたい。例えば、要素”ｎａｍｅ”のドメインは、アルファベット順に分類可能である。要素”ａｄｄｒｅｓｓ”のドメインは、存在する地域や国に従って分割可能である。順序維持制約は、”ｃｎａｍｅ”のドメインの任意の２つの値”ｃｖａｌ１”と”ｃｖａｌ２”に対し、ｃｖａｌ１≦ｃｖａｌ２である場合、ＭａｐＦｕｎｃ（ｃｖａｌ１）≦ＭａｐＦｕｎｃ（ｃｖａｌ２）となることを意味する”ＭａｐＦｕｎｃ：ドメイン（ｃｎａｍｅ）→整数”のマッピングにより実行可能である。
【００４１】
”ｎｕｍｂｅｒ”、”ｎａｍｅ”、”ａｄｄｒｅｓｓ”及び”ａｍｏｕｎｔ”に対するマッピング関数が、図５に示されるような識別子を返すと仮定すると、図４は、ＸＭＬ文書ｄｏｃ１などの結果としての符号化、すなわち、ＤＯＣＨａｓｈＴａｂｌｅｄｔｄ１をプロットする。１つのＤＴＤに従うすべての文書は、同一の文書ハッシュテーブルを共有する。競合するペアは、競合するハッシュアドレスのバケットにリンクされる。
【００４２】
文書群をインデックス処理する方法はさらに、ステップ５７、５９及び６１を有するようにしてもよい。これらのステップは、ステップ５１、５３及び５５の前後又はパラレルに実行されてもよい。ステップ５７は、さらなる整数範囲からの各整数が文書構造定義にマッピング可能であるさらなるエンプティインデックスを生成することからなる。ステップ５９は、さらなるハッシュ関数をブランチに適用することにより、ブランチの少なくとも一部に対するさらなる番号を計算することからなる。このさらなる番号は、さらなる整数範囲に限定され、当該計算によりおそらく異なるブランチに対する同一のさらなる番号が生成される。ステップ６１は、さらなるインデックスへのエントリを生成することからなり、このさらなるインデックスのエントリは、計算されたさらなる番号から文書が従う文書構造定義へのマッピングからなる。
【００４３】
好ましくは、異なる長さのパスが、異なるインデックスにハッシュ処理可能である。例えば、異なる長さのパスが、それぞれ”ＤＴＤＨａｓｈＴａｂｌｅ０”、”ＤＴＤＨａｓｈＴａｂｌｅ１”、”ＤＴＤＨａｓｈＴａｂｌｅ２”、．．．、”ＤＴＤＨａｓｈＴａｂｌｅｍａｘ＿ｐａｓｕｔｈＬｅｎ”と名付けられた異なるハッシュテーブルにハッシュ処理可能である。図６を参照されたい。長さｌ（ただし、１≦ｌ≦ｍａｘ＿ｐａｔｈＬｅｎ）のすべてのパスは、それがどのＤＴＤからのものであろうと、１つのハッシュテーブルＤＴＤＨａｓｈＴａｂｌｅ１を有し、各バケットは当該バケットにハッシュ処理されたパスを有するＤＴＤ群を示す。ｄｔｄ１から抽出されたパスｐが存在すると仮定すると、ハッシュ関数ＨａｓｈＦｕｎｃ（ｐ）（アルゴリズム１）は、それのハッシュ値、すなわち、ハッシュテーブルＤＴＤＨａｓｈＴａｂｌｅ｜ｐ｜におけるバケットアドレスを計算する。対応するバケットにおいて、ｄｔｄ１の識別子がリンクされ、これはｐが存在するＤＴＤを示す。ハッシュベース符号化方法に対するより完全な概略を提供するため、図７において他のＤＴＤの例ｄｔｄ２が示される。図６において、各自のバケットにおいてマークされた対応するＤＴＤを有するｄｔｄ１とｄｔｄ２からのすべてのパスは、同一のハッシュ関数を用いてハッシュ処理される。もちろん、同一のインデックスにおいて異なる長さを有するパスをハッシュ処理することも可能である。
【００４４】
図８に参照されるように、本発明による文書群をインデックス処理する電子装置７１は、電子回路７３を有する。電子回路７３は、インデックス生成装置７５、ハッシュ計算装置７７及びインデックス充填装置７９を機能的に有する。インデックス生成装置７５は、文書構造定義群の各文書構造定義に対しエンプティインデックスを生成するよう動作し、このインデックスは、ある整数範囲からの整数を文書群の文書にマッピングする。ハッシュ計算装置７７は、文書分のある文書のブランチの少なくとも一部に対する番号を、当該ブランチの少なくとも一部にハッシュ関数を適用することにより計算する。当該番号は上記整数範囲に限定され、上記計算はおそらく異なるブランチに対し同一の番号を生成する。インデックス充填装置７９は、当該文書が従う文書構造定義に対するインデックスへのエントリを生成し、当該エントリは、計算された番号からブランチの少なくとも一部を有する文書へのマッピングを有する。
【００４５】
電子装置７１は、例えば、コンピュータ又は消費者電子装置であってもよい。ロジック回路は、例えば、コンピュータプログラム実行可能な汎用的なＣＰＵ（ＡＭＤ  ＡｔｈｌｏｎやインテルのＰｅｎｔｉｕｍ（登録商標）  ＣＰＵなど）であってもよい。好ましくは、インデックス生成装置７５、ハッシュ計算装置７７及びインデックス充填装置７９は、コンピュータプログラムの機能コンポーネントである。電子装置７１は、電子装置７１を構成し、及び／又はインデックス処理などを開始するキーボードなどの入力装置４５に結合されてもよい。電子装置７１は、電子装置７１を構成し、及び／又はインデックスなどを手動により検証するためのＣＲＴやＬＣＤモニタなどの出力装置４７に結合されてもよい。電子装置７１は、記憶手段４３を有するようにしてもよい。記憶手段４３は、例えば、１以上のハードディスク及び／又は１以上の光ディスクなどを有するものであってもよい。記憶手段４３は、例えば、生成されたインデックス、文書構造定義（ＸＭＬ  ＤＴＤ及び／又はＸＭＬ  Ｓｃｈｅｍａなど）及び文書（ＸＭＬ文書など）を有するものであってもよい。電子装置７１は、生成されたインデックス、１以上の文書構造定義及び／又は１以上の文書を格納する記憶手段を有する１以上の電子装置を有するコンピュータネットワークに接続されてもよい。
【００４６】
図９において、本発明による文書群における検索方法が示される。本方法は、少なくとも４つのステップを有する。ステップ１は、あるブランチを受信することからなる。ステップ３は、文書構造定義群のサブセットを決定することからなり、当該サブセットの各文書構造定義は、当該ブランチが当該文書構造定義に従う文書に存在することを可能にする。ステップ５は、文書群のサブセットを決定することからなり、当該文書サブセットは、サブセットの文書構造定義の何れかに従う文書群のすべての文書を有する。最後に、ステップ７は、各文書におけるブランチの少なくとも一部を検索することからなる。当該ブランチは、例えば、ユーザによりキーボードを介し入力され、パスに変換されたＸＰａｔｈ表現であってもよい。
【００４７】
ＸＰａｔｈ言語は、ＸＭＬ文書の部分をアドレス指定するためのＷ３Ｃにより提案された規格である。それは、ＸＭＬ文書を要素／属性に対応するノードのツリーとして処理し、当該ツリー内のノードを指定及び特定する表現的方法を提供する。
【００４８】
ＸＰａｔｈ表現は、ＸＭＬデータツリーのノードシーケンスから構成されるパスに一致可能な構造的パターンを記述する。このようなパスは、データツリーのルートからの絶対パスであってもよいし、あるいは、既知のコンテクストノードから始まる相対パスであってもよい。ノード間の階層的関係は、親子演算子（”／”）と先祖子孫演算子（”／／”）を用いてＸＰａｔｈ表現により指定される。例えば、ＸＰａｔｈ表現”／ｐａｙＩｎｆｏ／ｃｒｅｄｉｔＣａｒｄ／＠ｌｉｍｉｔ”は、文書の”ｐａｙＩｎｆｏ”ルート要素の子供要素である”ｃｒｅｄｉｔＣａｒｄ”の”ｌｉｍｉｔ”属性をアドレス指定する。相対パス表現”／／ｃｒｅｄｉｔＣａｒｄ／ｎａｍｅ”の”ｎａｍｅ”要素は、それの親である”ｃｒｅｄｉｔＣａｒｄ”要素に対する子供である。”／ｐａｙＩｎｆｏ／／ｎａｍｅ”の表現は、”ｐａｙＩｎｆｏ”ルート要素の”ｎａｍｅ”子孫要素をアドレス指定する。
【００４９】
ＸＰａｔｈはまた、文書データツリーのコンテクストノードに関する任意の要素又は属性ノードに一致可能なワイルドカード演算子（”＊”又は”＠＊”）の使用を許可する。さらに、スクエアブラケット（”［］”）に囲まれた述語は、ＸＰａｔｈ表現の選択されたノード群をさらに選別するのに適用可能である。例えば、”／ｐａｙＩｎｆｏ／ｃｒｅｄｉｔＣａｒｄ［＠ｌｉｍｉｔ＜１０００］／ｎａｍｅ”は、”ｃｒｅｄｉｔＣａｒｄ”の”ｌｉｍｉｔ”属性が１０００未満である場合、ＸＭＬ文書の”ｎａｍｅ”要素を選択する。
【００５０】
（”｜”）や（”ａｎｄ”）などの演算子もまた、パスの構成ノードを選択するのに適用可能である。例えば、”／ｐａｙＩｎｆｏ／（ｃｒｅｄｉｔＣａｒｄ｜ｃａｓｈ）／ｎａｍｅ”の表現は、ルート要素”ｐａｆＩｎｆｏ”の子供であって、”ｃｒｅｄｉｔＣａｒｄ”又は”ｃａｓｈ”要素である親を有するすべての”ｎａｍｅ”要素を選択する。他方、”／ｐａｙＩｎｆｏ／ｃｒｅｄｉｔＣａｒｄ［＠ｌｉｍｉｔ  ａｎｄ  ＠ｄｕｅＤａｔｅ］”は、ルート要素”ｐａｙＩｎｆｏ”のすべての”ｃｒｅｄｉｔＣａｒｄ”の子供が、”ｌｉｍｉｔ”属性と”ｄｕｅＤａｔｅ”属性の両方を有する必要があることを示す。
【００５１】
データツリーの部分を特定するのに用いられるＸＰａｔｈ表現ｅは、以下の３つのステップを通じてパス群と一致する必要がある。
【００５２】
ステップａ
ＸＰａｔｈ表現ｅを”／／”演算子の位置において複数のものに分解せよ。
【００５３】
オフラインクエリ準備段階中に符号化されるパスは、連続するノード間の親子関係（”／”）のみを有するため（図３に示されるように）、ＸＰａｔｈ表現は、”／／”演算子が存在する位置から、最初のものを除いた各ノードが”／”によってのみプリフィックスされる複数のものに分断される必要がある。これにより、結果として得られるＸＰａｔｈ表現は、連続するすべての２つのノード間の先祖子孫関係（”／／”）を含まない。
【００５４】
例３
ＸＰａｔｈ表現ｅ＝”／ｐａｙＩｎｆｏ［ａｍｏｕｎｔ＞１００］／／ｎａｍｅ”は、より短い２つのＸＰａｔｈ表現ｅ１’＝”／ｐａｙＩｎｆｏ［ａｍｏｕｎｔ＞１００］”とｅ２’＝”／／ｎａｍｅ”に分解することが可能である。
【００５５】
【数４】
2006528382.tif 000008
を用いて、このような意味的に等価な分解を示す。
【００５６】
説明を簡単化するため、ＸＰａｔｈ表現は、ｅ’などのプライムシンボルを用いてステップａの後に導出される。それらは、ステップｂの入力を構成する。
【００５７】
ステップｂ
各ＸＰａｔｈ表現ｅ’の述語制約を階層的関係のみに単純化せよ。
【００５８】
ＤＴＤ符号化は、候補ＤＴＤフィルタリングを容易にするため、パスノードに対する値の制約を取り除き、その階層的関係のみに着目すると、ＸＰａｔｈ述語条件に指定される”［ａｍｏｕｎｔ＞１００］”及び”［＠ｌｉｍｉｔ＝１０００］”などのノードに対する値の制約は、抑制可能であり、それらの本来の親子又は要素属性関係のみを維持することが可能である。
【００５９】
例４
ｅ１’＝”／ｐａｙＩｎｆｏ［ａｍｏｕｎｔ＞１００］”の述語制約は、”ａｍｏｕｎｔ”が”ｐａｙＩｎｆｏ”と”ａｍｏｕｎｔ”との間の親子関係を拡大することにより解消される値の制約を有する”ｐａｙＩｎｆｏ”の子供要素となることを意味し、ステップ２の後により緩和されたＸＰａｔｈ表現ｅ１’’＝”／ｐａｙＩｎｆｏ／ａｍｏｕｎｔ”を生成する。
【００６０】
【数５】
2006528382.tif 000009
は、このような単純化変換、すなわち、
【００６１】
【数６】
2006528382.tif 000010
を示すのに利用される。
【００６２】
例５
”／ｐａｙＩｎｆｏ［ａｍｏｕｎｔ＞１００］／ｃｒｅｄｉｔＣａｒｄ”などのＸＰａｔｈ表現の中間に位置する述語は、ステップｂの後に生成される２つのＸＰａｔｈ表現である”／ｐａｙＩｎｆｏ／ａｍｏｕｎｔ”と”／ｐａｙＩｎｆｏ／ｃｒｅｄｉｔＣａｒｄ”を導く。すなわち、
【００６３】
【数７】
2006528382.tif 000011
となる。ｅ’’は、ステップｂの後に返されるＸＰａｔｈ表現を示す。
【００６４】
ステップｃ
各ＸＰａｔｈ表現ｅ’’における論理演算子”｜”及び”ａｎｄ”を、当該表現を”Λ”又は”Ｖ”と論理接続された複数の表現に書き換えることによって消去せよ。
【００６５】
定義１のパスの概念に一致させるため、ステップＢの後、論理演算子”｜”及び”ａｎｄ”を含むすべてのＸＰａｔｈ表現は、”Λ”又は”Ｖ”を介し論理接続されるより短いＸＰａｔｈ表現群により置き換えられる。
【００６６】
例６
ＸＰａｔｈ表現ｅ’’＝”／ｐａｙＩｎｆｏ／（ｃｒｅｄｉｔＣａｒｄ｜ｃａｓｈ）／ｎａｍｅ”は、２つの選言的（ｄｉｓｊｕｎｃｔｉｖｅ）表現、すなわち、ｅ１’’’＝”／ｐａｙＩｎｆｏ／ｃｒｅｄｉｔＣａｒｄ／ｎａｍｅ”ａｎｄ”ｅ２’’’＝”／ｐａｙＩｎｆｏ／ｃａｓｈ／ｎａｍｅ”とみなすことができ、
【００６７】
【数８】
2006528382.tif 000012
として示される。
【００６８】
同様に、”／ｐａｙＩｎｆｏ／ｃｒｅｄｉｔＣａｒｄ［ｎａｍｅ  ａｎｄ  ｄｕｅＤａｔｅ］”という表現は、”／ｐａｙＩｎｆｏ／ｃｒｅｄｉｔＣａｒｄ／ｎａｍｅ”Λ”／ｐａｙＩｎｆｏ／ｃｒｅｄｉｔＣａｒｄ／ｄｕｅＤａｔｅ”に等価変換することが可能である。
【００６９】
上記３つのステップを実行した後、もとのＸＰａｔｈ表現は、各々が連続するすべての２つのノード間の先祖子孫関係、ノードに対する値の制約、及び論理演算子（”｜”）及び（”ａｎｄ”）を有しないシンプルなＸＰａｔｈ表現群に変換される。
【００７０】
例７
”／ｐａｙＩｎｆｏ［ａｍｏｕｎｔ＞１００］／（ｃｒｅｄｉｔＣａｒｄ｜ｃａｓｈ）／ｎａｍｅ”などの述語制約及び演算子（”｜”）を含むもとのＸＰａｔｈ表現から、３つのシンプルＸＰａｔｈ表現、”／ｐａｙＩｎｆｏ／ａｍｏｕｎｔ”Λ（”／ｐａｙＩｎｆｏ／ｃｒｅｄｉｔＣａｒｄ／ｎａｍｅ”Λ”／ｐａｙＩｎｆｏ／ｃａｓｈ／ｎａｍｅ”）を導出することができる。
【００７１】
ＸＰａｔｈクエリ表現から生成されるシンプルＸＰａｔｈ表現に基づき、与えられたクエリに対する候補ＤＴＤ及び文書のコンセプトを定義することが可能である。クエリから導出されるすべてのシンプルＸＰａｔｈ表現に対して、当該シンプルＸＰａｔｈ表現に一致するパスｐがＤＴＤにおそらく存在する場合、ＸＭＬ  ＤＴＤは当該クエリに対する候補ＤＴＤと呼ばれる。より簡単な方法では、ＸＭＬ文書は、１）それのＤＴＤが候補ＤＴＤであって、かつ２）それがＸＰａｔｈクエリ表現のノードに課せられるすべての述語制約をおそらく満たす場合、かつその場合に限って、当該クエリに対する候補文書であると定義可能である。
【００７２】
文書群における検索方法はさらに、文書サブセットの各暗号化文書を解読するステップ９を有するようにしてもよい。候補ＤＴＤは、パスワード又は公開鍵インフラストラクチャベース解読技術などを用いて解読されてもよい。
【００７３】
文書構造定義群のサブセットを決定するステップ３は、特定ブランチの少なくとも一部に対するさらなる番号を、特定ブランチの少なくとも一部にさらなるハッシュ関数を適用することによって計算するステップ１１と、番号から文書構造定義へのマッピングにおいて計算された番号にマッピングされる文書構造定義を検索するステップ１３とを有するようにしてもよい。例えば、クエリに対する非候補ＤＴＤをフィルタリングするため、当該クエリのすべてのＸＰａｔｈのハッシュ値が同一のハッシュ関数を用いて計算することができ、その後、例えば図６に示されるように、ＤＴＤハッシュテーブルの対応するバケットを、要求されたパスをおそらく含むＤＴＤサブセットを取得するためチェックすることが可能である。これらのＤＴＤは、クエリに対して考慮される候補ＤＴＤである。
【００７４】
与えられたクエリに対し候補ＤＴＤ群を予め選択した後、各候補ＤＴＤに対して候補文書がフィルタリング可能である。この段階において、パスノード上の［ｃｎａｍｅΘｃｖａｌ］形式による各種値の制約が考慮される（ただし、”ｃｎａｍｅ”は要素／属性ノード名を表し、”Θ”は｛＝，≠，＜，≦，＞，≧｝の演算子の１つであり、”ｃｖａｌ”は要素コンテンツ／属性値を表す）。明らかに、候補文書は、ＸＰａｔｈクエリ表現内に規定された値の制約の何れにも違反してはならない。
【００７５】
例えば、制約［ｃｎａｍｅΘｃｖａｌ］によると、ノード名”ｃｎａｍｅ”（すなわち、１つのノードのみを含むパス）が、まずハッシュ関数”ＨａｓｈＦｕｎｃ（ｃｎａｍｅ）”を介し”ＤＯＣＨａｓｈＴａｂｌｅｄｔｄｉにハッシュ処理される。他方、”ｃｖａｌ”の範囲識別子がさらに、順序維持関数”ＭａｐＦｕｎｃ（ｃｖａｌ）を用いて計算される。最後に、”ＤＯＣＨａｓｈＴａｂｌｅｄｔｄｉ”のバケットアドレス”ＨａｓｈＦｕｎｃ（ｃｎａｍｅ）”にリンクされる各エントリ値νが比較される。すなわち、
【００７６】
【数９】
2006528382.tif 000013
である場合、制約［ｃｎａｍｅΘｃｖａｌ］がおそらく成り立つ。その後、νが存在する関連する文書が、候補文書として返される。
【００７７】
例８
クエリが”ｃｒｅｄｉｔＣａｒｄ”要素に対する制約”［＠ｌｉｍｉｔ＞２０００］”を課すＸＰａｔｈ表現”／ｐａｙＩｎｆｏ／ｃｒｅｄｉｔＣａｒｄ［＠ｌｉｍｉｔ＞２０００］／ｎａｍｅ”を含むと仮定する。図４のインデックスを参照するに、ｓ＝４、ＳｉｚｅＤＯＣＨａｓｈＴａｂｌｅｄｔｄ１＝４である。”ＤＯＣＨａｓｈＴａｂｌｅｄｔｄ１”のアドレス０におけるマップされたすべての値は、２（＝ＭａｐＦｕｎｃ（２０００））より小さな１又は０であるため、例となる文書は、当該クエリの候補文書ではなく、破棄することができる。
【００７８】
文書構造定義群のサブセットを決定するステップ３は、文書構造定義群の各暗号化文書構造定義を解読するステップ１５と、各文書構造定義に対して、当該文書構造定義により特定ブランチが文書構造定義に従う文書内に存在することを許容するか決定するステップ１７とを有するようにしてもよい。
【００７９】
文書群のサブセットを決定するステップ５は、特定ブランチの少なくとも一部に対する番号を、特定ブランチの少なくとも一部にハッシュ関数を適用することにより計算するステップ２１と、番号から文書へのマッピングにおいて計算された番号にマッピングされる文書を検索するステップ２３とを有するようにしてもよい。ここで、当該マッピングは、文書構造定義のサブセットの文書構造定義と、当該定義に従うマッピングにおける文書とに関連付けされる。
【００８０】
例えば、クエリが与えられると、当該クエリから導出される各シンプルＸＰａｔｈ表現に対し、どの暗号化ＤＴＤが候補ＤＴＤであるかチェックするため、それはパスｐと一致可能であり、ＤＴＤのインデックスを生成しながら、ハッシュ値は同一のハッシュ関数”ＨａｓｈＦｕｎｃ（ｐ）”を用いてｐに対し計算することができる（アルゴリズム１）。返されたこのハッシュ値（すなわち、バケットアドレス）によると、図６に示されるように、ハッシュテーブル”ＤＴＤＨａｓｈＴａｂｌｅ｜ｐ｜”が、パスｐをおそらく含むＤＴＤのすべての識別子を与える対応するバケットにより照会される。これに対する根拠は、パスｐがＤＴＤに存在する場合、それはＤＴＤＨａｓｈＴａｂｌｅ｜ｐ｜のバケットにハッシュ処理され、バケットエントリに当該ＤＴＤのマークを残すという直接的なものである。
【００８１】
例９
あるクエリが、パスｐ＝”ｐａｙＩｎｆｏ／ｃｒｅｄｉｔＣａｒｄ／ｄｕｅＤａｔｅ”に対応する１つのみのシンプルＸＰａｔｈ表現から構成されると仮定する。ｓ＝４、ＳｉｚｅＤＴＤＨａｓｈＴａｂｌｅ２＝８である図６に示されるＤＴＤインデックスを参照するに、それのハッシュ値は以下のように計算される。
【００８２】
【表３】
2006528382.tif 000014
それのハッシュ値”１”により、ＤＴＤＨａｓｈＴａｂｌｅ２のアドレス１におけるエントリのみがｄｔｄ１を示しているため、例となるｄｔｄ２が当該パスを含まないことが確認できる。この結果、ｄｔｄ１のみが候補ＤＴＤとして返され、ｄｔｄ２とそれに関連する準拠した文書は、さらなる考察から削除することができる。
【００８３】
文書群のサブセットを決定するステップ５は、文書構造定義から文書へのマッピングにおいて、文書構造定義サブセットの何れかに従う文書を検索するステップ２５を有するようにしてもよい。
【００８４】
文書群における検索方法はさらに、特定ブランチに係る値を受信するステップ２７を有するようにしてもよい。このマッピングはさらに、マッピングにおける文書と値域パーティションとの間の関連付けを有する。文書群サブセットを決定するステップ５はさらに、計算された番号にマッピングされる文書に係る値域パーティションが、受信した値を有するさらなる値域パーティションに一致するかチェックするステップ２９を有するようにしてもよい。
【００８５】
図１０に示されるように、本発明による文書群における検索を行う電子装置３１は、電子回路３３を有する。電子回路３３は、入力受付器３５、定義サブセット決定装置３７、文書サブセット決定装置３９及び検索装置４１を機能的に有する。入力受付器３５は、特定のブランチを受信するよう動作する。定義サブセット決定装置３７は、サブセットの各文書構造定義により文書構造定義に従う文書内に当該ブランチが存在することを可能にする文書構造定義群のサブセットを決定するよう動作する。文書サブセット決定装置３９は、サブセットの文書構造定義の何れかに従う文書群のすべての文書を有する文書群のサブセットを決定するよう動作する。検索装置４１は、各文書において特定ブランチの少なくとも一部を検索するよう動作する。
【００８６】
電子装置３１は、例えば、コンピュータ又は消費者電子装置（携帯電話機やパーソナルビデオレコーダなど）であってもよい。ロジック回路は、例えば、コンピュータプログラム実行可能な汎用的なＣＰＵ（ＡＭＤ  ＡｔｈｌｏｎやインテルのＰｅｎｔｉｕｍ（登録商標）  ＣＰＵなど）であってもよい。好ましくは、入力受付器３５、定義サブセット決定装置３７、文書サブセット決定装置３９及び検索装置４１は、コンピュータプログラムの機能コンポーネントである。電子装置３１は、特定のブランチ又は特定のブランチなどに対応する表現などを入力するためのキーボードやキーパッドなどの入力装置４５に結合されてもよい。電子装置７１は、検索結果などを表示するためのＣＲＴやＬＣＤモニタなどの出力装置４７に結合されてもよい。電子装置３１は、記憶手段４３を有するようにしてもよい。記憶手段４３は、例えば、１以上のハードディスク及び／又は１以上の光ディスクなどを有するものであってもよい。記憶手段４３は、例えば、マッピング／インデックス、文書構造定義（ＸＭＬ  ＤＴＤ及び／又はＸＭＬ  Ｓｃｈｅｍａなど）及び文書（ＸＭＬ文書など）を有するものであってもよい。電子装置３１は、１以上のマッピング／インデックス、１以上の文書構造定義及び／又は１以上の文書を格納する記憶手段を有する１以上の電子装置を有するコンピュータネットワークに接続されてもよい。
【００８７】
本発明が好適な実施例に関して説明されたが、上記概略された原則の範囲内の変更が当業者には明らかであり、このため、本発明は好適な実施例に限定されるものではなく、このような変更も含むものであるということは理解される。本発明は、それぞれ新規な特徴的構成及び特徴的構成の各組み合わせにおいて備えられる。請求項の参照番号は、その保護範囲を限定するものではない。「有する」という動詞及びその活用形の使用は、請求項に記載された以外の要素の存在を排除するものではない。要素に先行する「ある」という冠詞の使用は、当該要素が複数存在することを排除するものではない。
【００８８】
「コンピュータプログラム」は、フロッピー（登録商標）ディスクなどのコンピュータ可読媒体に格納され、インターネットなどのネットワークを介しダウンロード可能であり、あるいは、他の何れかの手法により入手可能な任意のソフトウェアプロダクトを意味するものと理解される。
【図面の簡単な説明】
【００８９】
【図１】図１は、本発明による文書群をインデックス処理する方法のフローチャートである。
【図２】図２は、第１の文書例と対応する第１のＤＴＤ例を示す。
【図３】図３は、第１のＤＴＤ例から抽出されたパスを有するテーブルである。
【図４】図４は、インデックスの一例を示す。
【図５】図５は、第１の文書例の値域パーティションを有するテーブルである。
【図６】図６は、さらなるインデックスの一例を示す。
【図７】図７は、第２のＤＴＤ例を示す。
【図８】図８は、本発明による文書群をインデックス処理する電子装置のブロック図である。
【図９】図９は、本発明による文書群における検索方法のフローチャートである。
【図１０】図１０は、本発明による文書群における検索を行う電子装置のブロック図である。
【図１】
2006528382.tif 000015
【図２】
2006528382.tif 000016
【図３】
2006528382.tif 000017
【図４】
2006528382.tif 000018
【図５】
2006528382.tif 000019
【図６】
2006528382.tif 000020
【図７】
2006528382.tif 000021
【図８】
2006528382.tif 000022
【図９】
2006528382.tif 000023
【図１０】
2006528382.tif 000024
【国際調査報告】
2006528382.tif 000025
2006528382.tif 000026
2006528382.tif 000027
2006528382.tif 000028