(57)【要約】検索は、ユーザにスキーマに依存しないドキュメントの複数の区分内の検索を可能にする。構造化データ（図１、１２０）、準構造化データ（図１、１３０）および非構造化データ（図１、１４０）を含む上記ドキュメントは、ＸＭＬタグ（図３ａ）などの複数の区分に組織化されたテキストを含む。ドキュメントのリポジトリは、上記検索システムが上記区分に関するあらかじめ決められたフィールドを必要としないように、スキーマに依存しない。検索を実行するために、上記検索システムは、少なくとも１つの区分およびその区分内のテキストに関する少なくとも１つのフリーテキストクエリーコンストラクトを指定するクエリーを入力する（図５、１２１０−１２９０）。上記検索システムは、リポジトリ内の区分を同定し、複数の区分内のテキストに関する上記フリーテキストクエリーコンストラクトを評価し、上記フリーテキスト検索条件が満たされるか否かを決定する。
2005525659.tif 000002
【特許請求の範囲】
【請求項１】
ドキュメントを検索する方法であって、
複数の区分に組織化されたテキストを含むドキュメントのリポジトリを記憶するステップ；
少なくとも１つの指定区分および上記指定区分内のテキストに関する少なくとも１つのフリーテキストクエリーコンストラクトを含むクエリーを入力するステップであって、上記フリーテキストクエリーコンストラクトが少なくとも１つのフリーテキスト検索条件を指定するステップ；
上記クエリーを処理して、１グループのドキュメント内で上記指定区分を同定するステップ；および
上記ドキュメントグループ内の上記テキストに関する上記フリーテキストクエリーコンストラクトを評価して、上記フリーテキスト検索条件が満たされるか否かを決定するステップ
を含む方法。
【請求項２】
請求項１に記載の方法であって、
上記記憶するステップが、対応するノードおよび上記ノードと組み合わされたテキストを含むドキュメントを記憶するステップを含み；
上記入力するステップが、少なくとも１つのノードを指定するノードコンストラクトおよび上記フリーテキストクエリーコンストラクトを含むクエリーを入力するステップを含み；
上記処理するステップが、上記ノードコンストラクトに対応する上記ドキュメントのリポジトリ内でノードを同定するステップを含む
方法。
【請求項３】
請求項２に記載の方法であって、
上記入力するステップが、ロケーションパスを入力してノード集合を同定するステップを含む
方法。
【請求項４】
請求項１に記載の方法であって、もし上記フリーテキストクエリー条件が満たされるとすると、ドキュメント区分を返すステップをさらに含む方法。
【請求項５】
請求項１に記載の方法であって、
上記入力するステップが、準構造化ドキュメントを入力するステップを含み、上記準構造化ドキュメントが、組み合わされたデータを含む複数のフィールドを含み、上記準構造化ドキュメントの少なくとも１部分が非構造化フリーテキストを含む
方法。
【請求項６】
請求項１に記載の方法であって、
上記入力するステップが、複数のドキュメントに関する情報を入力するステップを含み、上記ドキュメントは、複数の構造化フィールドおよび上記構造化フィールドに組み合わされたフリーテキストを含み、上記ドキュメントが、上記ドキュメントの区分に関する形式を定義する複数の異なるスキーマを含み；
上記ドキュメントの索引を生成するステップであって、上記ドキュメントおよび上記索引内の複数の単語を同定する上記索引が、上記フリーテキストを、異なるスキーマを含むドキュメントに関する上記構造化フィールドに組み合わせる情報を含む
方法。
【請求項７】
請求項６に記載の方法であって、
上記生成するステップが、上記フリーテキストおよび対応する構造化フィールドの間のオフセットを生成するステップを含む
方法。
【請求項８】
請求項６に記載の方法であって、
上記生成するステップが、構造化フィールドに組み合わされたフリーテキストを定義する開始位置および終了位置を生成するステップを含む
方法。
【請求項９】
請求項６に記載の方法であって、
上記生成するステップが、構造化フィールドに組み合わされた単語数を指定する単語計数値を生成するステップを含む
方法。
【請求項１０】
請求項６に記載の方法であって、
上記入力するステップが、階層的に配置された１以上のノードに組織化された構造化フィールドを含むドキュメントを記憶するステップを含み；
上記生成するステップが、上記階層内のある単語のレベルに対応する上記単語に関する深さレベル情報を経由して、上記フリーテキストを上記構造化フィールドに組み合わせるステップを含む
方法。
【請求項１１】
コンピュータ読み取り可能な記録媒体であって、
複数の区分に組織化されたテキストを含むドキュメントのリポジトリを記憶し、
少なくとも１つの指定区分および上記指定区分内のテキストに関する少なくとも１つのフリーテキストクエリーコンストラクトを含むクエリーを処理する実行可能な命令であって、上記フリーテキストクエリーコンストラクトが少なくとも１つのフリーテキスト検索条件を指定する実行可能な命令；
上記クエリーを処理して、１グループのドキュメント内で上記指定区分を同定する実行可能な命令；および
上記ドキュメントグループ内で上記テキストに関する上記フリーテキストクエリーコンストラクトを評価して、上記フリーテキスト検索条件が満たされるか否かを決定する実行可能な命令
を含むプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１２】
請求項１１に記載の記録媒体であって、
上記リポジトリが、
対応するノードおよび上記ノードと組み合わされたテキストを含むドキュメントを含み、
上記実行可能な命令が
少なくとも１つのノードを指定するノードコンストラクトおよび上記フリーテキストクエリーコンストラクトを含むクエリーを入力する命令；および
上記ノードコンストラクトに対応する上記ドキュメントのリポジトリ内でノードを同定する命令
を含む記録媒体。
【請求項１３】
請求項１２に記載の記録媒体であって、
上記実行可能な命令が、
ロケーションパスを入力してノード集合を同定する命令
を含む記録媒体。
【請求項１４】
請求項１１に記載の記録媒体であって、もし上記フリーテキストクエリー条件が満たされるとすると、ドキュメント区分を返す実行可能命令をさらに含む記録媒体。
【請求項１５】
請求項１１に記載の記録媒体であって、
上記リポジトリが、
上記準構造化ドキュメントが、組み合わされたデータを含む複数のフィールドを含み、上記準構造化ドキュメントの少なくとも１部分が非構造化フリーテキストを含む
記録媒体。
【請求項１６】
請求項１１に記載の記録媒体であって、
上記リポジトリが、
複数の構造化フィールドおよび上記構造化フィールドに組み合わされたフリーテキストを含み、上記ドキュメントの区分に関する形式を定義する複数の異なるスキーマを含むドキュメント；
ここで、上記実行可能な命令は、
上記ドキュメントの索引を生成し、上記ドキュメントおよび上記索引内の複数の単語を同定する上記索引が、上記フリーテキストを、異なるスキーマを含むドキュメントに関する上記構造化フィールドに組み合わせる情報を含む命令
を含む記録媒体。
【請求項１７】
請求項１６に記載の記録媒体であって、上記実行可能な命令が、
上記フリーテキストおよび対応する構造化フィールドの間のオフセットを生成する命令
を含む記録媒体。
【請求項１８】
請求項１６に記載の記録媒体であって、上記実行可能な命令が、
構造化フィールドに組み合わされたフリーテキストを定義する開始位置および終了位置を生成する命令
を含む記録媒体。
【請求項１９】
請求項１６に記載の記録媒体であって、上記実行可能な命令が、
構造化フィールドに組み合わされた単語数を指定する単語計数値を生成する命令
を含む記録媒体。
【請求項２０】
請求項１６に記載の記録媒体であって、
上記リポジトリが
階層的に配置された１以上のノードに組織化された構造化フィールドを含むドキュメント；
を含み、
ここで、上記実行可能な命令が、
上記階層内でのある単語のレベルに対応する、上記単語に関する深さレベル情報を経由して、上記フリーテキストを上記構造化フィールドに組み合わせる命令
を含む
記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
一般的に、本発明は検索システムに関する。より詳細には、本発明は構造化、準構造化、および非構造化データの検索に関する。
【背景技術】
【０００２】
一般的に、検索システムは情報リポジトリを処理し、ユーザが上記情報リポジトリ内の情報を検索することを可能にする。上記情報リポジトリ内の情報を見つけるために、ユーザはクエリーを定式化する。それに応じて、システムは、クエリー内で指定された検索基準を満足する情報を見つけることにより上記クエリーを実行する。上記情報リポジトリはドキュメントを含むことができる。
【０００３】
検索システムは情報を記憶する方法を必要とする。データベースが、データを記憶し、組織化するために一般的に使用される。一般的に、データを記憶するためにデータベースを使用するために、ユーザはスキーマを指定する。上記スキーマはデータを記憶する所定のフィールドを定義する。例えば、関係データベースでは、データベーステーブルの列を定義して、上記データベーステーブルの列の内に記憶されるデータのための形式を定義する。例えば、ユーザは、１つの列が浮動小数点数を記憶するか、または１つの列が文字列を記憶するかを指定可能である。一般的に、データベースは、そのデータベース中に記憶されたデータを見つけるために正規のクエリー言語を使用する。１つの種類の正規のクエリー言語は標準的なクエリー言語（“ＳＱＬ”）である。上記データベース内のデータを検索するために、上記ユーザは上記正規のクエリー言語にしたがってクエリーを指定する。データベースはある用途にはよく適している。例えば、データベースは、値を指定する（すなわち、値８および１０の間の全てのフィールドを同定する）データベースのフィールドについての範囲指定クエリーをユーザが実行できるようにする。しかし、データベースは上記ユーザに上記データを既定のフィールドに割り当てることを要求するので、データベースは厳格である。もし検索システムのユーザが検索のためにドキュメントをインポートすると、上記ドキュメントを厳格なデータベース構造内に記憶することは役に立たない。したがって、ドキュメント用の所定のスキーマを必要としない（すなわち、スキーマに依存しないドキュメント）検索システムを開発することが望ましい。
【特許文献１】米国特許出願第ＰＣＴ／ＵＳ０３／１５５０７号
【発明の開示】
【発明が解決しようとする課題】
【０００４】
検索システムのドキュメントは１つの厳格なスキーマに従わなくてもよいが、複数のドキュメントはフィールドまたはタグの形で構造を含むことができる。ＸＭＬはＷＷＷ上の構造化ドキュメントおよびデータ用の一般的形式である。ＸＭＬの使用を通して、ＸＭＬタグを定義することによりドキュメントは構造を含むことができる。システムの能力を最大化するため、ＸＭＬタグにより定義される区分などのドキュメントの区分についてユーザが検索することを可能にする検索システムを開発することが望ましい。
【０００５】
ドキュメントはタグまたはフィールド内にフリーテキスト(論理演算子を使用しないテキスト）を含んでもよい。例えば、履歴書は学歴、職歴などの複数の既定フィールドを含んでいてもよい。学歴フィールドおよび職歴フィールド内では、見本ドキュメントは（その人の学歴および職歴を記載した）フリーテキストを含んでも良い。この例では、検索システムのユーザは学歴フィールドおよび職歴フィールド内のフリーテキストのみの検索を望んでいるかもしれない。それ故、ユーザにドキュメントの複数の区分のみの中のフリーテキストに関して検索可能にする検索システムを開発することが望ましい。ここに説明したように、本発明の検索システムはドキュメント内で構造化データ、準構造化データ、および非構造化データについての検索を実行可能にする。
【課題を解決するための手段】
【０００６】
検索技術は、ドキュメントの複数の区分内のフリーテキストをユーザが検索することを可能にする。少なくともいくつかのドキュメントは、複数の区分へと組織化されたテキストを含む。上記ドキュメントは構造化ドキュメント、準構造化ドキュメント、および非構造化ドキュメントを含んでもよい。１つの実施の形態では、上記複数の区分はＸＭＬタグなどの構造化フィールドを含む。ドキュメントのリポジトリはスキーマに依存しないので、上記検索システムは上記複数の区分に関する既定のフィールドを必要としない。
【０００７】
検索を実行するために、上記検索システムは、少なくとも１つの区分と上記区分内でのテキストについての少なくとも１つのフリーテキストクエリーのコンストラクトとを指定するクエリーを入力する。一般的に、上記フリーテキストクエリーのコンストラクトは少なくとも１つのフリーテキスト検索条件を指定する。上記検索システムは、クエリー内で指定されたようにドキュメントのリポジトリ内で複数の区分を同定し、区分内の上記テキストについてのフリーテキストクエリーのコンストラクトを評価して、フリーテキスト検索条件を満足するか否かを決定する。
【発明を実施するための最良の形態】
【０００８】
図１は、本発明の検索システムの１つの実施の形態を示すブロック図である。本システム１００は検索システムモジュール１１０においてユーザのクエリーおよびドキュメントを入力する。上記検索システムモジュール１１０は、構造化データ１２０、準構造化データ１３０および非構造化データ１４０を記憶し、続いて検索するための実行可能命令を含む。
【０００９】
一般的に、上記検索システムは、情報またはドキュメントのリポジトリ内の指定情報をユーザが見つけることを可能にするように動作する。この実施の形態のために、上記ドキュメントリポジトリは構造化データ、非構造化データおよび準構造化データを含む。ここで使用されているように、「構造化データ」は所定のスキーマ内で組織化されたデータを結合する。例えば、関係データベースまたはオブジェクト指向データベースのフィールドに組織化されたデータは、構造化データと考えられる。関係データベースでは、データはテーブル内に記憶される。各テーブルは各エントリの列内に記憶されたデータの種類を指定する所定の上記列すなわちフィールドまたはデータベーステーブル内の行をもつ。関係データベースは、数値データを操作するアプリケーションをもつ。例えば、上記フィールドは整数値を指定して１週間の曜日（例えば、１−７）を表現可能であり、上記テーブル内の各行は１−７の値を記憶可能である。データベース内に記憶された構造化データは、あるアプリケーション内では、データを組織化して検索する効率的な手段を提供するが、全てのデータが所定のフィールドに配置されねばならないためデータベースは非常に厳格である。
【００１０】
ここで使用されているように「準構造化」データは１以上の識別子をもつデータを結合するが、データの各部は必ずしも所定のフィールドに組織化されていない。準構造化データの例は、ＸＭＬなどのマークアップ言語でタグ付けされたドキュメントを含む。準構造化ドキュメントはフィールドに組み合わされたテキストをもってもよい。しかし、上記フィールドまたは上記タグはテキストの所定の長さを指定しないので、テキストの分量は異なってもよい。本発明の検索システムに記憶される３種目の情報は「非構造化データ」である。ここで使用されているように、「非構造化データ」は所定のフィールドタグを使用して同定されないデータを結合する。例えば、非構造化データはテキストドキュメントを含むことができる。
【００１１】
図２は本発明の検索システムで取り扱い可能な異なる種類のデータの例を示す。構造化データの例１２０はＸＭＬ要素およびそれらの要素に対応する値を含む。上記構造化データ１２０の例は、身長、体重、目の色、郵便番号などの人に関する属性を指定する。準構造化データ１３０は、また、ＸＭＬ要素およびそれに対応するデータを含む。例えば、準構造化データ１３０は要素"item-name"および関連値"3/4 inch bolt"を含む。さらに、準構造化データ１３０はitem-nameの一般的記述を含む。特に、“description”タグの下に、item-name（例えば、3/4 inch bolt）を記述するために、フリーテキストの記述が提供される。図２の非構造化データ１４０を示すデータの例はフリーテキストである。この例に関しては、ＸＭＬタグ用いられない。
【００１２】
１つの実施の形態では、ドキュメント内のデータ構造はＸｐａｔｈを使用する。Ｘｐａｔｈは、ＵＲＩに使用されている表記法と同様な表記法を使用してＸＭＬドキュメント内のデータのアドレスを表現する。このアドレスは「ロケーションパス」とも呼ばれる。各ＸＭＬドキュメントは、要素ノードの階層からなるツリーとして表現可能である。
【００１３】
図３ａは、本発明の検索システムに使用するＸＭＬドキュメントの例を示す。図３ａの例は、ＸＭＬドキュメントの本のカタログのエントリを示す。上記ドキュメントは階層的に配置された複数のタグを含む。例えば、上記ドキュメントの最上階層のタグは“Catalog”である。第２階層のタグは“vendor”のタグと“book”のタグを含む。第３階層のタグは、タグ“title”、“author”、および“publisher”を含み、図３ａの例ではパス/catalog/bookの下で提供される。
【００１４】
ＸＭＬドキュメントの階層タグ構造はツリー構造で配置可能である。図３ｂは図３ａの上記ＸＭＬドキュメントのツリー構造を示す。図３ｂに示されているように、ツリーの上記最上階層ノード、catalog、は上記ドキュメント（図３ａ）内の最上階層タグである。図３ｂのツリー構造の第２階層ノードはノード“vendor”、“book”、“book”および“book”を含む。上記ノード“title”、“author”および“publisher”は上記“book”ノードの下のツリー構造内の第３階層ノードを構成する。
【００１５】
図３ａに示されているように、各タグは組み合わされるフリーテキストをもつ。例えば、第１のvendorタグはフリーテキスト“Barnes and Noble”を含む。またフリーテキスト“The Classical Guitar: Its Evolution”は第１の/catalog/book/titleタグに組み合わされる。それ故、上の例に示されているように、準構造化テキストはフリーテキストおよびそのフリーテキストに組み合わされるタグを含む。
【００１６】
本発明の検索システムはスキーマに依存しない。ここで使用しているスキーマはドキュメントの１以上の構造化フィールドを定義する。上記構造化フィールドは、組み合わされるデータの形式（例えば、整数データまたは所定の文字列）を指定可能であるか、または、形式を指定不可能である（例えば、フリーテキスト）。一般的に、上記検索システムは複数のドキュメント（例えば、ＸＭＬドキュメント）を入力し、ドキュメントを処理して、上記構造化フィールドおよび組み合わされるフリーテキストに関する検索を可能にする。上記ドキュメントは既定のスキーマをもつ必要はない。上記ドキュメントは全て異なるスキームをもってもよい。以下に説明するように、上記検索システムの一意の索引はスキーマに依存しないドキュメントを検索可能にする。
【００１７】
ロケーションパスは上記ツリーを横断して情報の位置に達するのに使用される。例えば、catalog内のbookのtitleに関するロケーションパスは
/catalog/book/title
である。
【００１８】
上記ロケーションパスはルートノードから、明示して名前の付けられたＸＭＬ要素を含む１組のロケーションステップへ下がる。スラッシュにより区切られる１組の要素の名前はロケーションパスの最も簡単な形の１つである。
【００１９】
ロケーションパスは、ノードの最後の既知のロケーションステップまたはコンテクストノードに対する関係に基づいてノードを同定する１以上のロケーションステップからなる。例えば、ロケーションパス内の１組の要素の名前を区切る上記スラッシュは、上記スラッシュの左および右の要素の間に親／子関係が存在することを示す。
【００２０】
上記スラッシュの区切りは、child::name式の省略形であって、childはコンテクストノードの子供を含む軸の名前であって、nameは一致する値をもつ要素を選択するnameテストとして使用される文字列である。子供の軸に加え、ロケーションステップを定義するために使用可能な追加のロケーション軸がある。表１は、ロケーション軸およびロケーション軸が含む項目の１つの実施の形態を説明する。
【表１】
2005525659.tif 000003
【００２１】
１つの実施の形態では、上記検索システムは、ワイルドカードの使用を可能にする。ワイルドカード文字、*、をノードテストに関して使用し、名前の付けられた軸内の全ての項目が選択される。例えば、以下のロケーションパス内のワイルドカードは要素vendorの全ての属性を選択する。
/catalog/vendor/attribute::*
【００２２】
また、以下の関数は、ノードの種類に基づいて、軸の項目の選択を制限するノードテストとして使用可能である。
text()：textノードを選択する。
comment()：commentノードを選択する。
processing-instruction(name)：全てのＸＭＬ処理命令ノードまたは任意のname引数に一致する処理命令ノードを選択する。
node()：全ての種類のノードを選択する。
【００２３】
１つの実施の形態では、上記検索システムは、ノードの選択をさらに絞り込む述語の使用を可能にする。述語は、ユーザに軸内のノードの選択をある位置のノードまたはブーリアン基準を満たすノードに制限することを可能にする。述語は、関数およびフリーテキストクエリー式を含む上記検索システム内の任意の有効な式から構成できる。
【００２４】
１つの実施の形態では上記検索システムは、ロケーションパスの省略された表記法の使用を可能にする。表２は、ロケーションパスを同定するために使用される省略形の１つの実施の形態を説明する。
【表２】
2005525659.tif 000004
【００２５】
図１に示されているように、ユーザはコマンドおよびドキュメントを検索システム１１０に提供する。上記コマンドは、上記検索システムに、ドキュメントの追加および削除と同様にクエリー実行を要求する。ユーザのクエリーコマンドに応じて、上記検索システム１１０はドキュメントのリポジトリ内の情報にアクセスし、ユーザのクエリーに関連する情報を同定する。
【００２６】
図１に示されているように、上記リポジトリは構造化データ１２０、準構造化データ１３０、および非構造化データ１４０を含む。上記検索システム１１０は、上記ドキュメントが構造化データ、準構造化データまたは非構造化データを含んでいるかにかかわらず、ユーザのクエリーを処理して情報を見つける。この厳格でない検索システムは、ユーザに全ての媒体の種類を検索可能にする。例えば、ユーザは、１つのクエリーのみで、構造化ドキュメント内に記憶された数値データおよび準構造化データとして記憶されたＸＭＬドキュメントを検索可能である。それ故、上記検索システムは、データの種類が複数の異なる種類のデータから構成されていても、１つのクエリーを使用して、複数のデータの種類を同定するために使用可能である。
【００２７】
一般的に、フリーテキスト検索は、ユーザに、単語および語句から成るに基づいてドキュメントを同定可能にする。１つの実施の形態では、フリーテキストクエリー式は、必要に応じて、語、引用符に囲まれた語句、および括弧でグループ分けされたブーリアン式から成る。
【００２８】
１つの実施の形態では、検索システム１００は一意のクエリー言語を利用する。一般的に、一意のクエリー言語は構文を指定し、準構造化テキストを検索する。さらに、上記一意のクエリー言語は、返される結果の形式を上記ユーザが指定可能にするとともに、ドキュメントの複数の部分を検索用に指定可能にする。１つの実施の形態では、上記一意のクエリー言語は、Ｗ３ＣのＸＭＬクエリー言語（”ＸＱｕｅｒｙ”）からの要素で質を高められ、完璧なフリーテキストクエリー言語と共に議論されているＷ３Ｃ  ＸＭＬパス言語（”ＸＰａｔｈ”）の実装を含む。上記一意のクエリー言語は、単一構文にこれらのリソースからの特徴を統合する。
【００２９】
１つの実施の形態では、ＸＱｕｅｒｙ言語の複数部分を実装するために、上記検索システムはＸＱｕｅｒｙ  ＦＬＷＲ式および要素コンストラクタの特徴を実装する。上記ＦＬＷＲ式は、複数の値を１以上の変数にまとめて、これらの変数を使用して結果を構築する方法を提供する。上記ＸＱｕｅｒｙ  ＦＬＷＲ式のFOR、WHERE、およびRETURN節はクエリー言語の基本構造を提供する。FOR節は繰り返しループを定義し、１つの変数を、ロケーションパスを含むＸＰａｔｈ式の連続した値にまとめる。WHERE節は、どのFORループの繰り返しがRETURN節の評価として考えられるかを制御するブーリアンフィルタとして働く。RETURN節式はWHEREフィルタを通過する各ループの繰り返しに関して評価される。
【００３０】
上記検索システムがクエリーをドキュメントに適用するとき、２変数を上記ドキュメントに関するメタ情報にまとめる。１つに実施の形態では、本来備えている変数は、
$xbd:docid：評価されているドキュメントの同定番号を含む。
$xdb:uri：評価されているドキュメントのドキュメントＵＲＩを含む。
【００３１】
１つの実施の形態では、上記検索システムは、複数の値で検索すること、および、上記データベース内に存在する任意のドキュメントタグの複数の値を検索することを可能にする。上記ドキュメントタグは、以下の構文（：$xdbtag:タグ名）を使用した変数として参照される。以下のクエリーは、英語でcatalogのvendorに関するドキュメントタグを使用する。
FOR $c IN /catalog
WHERE $xdbtag:XdbLanguage="31"
RETURN $c/vendor
【００３２】
１つの実施の形態では、上記検索システムのための上記クエリー言語は追加のPRESORT節を上記ＸＱｕｅｒｙ  ＦＬＷＲ式に加えて、クエリー結果の分類順序を指定する。ASCENDINGおよびDESCENDINGの両方の分類順序は、１つのPRESORT式でサポートされ、組み合わせ可能である。
【００３３】
上記要素コンストラクタは、上記検索システムのユーザにクエリー結果の出力形式を制御させることを可能にする。上記要素コンストラクタ式は１以上の要素指定子、属性指定子および式から成る。上記要素指定子は上記要素コンストラクタ式を区切る。上記属性指定子は括弧で囲まれた文字列または式のどちらから成っていてもよい。要素コンストラクタ内の評価のための上記クエリー式は括弧で囲まれている。
【００３４】
１つの実施の形態では、上記検索システム１００は２つのモードで動作する。構造化クエリーモードおよびフリーテキストクエリーモードである。上記構造化クエリーモードは、フリーテキストクエリー式を含み、一意のクエリー言語の構文および機能性を使用するクエリーを送るために使用される。上記フリーテキストクエリーモードは、ユーザにフリーテキストクエリー式のみを送ること可能にする。１つの実施の形態では、上記ユーザは、”クエリー”コマンドを使用してサーバにクエリーを送り、続いて、クエリー文字列を含むデータブロックを送る。上記クエリーコマンド用の構文の１つの実施の形態は以下のようである。
2005525659.tif 000005
表３：クエリーコマンドのパラメータと説明のリスト
【表３】
2005525659.tif 000006
【００３５】
１つの実施の形態では、送るデータブロックの文字列は以下のように表現される。
<xdbdata length="numBytes">クエリー文字列</xdbdata>
【００３６】
ここで、lengthパラメータは上記クエリー文字列内のバイト数を指定し、上記クエリー文字列はクエリーテキストを含む。成功したコマンドは上記クエリーの結果を返す。上記結果はＸＤＢデータブロックで返される。
【００３７】
１つの実施の形態では、上記一意のクエリー言語は、”+”および”-”演算子を使用してフリーテキストクエリー式の構築をサポートする。もしこれらの式が真に設定されたフリーテキストクエリーコマンドパラメータに含まれていると、上記検索システムはＵＲＩ、ドキュメントＩＤ、および、いくつかの実施の形態では、上記リポジトリ内の一致する各ドキュメントのスコアを返す。例えば、フリーテキストクエリーモードでは、以下の式は、単語”vacuum”を含み、単語”cleaner”を含まないドキュメントのスコア計算されたＵＲＩを返す。
+vacuum-cleaner.
【００３８】
別の実施の形態では、フリーテキストクエリーは”free-text-query ()  関数”を使用して構造化クエリーの中に組み込み可能である。１つの実施の形態では、フリーテキストクエリーを構造化クエリー言語の特徴と組み合わせるために、上記検索システムは上記free-text-query ()  関数を提供する。１つの実施の形態では、上記free-text-query ()  関数は、以下のように、構造化フィールドの識別表示（すなわち、構造化フィールドコンストラクト）およびフリーテキストの識別表示（すなわち、フリーテキストコンストラクト）をパラメータとして含む。
Free-text-query(構造化フィールドコンストラクト,フリーテキストコンストラクト).
【００３９】
１つの実施の形態では、上記構造化フィールドの同定表示はＸＰａｔｈ言語にしたがって実行される。この実施の形態では、上記構造化フィールドコンストラクトは、上記リポジトリ内のドキュメントのノード集合を同定する。
【００４０】
free-text-query ()  関数はドキュメントの部分にも適用可能である。例えば、以下の式は“title”要素内に語句“Glean Fleeber”を含むドキュメントを選択し、各一致ドキュメントのＵＲＩおよびスコアを返す。
FOR $score IN free-text-query(//title,"Glean Fleeber")
RETURN<result uri={$xdb:uri}>｛$score</result>
【００４１】
上記クエリーは以下の結果を返すことができる。
<xdbdata length = "50"><result uri="http://www.glean-fleeber.com/ docs/users-guide.xml">10.693147</result>
</xdbdata>
【００４２】
以下のクエリーはWHERE節内のfree-text-query()関数を使用して検索基準を指定する。
FOR $b IN /catalog/book
WHERE free-text-query($b/description,"+history +classical")
RETURN $b
【００４３】
１つの実施の形態では、上記ユーザはクエリーコマンド“true”のパラメータを設定し、送るデータブロック内のクエリー文字列としてフリークエリー式を直接送る。例えば、以下の式は送るデータブロック内で送られる。
<xdbdata length = "23">+satellite-television</xdbdata>
【００４４】
以下のブーリアン演算子、“OR”、“AND”、“AND NOT”、“AND HAS”、“+”、および“-”、はフリーテキストクエリー検索式内で使用可能である。例えば、以下のフリーテキストクエリー式は、語句”regenerative braking”および語句”hybrid vehicle”または語句”HEV”のいずれかまたは両方を含むドキュメントを選択する。
(("hybrid vehicle" OR HEV)AND"regenerative braking))
【００４５】
本システムは、”+”および”-”のブーリアン演算子を使用してユーザがクエリーを簡単にすることを可能にする。例えば、以下のフリーテキストクエリー式は、単語”satellite”を含み、単語”television”を含まないドキュメントを選択する。
+satellite-television
【００４６】
１つの実施の形態では、上記一意のクエリー言語は、式の操作のために標準的な算術演算子およびブーリアン演算子をサポートする。本発明の検索システムは、特にノード集合のコンテンツの検索の実行に使用するために設計された関係演算子の追加の集合を用いるフリーテキストクエリー構文を含む。以下の算術演算子は上記一意のクエリー言語に含まれる。
【表４】
2005525659.tif 000007
【００４７】
算術演算子のオペランドは数字として解釈される。１つの実施の形態では、上記一意のクエリー言語はブーリアン演算子、“OR”、“AND”、“=,!=”、“<=,<,>=,>”を含む。括弧を使用した明示のグループ分けがないと、これらのブーリアン演算子は左側に結合する。ノード集合が文字列または数値と比較されるとき、もし上記ノード集合の任意の１要素の値に関しての比較が真であるならば、その式は真である。
【００４８】
上記検索システムは１つのクエリーを１つのドキュメントに適用するか上記クエリーをドキュメントの完成した集合に適用するかの選択を提供する。１つのクエリーを１つのドキュメントに適用するために、上記クエリーは、document()関数を使用したＦＬＷＲ式のアドレスのような、FOR節内の対象ドキュメントのアドレスを指定する。上記document()関数は、対象ドキュメントのＵＲＩを文字列パラメータとして取得し、上記アドレスにおけるドキュメントのルートノードを返す。例えば、以下のクエリーはJason Waldronによる特定のドキュメントの題名（title）を検索する。
FOR $B IN document(http://www.bn.com/book_catalog.xml)//book
WHERE $b/author="Jason Waldron"
RETURN $b/title
【００４９】
このクエリーは、ＵＲＩが“http://www.bn.com/book_catalog.xml”のドキュメントの中の全てのbook要素にわたって繰り返す。
【００５０】
対象ドキュメントを明示して指定しないと、上記クエリーは、自動的に、上記リポジトリ内の全てのドキュメントを対象とするクエリーに拡大される。例えば、以下のクエリーはdocument()関数を明示しては含まない。
FOR $b IN //book
RETURN $b//title
【００５１】
しかし、上記クエリーは自動的に上記クエリーを以下の式へ拡大する。
FOR $doc IN document("*"),$b IN $doc//book
RETURN $b/title
【００５２】
本検索エンジンはこのクエリーを、ネストされたループとして実行する。外側のループは全ドキュメントにわたって繰り返す。外側のループ内の各ドキュメントに関し、内側のループは各book要素にわたって繰り返す。
【００５３】
１つの実施の形態では、上記一意のクエリー言語は語幹のサポートを提供する。この実施の形態では、上記ユーザはある単語の任意の「語幹」を含む全てのドキュメントを検索可能である。例えば単語”run”は以下の派生語、running、ran、runsをもつ。１つの実施の形態では、語幹を指定するために、上記クエリー語は上記語幹の接頭辞の前に配置される。例えば、語“play”の語幹の検索を指定するために、ユーザは以下のクエリーを送る。
stem:play
【００５４】
指定された語幹を備えたクエリー項に応じて、上記検索システムは、異なる時制を含むその単語の全ての文法的に正しい派生語を同定する。”play”の例では、“playing”、“played”、および“plays”を含む単語“play”の語幹の変化形を含む全てのドキュメントを検索する。１つの実施の形態では、上記パーサは、単語の索引内の全ての語幹の変化形の選択のために、上記入力クエリーを語幹の全ての変化形に変換する。上記ユーザは過去形を避けてドキュメントを同定可能である。上の例では、過去形を避けるために上記ユーザは以下のように指定可能である。“stem:play-played”
【００５５】
図４は、本発明の検索システムの１つの実施の形態を示すブロック図である。検索システム３００は、入力として、上記検索システムの情報源であるドキュメントを入力する。以下により十分に説明するように、上記ドキュメントは、索引付けコンポーネント３３０内で索引付けされ、リポジトリコンポーネント３５０内に記憶される。検索システム３００のユーザは、上記ドキュメント（すなわち、索引付けされ、リポジトリコンポーネント内に記憶されたドキュメント）に関する情報を同定し検索するためのクエリーを送る。
【００５６】
図４に示されているように、通信コンポーネント３１０はコマンドおよびドキュメントを入力する。１つの実施の形態では、上記通信コンポーネント３１０はＨＴＴＰコマンドおよびドキュメントだけでなくＸＭＬコマンドおよびドキュメントを入力する。上記通信コンポーネント３１０はＸＭＬコマンドならびにドキュメントおよびＨＴＴＰコマンドならびにドキュメントを処理するために必要な必須のプロトコルをサポートする。上記通信コンポーネント３１０は上記コマンドおよびドキュメントをコマンドコンポーネント３２０に渡す。もし上記コマンドがクエリーならば、上記コマンドコンポーネント３２０は上記コマンドをクエリーコンポーネント３４０に渡す。
【００５７】
上記クエリーコンポーネント３４０は上記索引付けコンポーネント３３０から索引のリストを得て、これらの索引に対してクエリーを実行する。上記クエリーコンポーネント３４０は、必要に応じて、上記クエリーコマンドに応じて、リポジトリコンポーネント３５０からのドキュメント情報にアクセスする。もし検索システム３００への入力がドキュメントならば、上記コマンドコンポーネント３２０は上記ドキュメントを上記索引付けコンポーネント３３０に渡す。一般的に、上記索引付けコンポーネント３３０は、索引付けマネージャ３３２および索引パイプライン３３６を使用してドキュメントを索引付けして、索引３３４を生成する。加えて、上記ドキュメントは記憶のための上記リポジトリコンポーネント３５０に入力される。
【００５８】
１つの実施の形態では、上記検索システム３００は関連性順位付けコンポーネント（図示されていない）を含む。一般的に、上記関連性順位付けコンポーネントは、ユーザに、検索で同定された非構造化、準構造化および構造化テキストドキュメントを関連性順位付け可能にする。非構造化、準構造化および構造化テキストドキュメントの関連性順位付けの完全な説明は特許文献１に記載されていて、参照によりここに明示して組み込まれている。
【００５９】
１つの実施の形態では、本発明の検索システムは、上記システムの中にドキュメントを入力し、上記システム内のドキュメントを削除するだけでなくクエリーの処理も可能にする。従来の検索システムでは、全てのドキュメントは、クエリーを処理する前に、入力され、索引付けされねばならない。これらのシステムでは、上記リポジトリにドキュメントを追加し、上記リポジトリからドキュメントを削除するために、上記ドキュメントの全体の集合は再度索引付けされねばならない。本発明の検索システムは、ユーザが上記システム内のドキュメントを追加、削除および変更するだけでなくクエリーを実行可能である点で「動的」である。以下にさらに十分に説明するように、上記検索システムは複数の索引を使用して動的検索システムをサポートする。上記複数の索引は、クエリーを実行するためだけでなく、上記検索システムへ新しいドキュメントを入力するためにも使用される。
【００６０】
上記検索システムは上記検索システムへ入力された新しいドキュメントを処理する。図５は上記検索システムへの入力ドキュメントを処理する１つの実施の形態を示すフローチャートである。上記システムは新しいドキュメントを入力する（図５、ブロック１２１０）。各ドキュメントはドキュメント同定番号”document ID”を割り当てられる（図５、ブロック１２２０）。上記新ドキュメントは分析されてツリーを生成する（図５、ブロック１２３０）。一般的に、ＸＭＬ形式の上記入力ドキュメントは階層的ツリー構造に変換される。１つの実施の形態では、上記検索システムはドキュメントオブジェクトモデル（”ＤＯＭ”）パーサを利用する。上記分析処理は上記新しいドキュメント内で単語の分割を決定する機能を含む。以下に十分に説明するように、上記索引はドキュメント内の複数の単語に関する位置情報を記憶する。１つの実施の形態では、上記検索システムは、特にいくつかの非英語言語（例えば、漢字）用に単語の境を決定する特別なソフトウェアを利用する。
【００６１】
上記システムへ入力された各新ドキュメントに関して、上記処理は索引ドキュメントを作成する。一般的に、上記索引ドキュメントを作成するために、上記検索システムは上記ツリー（すなわち、ＤＯＭパーサにより生成されたツリー）の複数のノードを横断する。上記ツリーの各ノードに関し、上記検索システムは上記各ノードの単語を単語索引へ入力する。これから、上記検索システムは単語リスト、ドキュメントリストおよび位置ベクトルを構築する。上記索引ドキュメントを作成するために、上記新しいドキュメントからの各単語が入力される。この処理は、整数変数”n”の0への初期化を通して図５に示されている。上記変数nは処理中の現在の単語を同定するポインタを示す。もし上記現在の単語（word[n]）が上記索引ドキュメント内に存在しないとすると、上記処理は上記単語に関するエントリを作成する（図５、ブロック１２５０および１２６０）。１度単語エントリが上記現在の単語に関して作成されると、上記処理は、上記単語エントリに関する情報内に場所を占める（図５、ブロック１２７０）。その代わりに、もし上記単語が既に上記索引ドキュメント内に存在すると、上記処理は上記現在の単語word[n]関する情報内に場所を占める（図５、ブロック１２５０および１２７０）。１つの実施の形態では、上記索引ドキュメントは各単語エントリに関してドキュメントリストを含み、上記ドキュメントリスト内の各ドキュメントに関する位置ベクトルを含む。上記単語リスト、上記ドキュメントリストおよび上記位置ベクトルの内容は以下にさらに十分に説明する。
【００６２】
上記現在の単語はインクリメントされ（図５、ブロック１２８０）、もし現在の単語が上記ドキュメント内の最後の単語でなければ、上記ドキュメント内のその次の単語が上記索引ドキュメントに入力される（図５、ブロック１２９０、１２５０、１２６０、１２７０、および１２８０）。索引ドキュメントを生成する上記処理は、上記ドキュメント内の最後の単語が上記索引ドキュメントに入力された後に完了する（図５、ブロック１２９０）。
【００６３】
１つの実施の形態では、新しいドキュメントを生成する上記処理は上記索引パイプライン３３６内で実行される（図４）。上記索引パイプライン３３６は１以上の索引ドキュメントを索引マネージャ３３２に渡す。上記索引マネージャ３３２は上記索引ドキュメントを挿入可能な索引のプールへ統合する処理を実行する（図６参照）。
【００６４】
１つの実施の形態では、上記検索システムへ入力されるドキュメントの処理は、追加の機能を含む。もし上記単語エントリがＸＭＬタグで、組み合わされた値が数字ならば、上記処理は、上記位置ベクトルで、記憶のために、上記ドキュメント内で数字表現を浮動小数点表現へ変換する（図１０、エントリ８００）。また、上記処理は、索引ドキュメントの中に含めるために、上記ツリー構造内で同定されたＸＭＬ属性を指定する。
【００６５】
１つの実施の形態では、上記検索システムは、複数の永続的索引および複数のインクリメントする索引を使用する。ここで使用されているように、複数の「永続的索引」は、上記システムが永続的記憶媒体（例えば、ハードディスクドライブ）上に記憶する索引である。上記検索システムは、複数のインクリメントする索引をコンピュータ（例えば、サーバ）のランダムアクセスメモリ（“ＲＡＭ”）内に記憶する。上記索引マネージャ３３２（図４）は１以上の索引を組み合わせる統合処理を実行する。
【００６６】
１つの実施の形態では、上記索引付けコンポーネント３３０（図４）は、挿入可能な索引のプールを使用してドキュメントを上記システムに入力する。図６は、上記検索システムに索引ドキュメントを挿入する１つの実施の形態を示すブロック図である。一般的に、上記索引マネージャ３３２は入力ドキュメントに関する挿入可能な索引のプール４１５を管理する。特に、索引マネージャ３３２は、挿入可能な索引のプール４１５から挿入可能な索引を選択して１つのドキュメントを索引付けする。１度に１つのドキュメントのみが挿入可能な索引に挿入される。上記挿入可能な索引は所定の最大サイズをもつ。挿入可能な索引が最大サイズに達したとき、挿入可能な索引のプール内にはもはや挿入不可能である。１つの実施の形態では、ドキュメント索引の数は索引のサイズを計測する。図６に示されているように、索引マネージャ３３２は、上記検索システムに挿入された各ドキュメント各々に関し、挿入可能な索引を選択する。この例では、索引マネージャ３３２は、ドキュメント４０２に関する挿入可能な索引４２０、ドキュメント４０５に関する挿入可能な索引４２５、およびドキュメント４１０に関する挿入可能な索引４３０を選択する。
【００６７】
１つの実施の形態では、上記索引マネージャは、挿入可能な索引の閾値が最大になったとき、統合処理を実行する。図７は統合処理の１つの実施の形態を示すブロック図である。統合処理において、統合５００は複数のインクリメントする索引を組み合わせて１以上の永続的索引を作成する。図７の例では複数のインクリメントする索引５１０は１以上の永続的索引（５２０および５３０）と組み合わされ、１以上の永続的索引（５４０および５５０）を生成する。１つの実施の形態では、上記検索システムは永続的索引のサイズに制限を設ける、それ故統合処理は１以上の永続的索引を生成可能である。また、大きな索引を小さな索引と統合することは非効率である。このシナリオのもとで、上記統合は、もし必要ならば、複数の永続的索引を生成することにより上記処理の効率性を最大限に高めることができる。別の実施の形態では、上記索引マネージャは索引の全数に制限を設ける。もし最大数が超過すると、統合作業が開始される。
【００６８】
図８は、上記検索システム内の索引を組み合わせる統合処理の１つの実施の形態を示すフローチャートである。１つの実施の形態では、上記索引マネージャ３３２は、所定の長さの時間（例えば、前の統合作業の完了後１５秒ごとに）経過後、上記統合処理を実行する。もし所定の長さの時間が経過すると、上記統合処理はインクリメントする索引および永続的索引の候補を選択する（ブロック６００および６１０）。索引の候補を選択して統合するとき、上記統合はすべての永続的索引および最大サイズに達したインクリメントする索引を考慮する。上記索引の候補はブロック６２０に示されているように小さいサイズから始まって大きいサイズに至るまで順位付けされる（例えば、Index0が最上位で、Indexxが最下位になるようにIndex0からIndexxまで順位付けする）。この順序を使用し、生成された新しい索引のサイズが最大サイズを超えるまで、上記統合が索引を選択する。この処理はindex[n]へのポインタを0に初期化することにより（ブロック６２５）図８に示されている。Index0は永続的索引に統合される（ブロック６３０）。上記統合処理は、次に、上記新しい統合された索引が可能な最大サイズを超えるか否かを決定する（ブロック６４０）。もし超えなければ、上記処理は次の索引の候補を選択し、統合する追加の索引の候補があるか否かを決定する（ブロック６５０および６６０）。もし統合する索引の候補がまだあれば、上記処理はステップ６３０、６４０、６５０、および６６０を繰り返す。代わりに、もし索引の最後の候補が統合されるか、または、もし統合された索引が最大サイズを超えると、上記処理は作業６００に戻り、別の統合処理を実行する前の所定の長さの時間待つ。
【００６９】
上記検索システムは、クエリー実行の間、考慮すべきドキュメントの動的削除をサポートする。１つの実施の形態では、各索引（インクリメントする索引および永続的索引）は「削除された”document ID”リスト」をもつ。上記システムからドキュメントを削除するために、削除するドキュメントを同定するコマンドを送る。それに応じて、上記システムは、対応するドキュメントに関する索引を同定する。特に、上記システムは、上記ドキュメントをdocument IDから、同定する索引に関してドキュメントリストを検索する。１度上記ドキュメントに関する上記索引が見つけられると、上記システムは、削除されたdocument IDリストに、上記Document IDを入力する。上記システムがクエリーを処理したとき、上記システムは、上記削除されたdocument IDリスト上にリストされたドキュメントを無視する。
【００７０】
一般的に、上記索引マネージャは２つの状態、削除可能状態または挿入可能状態で動作する。１つの実施の形態では、上記索引マネージャは、削除動作がクエリー実行中に発生するのを防ぐ。このように、ドキュメントはクエリー実行中には削除されない。これは中間結果をクエリー実行から保護する。以下にさらに十分に示すように、上記索引マネージャは、索引リストをクエリー実行に渡すので、クエリーが実行されているという知識をもつ。上記クエリー実行が完了すると、上記クエリーコンポーネント（３４０）は上記索引付けコンポーネントへ索引リストを返す。
【００７１】
上記システムは、統合作業の間に、成功する削除作業も実行する。統合作業の間にドキュメントを削除するために、上記統合が完了した後で、上記統合は、統合された上記索引からの削除されたdocument IDリストを横断し、上記統合された索引の上記削除されたdocument IDリスト上のdocument IDを上記新しい統合された集合内のドキュメントと比較し、上記新しい統合されたドキュメント集合内で同定された上記ドキュメントの上記削除されたdocument IDを上記新しい統合された索引に関する上記document IDリストに加える。それに続く統合の間、上記統合は、もし上記削除されたdocument IDリスト上の任意のドキュメントがもう上記新しい統合された索引内で同定されなければ、上記削除されたdocument IDリスト上の任意のドキュメントをリストから省く。それ故、上記削除されたdocument IDリスト上の上記ドキュメントは、その次の統合作業の間にガーベージコレクトされる。
【００７２】
一般的に、上記索引３３４（図４）は、ドキュメント、ドキュメント内の単語、ドキュメント内の単語の位置および追加情報を同定し、上記ドキュメントの指定区分内でフリーテキストクエリー検索を実行する。図９は本検索システムの索引の１つの実施の形態を示すブロック図である。この実施の形態では、１つの索引は、単語リスト、各単語リストに関して１つの、複数のドキュメントリスト、および上記ドキュメントリスト内の各エントリに関して１つの、複数の位置ベクトルを含む。例えば、もし５つのドキュメントが索引７００により表されているとすると、単語リスト７０５は５つのドキュメント全ての中の全ての単語を同定する。１つの実施の形態では、上記単語リストは、対応する１単語に関し、「メタ単語」から導出される値をもつ。特に、ＭＤ５ハッシュが上記メタ単語上で実行される。上記メタ単語は、上記単語、要素の名前などを使用して形成される。１つの実施の形態では、上記メタ単語は以下の一般形式をもつ。
<type>:<case>:<word>
<type>に関する可能な値は表５で説明されている。
【表５】
2005525659.tif 000008
<case>に関する可能な値は表６で説明されている。
【表６】
2005525659.tif 000009
【００７３】
上記<word>部分は単語自体である。以下はＸＭＬの断片の例である。
<message type=foo>
Hello, world!
<message>
【００７４】
この例では、メタ単語の以下の集合は作成されて上記単語リストに挿入される。
elem:lower:message,        attr:lower:type,  word:exact:Hello,            およびword:lower:world
【００７５】
１つの実施の形態では、索引の上記単語リストは上記単語に関する追加の情報を記憶する。一般的に、上記追加の情報は、上記検索システムにフリーテキストを構造化フィールド（例えば、ＸＰａｔｈノード）と組み合わせ可能にする。図９に示されているように、上記単語に関する種類が記憶される。例えば、もし上記ドキュメントから抽出された単語がテキストならば、上記単語リスト内の対応するエントリが”Word”を同定する（例えば、”satellite”および”Satellite”の両方がドキュメントから抽出される単語である）。これは上記検索システムに構造化フィールド指定子とフリーテキストとを区別することを可能にする。上記単語リストはＸＭＬドキュメントからの要素および属性の同定もする。図９の例ではWord4に記憶された値はＸＭＬスキーマ内で定義された要素を表し、Word5に記憶された値はＸＭＬスキーマ内で定義された属性を表す。１つの実施の形態では、索引の上記単語リスト内に記憶されたデータは、上記単語が小文字で表されているか否か、または上記単語が正確に上記ドキュメント内で現れるように表されているか否かも同定する。例えば、上記単語”Satellite”は上記ドキュメント内では大文字で現れるかもしれない。それ故、単語索引はWord2として、大文字の単語”Satellite”の正確な表現を記憶する。この方法で、上記索引は大文字小文字区別検索だけでなく大文字小文字非区別検索もサポートする。
【００７６】
単語リスト内の各エントリは対応するドキュメントリストをもつ。上記ドキュメントリストは上記対応する単語が現れる全てのドキュメントを同定する。図９の索引７００の例では、word(0)はドキュメントリスト７１０をもつ。上記ドキュメントリスト７１０は、word(0)が現れる各ドキュメント（例えば、ドキュメント２３、４５、４７、５４、５７、６５、７２、８５および９０）をそのDocument IDにより同定する。
【００７７】
ドキュメントリスト内で同定される各ドキュメントは、対応する位置ベクトルをもつ。図９の索引７００の例では、ドキュメントリスト７１０のドキュメント２３は位置ベクトル７２０をもち、ドキュメント８５は位置ベクトル７３０をもつ。一般的に、位置ベクトルは、上記対応する単語が上記対応するドキュメント内に現れる全ての位置を同定する。例えば、word0はドキュメント２３内の位置１１、２１、３３、および９９に現れる。またword0はドキュメント８５内の位置６６、７７、８２、および９８に現れる。上記位置ベクトルは、上記検索システムにドキュメント内で単語間の位置距離を指定するクエリー実行を可能にする。例えば、クエリーはword3の５単語位置にword0を含むドキュメントの同定を要求可能である。この例では、上記検索システムは各単語エントリからの上記位置ベクトルを利用し、word5の５単語以内にword0が現れるか否かを決定する。
【００７８】
１つの実施の形態では、上記位置ベクトルはドキュメント内での上記単語の位置を加えて情報を含む。図１０は１つの位置ベクトルを含む情報の１つの実施の形態を示すブロック図である。位置ベクトルは、対応するドキュメントに含まれる１つの単語に関する情報を記憶する。上記位置ベクトル８００は、上記ドキュメントでの上記単語の開始位置（８１０）、上記ドキュメントでの上記単語の終了位置（８２０）、コンテンツに対するオフセット（８３０）、ＸＭＬスキーマ内の単語の深さレベル（８４０）、もしあれば上記単語に組み合わされる値（８５０）および要素単語計数値（８６０）を同定するデータを含む。
【００７９】
コンテンツに対するオフセット（図１０，８３０）を同定する情報は上記クエリーシステムにフリーテキストの開始から構造化フィールドまでの同定を可能にさせる。例えば、ドキュメントスキーマはフリーテキスト“Jim Smith”とともに“name”構造化フィールドを指定できる。この例では上記コンテンツに対するオフセット（図１０，８３０）を同定する情報は、上記“name”構造化フィールドに関する“Jim”の単語開始位置を同定する。もし上記検索システムが上記構造化フィールド“name”内の“Jim Smith”を同定するクエリー（例えば、フリーテキストクエリー関数）を入力すると、上記検索システムは、単に上記索引から、上記フリーテキスト“Jim Smith”が“name”フィールドと組み合わされているか否かを決定する。特に、この例では、上記検索システムは、上記コンテンツに対するオフセット（図１０，８３０）を同定する情報から、上記単語“Jim”が“name”フィールドと組み合わされたフリーテキストの始まりであると決定する。また、上記位置ベクトルから、上記検索システムは上記単語“Smith”が上記単語“Jim”と隣接していると決定する。したがって、上記コンテンツに対するオフセット（図１０，８３０）を同定する情報は、上記索引を使用し、構造化フィールドに組み合わされたフリーテキストに関して検索を実行するために使用可能である。
【００８０】
ＸＭＬスキーマ内の上記単語の深さレベル（図１０、８４０）を同定する情報は上記クエリーシステムでドキュメントスキーマ内の構造化フィールドまたはノードを同定することを可能にする。例えば、ドキュメントの上記構造化フィールドは複数のノードの階層で組織化される。ＸＭＬスキーマ内の上記単語の深さレベル（図１０、８４０）を同定する情報は、上記システムに、クエリー内で指定されたＸＭＬスキーマのノード集合の同定を可能にする。例えば、ドキュメントは、図３ａおよび図３ｂに示されているように、ＸＭＬスキーマを含んでもよい。この例では、上記catalogノードはレベル１として指定され、vendorおよび３つのbookノードはレベル２として指定される。ユーザはパス“/catalog/book”で全てのノードを同定するクエリーを指定可能である。このクエリーとスキーマの例では、上記検索システムは、上記索引から、レベル１ノード“catalog”の下のレベル２ノードとして同定される３つのbookは上記検索基準を満たすことを決定する。結果的に、ＸＭＬスキーマ内の上記単語の深さレベル（図１０、８４０）を同定する情報は、上記検索システムに、ノードの階層からの上記索引からノード集合を同定することを可能にする。
【００８１】
上記単語に組み合わされた値（図１０、８５０）は上記システムが範囲指定クエリーを実行することを可能にする。例えば、ＸＭＬスキーマ内の属性または要素は、組み合わされる値をもつことができる（例えば、book ID = 49）。この値は位置ベクトル内に記憶される（図１０、８５０）。このように、上記検索システムは、クエリー実行のために上記リポジトリ内のドキュメントにアクセスし、上記単語に組み合わされた対応値を抽出する必要はない。１つの実施の形態では、上記検索システムは浮動小数点値を上記索引内に記憶する。例えば、構造化フィールド“/age”は”29”などの値を含んでもよい。このスキーマの例では、ユーザは２５から３５の値をもつageフィールドを含む全てのドキュメントを要求するクエリーを送ることが可能である。上記索引が“age”構造化フィールドに関する実際の値を記憶するので、上記検索システムは、直接、上記索引から範囲指定クエリーを実行可能である。
【００８２】
１つの実施の形態では、上記位置ベクトル８００は要素単語計数値（図１０、８６０）を含む。上記要素単語計数値は、組み合わされた要素に関する実単語計数値（すなわち、実単語計数値はマークアップ単語を含まない）を指定する。例えば、ドキュメントは図３ａおよび図３ｂに示されているようなＸＭＬスキーマを含んでいてもよい。ＸＭＬスキーマの一部は以下のようである。
<book>
<title>The Jazz Guitar</title>
<author>Maurice J. Summerfield</author>
<publisher>Hal Leonard Pub.</publisher>
</book>
【００８３】
この例では、開始位置から終了位置までのマークアップ単語を含む全体の計数値は１４に等しいが、エントリ“elem:lower:book”に関する単語計数値は１１に等しい。
【００８４】
１つの実施の形態では、上記検索システムは索引構造内に「イテレータ（反復子）」を記憶する。一般的に、イテレータは、インクリメントする索引および永続的索引の両方について索引構造内の位置を同定する。イテレータの実際の値は索引の種類（すなわち、永続的索引またはインクリメントする索引）に基づく。上記単語リスト内の各単語に関し、単語リストのイテレータはドキュメントリストイテレータを同定する。順に、ドキュメントリストイテレータは位置ベクトルへの参照を提供する。
【００８５】
１つの実施の形態では、インクリメントする索引のイテレータはＳＴＬマップへの参照である。上記ＭＤ５値は上記ＳＴＬマップの下付き文字である。上記ＳＴＬマップはＳＴＬベクトルを含む構造を返す。永続的索引に関しては、上記イテレータは、対応する単語、ドキュメントリスト、または位置ベクトルに関する永続的記憶装置でのファイルの位置に対するオフセットを提供する。
【００８６】
本発明の検索システムは、適切に終了されなかったセッション（例えば、コンピュータクラッシュ）から回復するための処理を実行する。一般的に、ドキュメントが、上記検索システムの入力のために通信モジュールにおいて入力されるとき、上記ドキュメントは、上記索引付けシステム用の索引ドキュメントおよび上記リポジトリ用のコンパイルされたドキュメントにコンパイルされる。１つの実施の形態では、上記検索システムは、複数のコンパイルされたドキュメントを一度に永続的記憶媒体に挿入する。これはハードディスクドライブをアクセスするときの効率性を増す。上記検索システムは、書き込み動作が上記ハードディスクドライブ内で発生したとき、ユーザのコマンドに応答してドキュメントを上記システムに入力する。それ故、上記システムは、コンパイルされた上記ドキュメントが上記リポジトリ内に保存されたとき、ドキュメントのエントリを確認するのみである。
【００８７】
もし上記コンピュータが、上記ユーザが上記ドキュメントが上記システムに入力されたことの確認を入力した後で、任意の時間にクラッシュしたら、上記コンパイルされたドキュメントは既に安全に上記永続的記憶媒体内に記憶されている。しかし、上記対応するドキュメントの上記索引が、インクリメントする索引（すなわち、ＲＡＭ内に）に記憶されているかもしれない。このシナリオでは、もし上記コンピュータがクラッシュしたら、上記インクリメントする索引は失われる。
【００８８】
上記リポジトリ内に記憶されたドキュメントの索引を回復するために、上記検索システムは立ち上げ時に回復処理を実行する。第１に上記検索システム（索引マネージャ）は上記リポジトリからdocument IDのリストを得る。次に、上記索引マネージャは全ての永続的索引を分析して全てのdocument IDを得る。もし上記ドキュメントがリポジトリdocument IDリストおよび永続的索引document IDリストの両方で同定されると、上記ドキュメントは上記検索システム内で安全に同定される。代わりに、もし上記ドキュメントが上記リポジトリ内で同定されるが、永続的索引内では同定されないと、恐らく上記システムは、インクリメントする索引が永続的索引に統合される前に、クラッシュした。このシナリオでは、上記索引マネージャは上記リポジトリコンポーネントからの上記ドキュメントをフェッチし、上記ドキュメントを索引付けする。もしドキュメントが索引内で同定され、上記リポジトリ内で同定されないと、上記検索システムは上記索引から上記ドキュメントを削除する（すなわち、上記システムは上記リポジトリに同期する）。
【００８９】
図１１は上記システムでクエリーを処理する１つの実施の形態を示すフローチャートである。上記処理を開始するために、クライアントはサーバ（検索システムを運用するサーバ）に接続し、上記サーバへクエリーコマンドを送る（ブロック９００）。通信コンポーネントにおける上記クエリーコマンドに応じて、上記通信コンポーネントはクエリー実行コンポーネント（ブロック９１０）を呼び出す。上記クエリー実行コンポーネントは、上記索引マネージャから全有効索引のリストを得て、上記クエリーを実行する（ブロック９２０）。次に、上記クエリーコマンドは分析ツリーへコンパイルされる（ブロック９３０）。１つの実施の形態では、上記検索システムはＸＱｕｅｒｙ分析ノードの以下の種類（すなわち、算術PLUS、算術MINUS、算術DIVIDE、算術MULTIPLY、算術MODULO、ネゲート、ブーリアンOR、ブーリアンAND、数値定数、文字列定数、ブーリアン定数、からノード集合定数、要素コンストラクタ、等号EQUAL、不等号NOT EQUAL、関数、ロケーションパス、関係LESS THAN、関係LESS THAN OR EQUAL、関係GREATER THAN、関係GREATER THAN EQUAL、追加のUNION設定、タグ、および変数）を利用する。上記検索システムはフリーテキスト分析ノードの以下の種類（すなわち、選択および語句または単語）を利用する。
【００９０】
１つの実施の形態では、上記クエリーのパーサは、ＬＥＸやＹＡＣＣなどのよく知られたツールを使用して開発される。ＬＥＸツールは所定のトークンを同定するパーサを開発するために使用される。それ故、上記パーサは上記システムへ入力される文字列クエリーを分析し、所定のトークンを同定する。ＹＡＣＣツールは上記パーサの文法規則を指定するために使用される。例えば、上記ＹＡＣＣツールは、クエリーを指定するために使用されるＦＬＷＲ式の分析を指定するために使用される。
【００９１】
１つの実施の形態では、上記クエリーコマンドはＸＭＬドキュメントである。上記クエリー自体はＸＭＬドキュメント内でテキストに囲まれている。分析ツリーは最適化される。クエリー実行コンポーネントは、コンパイルされた分析ツリーを横断することにより上記クエリーを実行する。特に、上記クエリー実行モジュールは上記分析ツリーにより同定される索引のイテレータを得る（ブロック９４０）。上記イテレータは、上記索引から相対的情報（すなわち、クエリーコマンドに対する関連性情報）を抽出するために使用される。この情報に基づいて、上記クエリー実行コマンドは上記クエリーコマンドで指定された論理を実行する（ブロック９６０）。これから、上記クエリー実行コンポーネントは応答を構築する（ブロック９７０）。上記応答は、単に上記索引から抽出された情報に基づいていてもよく、または、上記リポジトリ内の上記ドキュメントから抽出された抜粋に基づいていてもよい。
【００９２】
クエリー実行の間、上記索引マネージャは、リストを上記システムの全有効索引のクエリー実行コンポーネントへ提供する。これから、上記索引マネージャは、上記検索システムでのドキュメントの全ての削除および挿入を停止する状態に入る。上記索引マネージャが上記クエリー実行コンポーネントから返される索引リストを入力したとき、ドキュメントの削除および挿入が再開する。
【００９３】
図１２は、本発明の検索システム内のクエリー実行の１つの実施の形態を示すもう１つのフローチャートである。上記検索システムがクエリーを入力したときにこの処理が開始される（図１２、ブロック１９００）。上記クエリーはツリーに分析される（図１２、ブロック１９２０）。クエリーの１例である“//name = Joe Blow”は分析され、ロケーションパスノード（すなわち、//name）および文字列定数ノード（すなわち、“Joe Blow”）が続く最高位レベルの等しいノードから成るツリーになる。
【００９４】
上記クエリー実行（図４、ブロック３４０）は、上記索引マネージャから現在のすなわち有効な索引のリストを得る（図１２、ブロック１９３０）。上記有効な索引のリストは、上記クエリーのために使用されるドキュメントの上記リポジトリに関する情報を含む。
【００９５】
上記処理は上記現在の索引に基づいてクエリーツリーを最適化する（図１２、ブロック１９４０）。一般的に、上記処理は、もし可能ならば、上記クエリーツリーのサブツリーを削除することにより、上記クエリーツリーを最適化する。特に、上記処理は、上記クエリーツリーの種々のノードを通り、任意のサブツリーが所定の状態まで評価するか否かを決定する。例えば、もし上記クエリーがある単語を必要とし、その単語が上記索引の中になければ、他の制約にかかわらず上記クエリーは０に評価する。
【００９６】
図１３は、クエリーの例である”//name = Joe Blow AND 1 = 1”に関するクエリーツリーを示す。上記クエリーの例は２つの要件を含む、１）要素“//name”内で文字列”Joe Blow”を同定し、条件“1 = 1”を評価する。上記検索システムは、上記文字列”Joe Blow”および上記要素”//name”が索引内に見つかるか否かを決定する。もし存在すれば、図１３の１３１０とラベルされたサブツリーは最適化不可能である（すなわち、条件“//name = “Joe Blow”が満たされる可能性がある）。次に、このサブツリー１３２０が評価される。上記条件“1 = 1”は常に真であるため、サブツリー１３２０はさらなる処理から削除される。加えて、次に、ＡＮＤ式がサブツリー１３３０の条件に完全に依存しているので、サブツリー１３３０も削除される。
【００９７】
上記クエリー処理はドキュメント候補（すなわち、上記クエリー内で指定される単語、要素、属性を含むドキュメント）を同定し、上記クエリーツリーに対してこれらのドキュメントを評価する。まず、変数（例えばn）は、ドキュメント候補を同定するために使用される。上記処理を開始するために、上記変数nは0に初期化される（図１２、ブロック１９４５）。変数nを0に設定して、上記処理は、ドキュメント候補ID[n]として同定される第１のドキュメント候補を得る（図１２、ブロック１９５０）。これを達成するために、上記クエリーコンポーネントは必須の単語を含む第１のドキュメントを同定する。クエリー”//name = ”Joe Blow”の例では、上記クエリーコンポーネントは、上記索引から、上記文字列”Joe Blow”および上記要素”//name”を含むドキュメントを同定する。上記クエリーコンポーネントは、上記ドキュメント候補が上記最適化されたツリー内の検索基準を満たすか否かを決定する（図１２、ブロック１９５５）。上の例では、上記クエリーコンポーネントは、上記文字列”Joe Blow”が上記要素”//name”と組み合わされるか否かを決定する。もし上記ドキュメント候補ID[n]が上記検索基準を満たさなければ、上記ドキュメントID[n]は結果に加えられる（図１２、ブロック１９６０）。もし上記ドキュメント候補が最後のドキュメント候補でなければ、上記クエリーコンポーネントは次のドキュメント候補へ進む（図１２、ブロック１９６５および１９７０）。上記ドキュメント候補を得るステップ、上記ドキュメント候補が上記クエリーツリーまで評価するか否かを決定するステップ、およびもしそうならば、上記結果に上記ドキュメント候補を加えるステップは、全てのドキュメント候補に関して繰り返される。次に、上記クエリーコンポーネントは全てのドキュメント候補から結果を集め、それらの結果をユーザに返す（図１２、ブロック１９８０）。また、上記クエリーコンポーネントは索引の上記リストを上記索引マネージャに返す。
【００９８】
１つの実施の形態では、上記クエリー実行コンポーネントは５つの方法を利用して上記クエリーを実行する。索引をロードして、第１のdocument IDを探索し、次のdocument IDを探索し、ツリーを最適化し、ドキュメントに対してクエリーツリーを評価する。ドキュメント候補を同定するために、上記クエリーコンポーネントは、対応するノードを含む索引に関する全てのイテレータを同定する。例えば、上記クエリーコンポーネントは、上記要素エントリ”//name”および上記単語”Joe”および“Blow”に対するイテレータを同定する。次に上記イテレータを使用して、上記クエリーコンポーネントは、入力クエリーに関する重なる単語エントリをもつ第１のドキュメントを探索する。例えば、上記処理は上記要素”//name”、上記単語”Joe”および上記単語”Blow“の全てを含むドキュメントを探索する。１つの実施の形態では、上記評価処理は、種々の結果として、真／偽、１組のノード（ＸＭＬの断片）、数値、文字列およびスコアを返す。
【００９９】
図１４は本発明の検索システムを実行する汎用コンピュータシステムの高レベルブロック図を示す。コンピュータシステム１０００は、プロセッサユニット１００５、メインメモリ１０１０および相互接続バス１２０５を含む。上記プロセッサユニット１００５は１つのマイクロプロセッサを含むか、または、マルチプロセッサシステムとして上記コンピュータシステム１０００を設定する複数のマイクロプロセッサを含んでもよい。上記メインメモリ１０１０は、一部は、上記プロセッサユニット１００５による実行のための命令およびデータを記憶する。もし本発明の検索システムが部分的にソフトウェアとして実装されていると、上記メインメモリ１０１０は、動作中に、実行可能なコードを記憶する。上記メインメモリ１０１０は、高速キャッシュメモリだけでなくダイナミックランダムアクセスメモリ（ＤＲＡＭ）のバンクを含んでもよい。
【０１００】
上記コンピュータシステム１０００はさらに大容量記憶装置１０２０、周辺機器１０３０、ポータブル記憶媒体ドライブ１０４０、入力制御装置１０７０、グラフィックスサブシステム１０５０、および出力ディスプレイ１０６０を含む。説明を単純にするため、上記コンピュータシステム１０００内の全てのコンポーネントは、上記バス１０２５経由で接続されている図１４に示されている。しかし、上記コンピュータシステム１０００は１以上のデータを送る手段経由で接続可能である。例えば上記プロセッサユニット１００５および上記メインメモリ１０１０はローカルマイクロプロセッサバス経由で接続可能であり、上記大容量記憶装置１０２０、周辺機器１０３０、ポータブル記憶媒体ドライブ１０４０、およびグラフィックスサブシステム１０５０は、１以上の入出力（Ｉ／Ｏ）バス経由で接続可能である。磁気ディスクドライブまたは光ディスクドライブに具体化可能な上記大容量記憶装置１０２０は、プロセッサユニット１００５により使用されるデータおよび命令を記憶する不揮発性記憶装置である。ソフトウェアの実施の形態では、上記大容量記憶装置１０２０は、上記メインメモリ１０１０へロードするために、上記検索システムソフトウェアを記憶する。
【０１０１】
上記ポータブル記憶媒体ドライブ１０４０は、フロッピーディスクまたはコンパクトディスクリードオンリーメモリー（ＣＤ−ＲＯＭ）のようなポータブル不揮発性記憶媒体を用いて動作し、データおよびコードを上記コンピュータシステム１０００へ入力し、上記コンピュータシステム１０００から出力する。１つの実施の形態では、上記検索システムソフトウェアはそのようなポータブル媒体に記憶され上記ポータブル記憶媒体ドライブ１０４０経由で上記コンピュータシステム１０００に入力される。上記周辺装置１０３０は、上記コンピュータシステム１０００に追加の機能性を加えるために、入出力（Ｉ／Ｏ）インタフェースなどの任意の種類のコンピュータサポート装置を含むことができる。例えば、上記周辺機器１０３０は、上記コンピュータシステム１０００をネットワークへインタフェースで接続するためのネットワークインタフェースカードを含むことができる。
【０１０２】
上記入力制御デバイス１０７０は、上記コンピュータシステム１０００のユーザのためにユーザインタフェースの一部を提供する。上記入力制御デバイス１０７０は、英数字または他のキー情報を入力するための英数字キーパッド、マウス、トラックボール、スタイラスペンなどのカーソル制御装置、または矢印キーを含むことができる。テキスト情報およびグラフィカル情報を表示するために、上記コンピュータシステム１０００は上記グラフィックスサブシステム１０５０および上記出力ディスプレイ１０６０を含む。上記出力ディスプレイ１０６０は陰極線管（ＣＲＴ）ディスプレイまたは液晶ディスプレイ（ＬＣＤ）を含むことができる。上記グラフィックスサブシステム１０５０は、テキスト情報およびグラフィック情報を入力し、上記出力ディスプレイ１０６０への出力のために上記情報を処理する。上記コンピュータ１０００に含まれる複数のコンポーネントは、汎用コンピュータシステムにおいて典型的に見つかるコンポーネントであり、実際には、これらのコンポーネントは当業者には既知の広い範囲のそのようなコンピュータコンポーネントを表すことを意図している。
【０１０３】
上記検索システムはハードウェアとしてもソフトウェアとしても具体化可能である。ソフトウェア実装では、上記検索システムは汎用コンピュータシステム上で実行するための複数のコンピュータ実行可能命令を含むソフトウェアである。汎用コンピュータ内にロードする前に、上記検索システムソフトウェアは、コード化された情報として、磁気フロッピーディスク、磁気テープおよびコンパクトディスクリードオンリーメモリ（ＣＤ−ＲＯＭ）などのコンピュータ読み取り可能な記録媒体に存在できる。ハードウェア実装では、上記検索システムは、ここに記載した機能を実行するためのプロセッサ命令を含む専用プロセッサを備えてもよい。ここに記載した機能を実行するために回路が開発されてもよい。
【図面の簡単な説明】
【０１０４】
【図１】本発明の検索システムの１つの実施の形態を示すブロック図
【図２】本発明の検索システムの可能な異なるタイプのデータの例を示す図
【図３ａ】本発明の検索システム内で使用するためのＸＭＬドキュメントの見本を示す図
【図３ｂ】図３ａのＸＭＬドキュメントのツリー構造を示す図
【図４】本発明の検索システムの１つの実施の形態を示すブロック図
【図５】入力ドキュメントを処理する検索システムの１つの実施の形態を示すフローチャート
【図６】ドキュメントを検索システムへ挿入する１つの実施の形態を示すブロック図
【図７】本発明の実施の形態にしたがって実行される統合処理の１つの実施の形態を示すブロック図
【図８】検索システム内の索引を統合する統合処理の１つの実施の形態を示すフローチャート
【図９】検索システムの索引の１つの実施の形態を示すブロック図
【図１０】位置ベクトル内に含まれる情報の１つの実施の形態を示すブロック図
【図１１】検索システム内のクエリーを処理する１つの実施の形態を示すフローチャート
【図１２】本発明の検索システム内のクエリーを実行する１つの実施の形態を示すもう１つのフローチャート
【図１３】クエリーの例"//name=Joe Blow AND 1=1."のクエリーツリーを示す図
【図１４】本発明の検索システムを動作させるための汎用コンピュータシステムの高レベルブロック図を示す図
【図１】
2005525659.tif 000010
【図２】
2005525659.tif 000011
2005525659.tif 000012
2005525659.tif 000013
【図４】
2005525659.tif 000014
【図５】
2005525659.tif 000015
【図６】
2005525659.tif 000016
【図７】
2005525659.tif 000017
【図８】
2005525659.tif 000018
【図９】
2005525659.tif 000019
【図１０】
2005525659.tif 000020
【図１１】
2005525659.tif 000021
【図１２】
2005525659.tif 000022
【図１３】
2005525659.tif 000023
【図１４】
2005525659.tif 000024
【国際調査報告】
2005525659.tif 000025