(57)【要約】【課題】  複数の構造化ドキュメントを含むデータベースの探索用語に関するクエリを行うことを提供する。【解決手段】  探索用語を含まない構造化ドキュメントが、初期探索中に探し出されるか、または濾過して除かれる。探索用語を含む構造化ドキュメントであるマッチした構造化ドキュメントが、個別の要素が探索用語にどれだけよくマッチするかに基づいて個々の要素にランク付けを行い、個々の要素にユーザがアクセスすることができる個々の要素のランク付けをユーザに示すことによって評価される。【選択図】  図６
2004213675.tif 000002
【特許請求の範囲】
【請求項１】
複数の構造化ドキュメントを含むデータベースの探索用語に関するクエリを行うステップと、
前記探索用語を含まない構造化ドキュメントを探し出すステップと、
前記探索用語を含む構造化ドキュメントであるマッチした構造化ドキュメントの要素を評価することを、
それぞれの個々の要素が前記探索用語にどれだけよくマッチしているかに基づいて前記個々の要素にランク付けするステップ、および
前記個々の要素にユーザがアクセスすることができる前記個々の要素の前記ランク付けに基づいてユーザに示すステップとを含むことを特徴とする方法。
【請求項２】
前記ユーザに示すステップは、前記マッチしたドキュメントの階層構造をユーザに表示するステップを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記階層構造を前記表示するステップは、前記構造化ドキュメントの構造を表示する階層ツリーを提供するステップを含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記ドキュメントの細分性に基づいて前記個々のランク付けされた要素をスケーリングするステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記個々の数の前記ランク付けが、いくつかのグラフィック標識を使用して示されることを特徴とする請求項１に記載の方法。
【請求項６】
前記いくつかのグラフィック標識は、いくつかのアスタリスクを含むことを特徴とする請求項５に記載の方法。
【請求項７】
エントロピー測定を含む個々の要素に重み付けするステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項８】
構造化ドキュメントを前記探し出すステップは、少なくとも１つのクエリ用語を含むすべての要素を特定するステップを含み、
前記個々の要素に前記ランク付けするステップは、
【数１】
2004213675.tif 000011
がクエリ用語の重みを表わすクエリ用語ｔｉの逆ドキュメント頻度（ＩＤＦ）値であり、Ｑが、クエリの中のクエリ用語の数である前記パスにランク付けすることを、計算、
【数２】
2004213675.tif 000012
を使用し、前記ランク付けされたパスに対応する要素を上位から順に戻して行うステップを含むことを特徴とする請求項１に記載の方法。
【請求項９】
最も近いマッチを有する要素を表示するステップをさらに含むことを特徴とする請求項８に記載の方法。
【請求項１０】
前記個々の要素に前記ランク付けするステップは、
【数３】
2004213675.tif 000013
がクエリ用語の重みを表わすクエリ用語ｔｉの逆ドキュメント頻度（ＩＤＦ）値であり、Ｑが、クエリの中のクエリ用語の数であるパスにランク付けすることを、計算、
【数４】
2004213675.tif 000014
を使用して行うステップを含むことを特徴とする請求項８に記載の方法。
【請求項１１】
前記要素に重み付けするステップであって、
各段落要素に関して、重み（ｔｉ，Ｐｊ）が段落Ｐｊにおける用語ｔｉの重みを表わし、「ｔｆ（ｔｉ，Ｐｊ）」がその段落におけるｔｉの用語頻度であり、Ｎが、コーパスにおけるドキュメントの数を表わし、ｎｉが、用語ｔｉを含むドキュメントの数を表わし、計算、
【数５】
2004213675.tif 000015
に従って前記用語の重みを計算するステップと、
上位レベルにおける任意のセクション要素Ｅｊに関して、ボトムアップ方式に従って、「Ｉ（ｔｉ，Ｅｊ）」が要素Ｅｊにおける用語ｔｉのエントロピー測度であり、重み（ｔｉ，Ｅｊ）≧平均（Ｅｊ）＋ｓｔｄ＿ｄｅｖ（Ｅｊ）である場合、用語ｔｉが、要素Ｅｊの索引用語として選択され、Ｅｊのすべての下位要素が、自らの索引用語リストからｔｉを除去し、ただし、（Ｅｊ）は、要素Ｅｊにおけるすべての用語の重みの算術平均を表わし、ｓｔｄ＿ｄｅｖ（Ｅｊ）は、それらの重みの標準偏差を表わす、計算、重み（ｔｉ，Ｅｊ）＝ｌｎ（１＋ｔｆ（ｔｉ，Ｅｊ））×Ｉ（ｔｉ，Ｅｊ）を使用して用語の重みを計算するステップと、
根底要素（すなわち、ドキュメント要素）に到達するまで、前記計算、重み（ｔｉ，Ｅｊ）＝ｌｎ（１＋ｔｆ（ｔｉ，Ｅｊ））×Ｉ（ｔｉ，Ｅｊ）を使用して前記用語の重みを前記計算するステップを繰り返すステップとをさらに含むことを特徴とする請求項８に記載の方法。
【請求項１２】
ドキュメント要素、つまり根底要素と、少なくとも１つのセクション要素と、少なくとも１つの段落要素とを含む構造化ドキュメント内の構造化された要素にランク付けするステップであって、
各段落要素に関して、重み（ｔｉ，Ｐｊ）が段落Ｐｊにおける用語ｔｉの重みを表わし、「ｔｆ（ｔｉ，Ｐｊ）」がその段落におけるｔｉの用語頻度であり、Ｎが、コーパスにおけるドキュメントの数を表わし、ｎｉが、用語ｔｉを含むドキュメントの数を表わし、計算、
【数６】
2004213675.tif 000016
に従って前記用語の重みを計算するステップと、
上位レベルにおける任意のセクション要素Ｅｊに関して、ボトムアップ方式に従って、「Ｉ（ｔｉ，Ｅｊ）」が要素Ｅｊにおける用語ｔｉのエントロピー測度であり、重み（ｔｉ，Ｅｊ）≧平均（Ｅｊ）＋ｓｔｄ＿ｄｅｖ（Ｅｊ）である場合、用語ｔｉが、要素Ｅｊの索引用語として選択され、Ｅｊのすべての下位要素が、自らの索引用語リストからｔｉを除去し、ただし、「平均（Ｅｊ）」は、要素Ｅｊにおけるすべての用語の重みの算術平均を表わし、ｓｔｄ＿ｄｅｖ（Ｅｊ）は、それらの重みの標準偏差を表わす、計算、重み（ｔｉ，Ｅｊ）＝ｌｎ（１＋ｔｆ（ｔｉ，Ｅｊ））×Ｉ（ｔｉ，Ｅｊ）を使用して用語の重みを計算するステップと、
根底要素（すなわち、ドキュメント要素）に到達するまで、前記計算、重み（ｔｉ，Ｅｊ）＝ｌｎ（１＋ｔｆ（ｔｉ，Ｅｊ））×Ｉ（ｔｉ，Ｅｊ）を使用して前記用語の重みを前記計算するステップを繰り返すステップと、
すべての評価される候補要素に関するパスを獲得し、要素に関するクエリ用語の重みをパスにそれぞれ割り当てるステップと、
【数７】
2004213675.tif 000017
がクエリ用語の重みを表わすクエリ用語ｔｉの逆ドキュメント頻度（ＩＤＦ）値であり、Ｑが、クエリの中のクエリ用語の数であるパスにランク付けすることを、計算、
【数８】
2004213675.tif 000018
を使用して行うステップと、
前記ランク付けされたパスに対応する要素を上位から順に戻して行うステップとを含むステップを含むことを特徴とする方法。
【請求項１３】
個々の要素にユーザがアクセスすることができる前記個々の要素の前記ランク付けをユーザに示すステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記ユーザに示すステップは、マッチしたドキュメントの階層構造をユーザに表示するステップを含むことを特徴とする請求項１３に記載の方法。
【請求項１５】
前記階層構造を前記表示するステップは、前記構造化ドキュメントの構造を表示する階層ツリーを提供するステップを含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記個々の要素の前記ランク付けが、数値によって示されることを特徴とする請求項１２に記載の方法。
【請求項１７】
前記個々の数の前記ランク付けが、いくつかのグラフィック標識を提供することによって示されることを特徴とする請求項１２に記載の方法。
【請求項１８】
前記いくつかのグラフィック標識は、いくつかのアスタリスクを含むことを特徴とする請求項１７に記載の方法。
【請求項１９】
エントロピー測定を含む個々の要素に重み付けするステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項２０】
すべての要素に関するパスを獲得し、前記パスに関してクエリ用語の重みを割り当てるステップと、
【数９】
2004213675.tif 000019
がクエリ用語の重みを表わすクエリ用語ｔｉの逆ドキュメント頻度（ＩＤＦ）値であり、Ｑが、クエリの中のクエリ用語の数である計算、
【数１０】
2004213675.tif 000020
を使用してパスにランク付けするステップとを含むことを特徴とする方法。
【請求項２１】
前記ランク付けされたパスに対応する要素を上位から順に戻すステップをさらに含むことを特徴とする請求項２０に記載の方法。
【請求項２２】
前記個々の要素にユーザがアクセスすることができる前記個々の要素の前記ランク付けをユーザに示すステップをさらに含むことを特徴とする請求項２１に記載の方法。
【請求項２３】
前記ユーザに示すステップは、マッチしたドキュメントの階層構造をユーザに表示するステップを含むことを特徴とする請求項２２に記載の方法。
【請求項２４】
前記階層構造を前記表示するステップは、前記構造化ドキュメントの構造を表示する階層ツリーを提供するステップを含むことを特徴とする請求項２３に記載の方法。
【請求項２５】
前記個々の要素の前記ランク付けが、数値によって示されることを特徴とする請求項２０に記載の方法。
【請求項２６】
前記個々の数の前記ランク付けが、いくつかのグラフィック標識を提供することによって示されることを特徴とする請求項２０に記載の方法。
【請求項２７】
前記いくつかのグラフィック標識は、いくつかのアスタリスクを含むことを特徴とする請求項２６に記載の方法。
【請求項２８】
前記候補要素に重み付けするステップは、エントロピー測定を含むことを特徴とする請求項２０に記載の方法。
【請求項２９】
前記構造化ドキュメントが、エクステンシブルマークアップ言語（ＸＭＬ）で書かれることを特徴とする請求項２０に記載の方法。
【請求項３０】
汎用プロセスコンピュータによって実行された際、
複数の構造化ドキュメントを含むデータベースの探索用語に関するクエリを行うステップと、
前記探索用語を含まない構造化ドキュメントを濾過して除くステップと、
前記探索用語を含む構造化ドキュメントであるマッチした構造化ドキュメントを評価することを、それぞれの個々の要素が前記探索用語にどれだけよくマッチしているかに基づいて前記個々の要素にランク付けすることによって行うステップとを含む方法を行うことができるコンピュータ実行可能命令を有することを特徴とするコンピュータ可読媒体。
【請求項３１】
前記個々の要素にユーザがアクセスすることができる前記個々の要素の前記ランク付けをユーザに示すステップを含む請求項３０に記載の方法を行うことを特徴とするコンピュータ可読媒体。
【請求項３２】
前記ユーザに示すステップは、前記マッチしたドキュメントの階層構造をユーザに表示するステップを含む請求項３１に記載の方法を行うことを特徴とするコンピュータ可読媒体。
【請求項３３】
前記階層構造を前記表示するステップは、前記構造化ドキュメントの構造を表示する階層ツリーを提供するステップを含む請求項３２に記載の方法を行うことを特徴とするコンピュータ可読媒体。
【請求項３４】
前記個々の要素の前記ランク付けが、数値によって示される請求項３０に記載の方法を行うことを特徴とするコンピュータ可読媒体。
【請求項３５】
前記構造化ドキュメントの前記要素が、前記構造化ドキュメントの細分性に応じてスケーリングされる請求項３０に記載の方法を行うことを特徴とするコンピュータ可読媒体。
【請求項３６】
前記ランク付けが、いくつかのアスタリスクを使用して示される請求項３０に記載の方法を行うことを特徴とするコンピュータ可読媒体。
【請求項３７】
前記個々の要素に重み付けするステップは、エントロピー測定を含む請求項３０に記載の方法を行うことを特徴とするコンピュータ可読媒体。
【請求項３８】
前記構造化ドキュメントを濾過して除くステップは、少なくとも１つのクエリ用語を含むすべての要素を特定するステップを含み、
前記個々の要素に前記ランク付けするステップは、
【数１１】
2004213675.tif 000021
がクエリ用語の重みを表わすクエリ用語ｔｉの逆ドキュメント頻度（ＩＤＦ）値であり、Ｑが、クエリの中のクエリ用語の数である前記パスにランク付けすることを、計算、
【数１２】
2004213675.tif 000022
を使用し、前記ランク付けされたパスに対応する要素を上位から順に戻して行うステップを含む請求項３０に記載の方法を行うことを特徴とするコンピュータ可読媒体。
【請求項３９】
計算、
【数１３】
2004213675.tif 000023
を使用してパスにランク付けするステップを含む、
【数１４】
2004213675.tif 000024
がクエリ用語の重みを表わすクエリ用語ｔｉの逆ドキュメント頻度（ＩＤＦ）値であり、Ｑが、クエリの中のクエリ用語の数である前記個々の要素にランク付けするステップをさらに含むことを特徴とする請求項３０に記載の方法を行うコンピュータ可読媒体。
【請求項４０】
複数のドキュメントから少なくとも１つのドキュメントの一部分を検索するための方法であって、
複数の前記ドキュメントに対して探索用語に関するクエリを行うステップと、
検索されるべき各要素の重みのしきい値を設定するステップと、
前記しきい値が設定されたドキュメントのいずれが前記しきい値を超えたかを判定するステップと、
前記しきい値を超えた個々の要素にランク付けするステップとを含むことを特徴とする方法。
【請求項４１】
前記個々の要素にユーザがアクセスすることができる前記しきい値を超えた前記個々の要素の前記ランク付けをユーザに示すステップをさらに含むことを特徴とする請求項４０に記載の方法。
【請求項４２】
ドキュメントの要素の関連度をユーザに表示する方法であって、
探索用語に関して前記ドキュメントのクエリを行うステップと、
前記探索用語に関して前記要素の関連度にランク付けするステップと、
前記ドキュメントのある関係のある部分を前記ユーザに戻すステップと、
前記ドキュメント全体に対する前記ドキュメントの前記戻された部分の関連度を前記ユーザに示すステップとを含むことを特徴とする方法。
【請求項４３】
前記ドキュメントは、階層式に構成された複数の要素を含むことを特徴とする請求項４２に記載の方法。
【請求項４４】
前記要素の相異なる要素の関連度に応じて前記ドキュメント内の前記複数の要素の相異なる要素の関連度をランク付けするステップをさらに含むことを特徴とする請求項４２に記載の方法。
【請求項４５】
前記要素の前記関連度をユーザに前記示すステップが、前記複数の要素の前記相異なる要素の関連度に前記ランク付けするステップに応答して行われることを特徴とする請求項４４に記載の方法。
【請求項４６】
前記要素の関連度をユーザに表示するステップを含むことを示すことを特徴とする請求項４５に記載の方法。
【請求項４７】
前記ドキュメント内の前記要素のその他の要素に関連する前記要素の文脈を表示するステップを含むことを特徴とする請求項４３に記載の方法。
【請求項４８】
前記要素の関連度が、前記ドキュメント内の前記要素のパスを使用してユーザに示されることを特徴とする請求項４３に記載の方法。
【請求項４９】
ドキュメントの要素の関連度をユーザに表示する方法であって、
探索用語に関して前記ドキュメントのクエリを行うステップと、
前記探索用語に関して前記要素の関連度に重み付けを行うステップと、
前記ドキュメント内のその他の要素に対する前記要素の関連度を示す前記ドキュメントのパス構造を表示するステップとを含むことを特徴とする方法。
【請求項５０】
汎用プロセスコンピュータによって実行された際、
探索用語に関するクエリが行われているある要素をそれぞれが示す複数のパスを含むドキュメントのクエリを行うステップと、
前記探索用語に関して前記パスの相異なるパスの関連度に重み付けするステップと、
前記パスの前記重み付けされた相異なるパスに応じて前記パスの相異なるパスにランク付けするステップと、
前記ドキュメント内の前記パスの相異なるパスの関連度を示す前記ドキュメント内の前記複数の要素のパス構造を表示するステップとを含む方法を行うことができるコンピュータ実行可能命令を有することを特徴とするコンピュータ可読媒体。
【請求項５１】
探索用語に関して複数の要素を有するドキュメントのクエリを行うステップと、
前記要素の重み付けされた相異なる要素に応じて前記要素の相異なる要素にランク付けするステップと、
構造化ドキュメントの要素をスケーリングするステップとを含むことを特徴とする方法。
【請求項５２】
前記ドキュメント内の要素の相異なる要素の関連度を示す前記ドキュメント内の前記複数の要素のパス構造を表示するステップをさらに含むことを特徴とする請求項５１に記載の方法。
【請求項５３】
前記要素の相異なる要素の関連度に前記重み付けするステップは、少なくとも１つのクエリ用語を含むすべての要素を特定するステップを含み、
前記要素の相異なる要素の関連度に重み付けするステップは、すべての評価される候補要素に関するパスを獲得し、要素に関するクエリ用語の重みをパスにそれぞれ割り当てるステップを含み、
前記要素の相異なる要素に前記ランク付けするステップは、
【数１５】
2004213675.tif 000025
がクエリ用語の重みを表わすクエリ用語ｔｉの逆ドキュメント頻度（ＩＤＦ）値であり、Ｑが、クエリの中のクエリ用語の数である前記パスにランク付けすることを、計算、
【数１６】
2004213675.tif 000026
を使用し、前記ランク付けされたパスに対応する要素をランキングに基づいた順番で戻して行うステップを含むことを特徴とする請求項５１に記載の方法。
【請求項５４】
前記要素の相異なる要素に前記ランク付けするステップは、
【数１７】
2004213675.tif 000027
がクエリ用語の重みを表わすクエリ用語ｔｉの逆ドキュメント頻度（ＩＤＦ）値であり、Ｑが、クエリの中のクエリ用語の数であるパスにランク付けすることを、計算、
【数１８】
2004213675.tif 000028
を使用して行うステップを含むことを特徴とする請求項５１に記載の方法。
【請求項５５】
階層式索引における相異なるパスにランク付けするステップに先立って使用される方法であって、
前記相異なるパスに複数の要素のうちの相異なる要素が構成された探索用語に関する複数の要素を有するドキュメントのクエリを行うステップと、
前記探索用語に基づいて前記パスの相異なるパスの関連度に重み付けするステップとを含むことを特徴とする方法。
【請求項５６】
前記パスの前記相異なるパスの数をスケーリングするステップをさらに含むことを特徴とする請求項５５に記載の方法。
【請求項５７】
前記パスの相異なるパスに関連するテキストをユーザに表示するステップをさらに含むことを特徴とする請求項５５に記載の方法。
【請求項５８】
前記ドキュメントのその他の部分に関連する前記表示されたテキストの文脈を示すステップをさらに含むことを特徴とする請求項５７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ドキュメントの検索に関し、より詳細には、構造化ドキュメントの検索に関する。
【背景技術】
【０００２】
コンピュータ、ネットワーク、インターネット等の使用が増大するに伴って、ドキュメントが、しばしば、ある用語に関して探索される。例えば、特定のトピックに関して探索を行う個人または学生が、その用語に関してネットワーク化されたコンピュータ上で、独立型コンピュータ上で、またはインターネットを介して特定の探索エンジンを使用して電子ドキュメント（以下、「ドキュメント」という。）を探索することが可能である。探索エンジンは、コンピュータベースのドキュメント検索技術を使用してその用語を含むドキュメントのリストを戻す。しばしば、クエリに関して検索されたドキュメントは、それぞれの特定のドキュメントがクエリの行われた用語にどれだけよくマッチしているかに従ってランク付けされる。ユーザは、しばしば、ドキュメント全体を考慮して、特定の探索用語がどこに存在するかを特定しなければならない。
【０００３】
しばしば、コンピュータ内部の記憶位置が、あるドキュメントを階層構造で記憶する。階層構造に依存するｅＸｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  ｌａｎｇｕａｇｅ（ＸＭＬ）などのある構造化コンピュータ言語は、データを構造的に編成して特定のセクションまたは特定の要素にするタグ、または類似のデバイスを使用する。検索された構造化ドキュメントでは、ユーザは、しばしば、ドキュメント内で用語に関する文脈を見付けるのに、各ドキュメント内でどこに特定の探索用語が存在しているかに気付いていない。このさらなるユーザによる時間と労力は、幅広いクエリの場合、相当なものである可能性がある。
【０００４】
多くのドキュメント検索システムは、ドキュメントがさらに細分されることが不可能であるような、クエリが行われて戻されることが可能な比較的小さいサイズの別々の検索単位として、ドキュメントを見なす。しばしば、検索されたドキュメントは、ユーザが意味のある仕方で解析するには大きすぎる。したがって、ユーザは、しばしば、デジタルライブラリコンピュータアプリケーションにおいて検索されたドキュメント全体を注意深く検討して、関係のある用語の位置、および／または関係のある用語の文脈を特定しなければならない。
【０００５】
節（ｐａｓｓａｇｅ）検索は、原則として、ドキュメント検索と同様であるが、ドキュメントから節を抜き出す追加の予備的段階が関与する。節検索の一態様は、ユーザにより簡潔な答えを戻す。これを達するのに、例えば、用語頻度逆ドキュメント頻度（ｔｅｒｍ  ｆｒｅｑｕｅｎｃｙ  ｉｎｖｅｒｓｅ  ｄｏｃｕｍｅｎｔ  ｆｒｅｑｕｅｎｃｙ）（ＴＦＩＤＦ）アルゴリズム、またはこのアルゴリズムの変種を使用してドキュメントを固定長部分または事前定義された部分に分解して、節レベルまたは段落レベルで索引を構築することができる。ただし、多くのドキュメント検索システムが依存するこの索引付け方法は、ドキュメント内の要素の間で意味関係を保持しない。さらに、この索引付け機構により、多くの個別の検索された要素が、意味のあるテキストをユーザに提示するのに相当なコンピュータ作業を必要とする形態でもたらされる可能性がある。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本開示は、構造化ドキュメントを検索するためのスケーリング可能な方法および関連するシステムに関する。
【課題を解決するための手段】
【０００７】
一態様では、プロセスおよび関連するシステムが、複数の構造化ドキュメントを含むデータベースの探索用語に関するクエリを行うことを含む。探索用語を含まない構造化ドキュメントは、初期探索中に探し出される（ｆｅｒｒｅｔｅｄ）か、または濾過されて除かれる。探索用語を含む構造化ドキュメントであるマッチする構造化ドキュメントは、各個別要素が探索用語にどれだけよくマッチするかに基づいて個別要素をランク付けすることによって評価される。このランク付け評価は、少なくともいくつかの個別要素にユーザがアクセスできるような形でユーザに示される。
【０００８】
別の態様では、プロセスには、探索用語に関する複数の要素を有するドキュメントのクエリを行うことが関与する。相異なる要素の関連性に、探索用語に基づいて重み付けが行われる。相異なる要素に、重み付けされた相異なる要素に応答してランク付けが行われる。さらに、ドキュメント内の複数の要素のパス構造が表示され、パス構造は、ドキュメント内の相異なる要素の関連性を示す。構造化ドキュメントの要素は、ドキュメントの構造に基づいてスケーリングされる。  
図面すべてで、同様の特徴および同様の構成要素を同じ番号で示している。
【発明を実施するための最良の形態】
【０００９】
ドキュメント検索システムは、探索エンジンに依拠して、ユーザによって提供された１つまたは複数の所与の探索用語または探索語に基づいて関係のあるドキュメントを探し出し、大概、表示する。ドキュメント検索システムは、インターネットの時代においてより多く使用されている（また、より困難な処理を行うことが要求されている）。構造化ドキュメント検索システム１００の異なる実施形態、異なる実施形態が図１および２に示されており、構造化ドキュメントを検索するのに特に適している。Ｓｔａｎｄａｒｄ  Ｇｅｎｅｒａｌｉｚｅｄ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ（ＳＧＭＬ）およびｅＸｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ（ＸＭＬ）が、構造化ドキュメントを生成し、利用する最新のコンピュータ言語の例である。構造化ドキュメント検索システム１００は、ドキュメント全体を検索するのではなく、ユーザのクエリからの索引用語に基づいてドキュメントの最も関係のある部分を検索する。ＳＧＭＬおよびＸＭＬは、ユーザによって定義されることが可能なタグを使用して、ドキュメント内でデータ内容を異なる仕方で分類することができる。タグは、ドキュメントの内容、ならびに外観を定義することができる。ツリー構造または階層構造に構成されたドキュメントを生成することができる任意のコンピュータ言語が、本明細書で説明する構造化ドキュメント検索プロセスを利用することができる。
【００１０】
構造化ドキュメントは、意味のある情報検索に特に適している。というのは、ドキュメントの構造（例えば、階層）により、各セクション内に記憶されているデータに関する情報が提供されることが可能だからである。本開示の一態様は、探索エンジンがどのように、探索に関係のあるドキュメントの部分（例えば、部分は、タグ、または何らかの他の類似の機構で区別されている）を探索し、検索することができるかを説明する。構造化ドキュメント検索システムは、適切な細分性を有する構造化ドキュメントを戻すことができる。ドキュメントの細分性は、ドキュメントをどれだけ細分することができるかを示すことができる。細分性は、別々の要素にドキュメントを分割する可能性の度合いを表わす。一般に、構造化ドキュメントは高い度合いの細分性を有し、構造化されていないドキュメントは、高い細分性を欠いているが、この原則には、例外が存在する。
【００１１】
本開示の別の態様は、複数の構造化ドキュメントにおける複数のパスのうち１つのパスを探索し、使用することが、どのように索引付けスキームを利用するかを説明する。構造化ドキュメント検索システムは、構造化ドキュメントの関係のある部分をそれ自体で、またはドキュメントのその他の部分に対する何らかの関連において表示することができる。
【００１２】
図１は、クライアント部分１０２、サーバ部分１０４、データベース部分１０６、およびネットワーク部分１０８を含む構造化ドキュメント検索システム１００（ネットワークベースの）の一実施形態を示している。図１に示した構造化ドキュメント検索システム１００の実施形態は、ネットワークベースである。クライアント部分１０２とサーバ部分１０４は、標準のネットワーク通信プロトコルを使用してネットワーク部分１０８を介してインターフェースし、両部分の間でデータを転送する。システムコールが、ネットワーク部分１０８を介して転送されてデータ転送プロセスを助ける。通常の動作中、サーバ部分１０４が、データベース部分１０６からのデータにアクセスする。構造化ドキュメント検索システム１００は、ユーザ（クライアント部分１０２における）からのクエリに基づくある探索用語に関してベースとされるデータベース１０６の中に記憶されているドキュメントを探索する。
【００１３】
構造化ドキュメント検索システム１００の図２の実施形態は、独立型コンピュータ２０２、およびデータベース部分１０６（データベース部分は、独立型コンピュータの一部分であることが可能である）を含む。独立型コンピュータ２０２は、図１に示した結合されたクライアント部分１０２、サーバ部分１０４、およびネットワーク部分１０８と同様の仕方で、データベース部分１０６（モニタ上で見られる）から構造化ドキュメントを検索することができる。このため、構造化ドキュメント検索システムによってアクセスされるデータベース部分１０６は、図２に示した独立型コンピュータ、または図１に示したネットワークシステムを伴って構成される。データベース部分１０６は、それぞれ図１および２で、ネットワークまたは独立型コンピュータとは別個の構成要素として示しているが、現実には、データベース部分は、ネットワークまたは独立型コンピュータと一体化することができる。構造化ドキュメント検索システム１００に関連することが可能であるようなコンピュータ構造のさらなる詳細を以下に説明する。
【００１４】
異なる実施形態では、データベース部分１０６が、ＸＭＬ形式、ＨｙｐｅｒＴｅｘｔ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ（ＨＴＭＬ）形式、ＳＧＭＬ形式、またはその他の構造化された形式で記憶されたデータを含む構造化ドキュメントを記憶する。ＨＴＭＬは、インターネット上で現在、圧倒的に使用されているマークアップ言語である。ＨＴＭＬドキュメントは、通常、独自の構造を有する。ＨＴＭＬは、コンピュータディスプレイ上で表示される色、フォント等を定義するのに最も一般的に使用される。構造化ドキュメント検索システム１００の多くの実施形態では、例えば、ＸＭＬやＳＧＭＬと比べて、構造化されたクエリでＨＴＭＬを使用することの方が困難である。というのは、ＨＴＭＬは、従来、内容スタイルではなく、表示スタイルにより注意を払って適用されてきたからである。これと比べて、ＸＭＬおよびＳＧＭＬは、ユーザ定義型であり、データ内容を有するドキュメントに主に関係している。ＨＴＭＬ、ＸＭＬ、またはＳＧＭＬを構造化ドキュメント検索システムの異なる実施形態に適用することができる。ただし、ＸＭＬおよびＳＧＭＬが特に適している。本発明の開示の意図する範囲に含まれるマークアップ言語の変種形態および変更形態が存在する。
【００１５】
構造化ドキュメント検索システム１００は、ドキュメントを検索し、表示する際にドキュメントの内容および文脈に依存する。したがって、構造化ドキュメント検索システムは、構造化ドキュメントの内容（例えば、言語）をマッチさせる。構造化ドキュメントは、ドキュメントの検索された部分の文脈をユーザに示すこともする。適切なマッチを情報検索のために使用することができる。各構造部分を探索した後、各構造化された部分のどこでマッチが出現したかが特定される。
【００１６】
構造化ドキュメント検索システムがどのように構造化ドキュメントを検索するかを説明するため、構造化ドキュメントのある態様を説明する。図３は、構造化ドキュメント検索システム１００によって探索されるような構造化ドキュメント３００、およびそれに関連する要素の一実施形態の構成を示している。構造化ドキュメント３００は、内容ドキュメント要素３０２と、少なくとも１つの内容セクション要素３０４と、少なくとも１つの内容段落要素３０６とを含む。大きなドキュメントは、図３に示したよりもはるかに多くの内容セクション要素３０４および内容段落要素を含む。各内容セクション要素３０４は、内容ドキュメント要素３０２、および／または別の内容セクション要素３０４に依存するように関連している。各内容段落要素３０６は、内容ドキュメント要素３０２および／または内容セクション要素３０４に依存するように関連している。依存関係の方向は、下向き矢印を有する線で示されている。言い換えれば、図３の線上の矢印は、親ノードから子ノードに向かっている。図３に示した内容段落要素３０６は、通常、リーフノード要素として構造化される。というのは、そのようなリーフノード要素は、その他の依存的要素を全く有さないからである。
【００１７】
ドキュメントの特定の部分（すなわち、テキスト、イメージ、テーブル等）が、内容ドキュメント要素３０２と見なされるか、内容セクション要素３０４と見なされるか、または内容段落要素３０６と見なされるかは、それぞれの特定の要素に関連するタグに依存する。ＸＭＬ、ＳＧＭＬ、ＨＴＭＬ、およびその他のマークアップ言語におけるタグの使用は周知であり、ＸＭＬとＳＧＭＬがともにユーザ定義型タグを利用することを述べておく以外、さらに詳述することはしない。このため、特定のドキュメント内の内容ドキュメント要素３０２、内容セクション要素３０４、および内容段落要素３０６の特定の用語法は、ユーザまたはプログラマによって規定されることが可能である。内容ドキュメント要素３０２、内容セクション要素３０４、および内容段落要素３０６は、本発明の意図する範囲内に留まりながら、異なる名前または用語で記述されることも可能であるものとする（図４に関連して説明する要素に関しても同様に当てはまる）。
【００１８】
図３は、構造化ドキュメントの内容構造３００の一実施形態を示すブロック図である。これに対して、図４は、ドキュメント検索システムを使用して構造化ドキュメントの内容構造３００から導出された階層式索引４００の一実施形態を示すブロック図である。ドキュメントの内容構造３００（図３に示すような）は、内容要素が１対１関係で階層式索引要素にマップされる階層式索引付け機構を使用して、階層式索引４００（図４に示すような）に構造的にマップすることができる。階層式索引付け機構は、異なるレベルにおけるドキュメント要素を平等に扱い、ドキュメント要素のすべてに適切な索引用語を割り当てる。
【００１９】
ドキュメントの内容構造３００を階層式索引４００（図３および４にそれぞれ示す）にマップすることにより、ドキュメント索引要素３１２と、少なくとも１つのセクション索引３１４と、少なくとも１つの段落索引３１６とを含む構造がもたらされる。１対１マッピングを維持するため、各内容ドキュメント要素３０２が、階層式索引付け機構によってドキュメント索引要素３１２になるようにマップされる。各内容セクション要素３０４は、階層式索引付け機構によってセクション索引要素３１４になるようにマップされる。各内容段落要素３０６は、階層式索引付け機構によって段落索引要素３１６になるようにマップされる。各ドキュメント索引要素３１２、各セクション索引要素３１４、および各段落索引要素３１６は、用語を用語の記憶、転送、および索引付けを行うことができる。ドキュメント内の要素は（ドキュメント索引要素３１２、セクション索引要素３１４、および段落索引要素３１６が図４に示した階層式索引４００を形成するか、または内容ドキュメント要素３０２、内容セクション要素３０４、および内容段落要素３０６が図３に示した内容構造３００を形成して）、概念ツリーとして構成されているものと見なすことができる。概念ツリーにおいて、上位の要素は、その下のすべての概念を範囲に含むより広い概念を表わす。
【００２０】
通常のキーボードベースのクエリを使用することによってスケーリング可能な要素検索戦略を使用して、任意の細分性を有する関係のあるドキュメント要素を獲得することができる。構造化ドキュメント検索システム１００は、階層式索引付け機構、およびアルゴリズムを含む。索引用語は、異なるレベルにおける要素の中の用語の頻度と分布に従って、ＸＭＬドキュメントのツリー構造全体にわたって伝播する。このため、図３に示した各ドキュメント索引要素３１２、セクション索引要素３１４、および段落索引要素３１６は、対応する用語が、図４に示したそれぞれの内容ドキュメント要素３０２、内容セクション要素３０４、および内容段落要素３０６の中で出現する頻度に依存して索引要素を記憶する。アルゴリズム（すなわち、スケーリング可能なドキュメント要素検索アルゴリズム）は、階層式索引付け機構に基づいて適切なドキュメント要素を選択する。スケーリング可能なドキュメント要素検索アルゴリズムは、ドキュメント索引要素３１２、セクション索引要素３１４、および段落索引要素３１６の中に含まれるこの索引構造に基づいて実現される。
【００２１】
図４に示した階層式索引４００は、階層構造になっており（図３に示す内容構造３００も同様である）、このため、親ノードと子ノードを含む。各親ノードは、その親ノードの子ノードよりも上位であり、その子ノードを含む。階層ツリー（およびその他のツリー）構造では、子ノードは、親ノードの属性を継承しなければならない。このため、親ノードは、子ノードの上位概念（ｓｕｐｅｒ  ｃｏｎｃｅｐｔ）でなければならない。例えば、例を用いると、図５ｂに示したドキュメント検索例、中国は、中国の歴史、中国の経済、中国の文化等の上位概念である。したがって、中国の歴史要素、中国の経済要素、および中国の文化要素はそれぞれ、中国要素の属性を継承しなければならない。
【００２２】
構造化ドキュメント検索システム１００は、構造化ドキュメント検索におけるテキスト長正規化、およびしきい値設定に関して存在する可能性がある困難をある程度、克服する。ドキュメント全体が、しばしば、ユーザがある用語の文脈を効果的に解析する、または特定するには大きすぎる。ユーザ、特に長めのドキュメントを解析しているユーザが、ドキュメントの一部分だけを解析することが有益である可能性がある。さらに、ドキュメントの表示された部分とドキュメントのその他の部分の間の文脈（すなわち、関係）を示すことが重要である可能性がある。
【００２３】
ＸＭＬおよびＳＧＭＬ（ＨＴＭＬも）は、階層式索引付け、および構造化ドキュメント検索に特に向けられた構成において構造化ドキュメントを提供するコンピュータ言語を代表している。通常のＸＭＬドキュメントまたはＳＧＭＬドキュメントは、１組の論理要素（タイトル、セクション、サブセクション、段落などの）を含む。ＸＭＬドキュメントおよびＳＧＭＬドキュメントは、通常、階層関係に基づいて構造化されており、このため、階層式索引付け、および構造化ドキュメント検索システム１００に極めてよく適用されることが可能である。ＸＭＬおよびＳＧＭＬにより、ユーザ定義型タグを使用してドキュメントの構造を明示的に表わす標準の効果的なやり方が提供される。
【００２４】
本開示の一態様では、ドキュメント検索は、ユーザがドキュメント内の任意のレベルの要素を検索することができるのでない限り、有効な情報検索を提供しない。クエリに応答して１組の極めて長いドキュメントが検索されることは、ドキュメント内の探索用語（または索引用語）の文脈を導出する何らかの機構がユーザに提供されているのでない限り、しばしば、ほとんどユーザの役に立たない。ドキュメント内の任意のレベルの要素を得ることにより、構造化ドキュメント検索システム１００が、異なる長さ、および異なる構造を有するドキュメントのクエリを行うことに適合することが可能になる。これにより、検索システムは、ユーザによって決められたとおり、関係のある要素だけをユーザに戻すことができる。
【００２５】
構造化ドキュメント検索システム１００の一態様は、より対象を絞った（ｄｉｒｅｃｔｅｄ）データを検索する検索技術（例えば、索引付け技術を使用する）を利用することである。構造化ドキュメント検索システム１００は、任意の細分性を有することによって変更されたキーワードベースのクエリ（関係のあるドキュメント要素を検索するのにドキュメント検索で一般に使用されるような）を使用する。本開示の一態様は、２つの部分、すなわち、斬新な階層式索引付け機構と、図４に示した階層式索引４００に基づいて適切なドキュメント要素を選択し、表示するアルゴリズムとを含む。
【００２６】
ある従来の手法は、索引用語をリーフ要素または固定長の節に割り当てることだけを行う。異なるレベルの要素には、同等の適切な索引用語が割り当てられる。構造化ドキュメント検索システム１００は、階層式索引付け機構を使用して、余りにも広い意味、または余りにも狭い意味を有する用語を濾過して除きながら、各要素に関する固有の概念を正確に記述することができる索引用語を割り当てる。「中国」に関するサンプルドキュメントが、セクション「歴史」を含み、セクション「歴史」が、「唐王朝」、「明王朝」、および「清王朝」などのサブセクションも含むことを考慮されたい。セクション「歴史」に関する適切な索引用語を選択することは難しい。「中国」は、余りにも多くの結果をもたらす比較的広い用語であるように見える。これに比べて、「唐」、「明」、および「清」は、関係のあるドキュメントを逸する可能性がある狭い用語であるように見える。「歴史」および「王朝」などの用語が、良好な候補の用語であるように見える。
【００２７】
図５ａおよび５ｂは、親セクション索引要素の子としてそれぞれ構成された１つのセクション索引要素３１４と２つの段落索引要素３１６を含む階層式索引４００の一部分の中の索引用語を適切に濾過する一実施形態を示している。索引用語を濾過することにより、階層式索引４００の親ノード、または親要素において存在するのと重複する索引用語が子ノード、または子要素において出現する回数が抑えられる。さらに、索引用語を濾過することにより、それぞれが階層式索引４００における同じ親ノード、または親要素の子である複数の子ノード、または子要素において、索引用語の重複が制限される。図５ａおよび５ｂにおけるセクション索引要素３１４および段落索引要素３１６の使用は恣意的であるが、親−子構成で構成された索引要素（索引用語を含むことが可能な）を示すように選択されている。段落（すなわち、子）索引要素３１６は、リーフノードであることも、そうでないことも可能である。
【００２８】
図５ａで、１つの子索引要素３１６が、索引用語「中国」および「歴史」を含む一方で、別の子索引要素３１６は、索引用語「中国」および「経済」を含んでいる。親索引要素３１４は、全く索引用語を含んでいない。ドキュメント内の索引要素は、親索引要素３１４が、親索引要素３１４から下の子索引要素３１６のすべての概念に適用されるより広い概念を表わす概念ツリーとして構成されることが可能である。索引語を濾過してより少ない要素にすることができる概念ツリーとして階層式索引付け構造を構成することにより、探索エンジンのパフォーマンスが向上する。というのは、子索引要素３１６に共通の用語が、個々の子要素のすべての中で探索されなくてもよいからである。代わりに、用語は、親探索要素３１４の中で１回、探索されなければならない。
【００２９】
本明細書で説明する階層式索引付け機構は、ボトムアップ伝播方式に従って各要素に関する適切な索引用語を自動的に選択する。一実施形態では、構造化ドキュメント検索システム１００の索引付け方法により、ある要素において出現する索引用語が、その要素のいずれの子要素においても出現しないことが確実である。この索引付け方法により、かなりの量の記憶スペースと検索時間が節約される。さらに、この階層式索引付け機構は、検索プロセスが、ドキュメントツリー全体にわたる索引用語の完全な分布に直接に起因して所望の要素を得ることができるため、結果が集約するという潜在的な問題を回避する。広汎なドキュメント探索および検索プロセスにおける時間のこの節約により、相当な時間の節約がもたらされる。
【００３０】
図６は、ドキュメント検索システム１００に適用された階層式索引付け機構４７０の一実施形態を示している。階層式索引付け機構４７０は、４７２で開始して、ドキュメントにおける最低レベルの要素を選択する。例えば、段落索引要素３１６の１つが、図５ａに示した階層式索引４００において提供される。階層式索引付け機構は、４７４に進み、選択された要素に関するゼロの、または１つ以上の階層式索引用語を特定する。
【００３１】
階層式索引付け機構は、判定４７６に進み、ドキュメントにおいて考慮されるべきさらなる要素が存在するかどうかが判定される。４７２、４７４、および４７６は、索引用語に関して階層式索引４００の中の各要素を考慮するループを形成していることに留意されたい。一実施形態では、ユーザは、動作中にコンピュータによって提供されるプロンプトによるか、またはユーザが探索することを所望する領域の予備的なユーザ制限選択により、階層式索引４００のあるセクションが考慮されるのを制限することができる。
【００３２】
階層式索引付け機構４７０の４７２部分、４７４部分、および４７６部分を通るループを辿って、階層式索引付け機構は、４７８に進む。４７８で、階層式索引における各索引用語に関して、適切な用語が、階層式索引４００における子要素から親要素に伝播する。子要素から親要素への用語のそのような適切な伝播は、図５ａおよび５ｂに示し関連づけて説明した「濾波プロセス」と同一視することができる。
【００３３】
例えば、ユーザがクエリ「中国の歴史」をサブミットした場合、検索されるドキュメントのタイトルは「中国」であり、セクションは「歴史」である。見出し「中国」を通る最も適切なパスは、セクション「歴史」である。というのは、「歴史」セクションが、見出し「中国」に最も関連しているからである。このため、セクション「中国」と「歴史」が、クエリ「中国の歴史」からの索引パスを形成する。したがって、ユーザが中国の歴史のクエリを行うことは、このパスを戻す。
【００３４】
この方法の別の部分は、スケーリング可能なアルゴリズムを使用して、ユーザの情報ニーズを満たす適切なドキュメント要素を選択する。構造化ドキュメント検索システム１００に適用される「スケーリング可能な」という用語は、アルゴリズムが、ユーザのクエリにおける概念の範囲に従って任意の細分性の関係のあるドキュメント要素を検索することができることを示す。図４に示した階層式索引４００は、任意の細分性で直接にドキュメント要素を検索する有効なやり方を提供するので、検索アルゴリズムが、候補要素をクエリに従ってランク付けすることが重要である。図５ａおよび５ｂに示した階層式索引４００は３つの索引要素３１４および３１６を含んでいるが、図４の階層式索引は、１１の索引要素を含んでいる。さらに、大きいドキュメントにおける索引要素の数は、非常に多い可能性がある。
【００３５】
一態様では、ドキュメント検索システム１００は、スケーリング可能である。構造化ドキュメント検索システムのある実施形態は、ユーザが、ドキュメントを検索し、多種多様な構成および／または細分性でセクションドキュメントを表示することを可能にする。例えば、ユーザは、広い検索を行ってドキュメント全体にアクセスすることができる。このため、中国の例を使用すると、ユーザは、検索されるドキュメントの階層式索引４００全体をもたらす「中国」索引用語にアクセスすることができる。さらに、ユーザは、中間検索プロセスを行い、「中国の歴史」に対応する図４に示したセクション索引要素３１４を検索することができる。最後に、ユーザは、清王朝に対応する図４の段落索引要素３１６またはセクション索引要素３１４を検索することにより、ドキュメントの非常に狭い部分にアクセスすることができる。
【００３６】
以下に説明するパスランク付けアルゴリズムにより、ドキュメントの意味ある形での検索および表示が可能になる。特定の索引を使用して構造情報を有するデータを検索することは、多くの分野（例えば、データベース、ＩＲ、およびＸＭＬ）で用途を有する。構造化ドキュメント検索システム１００は、ドキュメントの構造に直接にマップされる階層式索引４００を含む。階層式索引付け機構は、ユーザのクエリ言語に全く制限を課さずに、どれが様々な細分性でドキュメント要素を検索するかを決める。例えば、構造化ドキュメント検索システム１００は、極めて長いドキュメントにも、比較的短いドキュメントにも適用することができる。ドキュメントツリーにおける各要素、または各構成要素に関して、索引ツリーにおける対応する索引要素、または索引構成要素が存在する。クエリが入ってきた際、探索エンジンは、索引ツリーを使用して最も関連のある１つまたは複数の構成要素パス（つまり、ユーザの探索に最も関連のある）を探し出す。この構成要素パスは、１つまたは複数のセクション要素３０４を経由して（根底パスまたはドキュメント要素３０２から）、パスの根底と呼ばれる図３に示した関係のある個別の段落要素３０６に至る。構造化ドキュメント検索システムは、パスの根底をユーザに戻す。
【００３７】
各ドキュメントに関して、ドキュメントと同じ構造を有する階層式索引４００が確立される。したがって、階層式索引４００の構造は、元のドキュメントの内容構造３００をミラーリングする。索引用語は、その索引用語がどれだけ一般的にドキュメントにおける概念を表わすかに応じてすべての要素に分散される。索引用語を要素に効果的に割り当てるため、索引用語は、要素をその他の要素と区別しながら、要素の概念を特徴付けなければならない。したがって、要素に関する索引用語を選択するのに、その要素における用語の頻度および分布が考慮されなければならない。また、索引用語の重みも、その要素におけるその他の用語と比較される。最上位にランク付けされた索引用語が、その要素に関する索引用語として選択される。ある用語が頻繁に出現し、要素のテキストにおいて均等に分布しており、しきい値を超えるランクも有している場合、その索引用語は、その要素に関する索引用語と考えられなければならない。
【００３８】
構造化ドキュメント検索システム１００は、ある構造化ドキュメントの階層構造を利用する。階層式ドキュメント（構造化ドキュメントの１つのタイプを表わす）は、親要素と子要素の間の関連を含む。親要素における用語の分布は、その親要素の子要素における用語の出現を考慮することによって定量化可能である。一実施形態では、この分布定量化は、親要素の直接の子孫である子要素だけに適用される。というのは、各要素のトピックは、その要素の直接の子孫である要素によってサポートされなければならないからである。ある用語がセクションまたはドキュメントの子要素において均等に分布している場合、その用語は、そのセクションまたはドキュメントに関する良好な候補索引用語である。情報理論により、エントロピーは、情報内容（または情報の不確実性）を捕捉することに関する特殊概念として定義されている。エントロピーは、一実施形態では、要素における用語の分布を測定する有用な基準である。
【００３９】
図３に示した段落要素３０６は、この段落要素３０６のいずれも子要素を有していないので、「原子」要素として分類される。したがって、従来のＴＦＩＤＦ測定を適用して単独の段落要素における用語に重み付けすることができる。段落要素３０６に関する用語の重みは、以下のとおりとなる。
【００４０】
【数１】
2004213675.tif 000003
【００４１】
重み（ｔｉ，Ｐｊ）は、段落Ｐｊにおける用語ｔｉの重みを表わす。「ｔｆ（ｔｉ，Ｐｊ）」は、その段落におけるｔｉの用語頻度である。Ｎは、コーパスにおけるドキュメントの数を表わし、ｎｉは、用語ｔｉを含むドキュメントの数を表わす。
【００４２】
原子要素ではない他のレベルにおける要素（例えば、セクション要素３０４およびドキュメント要素３０２）に関して、用語頻度と用語分布が結合されて用語に関する重みが提供される。したがって、任意の合成要素Ｅｊにおける用語ｔｉの重みは、以下のとおり定義することができる。
重み（ｔｉ，Ｅｊ）＝ｌｎ（１＋ｔｆ（ｔｉ，Ｅｊ）×Ｉ（ｔｉ，Ｅｊ）
Ｉ（ｔｉ，Ｅｊ）は、要素Ｅｊにおける用語ｔｉのエントロピー測度であり、以下のとおり定義される。
【００４３】
【数２】
2004213675.tif 000004
【００４４】
ただし、ｓｕｂｋは、Ｅｊの第ｋ番の直接の子孫である要素を表わし、Ｎ（ｓｕｂ）は、そのような子孫要素の数である。  
計算３において、用語
【００４５】
【数３】
2004213675.tif 000005
【００４６】
が、索引付け機構において重要な役割をする。用語頻度は、異なる要素において、その要素のテキスト長の大きな変化に起因して大幅に異なる。エントロピー測定は、他のドキュメント検索方法または節検索方法が直面するのと同じ長さ正規化の問題に出会う可能性がある。エントロピー測定は、要素における用語のすべての出現が、その要素の各子要素において厳密に等しいと仮定した場合にエントロピーを生成することを可能にし、これは、その用語のエントロピーに関する理論最大値である。この理論最大値の割合が、用語の分布測度である。後の実験で、この計算により、異なるレベルの要素における様々な用語頻度の副次的効果がほとんどトレードオフされることが判明している。
【００４７】
用語の重みは、異なる要素における重みを比較するためにさらに正規化される。計算１および２によって得られた用語の重みが、同一の要素におけるすべての用語の最大の重みで割られる。したがって、すべての用語の重みは、０から１までの範囲内に入る。
【００４８】
前述したとおり、重みがあるしきい値を超える用語または要素は、より一般的な概念を表わす可能性があるので、より上位のレベルに伝播されなければならない。しきい値は、特定の要素における用語の重みの統計に従って動的に調整することができる。この動的なしきい値設定の異なる実施形態は、図１３に示したコンピュータ環境のユーザまたは操作者が行うか、または本明細書で開示する概念に基づいて自動的に行われることが可能である。具体的には、用語は、その用語の重みが、平均値にその要素におけるすべての用語の重みの平均値に標準偏差を足した値を超えた場合だけに、要素に関する索引用語として選択される。言い換えれば、子要素における索引用語は、その用語の重みがしきい値制約を満たす場合に親要素まで伝播することが可能である。したがって、索引付け機構の一実施形態の概要を以下のとおり説明することができる。  
１．各段落要素３０６に関して、計算１に従って用語の重みを計算する。  
２．ボトムアップ方式に従う１つの上位レベルの任意の要素Ｅｊ（すなわち、セクション要素３０４またはドキュメント要素３０２）に関して、計算２を使用して用語の重みを計算する。重み（ｔｉ，Ｅｊ）≧平均（Ｅｊ）＋ｓｔｄ＿ｄｅｖ（Ｅｊ）である場合、用語ｔｉは、要素Ｅｊの索引用語として選択され、Ｅｊのすべての下位要素は、ｔｉを自らの索引用語リストから除去する。ここで、平均（Ｅｊ）は、要素Ｅｊにおけるすべての用語の重みの算術平均を表わし、ｓｔｄ＿ｄｅｖ（Ｅｊ）は、それらの重みの標準偏差を表わす。  
３．根底要素、すなわち、ドキュメント要素３０２に到達するまで２を繰り返す。
【００４９】
この索引付けの解決策は、ドキュメントの内部構造を徹底的に利用する。すべての用語が同じレベルにおいて互いに比較され、正規化係数としての理論最大値が計算に算入されるので、異なる要素におけるテキストの様々な長さの効果は、最小限に抑えられる。さらに、平均値に標準偏差を足したしきい値により、特定の要素に関する索引用語を決めるための動的な局所最適値が提供される。さらに、要素の索引用語は、その要素のすべての下位要素において出現することが必ずしも必須とされない。したがって、タイトルの中のいくつかの語以外のより代表的な索引用語が検出される。
【００５０】
構造化ドキュメント検索プロセス４００の一実施形態を図７ａおよび７ｂに示している。構造化ドキュメント検索プロセスは、ドキュメント全体を検索する代わりに、ユーザに最も関連のあるドキュメントの構成要素を検索する。ツリー構造、または階層構造を有する任意のコンピュータ言語が、本明細書で説明する構造化ドキュメント検索プロセスを利用することができる。図１に示した構造化ドキュメント検索システム１００の一実施形態では、各セクションおよび各段落が、個々に探索される。
【００５１】
構造化ドキュメント検索方法は、４０２で開始し、ユーザが、構造化ドキュメント検索システム１００内の初期探索エンジンに索引語を使用してクエリをサブミットして、複数の構造化ドキュメントを探索する。初期探索エンジンは、元のクエリに応答して、探索用語の１つまたは複数を含まないドキュメント全体から、探索用語の１つまたは複数を含むドキュメント全体を濾過して除く。
【００５２】
構造化ドキュメント検索システムのある実施形態では、４０２でユーザによってサブミットされたクエリは、戻されたドキュメントが表示される前のユーザからの最終入力であることが可能である。方法は、４０４に進み、探索エンジンが、索引用語に関する構造化ドキュメントのすべてに対する探索を行う。４０４で使用される探索エンジンは、ドキュメント全体をまとめて探索するように、または索引用語に関して個々の要素のすべてを探索するように構成されることが可能である。ただし、４０４の間、所与の探索用語に関してすべてのドキュメントが完全に探索される。この初期探索は、多くが市販され、一般に使用されている多種多様な探索エンジンのいずれか１つによって行うことができる。このため、４０２および４０４は、ユーザによってクエリの中に含められた探索用語を含まないドキュメントを追い出すことにより、今日、使用されるほとんどの探索エンジンと同様に動作する。
【００５３】
構造化ドキュメント検索プロセス４００は、判定４０６に進み、特定の構造化ドキュメントが索引用語を含むかどうかが判定される。判定４０６に対する答えが「いいえ」であった場合、構造化ドキュメント検索プロセス４００は、４０８に進み、探索用語のいずれも含まないドキュメントが追い出される（すなわち、濾過されて除かれる）。４０８が適用されるドキュメントは、構造化ドキュメント検索プロセス４００によってさらに考慮される必要がない（すなわち、構造化ドキュメント検索プロセス４００が終了される）。というのは、それらのドキュメントは、探索で使用されている関係のある索引用語のいずれも含まず、したがって、ユーザの関心対象である可能性がないからである。
【００５４】
判定４０６に対する答えが「はい」であった場合、構造化ドキュメント検索プロセス４００は４１０に進み、ユーザおよび／または構造化ドキュメント検索システム１００が、さらに探索されるべき構造化ドキュメントを選択する。４１０はオプションであり、プロセス４００は、代わりに４１２に直接に進むことができる。構造化ドキュメント検索システム１００は、４１２に進み、マッピングを使用して構造化ドキュメントと同じ構造を有する階層式索引４００を自動的に確立する。この階層式マッピングプロセスの例を図３および４に関連して説明する。４０２、４０４、４０６、４０８、および４１０でマッチングが行われたドキュメントのうちで、ドキュメントの要素が個々に評価される。マッチする探索用語を含むパスの終端要素が戻される。マッチした親の子である段落だけが探索される。
【００５５】
構造化ドキュメント検索プロセス４００は、４１４に進み、構造化ドキュメントの各要素における索引用語に重み付けが行われる。この重み付けにより、ドキュメントにおける各要素の関連度が決まる。各要素を別々に考慮する４１４の重み付けは、各ドキュメントを全体として探索する４０４とは異なる。４１４に関するさらなる詳細は、後に説明する。構造化ドキュメント検索プロセス４００は、ＸＭＬ構造における４１６に進み、最高レベルを探索して、マッチングを行った後、マッチした用語が存在すれば、その用語に関して次に下位のレベルを探索する。
【００５６】
構造化ドキュメント検索プロセス４００は、４１８に進み、最も近いマッチを有するドキュメントが表示される。本開示の一実施形態では、構造化ドキュメント検索システム１００は、要素、ならびに要素の文脈を表示する。例えば、以下に説明する図９に示すとおり、コンピュータ表示ウインドウの右側が、要素または要素群の関係のある部分を表示する。ユーザは、隣接する要素にアクセスする能力も有する。ウインドウの左側は、ウインドウの文脈を表示し、構造化ドキュメントの異なる要素を表わす構造が表示される。実施形態では、ドキュメントの異なる要素のランク付けも表示されることが可能である。各ドキュメントに関して、表示される複数のパスが存在することが可能である。このため、ユーザは、単独の探索用語の出現を探し出すのにドキュメント全体を探索する必要がなく、パスだけを探し出せばよい。
【００５７】
図８ａおよび８ｂは、４１２および４１４が含まれないことを除けば、図７ａおよび７ｂに示した実施形態と同様である構造化ドキュメント検索プロセス４００の別の実施形態を示している。４１２および４１４の重み付けプロセス、および／または階層式索引付けプロセスは、別々に行うことができ、図８ａおよび８ｂに示したパスランク付けプロセス中に結果を利用することができる。例えば、構造化ドキュメント検索プロセスの納入業者が、索引付けされ、かつ／または重み付けされた索引用語を含むバージョンを別個に供給することも可能である。重み付けプロセスおよび索引付けプロセスは、別々に考慮され、したがって、構造化ドキュメント検索プロセス４００の一実施形態は、重み付けは行うが、索引付けは行わない、または索引付けは行うが、重み付けは行わないことが可能である。
【００５８】
次に、図３に示した構造化ドキュメントに関連して用語重み付けを説明する。用語には、構造化ドキュメント検索システム１００によって重み付けが行われる。用語重み付けにより、特定の要素の関連度を定量化することができる機構が提供される。構造化ドキュメントにおける索引用語に重み付けを行った後、本明細書で説明するとおり、索引用語をランク付けすることもできる。
【００５９】
このセクションでは、階層式索引４００に基づいてユーザに表示される適切なドキュメント要素を選択するスケーリング可能な検索アルゴリズムの実施形態を説明する。階層式索引４００は、任意の細分性で直接にドキュメント要素を検索する有効な機構を提供するので、検索段階における主なタスクは、候補要素のオンライン探索およびランク付けである。構造化ドキュメント検索システム１００のある実施形態は、それぞれの検索された要素をその要素の構造上の文脈とともに表示してユーザが便利な形で検索結果をブラウズすることを容易にするインターフェースを提示する。表示されたユーザインターフェースは、多くの実施形態では、ユーザによって入力された索引用語に基づいて各要素のランク（関連度）を表示するので、ユーザにとって重要な役割をする。
【００６０】
各ドキュメントに関して、構造化ドキュメント検索システム１００は、パスランク付けアルゴリズムを使用して、クエリに対するすべての候補要素の関連度値を計算する。要素に関するパスは、ドキュメントツリーにおける根底（ドキュメント要素）とその要素の間のすべての要素（根底要素とその要素を含む）であると考えられる。１つの要素が別の要素の祖先である場合、その要素のパスは、後者の要素のパスのサブセットである。階層式索引付け機構の一実施形態によれば、要素は、その要素の子孫と索引用語を全く共有しない。このため、要素は、その要素のパスによって完全に記述される。したがって、要素ランク付けの問題が、パスランク付けの問題に変形されることが可能であり、つまり、目標は、クエリに対して高い関連度値を有する要素パスを見出すことである。
【００６１】
前述した中国のクエリを考慮すると、戻されたドキュメント「中国」に関して、ドキュメントレベルの索引用語には、「中国」、「中国の」が含まれる一方で、セクション「歴史」に関する索引用語は、「歴史」、「王朝」等であることが可能である。クエリ「中国の歴史」に対して、セクション「歴史」の要素パスは、すべてのクエリ用語を含み、他方、ドキュメント「中国」の要素パスは、１つのクエリ用語だけを含む。このため、セクション「歴史」が、クエリに対するより良好な答である。
【００６２】
要素のランクは、クエリに対する要素の関連度を判定する際に重要である。要素パスに関する用語の重みは、索引用語リストがその用語を含むパス上の要素におけるその用語の重みとして定義される。所与のクエリに応じたパスに関するランクは、以下のとおり定義される。
【００６３】
【数４】
2004213675.tif 000006
【００６４】
【数５】
2004213675.tif 000007
【００６５】
は、クエリ用語の重みを表わすクエリ用語ｔｉの逆ドキュメント頻度（ＩＤＦ）値であり、Ｑは、クエリの中のクエリ用語の数を表わす。
【００６６】
入ってくるクエリを所与として、従来のドキュメント検索技術を使用して、まず探索空間を絞り込むために関係のあるドキュメントのリストを得ることができる。次に、ユーザが関係のあるドキュメントの１つを選択した際、システムが、そのドキュメントのすべての候補要素を探索した後、クエリに従ってその要素のパスにランク付けを行う。
【００６７】
要素にランク付けを行う全体的プロセスを以下に説明する。少なくとも１つのクエリ用語を含むすべての要素が探し出される。すべての候補要素に関するパスが獲得され、クエリ用語の重みが、要素に関してパスにそれぞれ割り当てられる。重み付けされたパスは、計算４に従ってランク付けされる。ランク付けされたパスのすべて、または選択されたいくつかに対応する要素が、上位から順に戻される（さらに、通常、表示される）。
【００６８】
構造化ドキュメント検索における積年の問題は、ユーザのクエリニーズを最もよく満たすことが可能な（例えば、関連のある）適切な要素をどのように戻すかである。構造化ドキュメント検索システム１００は、すべての検索された要素のランクの平均を動的なしきい値として使用する。しきい値を超えるランクを有する要素が、結果として戻される。後の実験により、この動的なしきい値に基づいて正確な要素検索を達することができることが示されている。
【００６９】
すべての戻された要素は、図９に示すとおり、ドキュメントツリーにおける戻された要素の位置、ならびに周りの要素を示すことが可能な構造上の文脈とともに、構造化ドキュメント検索システム１００によって表示される。
【００７０】
図９は、所与のクエリ「清王朝」を伴うスケーリング可能な検索システムのインターフェースのスナップショットを示している。このため、図９は、ドキュメント検索システムのインターフェースの一部分を提供することができる。相当な数の要素が、「中国」という名前のドキュメントに関して戻されている。戻された要素のなかには、セクションおよび段落が存在する。最上位の要素は、中国の歴史における清王朝を説明することを専門とするタイトル「満州清王朝」を有するセクションである。このセクションは、そのドキュメントのタイトルが「歴史」であるセクション下にある。左ブラウジング画面区画が、ドキュメントに対する各セクションまたは各段落の位置を示している。このため、各要素の文脈に関する情報が、左画面区画内で記述されている。これに対して、ユーザが項目「清王朝」をクリックした場合、ドキュメント全体がそのトピックを中心に扱っているので、ドキュメント全体にアクセスが行われる。テキスト要素の上位レベルが読み取られて、より一般的な概念記述が獲得される。アスタリスクの付いたタイトルは、その要素のランクが、動的なしきい値である平均ランクを超えていることを示す。
【００７１】
本開示のこのセクションは、構造化ドキュメント検索システム１００に関して説明したドキュメント検索方法４００のパフォーマンスを評価する。また、しきい値設定の効果も考慮される。実験は、本開示を執筆している現時点で４０，０００を超えるよく構成されたＸＭＬドキュメントを含むＥｎｃａｒｔａ（登録商標）Ｍｕｌｔｉｍｅｄｉａ  Ｅｎｃｙｃｌｏｐｅｄｉａコーパスに対して行われた。クエリセットは、構造化ドキュメント検索システム１００の通常のユーザによって入力される可能性があるようなクエリと同様であるように見える表１にリストした１０のクエリを含む。各クエリには、関係のあるドキュメントの一部分（すなわち、要素）だけをユーザに表示することで返答が行われるのが最良であり得る。
【００７２】
予備的な実験結果により、構造化ドキュメント検索システム１００が、比較された方法よりも相当に良好なパフォーマンスを示すだけでなく、構造化ドキュメント検索および節検索における２つの積年の問題であるテキスト長正規化と要素選択しきい値の困難をある程度、克服することも示されている。
【００７３】
本ドキュメント検索システムの利点を例示するため、構造化ドキュメント検索システム１００と比較されるＴＦＩＤＦ  Ｐａｒａを使用する節検索システムを実施する。ＴＦＩＤＦ  Ｐａｒａシステムによる一実施形態では、段落だけが節として活用され、他方、他の構造上の情報は無視される。段落における用語の重みは、従来のＴＦＩＤＦ測定によって正規化なしに定義されることが可能であり、これにより、計算１と同様の結果がもたらされる。
【００７４】
【表１】
2004213675.tif 000008
【００７５】
節検索または構造化ドキュメント検索に関する以前の研究は、ドキュメント全体を検索することに対する節レベルの証拠の影響に主に焦点を当てて評価を行った。これらの研究のいずれも、要素検索の有効性を評価することを専門とする特別なを行っていない。前述した構造化ドキュメント検索システム１００の開発の一環として、スケーリング可能な検索方法がユーザのクエリに関して適切な細分性の要素を探し出す能力を試験するために一連の実験を行った。
【００７６】
軍事作戦の歴史を研究しているユーザが、「どのような軍用機がデザートストームで使用されたか」を調べ出すつもりであるものと想定する。最初の探索は、ともに関係のある内容の一部分を含む上位にランク付けされた結果として、２つの項目、「軍用機」および「湾岸戦争」をもたらす可能性がある。ユーザは、それぞれのドキュメント（しばしば、非常に長い）を走査して、戻されたドキュメント全体から関係のある内容を探さなければならない。
【００７７】
関連度判定は、人間の評価者によって行われる。各クエリに関して、ドキュメント内の関係のある要素が、評価者によって判定され、選択される。この場合に使用される測定は、ドキュメント検索で使用される測定と同様である。呼び戻し（ｒｅｃａｌｌ）は、検索されている関係のある要素の部分であり、精度は、関係があると判定された検索された要素の部分とする。戻された要素は、比較的少数の関係のある要素を有するものと考えられなければならないので、様々な精度値が異なる呼び戻しレベルで計算されることはない。代わりに、全体的な呼び戻しレベルおよび精度レベルが計算され、計算５で記述した結合されたＦ値の大部分に寄与するように使用される。
【００７８】
【数６】
2004213675.tif 000009
【００７９】
検索された要素のどの部分が答としてユーザに戻されるべきかを判定する際、０．１から０．９までの固定のしきい値と動的なしきい値がともに使用される。動的なしきい値は、すべての検索された要素（１つの選択されたドキュメントに関する）のランク値の平均（Ａｖｇ）とそれらの値の標準偏差（Ｓｔｄ＿Ｄｅｖ）によって決まる。したがって、「Ａｖｇ」および「Ａｖｇ＋Ｓｔｄ＿Ｄｅｖ」を実験における動的なしきい値として活用する。様々なしきい値を使用して以上２つの方法によって得られたＦ値を表２で比較し、示している。
【００８０】
【表２】
2004213675.tif 000010
【００８１】
表２のＦ値は、従来の方法と比較した構造化ドキュメント検索プロセス４００の向上を示している。Ｆ値は、１が完全なマッチを表し、０が全くマッチしないことを表わす０から１までの範囲のマッチングの測度である。表２は、様々なしきい値設定を有するスケーリング可能な検索システムが、段落レベルに直接にＴＦＩＤＦ測定を適用することに関わる別の検索方法よりも検索パフォーマンスの相当な向上を見せることを示している。
【００８２】
さらに、一般に、ユーザには、スケーリング可能な検索方法（評価者のフィードバックに応じた）によって提示されるより短い、より対象を絞った結果を扱う方が快適である。このさらなるユーザにとっての快適さは、主として、ユーザがドキュメント全体の編成、検索された要素の要素全体に対する文脈、および特定の要素の内容（または要素の一部分）を閲覧することができる構造化ドキュメント検索システム１００の階層式文脈の構造的提示によるものである。
【００８３】
要素の逐語的な文脈（ｌｉｔｅｒａｌ  ｃｏｎｔｅｘｔ）が、結果において保存される。というのは、以前の構造化されたドキュメントまたは節の検索方法は固定レベルの節だけを戻したが、スケーリング可能な検索方法は、クエリの指定に応じて段落、セクション、またはドキュメント全体であることが可能な様々な細分性で要素を戻すことができるからである。例えば、クエリ「清王朝」は、ドキュメント「中国」における「歴史」セクション下のタイトル「満州清王朝」を有するセクションによって最もよくサポートされることが可能である。このセクションには、数多くの段落が含まれる。構造化ドキュメント検索システムでは、このセクションは、クエリに対するこのドキュメントの最初の位置に提示される。しかし、ＴＦＩＤＦ  Ｐａｒａシステムでは、段落レベルランクを有する別々の段落が順に並べられる。ユーザは、そのクエリに対する個別の証拠だけによって順序付けられたそれらの段落の間の相関または文脈を明らかにすることができない。したがって、階層式索引付けにスケーリング可能な検索を併せることにより、比較的高い検索パフォーマンスが達せられ、ドキュメントの元の構造上の情報が徹底的に活用されるので、ユーザフレンドリーな結果提示がさらに提供される。
【００８４】
しきい値設定は、構造化ドキュメント検索が望ましい要素を獲得するのに重要である。ある従来のドキュメント検索システムでは、しきい値は、０．２に固定される。構造化ドキュメント検索システム１００に関する実験は、単一のしきい値を使用することで、すべてのクエリに関してシステムが常に最も良好なパフォーマンスを見せるようにすることができないことを示している。とうのは、クエリが行われるドキュメントの構造および長さは、非常に様々だからである。したがって、構造化ドキュメント検索システム１００は、変化しない（すなわち、静的な）しきい値ではなく、動的なしきい値を利用する。
【００８５】
様々なしきい値が２つの方法の検索パフォーマンスにどのような影響を与えるかを考慮されたい。図１０は、前述の実験において得られた固定しきい値の結果をグラフ６００にプロットしている。グラフ６００では、Ｆ値が、縦座標であるしきい値に対する横座標としてプロットされている。図１０は、スケーリング可能な検索方法の曲線６０２（スケーリング可能な検索方法によって生成された）が、ＴＦＩＤＦ  Ｐａｒａ方法によって得られたＴＦＩＤＦ曲線６０４よりもはるかに平坦であることを示している。ＴＦＩＤＦ  Ｐａｒａのパフォーマンスは、ＴＦＩＤＦ曲線６０４で示されるとおり、しきい値の変更とともに非常に大きく変化する。ＴＦＩＤＦ曲線６０４においてＴＦＩＤＦ  Ｐａｒａによって得られる最高のＦ値は、０．５５（しきい値０．４における）であり、これは、最低値０．２８（図示していない、しきい値０．９における）よりも９３％大きい。これに比べて、スケーリング可能な検索方法の曲線６０２のＦ値は最大（しきい値０．７）と最小（しきい値０．１）で、１６％だけしか変化しない。これは、階層式索引付け機構とスケーリング可能な検索機構により、検索プロセスがしきい値設定の影響を受けにくくなることを示す。本明細書で説明する値およびパーセンテージは、例示的な性質のものであり、範囲を限定するものではない。
【００８６】
第２に、動的なしきい値の効果を考慮されたい。図１１および１２は、しきい値に対してプロットされたＦ値（動的なしきい値、しきい値なし、および固定しきい値で獲得された）を示している。図１１で、ＴＦＩＤＦ棒グラフ７００に関する動的なしきい値の設定が、平均値７０２、平均に標準偏差を加えた値７０４、しきい値なしの値７０６、および最大値７０８を示している。図１２で、スケーリング可能な検索の棒グラフ８００に関する動的なしきい値の設定が、平均値８０２、平均に標準偏差を加えた値８０４、しきい値なしの値８０６、および最大値８０８を示している。ＴＦＩＤＦの棒グラフ７００に関する動的なしきい値の設定、およびスケーリング可能な検索の棒グラフ８００に関する動的なしきい値の設定がそれぞれ、ＴＦＩＤＦ  Ｐａｒａ方法およびスケーリング可能な検索方法のパフォーマンスを示している。図１１は、動的なしきい値を使用することで、段落検索方法が最良のパフォーマンスを実現するようにすることができないことを示している。しかし、図１２に示すとおり、スケーリング可能な検索方法は、平均ランクの動的なしきい値を使用する場合、より高いパフォーマンスを実現することができる。これは、動的なしきい値が固定のしきい値の良好な代案であり、様々なドキュメントおよびクエリにより適応することが可能であることを証明している。
【００８７】
ＥｎｃａｒｔａオンラインとＥｎｃａｒｔａ  ＣＤバージョンはともに、スケーリング可能な構造化ドキュメント検索システム１００を統合してスケーリング可能な検索機能を追加するように変更することができる。構造化ドキュメント（例えば、ＸＭＬ、ＳＧＭＬ、ＨＴＭＬのいくつかのアプリケーション等を使用する）を含むあらゆるデータベース製品に関して、この技術を使用して探索パフォーマンスおよび検索パフォーマンスを向上させることができる。
【００８８】
図１３は、正しいソフトウェアおよびハードウェアを使用して、構造化ドキュメント検索システム１００の一実施形態を提供することができるユーザインターフェースを含む適切なコンピュータ環境またはコンピュータ網５００の例を示している。同様のリソースが、コンピュータ環境と本明細書で説明するプロセスを使用して、例えば、図５ａ、５ｂ、６、７ａ、７ｂ、８ａ、および８ｂに示したコンピュータ関連プロセスを行うことができる。
【００８９】
図１３に示したコンピュータ環境５００は、本明細書で説明する構造化ドキュメント検索システム１００の技術を実施するのに使用することができる一般的なコンピュータ環境である。コンピュータ環境５００は、コンピュータ環境の一例に過ぎず、コンピュータおよびネットワークアーキテクチャの使用または機能の範囲に関する限定を何ら示唆するものではない。また、コンピュータ環境５００が、例示的なコンピュータ環境５００で例示する構成要素のいずれか１つ、またはその組合せに関連する依存性または要件を有すると解釈すべきでもない。
【００９０】
コンピュータ環境５００は、コンピュータ５０２の形態で汎用コンピューティングデバイスを含む。コンピュータ５０２は、例えば、独立型コンピュータ、ネットワーク化されたコンピュータ、メインフレームコンピュータ、ＰＤＡ、電話機、マイクロコンピュータまたはマイクロプロセッサの１つまたは複数、あるいはメモリと併せてプロセッサを使用する任意の他のコンピュータデバイスであることが可能である。コンピュータ５０２の構成要素には、１つまたは複数のプロセッサまたは処理ユニット５０４（オプションとして、暗号プロセッサ、または暗号コプロセッサを含む）、システムメモリ５０６、ならびにプロセッサ５０４およびシステムメモリ５０６を含む様々なシステム構成要素を結合するシステムバス５０８が含まれることが可能であるが、以上には限定されない。
【００９１】
システムバス５０８は、様々なバスアーキテクチャのいずれかを使用するメモリバスまたはメモリコントローラ、周辺バス、アクセラレーテッドグラフィックスポート、およびプロセッサバスまたはローカルバスを含むいくつかのタイプのバス構造のいずれかの１つまたは複数を表わす。例として、そのようなアーキテクチャには、インダストリスタンダードアーキテクチャ（Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ）（ＩＳＡ）バス、マイクロチャネルアーキテクチャ（Ｍｉｃｒｏ  Ｃｈａｎｎｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ）（ＭＣＡ）バス、エンハンストＩＳＡ（Ｅｎｈａｎｃｅｄ  ＩＳＡ）（ＥＩＳＡ）バス、ビデオエレクトロニクススタンダーズアソシエーション（Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ）（ＶＥＳＡ）ローカルバス、およびメザニン（Ｍｅｚｚａｎｉｎｅ）バスとしても知られるペリフェラルコンポーネントインターコネクツ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔｓ）（ＰＣＩ）バスが含まれることが可能である。
【００９２】
コンピュータ５０２は、通常、様々なコンピュータ可読媒体を含む。そのような媒体は、コンピュータ５０２によってアクセス可能である任意の可用な媒体であることが可能であり、揮発性の媒体と不揮発性の媒体、取外し可能な媒体と取外し不可能な媒体がともに含まれる。
【００９３】
システムメモリ５０６は、読取り専用メモリ（ＲＯＭ）５１２などの不揮発性メモリ、および／またはランダムアクセスメモリ（ＲＡＭ）５１０などの揮発性メモリの形態でコンピュータ可読媒体を含む。始動中などにコンピュータ５０２内部の要素間で情報を転送するのを助ける基本ルーチンを含む基本入力／出力システム（ＢＩＯＳ）５１４が、ＲＯＭ５１２の中に記憶されている。ＲＡＭ５１０は、通常、処理ユニット５０４によって即時にアクセス可能であり、かつ／または現在、処理されているデータおよび／またはプログラムモジュールを含む。
【００９４】
コンピュータ５０２は、その他の取外し可能な／取外し不可能な、揮発性／不揮発性のコンピュータ記憶媒体も含むことが可能である。例として、図１３は、取外し不可能な不揮発性磁気媒体（図示せず）に対して読取りおよび書込みを行うためのハードディスクドライブ５１５、取外し可能な不揮発性の磁気ディスク５２０（例えば、「フロッピー（登録商標）ディスク」）に対して読取りおよび書込みを行うための磁気ディスクドライブ５１８、およびＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ，またはその他の光媒体などの取外し可能な不揮発性の光ディスク５２４に対して読取りおよび／または書込みを行うための光ディスクドライブ５２２を示している。ハードディスクドライブ５１５、磁気ディスクドライブ５１８、および光ディスクドライブ５２２はそれぞれ、１つまたは複数のデータ媒体インターフェース５２７でシステムバス５０８に接続される。代替として、ハードディスクドライブ５１５、磁気ディスクドライブ５１８、および光ディスクドライブ５２２は、１つまたは複数のインターフェース（図示せず）でシステムバス５０８に接続することもできる。
【００９５】
ディスクドライブおよび関連するコンピュータ可読媒体により、コンピュータ可読命令、制御ノードデータ構造、プログラムモジュール、およびその他のデータの不揮発性ストレージが、コンピュータ５０２に提供される。この例は、ハードディスクドライブ５１５内部のハードディスク、取外し可能な磁気ディスク５２０、および不揮発性の光ディスク５２４を示しているが、磁気カセットまたは他の磁気記憶デバイス、フラッシュメモリカード、ＣＤ−ＲＯＭ、デジタルバーサタイルディスク（ＤＶＤ）または他の光ストレージ、ランダムアクセスメモリ（ＲＡＭ）、読取り専用メモリ、電気的に消去可能なプログラマブル読取り専用メモリ（ＥＥＰＲＯＭ）などのコンピュータによってアクセス可能なデータを記憶することができる他のタイプのコンピュータ可読媒体も例示的なコンピュータ環境５００を実施するのに利用できることを理解されたい。
【００９６】
例えば、ＯＳ５２６、１つまたは複数のアプリケーションプログラム５２８、他のプログラムモジュール５３０、およびプログラムデータ５３２を含め、任意の数のプログラムモジュールをハードディスクドライブ５１５内に含まれるハードディスク、磁気ディスク５２０、不揮発性の光ディスク５２４、ＲＯＭ５１２、および／またはＲＡＭ５１０に記憶することができる。各ＯＳ５２６、１つまたは複数のアプリケーションプログラム５２８、他のプログラムモジュール５３０、およびプログラムデータ５３２（または以上の何らかの組合せ）が、分散ファイルシステムをサポートする常駐する構成要素のすべて、または一部を実施することが可能である。
【００９７】
ユーザは、キーボード５３４およびポインティングデバイス５３６（例えば、「マウス」）などの入力デバイスを介してコマンドおよび情報をコンピュータ５０２に入力することができる。他の入力デバイス５３８（特に図示せず）は、マイクロホン、ジョイスティック、ゲームパッド、サテライトディッシュ、シリアルポート、スキャナ、および／または同様の物を含むことが可能である。以上の入力デバイス、およびその他の入力デバイスは、システムバス５０８に結合された入力／出力インターフェース５４０を介して処理ユニット５０４に接続されるが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ｕｎｉｖｅｒｓａｌ  ｓｅｒｉａｌ  ｂｕｓ）（ＵＳＢ）などの他のインターフェースおよびバス構造で接続することも可能である。
【００９８】
また、モニタ、フラットパネルディスプレイ、または他のタイプのコンピュータディスプレイ２００も、ビデオアダプタ５４４などのインターフェースを介してシステムバス５０８に接続することができる。コンピュータディスプレイは、図９に示し、前述したとおり、構造化ドキュメント検索システム１００からのそのような出力を表示することができる。コンピュータディスプレイ２００に加えて、他の出力周辺デバイスは、入力／出力インターフェース５４０を介してコンピュータ５０２に接続することが可能なスピーカ（図示せず）やプリンタ５４６などの構成要素を含むことが可能である。
【００９９】
コンピュータ５０２は、遠隔コンピュータデバイス５４８などの１つまたは複数の遠隔コンピュータに対する論理接続を使用するネットワーク化された環境で動作することができる。例として、遠隔コンピュータデバイス５４８は、パーソナルコンピュータ、可搬コンピュータ、サーバ、ルータ、ネットワークコンピュータ、ピアデバイスまたは他の一般的なネットワークノード、ゲームコンソール等であることが可能である。遠隔コンピュータデバイス５４８は、コンピュータ５０２に関連して本明細書で前述した要素および特徴の多く、またはすべてを含むことが可能な可搬コンピュータとして例示されている。
【０１００】
コンピュータ５０２と遠隔コンピュータデバイス５４８の間の論理接続は、ローカルエリアネットワーク（ＬＡＮ）５５０および一般的なワイドエリアネットワーク（ＷＡＮ）５５２として描かれている。そのようなネットワーキング環境は、オフィス、企業全体のコンピュータ網、イントラネット、およびインターネットで一般的である。
【０１０１】
ＬＡＮネットワーキング環境で実施される場合、コンピュータ５０２は、ネットワークインターフェースまたはネットワークアダプタ５５４を介してローカルネットワーク５５０に接続される。ＷＡＮネットワーキング環境で実施される場合、コンピュータ５０２は、通常、ワイドネットワーク５５２を介して通信を確立するためのモデム５５６またはその他の手段を含む。コンピュータ５０２の内部にあることも、外部にあることも可能なモデム５５６は、入力／出力インターフェース５４０、またはその他の適切な機構を介してシステムバス５０８に接続することができる。例示したネットワーク接続は、例示的なものであり、コンピュータ５０２と５４８の間で通信リンクを確立する他の手段も使用できることを理解されたい。
【０１０２】
コンピュータ環境５００で例示したようなネットワーク化された環境では、コンピュータ５０２に関連して描いたプログラムモジュール、またはプログラムモジュールの部分は、遠隔のメモリ記憶デバイスの中に記憶することができる。例として、遠隔アプリケーションプログラム５５８が、遠隔コンピュータ５４８のメモリデバイス上に常駐することが可能である。例示のため、アプリケーションプログラム、ならびにオペレーティングシステムなどの他の実行可能プログラム構成要素は、本明細書では、個別のブロックとして例示している。ただし、そのようなプログラムおよび構成要素は、様々な時点で、コンピュータ５０２の異なる記憶構成要素の中に存在し、コンピュータ５０２のデータプロセッサによって実行されるものと認識される。図示し、説明するネットワーク接続は、例示的であり、コンピュータ間で通信リンクを確立する他の手段も使用できることが認められよう。
【０１０３】
様々なモジュールおよび技術を本明細書では、１つまたは複数のコンピュータまたは他のデバイスによって実行されるプログラムモジュールなどのコンピュータ実行可能命令の一般的な文脈で説明することができる。一般に、プログラムモジュールには、特定のタスクを行う、または特定の抽象データタイプを実装するルーチン、プログラム、制御オブジェクト６５０、構成要素、制御ノードデータ構造６５４等が含まれる。通常、プログラムモジュールの機能は、様々な実施形態において所望に応じて結合する、または分散させることができる。
【０１０４】
以上のモジュールおよび技術の実施形態を何らかの形態のコンピュータ可読媒体に記憶する、またはその媒体を介して伝送することができる。コンピュータ可読媒体は、コンピュータがアクセスすることができる任意の可用な媒体であることが可能である。例として、限定としてではなく、コンピュータ可読媒体は、「コンピュータ記憶媒体」および「通信媒体」を含むことが可能である。
【０１０５】
「コンピュータ記憶媒体」は、コンピュータ可読命令、制御ノードデータ構造、プログラムモジュール、またはその他のデータなどの情報を記憶するための任意のプロセスまたは技術で実装することができる揮発性の媒体および不揮発性の媒体、取外し可能な媒体および取外し不可能な媒体を含む。コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタルバーサタイルディスク（ＤＶＤ）または他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージまたは他の磁気記憶デバイス、あるいは所望の情報を記憶するのに使用することができ、コンピュータがアクセスすることができる任意の他の媒体が含まれるが、以上には限定されない。
【０１０６】
「通信媒体」は、通常、搬送波または他のトランスポート機構などの変調されたデータ信号で、コンピュータ可読命令、制御ノードデータ構造、プログラムモジュール、またはその他のデータを実現する。また、通信媒体は、情報配信媒体も含む。「変調されたデータ信号」という用語は、情報を信号内で符号化するように特性の１つまたは複数が設定された、または変更された信号を意味する。例として、限定としてではなく、通信媒体には、有線網または直接配線接続などの有線媒体、音響媒体、ＲＦ媒体、赤外線媒体、およびその他の無線媒体などの無線媒体が含まれる。また、以上のいずれの媒体の組合せも、コンピュータ可読媒体の範囲内に含まれる。
【０１０７】
前述した構造化ドキュメント検索システム１００は、ドキュメント全体よりも小さい細分性で要素を検索する有効なやり方を提供する。構造化ドキュメント検索システム１００の非常に重要な適用例は、任意の細分性の適切な要素でユーザのクエリのニーズを満たすことである。
【０１０８】
本開示では、構造化ドキュメントに関する階層式索引付け機構、ならびに階層式索引付け機構に基づいて動作するスケーリング可能な構造化ドキュメント検索方法を説明している。索引用語は、特定のレベルの要素におけるその索引用語の統計情報を他のピア用語の値と比較することによって判定して、より一般的な概念を表わしている場合、ツリー構造におけるより上位のレベルの要素に伝播する。これにより、ドキュメントの同じ構造の中で、索引用語は、ツリー全体にわたって分布する。各要素は、その要素の概念を最もよく表わすことができる索引用語のリストを有する。このスケーリング可能な検索方法は、任意のレベルで最も満足のいく要素をユーザに提供することを専門とする。
【０１０９】
実験結果は、図７ａ、７ｂ、８ａ、および８ｂに示した構造化ドキュメント検索プロセスが、段落レベルだけにＴＦＩＤＦ測定を適用する方法よりも相当に高いパフォーマンスを示すことを明らかにしている。さらに、構造化ドキュメント検索システム１００において提示される構造上の文脈を伴う結果は、ユーザにとってより満足ができ、快適である。また、実験結果は、この方法がしきい値設定の影響を受けなかったことも示している。したがって、動的なしきい値が、ドキュメントの長さが様々であるそのような構造化ドキュメント検索方法に対する良好な解決策である。
【０１１０】
本システムおよび本方法は、構造上の特徴および／またはプロセスに特有の言葉で説明してきたが、特許請求の範囲で定義する本発明は、説明した特定の特徴またはプロセスに必ずしも限定されないことを理解されたい。むしろ、特定の特徴は、請求する発明を実施する好ましい形態として開示している。
【図面の簡単な説明】
【０１１１】
【図１】構造化ドキュメント検索システムの一実施形態を示すブロック図である。
【図２】構造化ドキュメント検索システムの別の実施形態を示すブロック図である。
【図３】階層式索引を使用するファイルの構造の一実施形態を示すブロック図である。
【図４】図１または図２に示したような構造化ドキュメント検索システムを使用して図３の構造化ドキュメントから導出された階層式索引の一実施形態を示すブロック図である。
【図５ａ】索引のいくつかに含まれる索引語を含む階層式索引の一部分を示すブロック図である。
【図５ｂ】２つの子ノードによって共有される共通の索引語を親ノードに転送した後の図５ａに示した階層式索引の部分を示す図である。
【図６】階層式索引付けプロセスの一実施形態を示す流れ図である。
【図７ａ】構造化ドキュメント検索プロセスの一実施形態を示す流れ図である。
【図７ｂ】構造化ドキュメント検索プロセスの一実施形態を示す流れ図である。
【図８ａ】構造化ドキュメント検索プロセスの別の実施形態を示す流れ図である。
【図８ｂ】構造化ドキュメント検索プロセスの別の実施形態を示す流れ図である。
【図９】構造化ドキュメント検索プロセスからの出力を表示するコンピュータディスプレイの一実施形態を示す図である。
【図１０】Ｐａｒａ  ＴＦＩＤＦ法と比べたスケーリング可能なドキュメント検索プロセスに関するＦ値対しきい値をプロットしたグラフである。
【図１１】ＴＦＩＤＦ  Ｐａｒａ法に関する動的しきい値設定をプロットした棒グラフである。
【図１２】構造化ドキュメント検索プロセスに関する動的しきい値設定をプロットした棒グラフである。
【図１３】構造化ドキュメント検索プロセスに関して使用することができるようなコンピュータ環境の一実施形態を示すブロック図である。
【符号の説明】
【０１１２】
１００  構造化ドキュメント検索システム
１０２  クライアント
１０４  サーバ
１０６  データベース
１０８  ネットワーク
【図１】
2004213675.tif 000029
【図２】
2004213675.tif 000030
【図３】
2004213675.tif 000031
【図４】
2004213675.tif 000032
【図５ａ】
2004213675.tif 000033
【図５ｂ】
2004213675.tif 000034
【図６】
2004213675.tif 000035
【図７ａ】
2004213675.tif 000036
【図７ｂ】
2004213675.tif 000037
【図８ａ】
2004213675.tif 000038
【図８ｂ】
2004213675.tif 000039
【図９】
2004213675.tif 000040
【図１０】
2004213675.tif 000041
【図１１】
2004213675.tif 000042
【図１２】
2004213675.tif 000043
【図１３】
2004213675.tif 000044